TỔNG QUAN VỀ CÁC PHƯƠNG PHÁP HỌC MÁY
Giới thiệu về học máy
Học máy (Machine Learning) là một ngành khoa học nghiên cứu các thuật toán cho phép máy tính có thể học đƣợc các khái niệm (concept)[7]
Có hai loại phương pháp học máy chính:
Phương pháp quy nạp trong máy học giúp phân biệt các khái niệm dựa trên dữ liệu đã thu thập trước đó Phương pháp này tận dụng hiệu quả nguồn dữ liệu phong phú và sẵn có, mang lại khả năng học tập và cải thiện mô hình một cách linh hoạt.
Phương pháp suy diễn trong máy học giúp phân biệt các khái niệm dựa trên các quy luật đã được xác định Phương pháp này cho phép tận dụng kiến thức chuyên ngành, từ đó hỗ trợ máy tính trong việc xử lý và phân tích thông tin hiệu quả hơn.
Hiện nay, các thuật toán đều cố gắng tận dụng được ưu điểm của hai phương pháp này
Các ngành khoa học liên quan đến lĩnh vực học máy điển hình là:
Lý thuyết thống kê đóng vai trò quan trọng trong việc cung cấp nền tảng cho nhiều phương pháp học máy, với các kết quả trong xác suất thống kê là cơ sở chính Đặc biệt, lý thuyết này giúp ước lượng sai số của các phương pháp học máy, từ đó nâng cao độ chính xác và hiệu quả của các mô hình.
Các thuật toán học máy thường áp dụng các phương pháp tính toán trên dữ liệu lớn, bao gồm các phép toán số thực và số nguyên Những bài toán như tối ưu có/không ràng buộc và giải phương trình tuyến tính là những ứng dụng phổ biến trong lĩnh vực này.
Khoa học máy tính: là cơ sở để thiết kế các thuật toán, đồng thời đánh giá thời gian chạy, bộ nhớ của các thuật toán học máy
Lĩnh vực học máy truyền thống được phân chia thành bốn lĩnh vực con, trong đó học có giám sát là một phương pháp quan trọng Trong học có giám sát, máy tính được cung cấp các mẫu dữ liệu với đầu vào và đầu ra tương ứng, từ đó học và rút ra quy luật Sau khi hoàn thành quá trình học, máy tính có khả năng tiếp nhận đầu vào mới và đưa ra kết quả dự đoán dựa trên những gì đã học.
Học không giám sát là phương pháp mà máy tính chỉ tiếp cận các mẫu dữ liệu mà không có đầu ra cụ thể Trong quá trình này, máy tính sẽ tự động phân loại các mẫu đã biết và các mẫu mới mà nó gặp phải.
Học nửa giám sát: Một dạng lai giữa hai nhóm giải thuật trên
Học tăng cường là quá trình mà máy tính đưa ra quyết định hành động và nhận phản hồi từ môi trường Sau khi nhận được phản hồi, máy tính sẽ điều chỉnh cách thức ra quyết định của mình để cải thiện hiệu suất.
Học máy được áp dụng rộng rãi trong nhiều ngành khoa học và sản xuất, đặc biệt là những lĩnh vực yêu cầu phân tích lượng dữ liệu lớn Một số ứng dụng phổ biến của học máy bao gồm phân tích dữ liệu, nhận diện hình ảnh và dự đoán xu hướng.
Xử lý ngôn ngữ tự nhiên (Natural Language Processing): xử lý văn bản, giao tiếp người – máy, …
Nhận dạng (Pattern Recognition): nhận dạng tiếng nói, chữ viết tay, vân tay, thị giác máy (Computer Vision) …
Chẩn đoán trong y tế: phân tích ảnh X-quang, các hệ chuyên gia chẩn đoán tự động
Tin sinh học: phân loại chuỗi gene, quá trình hình thành gene/protein
Vật lý: phân tích ảnh thiên văn, tác động giữa các hạt …
Phát hiện gian lận tài chính (financial fraud): gian lận thẻ tỉn dụng
Phân tích thị trường chứng khoán (stock market analysis)
Chơi trò chơi: tự động chơi cờ, hành động của các nhân vật ảo
Rôbốt: là tổng hợp của rất nhiều ngành khoa học, trong đó học máy tạo nên hệ thần kinh/bộ não của người máy
Khai phá dữ liệu (Data mining) là quá trình tìm kiếm tri thức mới và hữu ích từ các nguồn dữ liệu hiện có Đây là một bước quan trọng trong quy trình khai phá tri thức, giúp phát hiện những thông tin tiềm năng có giá trị.
Xác định vấn đề và không gian dữ liệu để giải quyết vấn đề
Chuẩn bị dữ liệu, bao gồm các quá trình làm sạch dữ liệu, tích hợp dữ liệu, chọn dữ liệu, biến đổi dữ liệu
Khai phá dữ liệu là quá trình xác định nhiệm vụ và lựa chọn các kỹ thuật phù hợp để thu thập thông tin Kết quả của quá trình này là một nguồn tri thức thô Để đảm bảo chất lượng, cần tiến hành đánh giá và lọc nguồn tri thức thu được dựa trên một số tiêu chí nhất định.
Quá trình khai phá tri thức không chỉ diễn ra theo trình tự tuyến tính từ bước đầu đến bước cuối, mà còn là một quá trình lặp đi lặp lại, cho phép quay trở lại các bước đã thực hiện trước đó.
Khai phá dữ liệu có thể áp dụng cho nhiều loại kho thông tin khác nhau, bao gồm các cơ sở dữ liệu quan hệ, kho dữ liệu, cơ sở dữ liệu giao tác, hệ thống cơ sở dữ liệu tiên tiến và các tệp.
Phân lớp dữ liệu là kỹ thuật sử dụng tập dữ liệu huấn luyện và các giá trị thuộc tính phân lớp để phân loại dữ liệu mới Kỹ thuật này không chỉ giúp dự đoán loại lớp của nhãn mà còn có sự tương đồng với kỹ thuật tiên đoán Tuy nhiên, phân lớp chỉ tập trung vào việc dự đoán loại lớp, trong khi kỹ thuật tiên đoán mô hình các hàm đánh giá liên tục.
Kĩ thuật phân lớp được tiến hành bao gồm 2 bước: Xây dựng mô hình và sử dụng mô hình
Xây dựng mô hình là quá trình mô tả một tập hợp các lớp đã được định nghĩa, trong đó mỗi bộ dữ liệu được gán thuộc về một lớp thông qua thuộc tính nhãn lớp Tập hợp các bộ dữ liệu này được gọi là tập huấn luyện, và mô hình được biểu diễn dưới dạng các luật phân lớp, cây quyết định, hoặc công thức toán học.
Việc sử dụng mô hình nhằm mục đích phân lớp dữ liệu trong tương lai hoặc cho các đối tượng chưa biết đến Trước khi áp dụng mô hình, cần đánh giá tính chính xác của nó bằng cách so sánh nhãn đã biết của mẫu kiểm tra với kết quả phân lớp của mô hình Độ chính xác được tính bằng phần trăm mẫu kiểm tra được phân loại đúng, trong đó tập kiểm tra phải độc lập với tập huấn luyện.
Phân lớp là một hình thức học có giám sát, tức là: tập dữ liệu huấn luyện
(quan sát, thẩm định ) đi đôi với những nhãn chỉ định lớp quan sát, những dữ liệu mới đƣợc phân lớp dựa trên tập huấn luyện này
Các phương pháp học máy
Học có giám sát là một kỹ thuật trong học máy nhằm xây dựng hàm f từ dữ liệu huấn luyện, bao gồm các cặp đầu vào và đầu ra mong muốn Hàm f có thể trả về giá trị liên tục hoặc dự đoán nhãn phân lớp cho đầu vào.
Chương trình học có giám sát nhằm dự đoán giá trị của hàm f cho một đối tượng đầu vào hợp lệ, dựa trên các mẫu dữ liệu huấn luyện đã được cung cấp Để thực hiện điều này, chương trình cần tổng quát hóa từ dữ liệu hiện có, cho phép dự đoán các tình huống chưa từng gặp một cách hợp lý.
Phương pháp học có giám sát có thể được mô tả tóm tắt như sau:
Hệ thống học giám sát sẽ phân tích một tập dữ liệu huấn luyện được gán nhãn, bao gồm các cặp (đặc tính, nhãn) như {(x1, y1), (x2, y2), , (xn, yn)} Mục tiêu chính là dự đoán nhãn y cho bất kỳ đầu vào mới với đặc tính x Trong học có giám sát, nếu y thuộc tập số thực ℝ thì nhiệm vụ được gọi là hồi quy, còn nếu y có các giá trị rời rạc thì là phân lớp Để giải quyết bài toán học có giám sát, cần thực hiện các bước cụ thể.
1 Xác định loại dữ liệu huấn luyện: Đầu tiên ta nên xác định xem loại dữ liệu nào sẽ đƣợc sử dụng làm dữ liệu huấn luyện Chúng có thể là dữ liệu liên tục hay dữ liệu rời rạc, hoặc một dạng đặt biệt nào đó
2 Xây dựng tập dữ liệu huấn luyện: Việc thu thập để tạo nên tập dữ liệu huấn luyện là quan trọng vì nó sẽ phục vụ cho việc sử dụng hàm huấn luyện f Dữ liệu huấn luyện có thể thu thập đƣợc từ nhiều nguồn khác nhau: dữ liệu đầu vào, số liệu đo đạc, tri thức hay kinh nghiệm của các chuyên gia lĩnh vực,…
3 Biễu diễn các đặc trƣng đầu vào: Sự chính xác của hàm chức năng phụ thuộc lớn vào cách các đối tượng đầu vào được biểu diễn Thông thường, đối tượng đầu vào đƣợc chuyển đổi thành một vec-tơ đặc trƣng, chứa một số các đặc trƣng nhằm mô tả cho đối tƣợng đó Số lƣợng các đặc trƣng không nên quá lớn nhƣng phải đủ lớn để việc dự đoán đầu ra đƣợc chính xác
4 Xác định cấu trúc của hàm chức năng cần tìm và giải thuật học tương ứng
Ví dụ, có thể lựa chọn việc sử dụng giải thuật K-láng giềng gần nhất hay giải thuật cây quyết định,…
5 Hoàn thiện thiết kế Người kĩ sư sẽ chạy giải thuật học từ tập huấn luyện thu thập đƣợc Các tham số của giải thuật học có thể đƣợc điều chỉnh bằng cách tối ƣu hóa hiệu năng trên một tập con (gọi là tập kiểm chứng -validation set) của tập huấn luyện, hay thông qua kiểm chứng chéo (cross-validation) Sau khi học và điều chỉnh tham số, hiệu năng của giải thuật có thể đƣợc đo đạc trên một tập kiểm tra độc lập với tập huấn luyện
Supervised learning algorithms include various methods such as Decision Trees, Support Vector Machines (SVM), k-Nearest Neighbors (k-NN), Maximum Entropy (MaxEnt), and Naive Bayes These techniques are essential for classification and regression tasks in machine learning, each offering unique advantages based on the data and problem context.
Học không giám sát là một phương pháp trong lĩnh vực học máy, nhằm tìm kiếm mô hình phù hợp với các quan sát mà không cần biết trước đầu ra đúng cho mỗi đầu vào Phương pháp này bắt đầu bằng việc thu thập một tập dữ liệu đầu vào, trong đó các đối tượng được coi như các biến ngẫu nhiên Sau đó, một mô hình mật độ kết hợp sẽ được xây dựng để phân tích tập dữ liệu đó.
Học không giám sát có thể kết hợp với suy diễn Bayes để tính toán xác suất có điều kiện cho bất kỳ biến ngẫu nhiên nào, dựa trên thông tin về các biến khác.
Học không giám sát đóng vai trò quan trọng trong việc nén dữ liệu, vì hầu hết các thuật toán nén đều dựa vào phân bố xác suất của tập đầu vào, dù là theo cách tường minh hay không tường minh.
Phân cụm dữ liệu là một ứng dụng quan trọng của học không giám sát, đóng vai trò then chốt trong việc tìm kiếm cấu trúc trong các tập dữ liệu không có nhãn Việc phân cụm giúp xác định các nhóm dữ liệu tương đồng, từ đó hỗ trợ trong việc phân tích và hiểu rõ hơn về thông tin tiềm ẩn trong dữ liệu.
Phân cụm là quá trình tổ chức các đối tượng dữ liệu thành các nhóm dựa trên sự tương đồng giữa chúng Mỗi cụm bao gồm những đối tượng có điểm chung, trong khi khác biệt với các đối tượng thuộc về các cụm khác.
Hình 1.1: Phương pháp phân cụm dữ liệu
Trong ví dụ này, chúng ta dễ dàng nhận diện 4 cụm dữ liệu được phân chia Tiêu chí chung là “khoảng cách”, trong đó hai hay nhiều đối tượng thuộc về cùng một cụm nếu chúng gần nhau hơn theo khoảng cách đã xác định Đây là phương pháp phân cụm dựa trên khoảng cách.
Phân cụm khái niệm là một hình thức phân cụm, trong đó hai hoặc nhiều đối tượng được xếp vào cùng một nhóm khi chúng chia sẻ một khái niệm chung Điều này có nghĩa là các đối tượng sẽ được tổ chức lại dựa trên các tiêu chí mô tả chung, giúp dễ dàng nhận diện và phân loại chúng.
Mục đích của phân cụm dữ liệu
Một số phương pháp học nửa giám sát
1.3.1 Phương pháp tự huấn luyện
Tự huấn luyện (Self-training) là một phương pháp học nửa giám sát phổ biến từ những năm 1960 đến 1970 Phương pháp này bắt đầu với một bộ phân lớp ban đầu được huấn luyện trên một lượng nhỏ dữ liệu đã gán nhãn Sau đó, bộ phân lớp sẽ phân loại các dữ liệu chưa gán nhãn, và các điểm chưa gán nhãn cùng với nhãn dự đoán sẽ được thêm vào tập dữ liệu huấn luyện Bộ phân lớp sẽ được huấn luyện lại, và quá trình này lặp lại, trong đó bộ phân lớp tự sử dụng dự đoán của mình để cải thiện khả năng phân loại Quá trình này còn được gọi là self-teaching hay bootstrapping.
Thuật toán Self-training: Đầu vào : - Tập dữ liệu đã gán nhãn {(x i , y i )} ℓ i=1
- Tập dữ liệu chƣa gán nhãn {(x j )} ℓ+u j= ℓ+1
3 Huấn luyện f từ tập L sử dụng một phương pháp học có giám sát
4 Dự đoán nhãn cho các phần tử x ∈ U
5 Bỏ đi tập con S từ tập U chứa các dữ liệu vừa đƣợc gán nhãn, đồng thời thêm vào tập L các mẫu dữ liệu này và nhãn của chúng (thêm {(x, f(x))| xϵS} vào L) Ƣu điểm:
- Là phương pháp học nửa giám sát đơn giản nhất
- Được xem như là phương pháp “Bao trùm” (Wrapper), áp dụng cho các bộ phân lớp sẵn có
- Thường được ứng dụng trong thực tế vào việc xử lý ngôn ngữ tự nhiên, phân lớp văn bản,… Độ phức tạp của thuật toán
Giả sử dữ liệu đầu vào bao gồm:
Trong bài viết này, chúng ta xem xét các khái niệm cơ bản về dữ liệu trong thuật toán tự huấn luyện, bao gồm số lượng dữ liệu đã gán nhãn (ℓ) và số lượng dữ liệu chưa gán nhãn (u), với điều kiện u ≫ ℓ Tổng số lượng dữ liệu được tính bằng n = ℓ + u Độ phức tạp của thuật toán tự huấn luyện phụ thuộc vào việc đánh giá quá trình lặp ở bước 2.
- Huấn luyện f từ tập L sử dụng một phương pháp học có giám sát
- Dự đoán nhãn cho các phần tử x ∈ U
Bỏ tập con S từ tập U với các dữ liệu đã được gán nhãn, đồng thời thêm vào tập L các mẫu dữ liệu này cùng nhãn của chúng, cụ thể là thêm {(x, f(x)) | x ∈ S} vào tập L.
- Thuật toán thực hiện số vòng lặp nhiều nhất có thể là: u vòng lặp Trong đó:
Vòng lặp thứ nhất có độ phức tạp: O (ℓ)
Vòng lặp thứ hai có độ phức tạp là: O (ℓ + 1)
Vòng lặp thứ u có độ phức tạp là: O (ℓ+u−1)
Do đó thuật toán có độ phức tạp là:
1.3.2 Phương pháp đồng huấn luyện Đồng huấn luyện (Co-training) là một kỹ thuật học nửa giám sát yêu cầu hai Khung nhìn dữ liệu (View) Nó giả sử rằng mỗi mẫu dữ liệu đƣợc mô tả bằng cách sử dụng hai bộ đặc tính khác nhau, đƣợc cung cấp khác nhau, bổ sung thông tin về mẫu dữ liệu đó Lý tưởng nhất, hai khung nhìn được xem là điều kiện độc lập (ví dụ: hai bộ đặc tính của mỗi mẫu dữ liệu là điều kiện độc lập để đƣa ra phân lớp của chúng) và mỗi khung nhìn là đủ (ví dụ: phân lớp của một mẫu dữ liệu có thể đƣợc dự đoán chính xác từ mỗi khung nhìn độc lập) Co-training ban đầu học một bộ phân lớp riêng cho mỗi khung nhìn, sử dụng bất kỳ mẫu dữ liệu đã gán nhãn nào Những dự đoán gần đúng nhất của mỗi bộ phân lớp trên các dữ liệu chƣa gán nhãn sau đó đƣợc sử dụng lặp đi lặp lại để xây dựng thêm các dữ liệu đƣợc gán nhãn[9]
Giả sử các dữ liệu đƣa ra đã đƣợc gán nhãn nhƣ sau:
- Dữ liệu đã gán nhãn : (x 1, y 1 ), , (x ℓ, y ℓ )
- Dữ liệu chƣa gán nhãn : xℓ+1, , x ℓ+u
Giả sử véc tơ đặc trƣng X có thể đƣợc chia thành hai Khung nhìn (View) nhƣ sau:
Huấn luyện hai bộ học cơ bản f (1) : x (1) ⟼y và f (2) : x (2) ⟼y Đầu tiên, học từ các dữ liệu đã gán nhãn: o f (1) học trên (x (1) 1, y 1 ), , (x (1) ℓ, y ℓ ) o f (2) học trên (x (2) 1, y 1 ), , (x (2) ℓ, y ℓ )
Sau khi sử dụng lặp lại các dữ liệu chưa gán nhãn, phương pháp o f (1) sẽ phân lớp các điểm chưa gán nhãn, chủ yếu là những điểm rỗng Tiếp theo, o f (1) sẽ thêm điểm này vào tập các nhãn của f (2) Quá trình này sẽ tiếp tục lặp lại như f (1) cho đến khi tất cả dữ liệu được gán nhãn hoàn toàn.
Phương pháp Co-training có nhiều ưu điểm nổi bật, bao gồm tính đơn giản và khả năng áp dụng rộng rãi cho hầu hết các bộ phân lớp hiện nay Đặc biệt, phương pháp này ít xảy ra lỗi hơn so với phương pháp Self-training, mang lại hiệu quả cao hơn trong quá trình huấn luyện mô hình.
Phương pháp Co-training có một số nhược điểm, bao gồm khả năng tồn tại hoặc không tồn tại của các Khung nhìn được chia tách Hơn nữa, việc sử dụng cả hai Khung nhìn trong mô hình có thể mang lại hiệu quả tốt hơn.
Ví dụ về phân lớp trang web với phương pháp Co-training
Co-training là một phương pháp hiệu quả để phân lớp các trang web thông qua văn bản trên các trang, như một Khung nhìn Bằng cách đặt văn bản trong các siêu liên kết, nó có thể cung cấp thông tin về trang web mà liên kết đến Phương pháp này có khả năng hoạt động trên các văn bản chưa được gán nhãn, thường thấy trên các trang web và email Các đặc trưng mô tả một trang web bao gồm từ ngữ trên trang và các liên kết dẫn đến trang đó Mô hình Co-training kết hợp hai bộ phân lớp để xác định xem trang web có chứa dữ liệu liên quan đến tiêu chí tìm kiếm hay không, đồng thời đánh giá sự phù hợp của bộ phân lớp thông qua văn bản trên các trang web.
Bài toán đặt ra là huấn luyện một chương trình để xác định các trang web có đặc điểm tương tự trong một tập hợp, nhưng chi phí gán nhãn cho các trang web là rất cao Do đó, chúng ta chỉ có thể gán nhãn cho một số trang nhất định và tận dụng dữ liệu chưa được gán nhãn để hỗ trợ cho việc gán nhãn các trang tiếp theo.
Với bài toán này, phương pháp Co-training có 2 bộ học sử dụng 2 Khung nhìn của dữ liệu đã gán nhãn và chƣa gán nhãn
Hai Khung nhìn của dữ liệu nhƣ sau: Phần văn bản (Page text) và Phần liên kết (Link)
Hình 1.2: Khung nhìn dữ liệu giữa văn bản và liên kết
Hình 1.3: Dữ liệu được học theo phương pháp Co-training
1.3.3 Phương pháp Máy véc tơ hỗ trợ truyền dẫn Để đề cập đến phương pháp máy véc tơ hỗ trợ truyền dẫn (Transductive Support Vector Machine-TSVM) trước hết ta xem xét phương pháp Máy véc tơ hỗ trợ (Support Vector Machines -SVM) Phương pháp SVM là một phương pháp phân lớp nhị phân, ra đời từ lý thuyết học thống kê, do Vapnik và Chervonenkis xây dựng Phương pháp SVM có nhiều ứng dụng trong thực tế với các bài toán phân lớp như: nhận dạng văn bản, nhận dạng chữ viết tay, phát hiện mặt người trong các ảnh và ƣớc lƣợng hồi quy, [8]
Phương pháp SVM (Máy Vector Hỗ Trợ) xây dựng các siêu mặt phẳng trong không gian nhiều chiều để phân loại dữ liệu Để đạt được độ chính xác cao nhất, các siêu mặt phẳng cần nằm càng xa các điểm dữ liệu của các lớp khác nhau càng tốt Điều này có nghĩa là lề (margin) càng lớn sẽ dẫn đến sai số tổng quát của thuật toán phân loại càng nhỏ.
Thuật toán phân lớp tuyến tính nhận diện lớp của một điểm dữ liệu mới dựa trên các điểm dữ liệu đã được gán nhãn thuộc hai lớp khác nhau (lớp −1 và lớp +1) Mỗi điểm dữ liệu được biểu diễn dưới dạng vector d chiều, và mục tiêu là xác định xem có thể phân chia hai lớp bằng một siêu phẳng d – 1 chiều hay không Trong số các siêu phẳng có thể phân lớp dữ liệu, chúng ta tập trung vào siêu phẳng có lề cực đại giữa hai lớp, gọi là Maximum margin.
Hình 1.4: Phương pháp Máy véc tơ hỗ trợ Giả sử, cho tập dữ liệu huấn luyện T gồm n phần tử có dạng sau:
Trong bài viết này, chúng ta xác định lớp của từng điểm x_i với giá trị y_i là -1 hoặc +1 Mỗi x_i được biểu diễn dưới dạng một vectơ thực trong không gian d chiều Mục tiêu là tìm siêu phẳng có lề cực đại để phân tách các điểm với y_i = -1 và y_i = 1.
Mỗi siêu phẳng có thể được biểu diễn bằng tập hợp các điểm x thỏa mãn phương trình w.x − b = 0, trong đó w là vectơ pháp tuyến của siêu phẳng và dấu chấm (.) biểu thị cho tích vô hướng.
Tham số xác định khoảng cách giữa gốc tọa độ và siêu phẳng theo hướng vectơ pháp tuyến của w
Kết luận
Trong chương này, chúng ta đã khám phá tổng quan về học có giám sát, học không giám sát và học nửa giám sát, đồng thời nghiên cứu các phương pháp học nửa giám sát phổ biến như Self-training, Co-training, TSVM và Graph-based Mỗi phương pháp có ứng dụng riêng, vì vậy cần xác định yêu cầu bài toán để chọn phương pháp phù hợp; ví dụ, phương pháp EM với mô hình sinh hỗn hợp là tối ưu cho việc tạo cụm dữ liệu, trong khi Co-training thích hợp khi đặc trưng dữ liệu được chia thành hai khung nhìn Nếu hai điểm dữ liệu có tính năng giống nhau có xu hướng thuộc cùng một lớp, phương pháp Graph-based sẽ được áp dụng TSVM là sự mở rộng của SVM, còn Self-training là lựa chọn cho các bộ phân lớp có giám sát phức tạp và khó thay đổi Tiếp theo, chúng ta sẽ tập trung vào nghiên cứu phương pháp dựa trên đồ thị (Graph-based) và các thuật toán phân lớp liên quan.
PHƯƠNG PHÁP HỌC NỬA GIÁM SÁT DỰA TRÊN ĐỒ THỊ
Giới thiệu
Dữ liệu đã gán nhãn là rất quan trọng cho học có giám sát, nhưng thường có số lượng hạn chế, trong khi dữ liệu chưa được gán nhãn lại phong phú Việc kết hợp dữ liệu chưa gán nhãn với dữ liệu đã gán nhãn đang thu hút sự chú ý trong cả lý thuyết và thực tiễn Nhiều phương pháp hiện nay đã được đề xuất, tương tự như phương pháp K-Nearest Neighbor (kNN) trong học có giám sát truyền thống, với giả định rằng các điểm dữ liệu gần nhau có xu hướng mang cùng một nhãn Những phương pháp này giúp lan truyền các nhãn qua các vùng dữ liệu dày đặc chưa được gán nhãn.
Gần đây, phương pháp học nửa giám sát dựa trên đồ thị đã thu hút sự quan tâm lớn từ các nhà nghiên cứu Phương pháp này sử dụng một đồ thị với các đỉnh là điểm dữ liệu đã được gán nhãn và chưa gán nhãn, trong đó các cạnh thể hiện sự tương tự giữa các đỉnh Khi các đỉnh được kết nối bằng cạnh có trọng số lớn, chúng có xu hướng mang cùng nhãn, cho phép các nhãn lan truyền trong đồ thị Phương pháp dựa trên đồ thị còn kế thừa nhiều đặc tính ưu việt từ lý thuyết quang phổ đồ thị.
Hình 2.1: Phương pháp dựa trên đồ thị
Trước khi đi vào việc học trên đồ thị, đầu tiên ta cần tìm hiểu một số định nghĩa liên quan trong đồ thị
Cấu trúc của đồ thị
Các thuật toán trong phương pháp học nửa giám sát dựa trên đồ thị đều có tư tưởng tương đồng, và điều quan trọng nhất là xây dựng một đồ thị chất lượng, hơn là việc lựa chọn thuật toán cụ thể nào trong số đó.
Đồ thị G = (V, E) bao gồm n đỉnh, với V là tập hợp các đỉnh và E là tập hợp các cạnh Đồ thị này được biểu diễn bằng ma trận liền kề W, trong đó giá trị wij > 0 thể hiện sự tồn tại của cạnh giữa đỉnh i và đỉnh j, còn w ij = 0 trong các trường hợp không có cạnh nối Đối với các cạnh thuộc chu trình, chúng sẽ không được tính và được gán w ij = 0 Trong trường hợp đồ thị có hướng, tổng bậc đầu ra của đỉnh i được ký hiệu là w i+ và tổng bậc đầu vào là w +i.
Tổng trọng số của đồ thị được ký hiệu là w, với giả định rằng không có đỉnh nào bị cô lập, tức là w+i > 0 và w i+ > 0 Trong trường hợp đồ thị không có trọng số, trọng số wij chỉ có thể nhận giá trị 0 hoặc 1 Đối với đồ thị vô hướng, tổng bậc đầu vào và đầu ra, được ký hiệu là di (= w i+ = w +i), được xem như một thuộc tính quan trọng để nhấn mạnh.
W ij thường được hiểu một cách tự nhiên, có thể biểu thị số lượng siêu liên kết từ một trang web đến các trang khác hoặc là giá trị nhị phân cho thấy protein i tương tác với protein j.
Khi không có trọng số từ dữ liệu, quá trình xây dựng chúng thường bao gồm hai bước Đầu tiên, sử dụng hàm không âm và đối xứng để đo lường mối quan hệ giữa các cặp đỉnh, ví dụ như hàm mật độ Gaussian a(i, j) = exp (−||x i −xj||² / 2σ²) trong không gian Euclidean ℝ d Tiếp theo, trọng số wij được xác định dựa trên mối quan hệ a(i, j) giữa các cặp Phương pháp ε-láng giềng đặt w ij = a(i, j) nếu a(i, j) > ε, ngược lại w ij = 0 Trong khi đó, phương pháp k-láng giềng gần nhất gán w ij = a(i, j) nếu j là một trong các láng giềng gần nhất của i, và w ij = 0 trong các trường hợp còn lại Như vậy, đồ thị được xây dựng với trọng số cạnh dựa trên phương pháp xác định trọng số trong không gian Euclidean.
Các loại đồ thị phổ biến có thể sử dụng trong học nửa giám sát
Đôi khi, dữ liệu mà chúng ta thu thập có thể bị hạn chế về miền tri thức, và để giải quyết vấn đề này, cần xây dựng một đồ thị Dưới đây là một số phương pháp phổ biến để tạo ra đồ thị phục vụ cho các thuật toán học nửa giám sát.
2.2.1 Đồ thị kết nối đầy đủ
Đồ thị kết nối đầy đủ là loại đồ thị mà mỗi cặp đỉnh đều có một cạnh nối, với các đỉnh tương tự có trọng số cạnh lớn hơn Ưu điểm của loại đồ thị này là khả năng học trọng số hiệu quả thông qua các hàm trọng số khác nhau, giúp dễ dàng tạo ra các dẫn xuất và trọng số tham số Tuy nhiên, nhược điểm lớn nhất của đồ thị kết nối đầy đủ là chi phí tính toán cao do sự hiện diện của cạnh nối giữa tất cả các đỉnh.
Đồ thị rời rạc, hay còn gọi là đồ thị NN hoặc εNN, là loại đồ thị mà mỗi đỉnh chỉ kết nối với một số đỉnh nhất định, giúp tính toán nhanh chóng và mang lại hiệu suất cao Tuy nhiên, một vấn đề cần lưu ý là sự giả lập kết nối giữa các đỉnh không đồng nhất, dẫn đến việc bỏ qua các mối liên hệ khác lớp Trong đồ thị rời rạc, các cạnh có thể được đánh trọng số hoặc không, nhưng nhược điểm của nó là khi thay đổi trọng số, các láng giềng của các đỉnh cũng sẽ bị thay đổi.
2.2.3 Đồ thị -láng giềng gần nhất
Đồ thị -láng giềng gần nhất là loại đồ thị trong đó hai đỉnh i và j được kết nối nếu đỉnh i nằm trong k láng giềng gần nhất của đỉnh j, với k là siêu tham số điều khiển mật độ của đồ thị Đặc điểm mở rộng của đồ thị -NN cho phép bán kính láng giềng thay đổi tùy thuộc vào các vùng dữ liệu có mật độ cao hoặc thấp Số lượng láng giềng nhỏ có thể xuất phát từ việc đồ thị không liên thông, nhưng với phương pháp lan truyền nhãn, điều này không gây ra vấn đề lớn nếu mỗi thành phần kết nối có một số điểm dữ liệu đã được gán nhãn.
Nhược điểm của phương pháp -NN là không thể mở rộng và kết quả trong đồ thị không đối xứng
2.2.4 Đồ thị -láng giềng gần nhất Đồ thị ε-láng giềng gần nhất là đồ thị trong đó đỉnh i và đỉnh j đƣợc kết nối bởi một cạnh nếu khoảng cách d(i, j) ≤ ε Siêu tham số ε quyết định bán kính của các láng giềng Mặc dù ε mang giá trị liên tục, việc tìm kiếm giá trị tối ƣu là rời rạc với hầu hết giá trị độ dài các cạnh O(n 2 )
2.2.5 Đồ thị trọng số exp
Hàm trọng số cạnh giữa hai đỉnh của đồ thị được định nghĩa là w_ij = exp(−d(i, j)²/α²), rất hữu ích trong trường hợp thiếu miền tri thức Tuy nhiên, đồ thị trọng số -NN với số lượng nhỏ thường cho kết quả tốt hơn theo kinh nghiệm Tất cả các phương pháp xây dựng đồ thị đều có các siêu tham số riêng Đồ thị này được biểu diễn qua ma trận trọng số Wn×n, trong đó W_ij = 0 nếu không có cạnh nối giữa đỉnh i và j Ma trận trọng số W cần phải chứa các giá trị không âm và đảm bảo tính đối xứng.
Các phương pháp xác định khoảng cách giữa các điểm dữ liệu
Trong phần trước, chúng ta đã khám phá các loại đồ thị hỗ trợ quá trình học, được tạo thành từ các điểm dữ liệu hay đối tượng dữ liệu Những đối tượng này có thể được mô tả qua nhiều chiều khác nhau, như miền rời rạc và miền liên tục Phương pháp học nửa giám sát dựa trên đồ thị chủ yếu phụ thuộc vào khoảng cách giữa các điểm trên đồ thị.
Trước khi khám phá các thuật toán học máy cụ thể, việc lựa chọn hàm xác định khoảng cách là rất quan trọng Dưới đây, chúng ta sẽ tìm hiểu một số hàm xác định khoảng cách phổ biến.
Giả sử mỗi đối tƣợng đƣợc mô tả bởi các thuộc tính có dạng nhƣ sau: : {A 1 = a 1 , A 2 = a 2 , …, An = a n } Hàm khoảng cách giữa hai đối tƣợng và q ký hiệu là: d( , q)
2.3.1 Khoảng cách cục bộ, khoảng cách toàn cục và trọng số
Hàm khoảng cách toàn cục có thể được xác định bằng cách kết hợp một số hàm khoảng cách cục bộ, dist A, trên từng thuộc tính của nó Phương pháp đơn giản nhất để thực hiện việc này là tính tổng các hàm khoảng cách cục bộ.
Khoảng cách toàn cục được định nghĩa là tổng trọng số của các khoảng cách cục bộ, trong đó các trọng số \( w_i \) cho phép xác định tầm quan trọng khác nhau của các thuộc tính trong việc tính toán khoảng cách tổng thể Các trọng số này thường nằm trong khoảng từ 0 đến 1, với trọng số bằng 0 chỉ ra rằng thuộc tính đó hoàn toàn không liên quan.
Trọng số trung bình thường là:
Các trọng số có thể đƣợc đƣa ra bởi các nhà thiết kế hệ thống Ngoài ra còn có các trọng số học từ một tập dữ liệu
Hàm khoảng cách cục bộ đơn giản nhất, được gọi là hàm nạp chồng, trả về giá trị 0 khi hai giá trị bằng nhau và 1 trong các trường hợp khác.
Hàm khoảng cách toàn cục được xác định là tổng của các hàm khoảng cách cục bộ, cho phép đếm số lượng thuộc tính mà hai trường hợp không giống nhau Khái niệm này được biết đến với tên gọi khoảng cách Hamming Ngoài ra, tổng trọng số và trọng số trung bình cũng có thể được áp dụng trong việc tính toán khoảng cách.
2.3.3 Khoảng cách Manhattan cho các thuộc tính số học
Nếu thuộc tính là thuộc tính số học, hàm khoảng cách cục bộ được định nghĩa là độ chênh lệch tuyệt đối giữa các giá trị.
Nếu khoảng cách toàn cục đƣợc tính bằng tổng của các khoảng cách cục bộ này thì chúng ta đề cập tới khoảng cách Manhattan
Tổng trọng số và trọng số trung bình cũng có thể xảy ra
Một nhược điểm của khoảng cách Manhattan là khi một thuộc tính có miền giá trị lớn, nó có thể chi phối các thuộc tính khác.
Khoảng cách cục bộ thường được chuẩn hóa trong phạm vi từ 0 đến 1 Có nhiều phương pháp để thực hiện việc chuẩn hóa này, nhưng trong bài viết này, chúng ta sẽ chỉ xem xét một công thức đơn giản Chúng ta sẽ chia miền giá trị chấp nhận được để dễ dàng áp dụng.
Trong đó, A max là giá trị lớn nhất có thể của A và A min là giá trị nhỏ nhất có thể của
A Chúng ta gọi là khoảng cách đã đƣợc chuẩn hóa
Một nhược điểm nữa của ý tưởng này là nó chỉ có thể được sử dụng trên các thuộc tính số học
2.3.4 Các hàm khoảng cách cục bộ không đồng nhất
Chúng ta có thể kết hợp khoảng cách tuyệt đối và độ trùng khớp để xử lý cả hai thuộc tính số và thuộc tính ký hiệu (symbolic):
Khoảng cách toàn cục ở đây có thể đƣợc tính bằng tổng trọng số hoặc trọng số trung bình của khoảng cách cục bộ
2.3.5 Hàm khoảng cách tri thức chuyên gia
Các chuyên gia có khả năng xác định miền đặc biệt cho hàm khoảng cách cục bộ, đặc biệt là đối với các giá trị-ký hiệu của các thuộc tính.
Một ví dụ không phổ biến là việc định nghĩa các giá trị thuộc tính ký hiệu, như trong trường hợp bữa ăn cuối cùng mà một người đã ăn Các giá trị có thể là: không ăn gì, ăn nhanh và ăn đầy đủ, được sắp xếp theo thứ tự tiêu thụ thức ăn: không ăn gì < ăn nhanh < ăn đầy đủ.
Chúng ta có thể phân loại các giá trị số nguyên theo ba mức độ: không ăn gì tương ứng với giá trị 0, ăn nhanh với giá trị 1, và ăn đầy đủ với giá trị 2 Sử dụng công thức này, chúng ta có thể áp dụng các giá trị để phân tích hành vi ăn uống.
Nhƣ vậy, chúng ta đã tìm hiểu một số hàm xác định khoảng cách giữa các điểm dữ liệu với các miền thuộc tính khác nhau
Thuật toán lan truyền nhãn trên đồ thị (Label Propagation) hoạt động bằng cách truyền nhãn từ các đỉnh đã gán nhãn tới các đỉnh láng giềng dựa vào mối quan hệ gần gũi giữa chúng Trong quá trình này, các nhãn trên tập dữ liệu đã được gán nhãn sẽ được cố định, coi như một nguồn thông tin, để từ đó xác định các nhãn cho dữ liệu chưa được gán nhãn.
Thuật toán lan truyền nhãn trong đồ thị
Hình 2.7: Đồ thị với các trọng số cạnh Cho đồ thị G = (V, E, W), trong đó:
- W: Ma trận trọng số các cạnh tính theo công thức Euclid (Wn×n)
n ℓ : số đỉnh đã đƣợc gán nhãn
n : số đỉnh chƣa đƣợc gán nhãn
- C: tập các nhãn, thể hiện số lƣợng các nhãn, với |C|=m
- P: Ma trận xác suất chuyển đổi nhãn, P n×n
- Y: ma trận nhãn ban đầu Yℓ×C
Ma trận f n×m lưu trữ thông tin về các nhãn của đỉnh trong quá trình huấn luyện Phương pháp học nửa giám sát với đồ thị sẽ tính toán ma trận f dựa trên các ma trận P và Y.
Cho tập dữ liệu đã gán nhãn {(x₁, y₁), …, (xℓ, yℓ)} với Yₗ = {y₁, …, yℓ} là các nhãn lớp, trong đó y = {1 C} và tập dữ liệu chưa gán nhãn {xℓ+1, …, xℓ+u} thường có ℓ ≪ u Tổng số dữ liệu n = ℓ + u, với L và U lần lượt biểu thị cho tập dữ liệu đã gán nhãn và chưa gán nhãn Giả sử số lượng lớp C đã biết và tất cả các lớp đã có mặt trong dữ liệu đã gán nhãn, chúng ta sẽ nghiên cứu bài toán lan truyền nhằm tìm kiếm các nhãn cho tập U.
Theo trực giác, chúng ta mong muốn rằng các điểm dữ liệu tương tự sẽ có nhãn giống nhau Để thực hiện điều này, chúng ta xây dựng một đồ thị đầy đủ với các đỉnh đại diện cho tất cả các điểm dữ liệu, bao gồm cả những điểm đã được gán nhãn và chưa gán nhãn Mỗi cạnh nối giữa các đỉnh i và j thể hiện mức độ tương đồng giữa chúng Giả sử đồ thị này là đầy đủ và có các trọng số được điều chỉnh bởi một tham số cụ thể.
Trong đó: d ij là khoảng cách giữa điểm dữ liệu x i và x j
Có nhiều phương pháp để tính toán giá trị khoảng cách, nhưng cách tính phù hợp nhất là khi x là các giá trị rời rạc Trong bài viết này, chúng tôi lựa chọn khoảng cách Euclid để xác định khoảng cách giữa các điểm dữ liệu, đồng thời điều chỉnh theo các giá trị siêu tham số cho từng chiều thuộc tính.
Tất cả các đỉnh có nhãn mềm có thể thay đổi nhãn trong quá trình thực hiện việc lan truyền nhãn và đƣợc hiểu là phân phối nhãn
Chúng ta phân phối nhãn từ một đỉnh lan truyền tới tất cả các đỉnh khác qua các cạnh kết nối Các cạnh có trọng số cao hơn giúp cho việc truyền nhãn diễn ra dễ dàng hơn Để mô tả quá trình này, ta định nghĩa một Ma trận xác suất chuyển đổi P có kích thước n×n.
Trong đó, P_ij đại diện cho xác suất chuyển từ đỉnh i sang đỉnh j Đồng thời, chúng ta cũng định nghĩa một ma trận nhãn Y có kích thước L×C, trong đó dòng thứ i chứa một vector chỉ số cho y_i, với i thuộc tập L: Y_ic = δ(y_i, c).
Chúng ta sẽ tính toán nhãn mềm f cho các đỉnh, trong đó f là ma trận n × C, với các hàng thể hiện phân bổ xác suất trên các nhãn Việc khởi tạo giá trị ban đầu cho f không quan trọng Tiếp theo, chúng ta sẽ xem xét thuật toán.
Thuật toán này nhận đầu vào là một đồ thị vô hướng, bao gồm các đỉnh đã được gán nhãn và các đỉnh chưa gán nhãn Kết quả đầu ra của thuật toán sẽ là một đồ thị vô hướng, trong đó tất cả các đỉnh đã được gán nhãn.
Thuật toán lan truyền nhãn thực hiện theo các bước sau:
Bước 2 Gán (giữ lại) các dữ liệu đã gán nhãn f L = Y L (Y L đã xây dựng ở trên)
Bước 3 Lặp lại từ bước 1 cho tới khi f hội tụ
Trong bước đầu tiên, tất cả các đỉnh sẽ truyền các nhãn đến các láng giềng của chúng Bước thứ hai rất quan trọng, vì chúng ta cần giữ lại các nhãn từ dữ liệu đã được gán nhãn Thay vì làm mờ các nhãn, chúng ta sẽ giữ chúng lại trong ma trận.
Với sự hỗ trợ từ các đỉnh đã được gán nhãn, các lớp biên có thể được phân loại dựa trên các vùng có tỉ trọng cao và thấp.
2.4.3 Sự hội tụ của thuật toán
Bây giờ ta thể hiện sự hội tụ của thuật toán tới một lời giải đơn giản
Vì f L được gán bằng Y L, chúng ta chỉ cần tập trung vào f U, là ma trận của các phần tử chưa được gán nhãn Mục tiêu của chúng ta là xác định ma trận f U này.
Chia ma trận P thành ma trận con đã gán nhãn và ma trận con chƣa gán nhãn, có dạng:
Theo công thức ở trên, thuật toán có thể đƣợc mô tả nhƣ sau :
Trong đó, f 0 U là giá trị khởi tạo ban đầu của fU Chúng ta cần cho thấy
Vì P có các hàng bình thường và P UU là ma trận con của P, dẫn đến:
Do đó tổng các hàng của (PUU) n hội tụ về 0 Điều này có nghĩa rằng
Do đó giá trị khởi tạo của f 0 U là không quan trọng Mà f U =(I−P UU ) −1 P UL Y L là cố định
Điểm cố định duy nhất là lời giải cho việc lặp lại thuật toán, cho phép chúng ta giải quyết bài toán lan truyền nhãn một cách trực tiếp mà không cần phải lặp lại quá trình lan truyền.
Lưu ý rằng lời giải chỉ khả thi khi ma trận (1 - P UU) có thể được nghịch đảo Điều này sẽ được đảm bảo nếu mọi thành phần kết nối trong đồ thị đều có ít nhất một điểm dữ liệu được gán nhãn.
2.4.4 Phương pháp xác định siêu tham số của đồ thị
Các thuật toán học nửa giám sát đã chứng minh hiệu quả trong nhiều ứng dụng khi chỉ có một lượng nhỏ dữ liệu có nhãn, tận dụng các dữ liệu không có nhãn Tuy nhiên, chất lượng của đồ thị và siêu tham số của nó là yếu tố quan trọng ảnh hưởng đến hiệu suất của các thuật toán này.
Phương pháp học nửa giám sát dựa trên đồ thị tạo ra một cấu trúc đồ thị với các đỉnh đại diện cho dữ liệu có nhãn và chưa có nhãn Các cạnh trong đồ thị thể hiện mức độ tương đồng giữa các cặp điểm dữ liệu Quá trình phân lớp được thực hiện thông qua việc sử dụng đồ thị, trong đó các dữ liệu chưa có nhãn sẽ được gán nhãn tương ứng dựa trên việc các đỉnh kết nối với nhau qua các cạnh có trọng số lớn hơn, cho thấy sự tương đồng cao hơn.
Thuật toán học nửa giám sát dựa trên đồ thị - Mincut
Thuật toán Mincut là một phương pháp tìm kiếm cắt nhỏ nhất trên đồ thị, sử dụng mối quan hệ giữa các điểm dữ liệu để học từ cả dữ liệu có nhãn và không có nhãn Thuật toán này xây dựng đồ thị dựa trên độ đo tương tự giữa các điểm dữ liệu, từ đó phân loại dữ liệu bằng cách tối thiểu hóa số lượng cặp dữ liệu tương tự nhưng có nhãn khác nhau.
Bài toán đặt ra là sử dụng một tập dữ liệu có sẵn cả nhãn và không có nhãn để xây dựng một đồ thị Việc tìm kiếm lát cắt nhỏ nhất trên đồ thị này sẽ giúp chúng ta thực hiện việc gán nhãn nhị phân tối ưu cho các dữ liệu chưa được gán nhãn, dựa trên một hàm tối ưu nhất định.
Thuật toán Mincut kết hợp dữ liệu đã gán nhãn và chưa gán nhãn bằng cách gán giá trị cho dữ liệu chưa có nhãn nhằm tối ưu hóa một hàm mục tiêu Phương pháp này giới hạn hàm tối ưu chỉ phụ thuộc vào mối quan hệ giữa các cặp dữ liệu Điều đặc biệt của Mincut là khả năng xử lý các hàm và cung cấp thuật toán với thời gian đa thức để đạt được tối ưu hóa toàn cục.
Trong bài toán phân lớp nhị phân, dữ liệu đã gán nhãn được ký hiệu bằng dấu cộng (+), trong khi dữ liệu chưa gán nhãn được ký hiệu bằng dấu trừ (−) Tập hợp L đại diện cho các dữ liệu đã gán nhãn, và U là tập hợp các dữ liệu chưa gán nhãn Trong đó, L+ là tập hợp các dữ liệu có nhãn dương trong L, còn L− là tập hợp các dữ liệu có nhãn âm trong L.
Bước đầu tiên trong quá trình xây dựng mô hình là tạo ra một đồ thị trọng số G=(V, E), trong đó V bao gồm các đỉnh L, U và hai đỉnh phân lớp v+ và v− Các cạnh e trong đồ thị thuộc tập E và có trọng số w(e) Đỉnh v+ và v− được gọi là các đỉnh phân lớp, trong khi tất cả các đỉnh còn lại được gọi là các đỉnh mẫu.
Trong bước 2, các đỉnh phân lớp có nhãn giống nhau được kết nối thông qua các cạnh có trọng số vô hạn Cụ thể, trọng số w(v, v +) được thiết lập là vô hạn cho tất cả các đỉnh v thuộc lớp L +, và trọng số w(v, v −) cũng được đặt là vô hạn cho tất cả các đỉnh v thuộc lớp L −.
Bước 3 liên quan đến việc gán trọng số cho các cạnh nối giữa các đỉnh mẫu, dựa trên mối quan hệ giữa các mẫu dữ liệu, chẳng hạn như sự giống nhau hoặc khoảng cách Cách chọn các trọng số này sẽ được trình bày chi tiết trong phần sau Hàm gán trọng số cho các cạnh kết nối giữa các đỉnh dữ liệu được gọi là Hàm gán trọng số w.
Để xác định lát cắt nhỏ nhất (v+, v−) cho đồ thị, cần tìm tổng trọng số nhỏ nhất của các cạnh mà khi loại bỏ sẽ làm mất kết nối giữa các đỉnh v+ và v− Việc này có thể thực hiện bằng cách áp dụng một thuật toán thích hợp.
Luồng cực đại trong đồ thị được xác định bởi các đỉnh đầu v + và các đỉnh ẩn v −, trong đó trọng số cạnh được coi là capacities Khi loại bỏ các cạnh theo lát cắt, đồ thị sẽ được chia thành hai tập đỉnh V + và V −, với v + thuộc V + và v − thuộc V − Nếu có nhiều lát cắt, thuật toán sẽ chọn tập đỉnh V + nhỏ nhất.
Trong bước 5, chúng ta gán nhãn dương (+) cho tất cả các mẫu dữ liệu chưa có nhãn trong tập V +, đồng thời gán nhãn âm (−) cho tất cả các mẫu dữ liệu chưa có nhãn trong tập V −.
Trong thuật toán này, các điểm dữ liệu tương tự nhau sẽ được nhóm lại trong cùng một tập đỉnh nếu các cạnh nối giữa chúng có trọng số cao tương tự Điều này phù hợp với giả thiết cơ bản của nhiều thuật toán học máy, như láng giềng gần nhất, rằng các điểm dữ liệu tương tự có xu hướng được phân lớp giống nhau.
Chúng ta có thể đánh trọng số các cạnh bằng cách xác định “khoảng cách” giữa các điểm dữ liệu có nhãn giống nhau Hàm tính khoảng cách sẽ gán trọng số cao cho các cạnh nối các điểm gần nhau và trọng số thấp cho các cạnh nối các điểm xa nhau Nếu không có hàm tính khoảng cách ban đầu, chúng ta có thể sử dụng các điểm dữ liệu đã gán nhãn trong các thuật toán học trợ giúp để học một hàm khoảng cách Ví dụ, dữ liệu đã gán nhãn có thể được sử dụng để đánh trọng số cho các thuộc tính dựa trên thông tin hiện có Chúng ta cũng có thể đánh trọng số cho một cạnh (x, y) với x thuộc U dựa trên y thuộc L hoặc không Việc lựa chọn hàm đánh trọng số cạnh có thể ảnh hưởng đáng kể đến chất lượng đầu ra của thuật toán.
Các trường Gaussian ngẫu nhiên và các hàm điều hòa
2.6.1 Các trường Gaussian ngẫu nhiên
Một phương pháp tiếp cận trong học nửa giám sát là sử dụng mô hình Gaussian ngẫu nhiên (GRF), trong đó dữ liệu đã gán nhãn và chưa gán nhãn được biểu diễn như các đỉnh trong một đồ thị có trọng số Các cạnh giữa các mẫu dữ liệu tương tự được mã hóa bằng trọng số, cho phép xây dựng bài toán học trong các trường Gaussian ngẫu nhiên trên đồ thị Ý nghĩa của các trường này được xác định thông qua các hàm điều hòa, và hiệu quả được cải thiện bằng cách áp dụng các phương pháp ma trận hoặc lan truyền tin cậy.
Khác với các phương pháp học máy hiện nay dựa trên hàm năng lượng cực tiểu và các trường ngẫu nhiên, bài viết này tập trung vào việc sử dụng các trường Gaussian ngẫu nhiên trên không gian trạng thái liên tục Các trường này thường được đặc trưng bởi các hàm điều hòa và có thể được tính toán bằng các phương pháp ma trận hoặc lan truyền Trong khi đó, việc tính toán cấu hình năng lượng thấp nhất cho các trường ngẫu nhiên đa nhãn thường gặp khó khăn và cần sử dụng các thuật toán xấp xỉ Kết quả từ thuật toán phân lớp với các trường Gaussian có thể được xem như một phương pháp tiếp cận láng giềng gần nhất, trong đó các mẫu dữ liệu láng giềng được gán nhãn thông qua phương pháp Bước di chuyển trên đồ thị.
Ta giả sử có ℓ điểm đã đƣợc gán nhãn (x 1 , y 1 ), , (xℓ, yℓ) và u điểm chƣa gán nhãn x ℓ+1 , , x ℓ+u ; ℓ