Giáo trình Trí tuệ nhân tạo - Chương 4: Học máy - Lý Anh Tuấn

1 Học Máy – Cây quyết định – Mạng neural 2 Học Máy • Học (learning) là bất cứ sự thay đổi nào trong một hệ thống cho phép nó thi hành tốt hơn ở lần thứ hai khi lặp lại cùng một nhiệm vụ hoặc với nhiệm vụ khác từ tập các nhiệm vụ. • Học liên quan đến vấn đề khái quát hóa từ kinh nghiệm (dữ liệu huấn luyện) => bài toán quy nạp • Nhiệm vụ học – Xác định người học cần học cái gì ? – Người học cần được cung cấp những gì ? – Đánh giá thành tích học 3 Một số khái niệm • Tập ví dụ huấn luyện (training set, training example): Là các ví dụ đã biết trước kết quả phân lớp cũng như các giá trị của các thuộc tính, dùng để xây dựng nên cây quyết định. • Mẫu (instance): Là một trường hợp cụ thể cần phân lớp. Một mẫu là một ví dụ cụ thể, biết một số hay toàn bộ các giá trị của các thuộc tính song không biết giá trị của thuộc tính phân lớp. • Thuộc tính đích (target distribute): Là thuộc tính chỉ ra một ví dụ thuộc một lớp nào đó, còn có tên gọi khác là thuộc tính phân lớp. • Hàm học (target function/ learning function): VD cây quyết định cần xây dựng, có chức năng phân lớp các mẫu. 4 Một số khái niệm • Ví dụ: Phân loại ba loại quả Mơ, Mận, Đào: – Xác định hàm f: từ tập M là tập gồm 3 loại quả Mơ, Mận, Đào => Tên quả = {Mơ, Mận, Đào}. Hàm f gọi là hàm mục tiêu hay còn gọi là hàm học a  M: f(a) = Mơ hoặc Mận hoặc Đào – Tập các ví dụ huấn luyện: D={(a, b)| a  M, b là tên quả} – Đánh giá thành tích: Cho xác định tên quả, xác định tỉ lệ đúng 5 Cây quyết định 6 Học cây quyết định Cây quyết định là một cấu trúc dạng lưu đồ, trong đó: • Mỗi nút trung gian kiểm tra một thuộc tính • Mỗi nhánh tương ứng với giá trị của thuộc tính • Các nút lá thể hiện sự phân loại Tỉ lệ thất nghiệp cao? Thị trường New York tăng trưởng hôm nay? Thị trường London sẽ không tăng trưởng ngày hôm nay {day4, day5, day6} Thị trường London sẽ tăng trưởng ngày hôm nay {day1} Thị trường London sẽ tăng trưởng ngày hôm nay {day2, day3} YES YES NO NO ngày trong quá khứ Ra quyết định: Thị trường London tăng trưởng hôm nay? Học cây quyết định • Tạo cây quyết định bao gồm hai pha – Dựng cây • Chia các ví dụ một cách đệ quy dựa trên thuộc tính được lựa chọn • Ở thời điểm bắt đầu, tất cả các đối tượng huấn luyện ở nút gốc – Cắt tỉa cây • Xác định và loại bỏ các nhánh phản ánh nhiễu hoặc dị biệt • Sử dụng cây quyết định: Phân loại một đối tượng chưa biết – Kiểm tra các giá trị thuộc tính của đối tượng dựa vào cây quyết định 7 8 Ví dụ: Cây quyết định Chơi Tennis • Mục đích: Kiểm tra xem sáng thứ sáu nào thì thích hợp cho việc chơi tennis • Cây quyết định: Có Quang cảnh nắng Âm u mưa Độ ẩm Có Gió cao Trung bình mạnh nhẹ Không Có Không VD: Trường hợp (Quang cảnh=nắng, Nhiệt độ=Nóng, Độ ẩm=cao, Gió=mạnh) thì Chơi Tennis = Không 9 Thuật toán dựng cây Ở mỗi nút của cây: 1. Chọn thuộc tính quyết định “tốt nhất” cho nút 2. Mở rộng cây bằng cách thêm nhánh mới cho mỗi giá trị của thuộc tính 3. Sắp xếp các ví dụ vào các nút lá 4. If tất cả các ví dụ trong một nút thuộc về cùng một lớp Then Stop Else lặp lại các bước 1-4 trên mỗi nút lá mới 10 Tập dữ liệu huấn luyện Ngày Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Tennis D1 Nắng Nóng Cao nhẹ Không D2 Nắng Nóng Cao Mạnh Không D3 Âm u Nóng Cao Nhẹ Có D4 Mưa ấm áp Cao nhẹ Có D5 Mưa Mát TB nhẹ Có D6 Mưa Mát TB Mạnh Không D7 Âm u Mát TB Mạnh Có D8 Nắng ấm áp Cao nhẹ Không D9 Nắng Mát TB nhẹ Có D10 Mưa ấm áp TB nhẹ Có D11 Nắng ấm áp TB Mạnh Có D12 Âm u ấm áp Cao Mạnh Có D13 Âm u Nóng TB nhẹ Có D14 Mưa ấm áp Cao Mạnh Không Giá trị của các thuộc tính + Phân loại ví dụ Cây phức tạp 11 Nhiệt độ Quang cảnh Gió lạnh trung bình nóng Có nắng mưa Không mạnh nhẹ Có âm u Quang cảnh nắng mưa Có âm u Gió Có Không mạnh nhẹ Gió Không Có mạnh nhẹ Độ ẩm Có cao bình thường Gió Có Không mạnh nhẹ Độ ẩm Có cao bình thường Quang cảnh Không nắng mưa Có âm u null Cây đơn giản 12 Quang cảnh Độ ẩm Gió Có nắng âm u mưa Có Không cao bình thường Có Không mạnh nhẹ Cây đơn giản hơn nhiều khi chọn Quang cảnh làm nút gốc Occam’s razor: cái đơn giản thường là cái tốt nhất! 13 Thuộc tính nào tốt nhất • Một nút S chứa 19 đối tượng dương (+) và 35 đối tượng âm (-), ký hiệu là [19+, 35-] • Nếu các thuộc tính A1 và A2 (mỗi thuộc tính có hai giá trị) chia S vào các nút con với tỉ lệ các đối tượng dương và âm như bên dưới, thuộc tính nào là tốt hơn? [29+, 36-] A1 = ? [29+, 36-] A2 = ? [21+, 6-] [8+, 30-] [18+, 34-] [11+,2-] 14 Entropy Entropy đo độ pha trộn của một tập đối tượng bất kỳ, hay là lượng thông tin cần thiết để phân lớp một đối tượng bất kỳ trong tập S là tập các đối tượng dương và âm là tỉ lệ đối tượng dương trong S là tỉ lệ đối tượng âm trong S   plogpplogp)S(Entropy 22 p p Entropy Hàm entropy tương ứng với phân lớp Boolean, vì tỉ lệ của các đối tượng dương biến thiên trong đoạn 0, 1. 15    c i ii ppSEntropy 1 2log)( p Ví dụ Từ 14 ví dụ của Chơi Tennis, có 9 đối tượng dương và 5 đối tượng âm (ký hiệu [9+, 5-]) Entropy([9+,5-]) = - (9/14)log2(9/14) - (5/14)log2(5/14) = 0.940 Lưu ý: 1. Entropy bằng 0 nếu tất cả các phần tử của S cùng thuộc một lớp. 2. Entropy bằng 1 nếu tập bao chứa số lượng ví dụ dương và âm bằng nhau. Nếu chúng không bằng nhau entropy nằm giữa 0 và 1. 16 17 Gia lượng thông tin Information Gain Gain(S, A) = Lượng giảm entropy mong đợi qua việc chia các ví dụ theo thuộc tính A trong đó: - Values(A) là tập tất cả các giá trị có thể có của thuộc tính A - Sv là tập con của S mà thuộc tính A của các phần tử có giá trị v.    )( )( || || )(),( AValuesv v v SEntropy S S SEntropyASGain Gia lượng thông tin Information Gain Values(Gió) = {Yếu, Mạnh}, S = [9+, 5-] Nút con có giá trị “yếu”, Syếu = [6+, 2-] Nút con có giá trị “mạnh”, Smạnh = [3+, 3-] = Entropy(S) - (8/14)Entropy(Syếu) - (6/14)Entropy(Smạnh) = 0.940 - (8/14)0.811 - (6/14)1.00 = 0.048 18    },{ )( || || )(),( ManhYeuv v v SEntropy S S SEntropyGióSGain 19 Chọn thuộc tính quyết định tốt nhất Độ ẩm Cao Trung bình [3+,4 – ] E = 0.985 [6+,1 – ] E = 0.592 S: [9+,5 – ] E = 0.940 Gió Nhẹ Mạnh [6+,2 – ] E = 0.811 [3+,3 – ] E = 1.0 S: [9+,5 – ] E = 0.940 Gain(S, Độ ẩm) = .940 – (7/14).985 – (7/14).592 = .151 Gain(S, Gió) = .940 – (8/14).811 – (6/14)1.0 = .048 20 Gia lượng thông tin của tất cả các thuộc tính • Gain (S, Quang cảnh) = 0.246 X • Gain (S, Độ ẩm) = 0.151 • Gain (S, Gió) = 0.048 • Gain (S, Nhiệt độ) = 0.029 21 Bước mở rộng cây tiếp theo {D1, D2, ..., D14} [9+, 5-] Quang cảnh? {D1, D2, D8, D9, D11} [2+, 3-] {D3, D7, D12, D13} [4+, 0-] {D4, D5, D6, D10, D14} [3+, 2-] Nắng Âm u Mưa ? ? Có Thuộc tính nào sẽ được kiểm tra ở đây? SNắng = {D1, D2, D8, D9, D11} Gain(SNắng, Độ ẩm) = .970 - (3/5)0.0 - (2/5)0.0 = 0.970 Gain(SNắng, Nhiệt độ) = .970 - (2/5)0.0 - (2/5)1.0 - (1/5)0.0 = 0.570 Gain(SNắng, Gió) = .970 - (2/5)1.0 - (3/5)0.918 = 0.019 22 Điều kiện dừng 1. Nhánh hiện tại của cây đã chứa tất cả các thuộc tính có thể có 2. Các ví dụ huấn luyện liên kết với mỗi nút lá đều âm hoặc đều dương (tức là entropy của chúng bằng 0) Lưu ý: Thuật toán ID3 sử dụng Information Gain để xây dựng cây quyết định 23 Overfitting trong cây quyết định • Cây quyết định có thể quá khớp (overfit) với dữ liệu huấn luyện: – Có quá nhiều nhánh, phản ánh sự bất thường do nhiễu hoặc dị biệt – Dẫn đến phân loại thiếu chính xác các đối tượng chưa gặp • Hai tiếp cận để tránh overfitting – Cắt tỉa trước: Dừng việc xây dựng cây sớm – không phân chia một nút nếu việc này làm cho độ tốt của cây rơi xuống dưới một ngưỡng – Cắt tỉa sau: Loại bỏ các nhánh khỏi một cây đã được phát triển đầy đủ - nhận được một chuỗi liên tiếp các cây được cắt tỉa 24 Chuyển cây về các luật IF (Quang cảnh = Nắng) và (Độ ẩm = Cao) THEN Chơi Tennis = Không IF (Quang cảnh = Nắng) và (Độ ẩm = Trung bình) THEN Chơi Tennis = Có có Quang cảnh nắng âm u mưa Độ ẩm có Gió cao Trung bình mạnh nhẹ không có không 25 Đánh giá hiệu suất • Mục đích: một cây quyết định có thể phân loại đúng một ví dụ chưa từng gặp • Việc học sử dụng một “tập huấn luyện” • Việc đánh giá hiệu suất sử dụng một “tập kiểm tra”: 1. Thu thập một tập lớn các ví dụ 2. Chia thành tập huấn luyện và tập kiểm tra 3. Sử dụng giải thuật và tập huấn luyện để xây dựng cây quyết định h 4. Đo phần trăm tập kiểm tra được phân loại đúng bởi h 5. Lặp lại bước 1 đến 4 cho các tập kiểm tra có kích cỡ khác nhau được chọn ngẫu nhiên Bài tập • Thuộc tính nào là gốc của cây quyết định được huấn luyện bởi tập dữ liệu sau? 26 Height Hair Eyes Attractive? small blonde brown No tall dark brown No tall blonde blue Yes tall dark Blue No small dark Blue No tall red Blue Yes tall blonde brown No small blonde blue Yes 27 Mạng nơron 28 Mạng nơron • Ưu điểm – Mức độ dự đoán chính xác tương đối cao – Làm việc cả khi các đối tượng huấn luyện có chứa lỗi – Đầu ra có thể là rời rạc, giá trị thực hoặc một véc tơ các thuộc tính rời rạc hoặc giá trị thực – Ước lượng nhanh nếu hàm mục tiêu đã được học • Nhược điểm – Thời gian huấn luyện lâu – Khó hiểu được hàm học (các trọng số) – Không dễ để hợp nhất các miền tri thức 29 Perceptron • Khái niệm cơ bản – Perceptron là một mô hình đơn giản nhất của mạng nơron. – Percetron biểu diễn hàm boolean của n biến (x1, x2, xn) với xi là các giá trị thực. – Thường được dùng để phân loại hay nhận dạng các đối tượng. • Kiến trúc s=∑ x0 = 1 x1 xn . . . wn w1 w0 y (1/0) 30 Perceptron • Trong đó: • Khả năng biểu diễn: – là phương trình của một siêu phẳng – Perceptron chỉ biểu diễn được các hàm siêu phẳng tuyến tính, siêu phẳng này chia không gian thành 2 phần s =    n i nnii xwxwwxw 0 110 ... y =       00 01 s s 0...110  nnxwxww 31 Perceptron • Ví dụ: – Xây dựng perceptron biểu diễn các hàm boolean: AND, OR, NAND, NOR – Xây dựng một mạng nơron kết hợp các perceptron để biểu diễn các hàm boolean: XOR, NXOR Giả sử các giá trị logic 1(true) và -1(false) AND: w0=-.8, w1=w2=.5 OR: w0=.3, w1=w2=.5 XOR: ? 32 Luật học perceptron • Hàm cần học: là hàm biểu diễn được bằng perceptron • Giá trị đầu ra: y = f (x1, x2, xn) • Tập ví dụ huấn luyện: D = {(x, t) | x= (x1, x2, xn), t = 1/0} • Nhiệm vụ: là xác định vector trọng số w = (w1, w2, wn) sao cho khi đưa giá trị vào x thì giá trị ra tương ứng y=t. S=∑ 1 x1 x2 w2 w1 w0 y (1/0) x1 and x2 33 Luật học perceptron • Tư tưởng: xuất phát từ việc khởi tạo 1 bộ trọng số ngẫu nhiên tính được đầu ra, căn cứ vào đầu ra điều chỉnh đầu vào • Thuật toán: i. Khởi tạo vector trọng số (w0,w1...,wn), wi nhỏ. Ví dụ: chọn (-0,5, 0,5) ii.Bước lặp: Đối với mọi ví dụ huấn luyện d=(x,t)  D • Tính đầu ra Ô của Perceptron ứng với x • Cập nhật trọng số theo công thức wi  wi + (i=0,1,...,n) ( : hằng số dương nhỏ gọi là tốc độ học) ixÔt )(   34 Mạng nơron truyền thẳng nhiều tầng Một mạng nơ ron truyền thẳng nhiều tầng: Một ví dụ huấn luyện, X=(x1, x2, , xi) được đưa vào tầng đầu vào. Giữa các tầng tồn tại các liên kết có trọng số, trong đó wij thể hiện trọng số từ một đơn vị j ở một tầng tới một đơn vị i ở một tầng phía trước 35 Mạng nơron truyền thẳng nhiều tầng • Thuật toán lan truyền ngược thực hiện việc học trên một mạng nơron truyền thẳng nhiều tầng • Đầu vào tương ứng với số các thuộc tính dùng đánh giá các đối tượng huấn luyện • Tầng thứ hai là các đơn vị ẩn • Tầng đầu ra đưa ra dự đoán của mạng về một ví dụ cho trước • Các trọng số được liên kết với các vòng tròn 36 Một đơn vị tầng ẩn hoặc tầng đầu ra Đầu vào (Đầu ra của lớp trước) Tổng trọng số Hàm hoạt hóa Đầu vào của tầng j là các đầu ra từ tầng phía trước. Chúng được nhân với các trọng số tương ứng để tạo thành một tổng có trọng số, sau đó tổng này được cộng thêm bias liên kết với đơn vị j. Một hàm hoạt hoá không tuyến tính được áp dụng để tính đầu ra của mạng 37 Xác định một tôpô cho mạng • Trước khi huấn luyện người sử dụng phải quyết định tô pô cuả mạng: số lượng các tầng, số lượng các đơn vị ở mỗi tầng. • Thường thì các giá trị đầu vào được chuẩn hoá sao cho rơi vào trong khoảng 0,1 hoặc -1,1. Các thuộc tính có giá trị riêng rẽ có thể được mã hoá sao cho có một đơn vị đầu vào cho mỗi miền giá trị. • Một đơn vị đầu ra có thể được sử dụng để đại diện cho hai lớp. Nếu nhiều hơn hai lớp, thì sử dụng một đơn vị đầu ra cho mỗi lớp. • Không có quy tắc rõ ràng để xác định số lượng “tốt nhất” các đơn vị tầng ẩn. Thiết kế mạng là quá trình thử- và- lỗi. 38 Huấn luyện mạng nơron • Mục tiêu chính của việc huấn luyện: – Thu được một tập các trọng số làm cho hầu hết các đối tượng trong tập dữ liệu huấn luyện được phân loại chính xác • Các bước: – Khởi tạo các trọng số với các giá trị ngẫu nghiên – Lần lượt đưa từng đối tượng đầu vào vào trong mạng – Với mỗi đơn vị: • Tính toán đầu vào thực sự của đơn vị là sự kết hợp tuyến tính tất cả các đầu vào của đơn vị • Tính toán giá trị đầu ra bằng việc sử dụng hàm hoạt hoá • Tính toán lỗi 39 Thuật toán lan truyền ngược • Học bằng cách lặp lại việc xử lý một tập các đối tượng huấn luyện, so sánh dự đoán mạng của mỗi đối tượng với nhãn lớp đã biết của nó (sai số) • Các trọng số được chỉnh sửa để làm cực tiểu sai số trung bình bình phương. Việc chỉnh sửa được thực hiện theo chiều “đi lùi”: từ tầng đầu ra, xuyên qua mỗi tầng ẩn xuống tầng đầu tiên • Đầu vào: Các đối tượng huấn luyện, tốc độ học l, một mạng truyền thẳng nhiều tầng • Đầu ra: Mạng nơron được huấn luyện để phân lớp các đối tượng 40 Thuật toán lan truyền ngược • Khởi tạo các trọng số – Là các số phát sinh ngẫu nhiên nhỏ (từ -1.0 đến 1.0 hoặc –0.5 đến 0.5) – Mỗi đơn vị j liên kết với một bias θj • Lan truyền các đầu vào về phía trước – Tính đầu vào và đầu ra của mỗi đơn vị ẩn và đơn vị đầu ra – Đầu vào được tính theo công thức: Ij = Σi wij Oi + θj – Ví dụ đầu ra có thể được tính bởi hàm sigmoid Oj = 1/(1+e -Ij) • Lan truyền ngược sai số – Sai số được tính toán và được lan truyền ngược lại bằng cách cập nhật các trọng số (wij = wij + Δwij) và bias (θj = θj + Δθj) để phản hồi sai số dự đoán của mạng • Điều kiện kết thúc – Tất cả Δwij ở lần trước là đủ nhỏ – Tỉ lệ các đối tượng bị phân lớp nhầm ở lần trước thấp hơn một ngưỡng nào đó – Số lượng các lần được chỉ ra từ trước có thể đã hết 41 Thuật toán lan truyền ngược 42 Thuật toán lan truyền ngược Khởi tạo các trọng số và các bias trong mạng While điều kiện dừng chưa được thoả mãn { for mỗi đối tượng huấn luyện X { /* lan truyền thẳng đầu vào */ for mỗi đơn vị tầng ẩn hoặc tầng đầu ra j { Ij = Σi wijOi + θj /* tính toán đầu vào thực sự của đơn vị j dựa vào tầng phía trước */ Oj = 1/(1+e -Ij) } for mỗi đơn vị j ở tầng đầu ra /* lan truyền ngược các sai số */ Errj = Oj(1 - Oj)(Tj – Oj) /* tính toán sai số */ for mỗi đơn vị j ở các tầng ẩn, từ tầng ẩn cuối cùng đến tầng ẩn đầu tiên Errj = Oj(1 - Oj) Σk Errkwjk /* tính toán sai số dựa vào tầng cao hơn tiếp theo k */ for mỗi trọng số wij trong mạng { Δ wij = (l) Errj Oi /* số gia trọng số */ wij = wij + Δ wij } /* cập nhật trọng số */ for mỗi bias θj trong mạng { θj = (l) Errj /* số gia bias */ θj = θj + Δ θj } /* cập nhật bias */ }} Bài tập • Xét mạng đơn giản sau đây: Giả sử các nơron sử dụng hàm hoạt hóa Sigmoid (i) Thực hiện một lần truyền thẳng trên mạng. (ii) Thực hiện một lần (huấn luyện) truyền ngược (mục tiêu = 0.5). (iii) Thực hiện thêm một lần truyền thẳng và nhận xét kết quả.