MẠNG NEURON NHÂN TẠO VÀ GIẢI THUẬT LAN TRUYỀN NGƯỢC

Ta cĩ nhiều phương pháp để phân loại dữ liệu như: cây quyết định, mạng Nạve Bayes, mạng neuron, luật kết hợp, giải thuật di truyền… Trong báo cáo này tơi sẽ trình bày phương pháp dùng mạ

TRƯỜNG ĐẠI HỌC QUỐC GIA TP.HCM TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN



TIỂU LUẬN KHAI THÁC DỮ LIỆU

MẠNG NEURON NHÂN TẠO

VÀ GIẢI THUẬT LAN TRUYỀN NGƯỢC

GVHD: PGS TS ĐỖ PHÚC SVTH: TRƯƠNG HỒNG THÁI MSSV: CH1101041

KHÓA: K6-2011

TP.HCM, 11/2012

MỤC LỤC

CHƯƠNG 1: GIỚI THIỆU 2

CHƯƠNG 2: GIỚI THIỆU MẠNG NEURON 3

2.1 Giới thiệu về mạng neuron nhân tạo 3

2.2 Perceptron 3

2.2.1 Quy tắc perceptron 5

2.2.2 Quy tắc delta 6

CHƯƠNG 3: GIẢI THUẬT LAN TRUYỀN NGƯỢC 9

3.1 Cấu tạo mạng neuron nhiều tầng 9

3.2 Giải thuật lan truyền ngược 10

3.2.1 Hàm squashing 11

3.2.2 Chi tiết giải thuật lan truyền ngược (sử dụng hàm sigmoid) 12

3.2.3 Một số lưu ý trong việc áp dụng giải thuật 14

3.3 Nhận xét về giải thuật lan truyền ngược 17

3.3.1 Sự hội tụ và cực tiểu cục bộ 17

3.3.2 Overfitting 17

CHƯƠNG 4: KẾT LUẬN 19

TÀI LIỆU THAM KHẢO 20

CHƯƠNG 1: GIỚI THIỆU

Phân lớp dữ liệu là 1 kỹ thuật quan trọng trong khai mỏ dữ liệu Mục đích của quá trình phân lớp dữ liệu là để rút trích các mơ hình mơ tả các lớp dữ liệu hoặc dự đốn

xu hướng của dữ liệu Quá trình phân lớp dữ liệu gồm 2 bước: bước huấn luyện (xây dựng bộ phân loại bằng việc phân tích, học các tập huấn luyện) và bước phân loại (phân loại dữ liệu mới hoặc dữ liệu chưa biết)

Ta cĩ nhiều phương pháp để phân loại dữ liệu như: cây quyết định, mạng Nạve Bayes, mạng neuron, luật kết hợp, giải thuật di truyền… Trong báo cáo này tơi sẽ trình bày phương pháp dùng mạng neuron, cụ thể là giải thuật lan truyền ngược

Chương 2: Giới thiệu mạng neuron

CHƯƠNG 2: GIỚI THIỆU MẠNG NEURON

2.1 Giới thiệu về mạng neuron nhân tạo

Theo các nghiên cứu khoa học, bộ não của con người chứa khoảng 1011 neuron thần kinh, mỗi neuron sẽ có nối kết với khoảng 104

neuron khác Các neuron hoạt động bằng cách truyền các rung động đên các neuron khác thông qua các kết nối Mô phỏng mạng neuron sinh học, mạng neuron nhân tạo cũng được tạo ra từ tập hợp những đơn

vị có liên kết nội với nhau, tại mỗi đơn vị đó sẽ mang một giá trị thực có thể là output của một đơn vị khác để làm input và sinh ra một giá trị thực output có thể làm input của nhiều đơn vị khác

2.2 Perceptron

Perceptron là mạng neuron đầu tiên có khả năng học Một perceptron nhận giá trị input

là một vector những giá trị thực, output được tính toán dựa trên một tổ hợp tuyến tính của những giá trị input này:

