Bài giảng Khai phá dữ liệu web - Chương 7: Phân lớp web - Hà Quang Thụy

0Các phương pháp đánh giá hiệu quả	Câu hỏi: Làm thế nào để đánh giá được hiệu quả của một mơ hình?Độ đo để đánh giá hiệu quảCâu hỏi: Làm thế nào để cĩ được ước tính đáng tin cậy?Phương pháp so sánh mơ hìnhCâu hỏi: Làm thế nào để so sánh hiệu quả tương đối giữa các mơ hình cĩ tính cạnh tranh?Đánh giá phân lớp nhị phân11Theo dữ liệu testGiá trị thực: P dương / N âm; Giá trị qua phân lớp: T đúng/F sai. : cịn gọi là ma trận nhầm lẫnSử dụng các ký hiệu TP (true positives), TN (true negatives), FP (false positives), FN (false negatives)TP: số ví dụ dương P mà thuật tốn phân lớp cho giá trị đúng TTN: số ví dụ âm N mà thuật tốn phân lớp cho giá trị đúng TFP: số ví dụ dương P mà thuật tốn phân lớp cho giá trị sai FFN: số ví dụ âm N mà thuật tốn phân lớp cho giá trị sai FĐộ hồi tưởng , độ chính xác , các độ đo F1 và FĐánh giá phân lớp nhị phân12Phương án khác đánh giá mơ hình nhị phân theo độ chính xác (accuracy) và hệ số lỗi (Error rate)Ma trận nhầm lẫnLớp dự báoLớp = 1Lớp = 0Lớp thực sựLớp = 1f11f10Lớp = 0f01f00So sánh hai phương án13Tập test cĩ 9990 ví dụ lớp 0 và 10 ví dụ lớp 1. Kiểm thử: mơ hình dự đốn cả 9999 ví dụ là lớp 0 và 1 ví dụ lớp 1 (chính xác: TP)Theo phương án (precision, recall) cĩ	= 1/10=0.1; =1/1=1; f1 = 2*0.1/(0.1+1.0)= 0.18Theo phương án (accurary, error rate) cĩ	accurary=0.9991; error rate = 9/10000 = 0.0009	Được coi là rất chính xác !f1 thể hiện việc đánh giá nhạy cảm với giá dữ liệu	Đánh giá phân lớp đa lớp14Lớp CiGiá trị thựcThuộc lớp CiKhơng thuộc lớp CiGiá trị qua bộ phân lớp đa lớpThuộc lớp CiTPiTNiKhơng thuộc lớp CiFPiFNiBài tốn ban đầu: C gồm cĩ k lớpĐối với mỗi lớp Ci , cho thực hiện thuật tốn với các dữ liệu thuộc Dtest nhận được các đại lượng TPi, TFi, FPi, FNi (như bảng dưới đây)Đánh giá phân lớp đa lớp15Tương tự bộ phân lớp hai lớp (nhị phân)Độ chính xác Pri của lớp Ci là tỷ lệ số ví dụ dương được thuật tốn phân lớp cho giá trị đúng trên tổng số ví dụ được thuật tốn phân lớp vào lớp Ci :Độ hồi tưởng Rei của lớp Ci là tỷ lệ số ví dụ dương được thuật tốn phân lớp cho giá trị đúng trên tổng số ví dụ dương thực sự thuộc lớp Ci: Đánh giá phân lớp đa lớp16Các giá trị i và i : độ hồi phục và độ chính xác đối với lớp Ci. Đánh giá theo các độ đo vi trung bình-microaveraging (được ưa chuộng)  và  trung bình lớn-macroaveraging M và M Các kỹ thuật phân lớp17Các phương pháp cây quyết định	Decision Tree based MethodsCác phương pháp dựa trên luật 	Rule-based MethodsCác phương pháp Bayes «ngây thơ» và mạng tin cậy Bayes	Nạve Bayes and Bayesian Belief NetworksCác phương pháp máy vector hỗ trợ	Support Vector MachinesLập luận dưa trên ghi nhớ 	Memory based reasoningCác phương pháp mạng nơron	Neural NetworksMột số phương pháp khácMơ hình phân lớp là cây quyết địnhCây quyết địnhGốc: tên thuộc tính; khơng cĩ cung vào + khơng/một số cung raNút trong: tên thuộc tính; cĩ chính xác một cung vào và một số cung ra (gắn với điều kiện kiểm tra giá trị thuộc tính của nút)Lá hoặc nút kết thúc: giá trị lớp; cĩ chính xác một cung vào + khơng cĩ cung ra.Ví dụ: xem trang tiếp theoXây dựng cây quyết địnhPhương châm: “chia để trị”, “chia nhỏ và chế ngự”. Mỗi nút tương ứng với một tập các ví dụ học. Gốc: tồn bộ dữ liệu họcMột số thuật tốn phổ biến: Hunt, họ ID3+C4.5+C5.xSử dụng cây quyết địnhKiểm tra từ gốc theo các điều kiệnPhân lớp cây quyết địnhVí dụ cây quyết định và sử dụngKết luận: Gán giá trị YES vào trường Cheat cho bản ghi1YesSystemProcessTimetableYesNoNo01010If System=0 and Process=0 then Class AI = Yes.If System=0 and Process=1 then Class AI = No.If System=1 and Timetable=1 then Class AI = Yes. If System=1 and Timetable=0 then Class AI = No.Ví dụ cây quyết định phân lớp văn bảnPhân lớp văn bản vào lớp AI : trí tuệ nhân tạoDựa vào các từ khĩa cĩ trong văn bản: System, Process, Timetable (Phân tích miền ứng dụng)Thuật tốn dựng cây quyết định sớm nhất, đệ quy theo nút của cây, bắt đầu từ gốcInputCho nút t trên cây quyết định đang được xem xétCho tập các ví dụ học Dt. Cho tập nhãn lớp (giá trị lớp) y1, y1,  yk. (k lớp)OutputXác định nhãn nút t và các cung ra (nếu cĩ) của tNội dung1: Nếu mọi ví dụ trong Dt đều thuộc vào một lớp y thì nút t là một lá và được gán nhãn y.2: Nếu Dt chứa các ví dụ thuộc nhiều lớp thì2.1. Chọn 1 thuộc tính A để phân hoạch Dt và gán nhãn nút t là A2.2. Tạo phân hoạch Dt theo tập giá trị của A thành các tập con2.3. Mỗi tập con theo phân hoạch của Dt tương ứng với một nút con u của t: cung nối t tới u là miền giá trị A theo phân hoạch, tập con nĩi trên được xem xét vơi u tiếp theo. Thực hiện thuật tốn với từng nút con u của t.Dựng cây quyết định: thuật tốn HuntGiải thích- Xuất phát từ gốc với 10 bản ghiThực hiện bước 2: chọn thuộc tính Refund cĩ hai giá trị Yes, No. Chia thành hai tập gồm 3 bản ghi cĩ Refund = Yes và 7 bản ghi cĩ Refund = No Xét hai nút con của gốc từ trái sang phải. Nút trái cĩ 3 bản ghi cùng thuộc lớp Cheat=No (Bước 1) nên là lá gán No (Don’t cheat). Nút phải cĩ 7 bản ghi cĩ cả No và Yes nên áp dụng bước 2. Chọn thuộc tính Marital Status với phân hoạch Married và hai giá trị kiaVí dụ: thuật tốn HuntThuật tốn cây quyết định ID3Bước 4.1. chọn thuộc tính A tốt nhất gán cho nút t.Tồn tại một số độ đo: Gini, Information gainĐộ đo GiniĐo tính hỗn tạp của một tập ví dụ mẫuCơng thức tính độ đo Gini cho nút t:	Trong đĩ p(j|t) là tần suất liên quan của lớp j tại nút tGini (t) lớn nhất = 1-1/nc (với nc là số các lớp tại nút t): khi các bản ghi tại t phân bố đều cho nc lớp; tính hỗn tạp cao nhất, khơng cĩ phân biệt giữa các lớpGini (t) nhỏ nhất = 0 khi tất cả các bản ghi thuộc một lớp duy nhất.Ví dụ: Bốn trường hợpThuộc tính tốt nhất: Độ đo GiniDùng trong các thuật tốn CART, SLIQ, SPRINTKhi một nút t được phân hoạch thành k phần (k nút con của t) thì chất lượng của việc chia tính bằng	trong đĩn là số bản ghi của tập bản ghi tại nút t,.ni là số lượng bản ghi tại nút con I (của nút t).Chia tập theo độ đo GiniTính tốn GINI cho Refund (Yes, No), Marital Status (Single&Divorced, Married) và Taxable Income (  y 	Trong đĩ:	 là sự kết nối các thuộc tính (cịn gọi là tiên đề/điều kiện của luật: LHS bên trái)	 y là nhãn lớp (cịn gọi là kết quả của luật: RHS bên phải).Ví dụ	Refund = ‘Yes”  Cheat = “No”	(Refund = “No”)  (Marital Status = “Married”)  Cheat = “No”Sử dụng luật Một luật được gọi là “bảo đảm” thể hiện r (bản ghi) nếu các thuộc tính của r đáp ứng điều kiện của luật. Khi đĩ, vế phải của luật cũng được áp dụng cho thể hiện.Phân lớp dựa trên luậtGiới thiệuTrực tiếp và gián tiếpTrực tiếpTrích xuất luật trực tiếp từ dữ liệuVí dụ: RIPPER, CN2, Holte’s 1RTrích xuất luật trực tiếp từ dữ liệuBắt đầu từ một tập rỗngMở rộng luật bằng hàm Học_một_luậtXĩa mọi bản ghi “bảo đảm” bởi luật vừa được họcLặp các bước 2-3 cho đến khi gặp điều kiện dừngGián tiếpTrích xuất luật từ mơ hình phân lớp dữ liệu khác, chẳng hạn, mơ hình cây quyết định, mơ hình mạng nơ ron, Ví dụ:C4.5RuleXây dựng luật phân lớpSử dụng thống kêThống kê các đặc trưng cho ví dụTìm đặc trưng điển hình cho từng lớpThuật tốn CN2Khởi đầu bằng liên kết rỗng: {}Bổ sung các liên kết làm cực tiểu entropy: {A}, {A, B}Xác định kết quả luật theo đa số của các bản ghi đảm bảo luậtThuật tốn RIPPERBắt đầu từ một luật rỗng: {}  lớpBổ sung các liên kết làm cực đại lợi ích thơng tin FAILR0: {} => lớp (luật khởi động)R1: {A} => lớp (quy tắc sau khi thêm liên kết)Gain (R0, R1) = t [log (p1 / (p1 + n1)) - log (p0 / (p0 + n0))]với t: số thể hiện đúng đảm bảo cả hai R0 và R1p0: số thể hiện đúng được bảo đảm bởi R0n0: số thể hiện sai được đảm bảo bởi R0P1: số thể hiện đúng được bảo đảm bởi R1n 1: số trường hợp sai được đảm bảo bởi R1Mở rộng luật: một số phương ánLuật phân lớp: từ cây quyết địnhTập luậtLiệt kê các đường đi từ gốcTrích xuất luật từ cây quyết định chưa cắt tỉaVới mỗi luật, r: A → yXem xét luật thay thế r’: A’ → y, trong đĩ A’ nhận được từ A bằng cách bỏ đi một liên kếtSo sánh tỷ lệ lỗi r so với các r’Loại bỏ các r’ cĩ lỗi thấp hơn rLặp lại cho đến khi khơng cải thiện được lỗi tổng thểThay thế sắp xếp theo luật bằng sắp xếp theo tập con của luật (thứ tự lớp)Mỗi tập con là một tập các luật với cùng một kết quả (lớp)Tính tốn độ dài mơ tả của mỗi tập conĐộ dài mơ tả = L(lỗi) + g* L(mơ hình)g : tham số đếm sự hiện diện của các thuộc tính dư thừa trong một tập luật (giá trị chuẩn, g=0.5)Sinh luật gián tiếp: C4.5rulesC4.5rules: Ví dụC4.5rules: Ví dụC4.5rules:(Give Birth=No, Can Fly=Yes)  Birds(Give Birth=No, Live in Water=Yes)  Fishes(Give Birth=Yes)  Mammals(Give Birth=No, Can Fly=No, Live in Water=No)  Reptiles( )  AmphibiansRIPPER:(Live in Water=Yes)  Fishes(Have Legs=No)  Reptiles(Give Birth=No, Can Fly=No, Live In Water=No) 	 Reptiles(Can Fly=Yes,Give Birth=No)  Birds()  MammalsGiới thiệuKhung xác suất để xây dựng bộ phân lớpXác suất cĩ điều kiệnHai biến cố A và CĐịnh lý Bayes:	P(c|x) = P(x|c).P(c)/P(x)P(x) bằng nhau cho tất cả các lớpTìm c sao cho P(c|x) lớn nhất Tìm c sao cho P(x|c).P(c) lớn nhấtP(c): tần suất xuất hiện của các tài liệu thuộc lớp cVấn đề: làm thế nào để tính P(x|c)?Phân lớp BayesMột bác sỹ biếtBệnh nhân viêm màng não cĩ triệu chứng cứng cổ S|M: 50% Xác suất một bệnh nhân bị viêm màng não M là 1/50.000Xác suất một bệnh nhân bị cứng cổ S là 1/20Một bệnh nhân bị cứng cổ hỏi xác suất anh/cơ ta bị viêm màng não ? 	Pang-Ning Tan, Michael Steinbach, Vipin Kumar. Introduction to Data Mining (Chapter 5: Classification: Alternative Techniques),  Addison Wesley, 2005, Định lý Bayes: Ví dụCác thuộc tính (bao gồm nhãn lớp) là các biến ngẫu nhiên.Cho một bản ghi với các giá trị thuộc tính (A1, A2, , An)Cần dự báo nhãn cTìm lớp c để cực đại xác suất P(C|A1, A2, , An)Cĩ thể tính xác suất P(C|A1, A2, , An) từ dữ liệu học? 	Pang-Ning Tan, Michael Steinbach, Vipin Kumar. Introduction to Data Mining (Chapter 5: Classification: Alternative Techniques),  Addison Wesley, 2005, ân lớp BayesPhân lớp văn bản Nạve BayesGiả thiết Nạve Bayes: giả thiết độc lập: xác suất xuất hiện của một từ khĩa trong văn bản độc lập với ngữ cảnh và vị trí của nĩ trong văn bản: Phân lớp văn bản Nạve BayesChoTập ví dụ Dexam = Dlearn + DtestTập từ vựng V = {f1, f2, , f||V||}Tập lớp C= {C1, C2, , Cn} với mỗi Ci một ngưỡng i > 0Tính xác suất tiên nghiệmTrên tập ví dụ học Dlearn p(Ci) = Mi/M, M= ||Dlearn||, Mi = ||Doc  Dlearn / Doc  Ci||Xác suất một đặc trưng (từ) fj thuộc lớp C:Cho tài liệu Doc mớiTính xác suất hậu nghiệmNếu P(C|Doc) > C 	thì Doc  C!Cơng thức phân lớp Bayes thứ haiPhân lớp k-NNCho trướcMột tập D các tài liệu biểu diễn bản ghi các đặc trưngMột đo đo khoảng cách (Ơcơlit) hoặc tương tự (như trên)Một số k > 0 (láng giềng gần nhấtPhân lớp tài liệu mới Doc được biểu diễnTính khoảng cách (độ tương tự) từ Doc tới tất cả tài liệu thuộc DTìm k tài liệu thuộc D gần Doc nhấtDùng nhãn lớp của k-láng giềng gần nhất để xác định nhãn lớp của Doc: nhãn nhiều nhất trong k-láng giềng gần nhấtPhân lớp k-NN: Ví dụBa trường hợp như hình vẽ1-NN: Chọn lớp “-”: láng giềng cĩ nhãn “-” là nhiều nhất2-NN: Chọn lớp “-”: hai nhãn cĩ số lượng như nhau, chọn nhãn cĩ tổng khoảng cách gần nhất3-NN: Chọn lớp “+”: láng giềng cĩ nhãn “+” là nhiều nhấtThuật tốn SVMThuật tốn máy vector hỗ trợ (Support Vector Machine – SVM): được Corters và Vapnik giới thiệu vào năm 1995.SVM rất hiệu quả để giải quyết các bài tốn với dữ liệu cĩ số chiều lớn (như các vector biểu diễn văn bản).Thuật tốn SVMTập dữ liệu học: D= {(Xi, Ci), i=1,n} Ci Є {-1,1} xác định dữ liệu dương hay âmTìm một siêu phẳng: αSVM .d + b phân chia dữ liệu thành hai miền.Phân lớp một tài liệu mới: xác định dấu của f(d) = αSVM .d + bThuộc lớp dương nếu f(d) > 0Thuộc lớp âm nếu f(d) < 0Thuật tốn SVMThuật tốn SVMNếu dữ liệu học là tách rời tuyến tính:Cực tiểu:Thỏa mãn: Nếu dữ liệu học khơng tách rời tuyến tính: thêm biến {ξ1 ξn}:	Cực tiểu: Thỏa mãn: 	Phân lớp Web bán giám sátGiới thiệu phân lớp bán giám sát web Khái niệm sơ bộTại sao học bán giám sátNội dung phân lớp bán giám sát webMột số cách tiếp cận cơ bảnCác phương án học bán giám sát phân lớp webPhân lớp bán giám sát trong NLPHọc bán giám sát:Tài liệu tham khảoXiaojin Zhu (2006 ***). Semi-Supervised Learning Literature Survey, 1-2006. (Xiao Zhu [1])	∼jerryzhu/pub/ssl survey.pdfZhou, D., Huang, J., & Scholkopf, B. (2005). Learning from labeled and unlabeled data on a directed graph. ICML05, 22nd International Conference on Machine Learning. Bonn, Germany. Zhou, Z.-H., & Li, M. (2005). Semi-supervised regression with co-training. InternationalJoint Conference on Artificial Intelligence (IJCAI). Zhu, X. (2005). Semi-supervised learning with graphs. Doctoral dissertation, Carnegie Mellon University (mã số CMU-LTI-05-192).Olivier Chapelle, Mingmin Chi, Alexander Zien (2006) A Continuation Method for Semi-Supervised SVMs. Proceedings of the 23rd International Conference on Machine Learning, Pittsburgh, PA, 2006. 	và các tài liệu khác Sơ bộ về học bán giám sátHọc bán giám sát là gì ? Xiao Zhu [1] FQA Học giám sát: tập ví dụ học đã được gán nhãn (ví dụ gắn nhãn) là tập các cặp (tập thuộc tính, nhãn)ví dụ gắn nhãnThủ cơng: khĩ khăn  chuyên gia  tốn thời gian, tiềnTự động: như tự động sinh corpus song hiệu quả chưa cao ví dụ chưa gắn nhãnDễ thu thập  nhiềuxử lý tiếng nĩi: bài nĩi nhiều, xây dựng tài nguyên địi hỏi cơng phuxử lý văn bản: trang web vơ cùng lớn, ngày càng được mở rộngCĩ sẵn  cĩ điều kiện tiến hành tự động gắn nhãnHọc bán giám sát: dùng cả ví dụ cĩ nhãn và ví dụ chưa gắn nhãnTạo ra bộ phân lớp tốt hơn so với chỉ dùng học giám sát: học bán giám sát địi hỏi điều kiện về dung lượng khối lượngCơ sở của học bán giám sátBiểu diễn dữ liệu chưa mơ tả hết ánh xạ gán nhãn trên dữ liệuchẳng hạn, nghịch lý “hiệu quả như nhau” trong biểu diễn văn bảnÁnh xạ gán nhãn cĩ liên quan mơ hình dữ liệu (mơ hình / đặc trưng/ nhân / hàm tương tự)  mơ hình đã cĩ theo tự nhiên hoặc giả thiết dữ liệu tuân theo. Hiệu lực của học bán giám sátDữ liệu chưa nhãn khơng luơn luơn hiệu quảNếu giả thiết mơ hình khơng phù hợp  giảm hiệu quảMột số phương pháp cần điều kiện về miền quyết định: tránh miền cĩ mật độ cao:Transductive SVM (máy hỗ trợ vector lan truyền) Information Regularization (quy tắc hĩa thơng tin)mơ hình quá trinh Gauxơ với nhiễu phân lớp bằng khơngphương pháp dựa theo đồ thị với trọng số cạnh là khoảng cách“Tồi” khi dùng phương pháp này song lại “tốt” khi dùng phương pháp khácCác phương pháp học bán giám sát điển hìnhEM với mơ hình trộn sinhSelf-trainingCo-trainingTSVMDựa trên đồ thị... So sánh các phương phápĐịi hỏi các giả thiết mơ hình mạnh. Giả thiết mơ hình phù hợp cấu trúc dữ liệu: khĩ kiểm nghiệmMột số định hướng lựa chọnLớp  phân cụm tốt: dùng EM với mơ hình sinh trộn.Đặc trưng phân thành hai phần riêng rẽ: co-trainingNếu hai điểm tương tự hướng tới một lớp: dựa trên đồ thịĐã sử dụng SVM thì mở rộng TSVMKhĩ nâng cấp học giám sát đã cĩ: dùng self-traningPhương pháp học bán giám sátPhương pháp học bán giám sátDùng dữ liệu chưa gán nhãnHoặc biến dạng hoặc thay đổi thứ tự giả thiết thu nhờ chỉ dữ liệu cĩ nhãnMơ tả chungGiả thiết dưới dạng p(y|x) cịn dữ liệu chưa cĩ nhãn p(x)Mơ hình sinh cĩ tham số chung phân bố kết nối p(x, y)Mơ hình trộn với EM mở rộng thêm self-trainingNhiều phương pháp là phân biệt: TSVM, quy tắc hĩa thơng tin, quá trình Gauxơ, dựa theo đồ thịCĩ dữ liệu khơng nhãn: nhận được xác suất p(x)Phân biệt “học lan truyền” với “học bán giám sát”Đa dạng về cách gọi. Hạn chế bài tốn phân lớp.“Bán giám sát”dùng ví dụ cĩ / khơng cĩ nhãn, “học dữ liệu nhãn/khơng nhãn, “học dữ liệu phân lớp/cĩ nhãn bộ phận”. Cĩ cả lan truyền hoặc quy nạp.Lan truyền để thu hẹp lại cho quy nạp: học chỉ dữ liệu sẵn. Quy nạp: cĩ thể liên quan tới dữ liệu chưa cĩ.Sơ bộMơ hình sớm nhất, phát triển lâu nhấtMơ hình cĩ dạng p(x,y) = p(y)*p(x|y)Với số lượng nhiều dữ liệu chưa nhãn cho P(x|y) mơ hình trộn đồng nhất. Miền tài liệu được phân thành các thành phần, Lý tưởng hĩa tính "Đồng nhất": chỉ cần một đối tượng cĩ nhãn cho mỗi thành phầnTính đồng nhấtLà tính chất cần cĩ của mơ hìnhCho họ phân bố {p} là đồng nhất nếu 1  2 thì p1 p2 cho tới một hốn đối vị trí các thành phần  tính khả tách của phân bố tới các thành phầnMơ hình sinh: Thuật tốn EMTính xác thực của mơ hìnhGiả thiết mơ hình trộn là chính xác  dữ liệu khơng nhãn sẽ làm tăng độ chính xác phân lớpChú ý cấu trúc tốt mơ hình trộn: nếu tiêu đề được chia thành các tiêu đề con thì nên mơ hình hĩa thành đa chiều thay cho đơn chiềuCực đại EM địa phươngMiền áp dụngKhi mơ hình trộn chính xácKý hiệuD: tập ví dụ đã cĩ (cĩ nhẵn /chưa cĩ nhãn)DK: tập ví dụ cĩ nhãn trong D (|DK| << |D|)Mơ hình sinh: Thuật tốn EMNội dung thuật tốn1: Cố định tập tài liệu khơng nhãn DU  D \ DK dùng trong E-bước và M-bước2: dùng DK xây dựng mơ hình ban đầu 03: for i = 0, 1, 2, . . . cho đến khi kết quả đảm bảo do4: for mỗi tài liệu d  DU do5: E-bước: dùng phân lớp Bayes thứ nhất xác định P(c|d,i)6: end for7: for mỗi lớp c và từ khĩa t do8: M-bước: xác định c,t dùng cơng thức (*) để xây dựng mơ hình i+19: end for10: end for	Mơ hình sinh: Thuật tốn EMMơ hình sinh: Thuật tốn EMMột số vấn đề với EMPhạm vi áp dụng: mơ hình trộn chính xácNếu cực trị địa phương khác xa cực trị tồn cục thì khai thác dữ liệu khơng nhãn khơng hiệu quả"Kết quả đảm bảo yêu cầu": đánh giá theo các độ đo hồi tưởng, chính xác, F1...Một số vấn đề khác cần lưu ý: Thuật tốn nhân là Bayes naive: cĩ thể chọn thuật tốn cơ bản khácChọn điểm bắt đầu bằng học tích cựcMơ hình sinh: Thuật tốn khácPhân cụm - và - NhãnSử dụng phân cụm cho tồn bộ ví dụcả dữ liệu cĩ nhãn và khơng cĩ nhãndành tập Dtest để đánh giáĐộ chính xác phân cụm cao Mơ hình phân cụm phù hợp dữ liệuNhãn cụm (nhãn dữ liệu cĩ nhãn) làm nhãn dữ liẹu khácPhương pháp nhân Fisher cho học phân biệtPhương pháp nhân là một phương pháp điển hìnhNhân là gốc của mơ hình sinhCác ví dụ cĩ nhãn được chuyển đổi thành vector Fisher để phân lớpSelf-TrainingGiới thiệuLà kỹ thuật phổ biến trong SSLEM địa phương là dạng đặc biệt của seft-trainingNội dungGọi L : Tập các dữ liệu gán nhãn. U : Tập các dữ liệu chưa gán nhãnLặp (cho đến khi U = )Huấn luyện bộ phân lớp giám sát h trên tập LSử dụng h để phân lớp dữ liệu trong tập UTìm tập con U’  U cĩ độ tin cậy cao nhất:L + U’  L U – U’  U Vấn đề tập U' cĩ "độ tin cậy cao nhất"Thủ tục "bootstrapping"Thường được áp dụng cho các bài tốn NLPTư tưởngMột dữ liệu cĩ hai khung nhìnVí dụ, các trang webNội dung văn bảnTiêu đề văn bảnCo-TrainingMơ hình thuật tốnCo-TrainingCo-TrainingĐiều kiện dừnghoặc tập dữ liệu chưa gán nhãn là rỗng hoặc số vịng lặp đạt tới ngưỡng được xác định trướcMột số lưu ýTập dữ liệu gán nhãn cĩ ảnh hưởng lớn đến co-trainingQuá ít: khơng hỗ trợ co-training Quá nhiều: khơng thu lợi từ co-trainingCơ sở tăng hiệu quả co-training: thiết lập tham số Kích cỡ tập dữ liệu gán nhãnKích cỡ tập dữ liệu chưa gán nhãnSố các mẫu thêm vào sau mỗi vịng lặpBộ phân lớp thành phần rất quan trọng Chặn thay đổi miền dày đặcTransductive SVMs (S3VMs)Phương pháp phân biệt làm việc trên p(y|x) trực tiếpKhi p(x) và p(y|x) khơng tương thích  đưa p(x) ra khỏi miền dầy đặc Quá trình Gauxơ)Mơ hình đồ thịBiểu diễn dữ liệu chưa mơ tả hết ánh xạ gán nhãn trên dữ liệu (chẳng hạn, nghịch lý “hiệu quả như nhau” trong biểu diễn văn bản)Ánh xạ gán nhãn cĩ liên quan mơ hình dữ liệu (mơ hình / đặc trưng/ nhân / hàm tương tự)  mơ hình đã cĩ theo tự nhiên hoặc giả thiết dữ liệu tuân theo. Tài liệu tham khảoSoumen Chakrabarti (2003). Mining the Web: Discovering Knowledge from Hypertext Data. Morgan Kaufmann Publishers. Chương 6. SEMISUPERVISED LEARNING)Các tài liệu về học máy tài liệu chưa gán nhẵn. Pierre Baldi, Paolo Frasconi, Padhraic Smyth (2003). Modeling the Internet and the Web: Probabilistic Methods and Algorithms. Wiley, 2003, ISBN: 0-470-84906-1(Tài liệu giảng dạy 2).Học bán giám sát với dữ liệu WebHọc bán giám sát với dữ liệu WebMột số thuật tốn điển hình (xem [chương 6])Expectation MaximizationExperimental ResultsReducing the Belief in Unlabeled DocumentsModeling Labels Using Many Mixture ComponentsLabeling Hypertext GraphsAbsorbing Features from Neighboring PagesA Relaxation Labeling AlgorithmA Metric Graph- Labeling ProblemCo- training