0 1

) , , , (

1 1 0

1 1 0 2

1

n n

n n n

x w x

w w

x w x

w w x

x x o







trong đó, trọng số w i là các hằng giá trị thực, quyết định sự phân phối của input x i đối

với output perceptron Lượng -w0 là ngưỡng để sự tổ hợp trọng số của input

n n

1 1 2 2

w x + w x + + w x phải vượt để cho output perceptron là 1

Perceptron

Ví dụ: Ứng dụng perceptron cho phép tính logic AND:

Ứng dụng của perceptron rất hạn chế, nó chỉ có thể giải các bài toán tuyến tính

mà không thể giải quyết các bài toán không phân hoạch tuyến tính đƣợc

Bài toán có thể phân hoạch tuyến tính

Chương 2: Giới thiệu mạng neuron

Bài toán không thể phân hoạch tuyến tính

Để xác định được các trọng số, ta có thể cho mạng neuron học tập huấn luyện Ta

có thể áp dụng nhiều giải thuật để huấn luyện, tuy nhiên trong báo cáo này tôi chỉ đề cập đến hai giải thuật là: qui tắc perceptron và qui tắc delta Hai giải thuật này là nền tảng cơ bản cho giải thuật lan truyền ngược

2.2.1 Quy tắc perceptron

Các trọng số sẽ được gán ngẫu nhiên ở trạng thái bắt đầu, sau đó đưa vào perceptron

để lặp đi lặp lại cho mỗi mẫu huấn luyện; tiếp tục thay đổi trọng số perceptron cho đến khi nó sắp xếp được mẫu này Vòng lặp này được sử dụng nhiều lần cho toàn bộ mẫu huấn luyện, cho đến khi perceptron phân loại được toàn bộ các mẫu huấn luyện một cách chính xác Các trọng số sẽ được thay đổi tại mỗi bước theo luật huấn luyện perceptron:

i i

t: ngõ ra đích cho mẫu huấn luyện hiện tại,

o: ngõ ra được sinh ra bởi perceptron,

η: tỉ lệ học, là một hằng dương, thường rất nhỏ, là mức độ thay đổi của trọng số sau mỗi bước

Phương pháp huấn luyện này được chứng minh là hội tụ sau một số bước hữu hạn với điều kiện là những mẫu huấn luyện này phải là phân hoạch tuyến tính và một

hằng số η hiệu quả được sử dụng Nếu dữ liệu không là phân hoạch tuyến tính thì sự hội tụ không được đảm bảo

2.2.2 Quy tắc delta

Qui tắc perceptron rất thành công trong việc tìm một vector trọng số khi mẫu huấn luyện là phân hoạch tuyến tính, nhưng nó lại không hội tụ trong trường hợp dữ liệu không là phân hoạch tuyến tính Qui tắc delta được thiết kế để loại bỏ vấn đề trên Nếu mẫu huấn luyện không là phân hoạch tuyến tính, qui tắc delta sẽ hội tụ về một xấp xỉ phù hợp nhất cho đối tượng

Qui tắc delta sử dụng gradient descent để đưa ra những trọng số mà phù hợp nhất cho những mẫu huấn luyện Đây là nền tảng cho giải thuật lan truyền ngược – giải thuật để học trong mạng có nhiều đơn vị liên kết nội

Qui tắc huấn luyện delta có thể được xem như là một tác vụ huấn luyện một perceptron không có ngưỡng, đó là một đơn vị tuyến tính cho output o được tính theo công thức:

x w x

d

t w

2

1 ) ( 

trong đó:

D: tập hợp những mẫu huấn luyện,

t d: output đích cho mẫu huấn luyện d,

o d : output của đơn vị tuyến tính cho mẫu huấn luyện d

Chúng ta có thể xem E như là một hàm số của w

vì output đơn vị tuyến tính o lệ thuộc vào vector trọng số này Ngoài ra, E lệ thuộc vào các mẫu huấn luyện Mục tiêu của quá trình huấn luyện là xác định các trọng số để E là cực tiểu, đây là giả thuyết có

thể nhất trong dữ liệu huấn luyện

Chương 2: Giới thiệu mạng neuron

Quá trình học là quá trình biến đổi các trọng số để đạt đƣợc E cực tiểu Qua các

biến đổi toán học, ta có đƣợc công thức cập nhật trong số theo qui tắc huấn luyện gradient descent:

w w

w

id d D

d d

xid biểu diễn một thành phần input đơn xi cho mẫu huấn luyện d

Chi tiết giải thuật Gradient-descent (training_example, ):

Mỗi mẫu huấn luyện là một cặp ở dạng (x, t), với x là vector của giá trị input và t là giá trị ouput đích,  là tỉ lệ học (tỉ lệ học)

1 Khởi tạo mỗi wi với một giá trị nhỏ ngẫu nhiên

2 Lặp cho đến khi gặp điều kiện kết thúc:

Khởi tạo gán mỗi w i bằng 0

For each (x, t), do:

Input x cho các đơn vị và tính toán output For each w i, do:

Cực tiểu cục bộ

Mạng neuron 1 tầng có thể sử dụng để giải quyết các vấn đề đơn giản Đối với các bài toán phức tạp, nó không đủ khả năng để tổng quát vấn đề Mạng neuron nhiều tầng đã ra đời để giải quyết các vấn đề phức tạp đó Trong đó, giải thuật lan truyền ngƣợc là một trong những giải thuật cơ bản dùng để học các trọng số cho mạng neuron nhiều tầng

Chương 3: Giải thuật lan truyền ngược

CHƯƠNG 3: GIẢI THUẬT LAN TRUYỀN NGƯỢC

Trong mạng neuron nhiều tầng, các giá trị output không còn là các tổ hợp tuyến tính của các giá trị input nữa mà là kết quả của 1 hàm phức tạp hơn Nhiều bài toán thực tế như nhận diện giọng nói, nhận diện khuôn mặt… đã áp dụng giải thuật này để giúp cho máy học một số ví dụ mẫu, sau đó tính toán output cho cho trường hợp khác

Ứng dụng mạng neuron nhiều tầng trong nhận diện giọng nói [3]

3.1 Cấu tạo mạng neuron nhiều tầng

Mạng neuron nhiều tầng cũng được cấu thành từ các phần tử cơ bản tương tự như các perceptron Vì vậy, nó giải quyết được những bài toán phức tạp hơn

Kiến trúc mạng neuron nhiều tầng [2]

Ngoài ra, để tính toán output, ta thường áp dụng 1 hàm số đặc biệt, gọi là hàm squashing để output của từng tầng không còn là 1 phân hoạch tuyến tính Ví dụ: nếu sử dụng hàm sigmoid để giải quyết 1 bài toán gồm có 2 input, khi đó output sẽ có dạng là

đồ thị của hàm sigmoid trong hệ trục tọa độ Descarte Kết hợp giữa việc sử dụng hàm squashing và nhiều tầng, mạng neuron có thể giải quyết được các vấn đề rất phức tạp

Thành phần cơ bản của mạng neuron nhiều tầng [3]

Mạng neuron nhiều tầng có cấu tạo gồm ít nhất là 3 tầng (1 tầng input, 1 hoặc nhiều tầng hidden, 1 tầng output) Tầng input và tầng hidden ta thường thêm 1 phần tử gọi là bias (đóng vai trò như một trọng số kết nối giữa tầng trước và tầng sau và luôn

có giá trị là 1) Sơ đồ mạng neuron này chỉ thể hiện được luồng thông tin từ tầng input đến output, trong quá trình quay lui, thông tin sẽ được truyền ngược lại

3.2 Giải thuật lan truyền ngược

Giải thuật lan truyền ngươc là giải thuật dùng để học trọng số cho mạng neuron nhiều tầng, dùng phương pháp gradient descent để đạt được sai số nhỏ nhất Giải thuật bao gồm 3 giai đoạn: truyền thông tin input qua tầng hidden đến tầng output, truyền lỗi từ tầng output qua tầng hidden đến tầng hidden, cập nhật lại các trọng số

Trong giai đoạn đầu, các phần tử của tầng input sẽ đọc các các giá trị input, các giá trị này sẽ được truyền đến tầng hidden Dựa vào các trọng số của mạng và hàm squashing ta sẽ tính được giá trị của các phần tử của tầng hidden Tương tự, tín hiệu sẽ được truyền đến tầng output Tại đây, các giá trị output tính được sẽ được so sánh với các giá trị output mong muốn (giai đoạn 2) Từ đây các giá trị lỗi sẽ được tính toán và

Chương 3: Giải thuật lan truyền ngược

đoạn 2 và các giá trị ở giai đoạn 1, mỗi trọng số của mạng sẽ được điều chỉnh lại để làm giảm các giá trị lỗi này

3.2.1 Hàm squashing

Hàm squashing (còn gọi là hàm activation) được dùng trong giải thuật lan truyền ngược có các đặc điểm sau: liên tục, khả vi và không giảm Ngoài ra, để tiện cho quá trình tính toán, ta thường chọn hàm squashing là những hàm dễ tính toán, dễ tính đạo hàm Trong giải thuật này, hàm squashing được dùng trong giai đoạn 1 (truyền input)

và đạo hàm của nó được dùng trong giai đoạn 3 (truyền lỗi)

1 ( )

) ( ) (x f x f x

x x

e e

e e x

1 ( )1 ( )

) (x f x f x

Hàm tanh [2]

3.2.2 Chi tiết giải thuật lan truyền ngược (sử dụng hàm sigmoid)

Phần này sẽ trình bày chi tiết các bước của giải thuật lan truyền ngược sử dụng hàm squashing là hàm sigmoid

Mỗi mẫu là một cặp ( t x,  )

, trong đó, x

là vector input của mạng neuron, t

là vector output mong muốn đạt được tương ứng

Chương 3: Giải thuật lan truyền ngược

1 Tạo một mạng neuron gồm n in input, n hidden hidden, n out output

2 Khởi tạo các trọng số trong mạng bằng các giá trị random (thường là các giá trị nhỏ trong khoảng -0.5 đến 0.5)

3 Cho đến khi đạt được sai số mong muốn hoặc đạt đến số lần lặp tối

đa, thực hiện các bước sau:

For each ( t x,  )

do, Gán x

vào các thành phần của tầng input, tính các giá trị output o u cho mỗi thành phần u trong mạng

Với mỗi thành phần output, tính các giá trị lỗi k:

))(

1( k k k

k

Với mỗi thành phần của tầng hidden, tính các giá trị lỗi h:

k kh h

ji j

3.2.3 Một số lưu ý trong việc áp dụng giải thuật

a Biểu diễn input, output

Trong giải thuật lan truyền ngược, cách mã hóa các input và output của hệ thống ảnh hưởng rất lớn đến tốc độ hội tụ của giải thuật Trong phần này sẽ trình bày 1 khảo sát đối với bài toán XOR

- Trường hợp 1: TRUE = 1, FALSE = 0

- Trường hợp 2: TRUE = 0.8, FALSE = -0.8

Tốc độ hội tụ khi sử dụng biểu diễn nhị phân [2]

Tốc độ hội tụ khi sử dụng biểu diễn (0.8, -0.8) [2]

Chương 3: Giải thuật lan truyền ngược

Như vây, với các mã hóa output khác nhau, tốc độ hội tụ cũng khác nhau Tốc độ hội tụ trong trường hợp thứ hai nhanh hơn nhiều so với trường hợp thứ nhất

b Khởi tạo các trọng số

Việc khởi tạo các giá trị cho các trọng số rất quan trọng, ảnh hưởng trực tiếp đến việc hội tụ cũng như tốc độ hội tụ Nếu các giá trị này không thích hợp, thuật toán sẽ không thể đạt được cực tiểu (rơi vào các điểm cực tiểu cục bộ) Thông thường, các trọng số được khởi tạo bằng các giá trị nhỏ (vì các hàm squashing thường có giá trị gần với giá trị tiệm cận khi input lớn)

Khi quá trình huấn luyện bị rơi vào cực tiểu cục bộ, ta có thể chọn giá trị ngẫu nhiên khác cho các trọng số để tiến hành học lại Đây cũng là cách giải quyết đối với các bài toán phức tạp, có nhiểu điểm cực tiểu cục bộ

c Số ví dụ mẫu

Số lượng mẫu quá ít, mạng neuron sẽ không thể tổng quát hóa được bài toán:

Ảnh hưởng của số lượng mẫu [1]

Trong hình trên, đường nét đứt là hàm số cần xấp xỉ, đường nét liền là hàm số mà mạng neuron đã học được Trong hình A, số lượng mẫu quá ít, do đó dù mạng neuron

đã học được 1 kết quả khá chính xác (so với các mẫu đã cung cấp) nhưng không thể hiện được đúng hàm mong muốn

d Số tầng hidden

Với nhiều hơn 1 tầng hidden, giá trị của các phần tử cũng như các giá trị lỗi cũng được truyền từ tầng này sang tầng kia Khi sử dụng nhiều tầng, mạng neuron sẽ có khả năng thể hiện được nhiều hàm phức tạp hơn, do đó có thể giải quyết được nhiều bài toán phức tạp Tuy nhiên, lúc này quá trình học sẽ tốn nhiều thời gian hơn

Nhiều nghiên cứu đã chỉ ra rằng, với 1 tầng hidden, mạng neuron có thể giải quyết được đa số các bài toán trong thực tế với độ chính xác cao Trong một số trường hợp, 2 tầng hidden có thể giúp giải quyết bài toán dễ dàng hơn

e Sử dụng momen

Đây là một kỹ thuật được áp dụng trong giai đoạn điều chỉnh các trong số Theo

đó, trọng số ở lần lặp thứ n sẽ được tính toán theo công thức sau:

)1()

w ji n j x ji  w ji n

)()

1()(n w n w n

w ji  ji   ji

trong đó,  là momen – hằng số có giá trị trong khoảng [0, 1) Khi không muốn sử dụng momen, ta có thể cho  0, khi đó ta sẽ có thuật toán như đã trình bày ở trên Trong giải thuật lan truyền ngược cơ bản (không sử dụng momen), nếu ta sử dụng tỉ lệ học nhỏ thì quá trình học sẽ tốn nhiều thời gian để đạt được cực tiểu Ngược lại, khi sử dụng tỉ lệ học lớn, có thể sẽ không đạt được cực tiểu do dao động quá lớn

Do đó, giải pháp sử dụng momen tương đối hiệu quả khi tăng tốc độ hội tụ của giải thuật

a: tỉ lệ học nhỏ - b: là tỉ lệ học lớn - c: sử dụng momen, tỉ lệ học lớn

Chương 3: Giải thuật lan truyền ngược

3.3 Nhận xét về giải thuật lan truyền ngược

Bản chất việc huấn luyện cho mạng neuron là điều chỉnh các trọng số để đạt đƣợc sai

số nhỏ nhất cho tập huấn luyện Do đó, nếu tập huấn luyện không đủ tổng quát thì khi

áp dụng cho dự liệu thực sẽ không chính xác Đây là vấn đề overfitting trong huấn luyện mạng neuron

Lỗi so với số lượng cập nhật trọng số [3]

♦ Lỗi trên tập huấn luyện + Lỗi trên tập kiểm tra

Các nguyên nhân dẫn tới overfitting:

- Quá trình huấn luyện quá lâu nên tính tổng quát của mạng neuron giảm vì quá gần với tập huấn luyện Nếu tập huấn luyện không tốt, kết quả trên dữ liệu thực sẽ không chính xác

- Sử dụng quá nhiều đơn vị hidden: Nhiều đơn vị hidden có thê mô hình hóa đƣợc những hàm phức tạp hơn và nhiều mẫu input hơn Tuy nhiên, với quá nhiều đơn vị hidden, quá trình mô hình hóa trên tập huấn luyện quá gần với input, do đó làm cản trở sự tổng quát hóa trên toàn tập huấn luyện

Ảnh hưởng của số đơn vị hidden đến quá trình huấn luyện [1]

hệ thống với độ chính xác cao

TÀI LIỆU THAM KHẢO

1 Ben Kröse, Patrick Van Der Smagt, 1996, Introduction to Neural Network, The

University of Amsterdam

2 Laurene Fausett, 1995, Fundamenteal of Neural Network

3 Tom Mitchel, 1997, Machine Learning, McGraw Hill