6

Rất nhiều vấn đề phổ biến trong học máy liên quan đến việc phân loại các điểm dữ liệu bị cô lập độc lập với nhau. Chẳng hạn, đưa ra một hình ảnh, dự đoán xem nó có chứa một con mèo hay một con chó, hoặc đưa ra một hình ảnh của một nhân vật viết tay, dự đoán đó là chữ số nào từ 0 đến 9.

Nó chỉ ra rằng rất nhiều vấn đề không phù hợp với khung trên. Chẳng hạn, đưa ra một câu, tôi thích học máy, gắn thẻ từng từ với một phần của bài phát biểu (danh từ, đại từ, động từ, tính từ, v.v.). Ngay cả ví dụ đơn giản này chứng minh, nhiệm vụ này không thể được giải quyết bằng cách xử lý từng từ một cách độc lập - có thể là một danh từ hoặc một động từ tùy thuộc vào ngữ cảnh của nó. Nhiệm vụ này rất quan trọng đối với nhiều tác vụ phức tạp hơn trên văn bản, chẳng hạn như dịch từ ngôn ngữ này sang ngôn ngữ khác, văn bản sang lời nói, v.v.

Không rõ ràng về cách bạn sẽ sử dụng một mô hình phân loại tiêu chuẩn để xử lý các vấn đề này. Một khung mạnh mẽ có thể được sử dụng để tìm hiểu các mô hình như vậy với sự phụ thuộc là các mô hình đồ họa xác suất (PGM). Đối với bài đăng này, nhóm Statsbot đã yêu cầu một nhà khoa học dữ liệu, Prasoon Gidel, thực hiện một hướng dẫn về khung này cho chúng tôi.

Trước khi nói về cách áp dụng mô hình đồ họa xác suất cho vấn đề học máy, chúng ta cần hiểu khung PGM. Chính thức, một mô hình đồ họa xác suất (hay gọi tắt là mô hình đồ họa) bao gồm một cấu trúc đồ thị. Mỗi nút của biểu đồ được liên kết với một biến ngẫu nhiên và các cạnh trong biểu đồ được sử dụng để mã hóa quan hệ giữa các biến ngẫu nhiên.

Tùy thuộc vào việc đồ thị được định hướng hay không bị dẫn hướng, chúng ta có thể phân loại các chế độ đồ họa thành hai loại: mạng Bayes và mạng Markov.

Bayesian Networks: Các mô hình đồ họa được định hướng

Một ví dụ điển hình của các mạng Bayes là mạng được gọi là mạng sinh viên, có vẻ như thế này:

Biểu đồ này mô tả một thiết lập cho một sinh viên ghi danh vào một lớp học đại học. Có 5 biến ngẫu nhiên trong biểu đồ:

  1. Độ khó (của lớp): lấy các giá trị 0 (độ khó thấp) và 1 (độ khó cao).

  2. Thông minh (của học sinh): lấy các giá trị 0 (không thông minh) và 1 (thông minh).

  3. Lớp (học sinh được vào lớp): lấy các giá trị 1 (điểm kém), 2 (điểm trung bình) và 3 (điểm tốt).

  4. SAT (điểm của học sinh trong kỳ thi SAT): lấy các giá trị 0 (điểm thấp) và 1 (điểm cao).

  5. Thư (chất lượng thư giới thiệu mà sinh viên nhận được từ giáo sư sau khi hoàn thành khóa học): lấy các giá trị 0 (không phải là một chữ cái tốt) và 1 (một lá thư tốt).

Các cạnh trong biểu đồ mã hóa phụ thuộc trong biểu đồ.

  • Điểm số của học sinh ở cấp độ cao của học sinh phụ thuộc vào mức độ khó khăn của lớp học và mức độ thông minh của học sinh.
  • Đến lượt lớp, lớp, xác định xem học sinh có nhận được thư giới thiệu tốt từ giáo sư hay không.
  • Ngoài ra, nhóm Intelligence Intelligence của học sinh ảnh hưởng đến điểm số SAT SAT của họ, ngoài ra còn ảnh hưởng đến lớp học.

Lưu ý rằng hướng mũi tên cho chúng ta biết về mối quan hệ nguyên nhân - sự thông minh, ảnh hưởng đến điểm số SAT SAT, nhưng điểm số SAT SAT không ảnh hưởng đến Trí thông minh.

Cuối cùng, hãy xem các bảng được liên kết với mỗi nút. Chính thức, chúng được gọi là phân phối xác suất có điều kiện (CPDs).

Phân phối xác suất điều kiện

Các CPD dành cho khó khăn và các trí thông minh có thể khá đơn giản vì các biến này không phụ thuộc vào bất kỳ biến nào khác. Các bảng về cơ bản mã hóa xác suất của các biến này, lấy 0 hoặc 1 làm giá trị. Như bạn có thể nhận thấy, các giá trị trong mỗi bảng phải tổng bằng 1.

Tiếp theo, chúng ta hãy xem CPD cho SAT SAT. Mỗi hàng tương ứng với các giá trị mà cha mẹ của nó (Thông minh đối với) có thể lấy và mỗi cột tương ứng với các giá trị mà siêu SAT SAT có thể lấy. Mỗi ô có xác suất có điều kiện p (SAT = s | Intelligence = i), nghĩa là giá trị của Thông minh Trí là i, xác suất của giá trị của SAT SAT là s là bao nhiêu.

Chẳng hạn, chúng ta có thể thấy p (SAT = s¹ | Intelligence = i¹) là 0,8, nghĩa là nếu trí thông minh của học sinh cao, thì xác suất điểm SAT cũng cao là 0,8. Mặt khác, p (SAT = s⁰ | Intelligence = i¹), mã hóa thực tế là nếu trí thông minh của học sinh cao, thì xác suất điểm SAT thấp là 0,2.

Lưu ý rằng tổng các giá trị trong mỗi hàng là 1. Điều đó có ý nghĩa bởi vì nếu Intelligence = i¹, điểm SAT có thể là s⁰ hoặc s¹, do đó, hai xác suất phải cộng tới 1. Tương tự, CPD cho Triệu Thư mã hóa các xác suất có điều kiện p (Letter = l | Lớp = g). Bởi vì hạng Hạng có thể có ba giá trị, chúng tôi có ba hàng trong bảng này.

CPD cho hạng Hạng dễ hiểu với những kiến ​​thức trên. Bởi vì nó có hai cha mẹ, nên xác suất có điều kiện sẽ có dạng p (Lớp = g | Độ khó = d, SAT = s), nghĩa là xác suất của Hạng Hạng là g, với giá trị của Độ khó Đây là d và đó là của SAT SAT. Mỗi hàng bây giờ tương ứng với một cặp giá trị của Khó Khó và Thông minh. Một lần nữa, các giá trị hàng cộng lại thành 1.

Một yêu cầu thiết yếu cho các mạng Bayes là đồ thị phải là đồ thị theo chu kỳ có hướng (DAG).

Markov Networks: Mô hình đồ họa vô hướng

Đây là một ví dụ đơn giản về mạng Markov:

Vì lợi ích của sự ngắn gọn, chúng ta sẽ xem xét biểu đồ trừu tượng này, trong đó các nút A, B, v.v. không tương ứng trực tiếp với số lượng trong thế giới thực, như trên. Một lần nữa, các cạnh thể hiện sự tương tác giữa các biến. Chúng ta thấy rằng trong khi A và B trực tiếp ảnh hưởng lẫn nhau, A và C thì không. Lưu ý rằng các mạng Markov không cần phải theo chu kỳ, như trường hợp của các mạng Bayes.

Chức năng tiềm năng

Giống như chúng ta đã có CPD cho các mạng Bayes, chúng ta có các bảng để kết hợp quan hệ giữa các nút trong mạng Markov. Tuy nhiên, có hai sự khác biệt quan trọng giữa các bảng và CPD này.

Đầu tiên, các giá trị không cần tổng hợp thành một, nghĩa là bảng không xác định phân phối xác suất. Nó chỉ cho chúng ta biết rằng các cấu hình có giá trị cao hơn có nhiều khả năng. Thứ hai, không có điều hòa. Nó tỷ lệ thuận với phân phối chung của tất cả các biến liên quan, trái ngược với phân phối có điều kiện trong CPDs.

Các bảng kết quả được gọi là “yếu tố” hay “chức năng tiềm năng”, và ký hiệu bằng cách sử dụng biểu tượng của Hy Lạp . Vì vậy, ví dụ, chúng ta có thể sử dụng hàm tiềm năng sau để nắm bắt mối quan hệ giữa ba biến A, B và C, trong đó C là phần mềm XOR của X và A, B có nghĩa là C có thể là 1 nếu A và B khác nhau và C có thể là 0 nếu A và B giống nhau:

Nói chung, bạn sẽ có một hàm tiềm năng được xác định cho từng cụm tối đa trong biểu đồ.

Cấu trúc biểu đồ và các bảng tóm tắt ngắn gọn phân phối xác suất chung trên các biến ngẫu nhiên.

Một câu hỏi bạn có thể có tại thời điểm này là, tại sao chúng ta cần đồ thị có hướng cũng như vô hướng? Lý do là vì một số vấn đề, việc thể hiện chúng dưới dạng biểu đồ có hướng, chẳng hạn như mạng sinh viên ở trên, nơi dễ mô tả mối quan hệ nhân quả giữa các biến - trí thông minh của học sinh ảnh hưởng đến điểm SAT, nhưng Điểm SAT không ảnh hưởng đến trí thông minh của học sinh (mặc dù nó có thể cho chúng ta biết về trí thông minh của học sinh).

Đối với các loại vấn đề khác, giả sử, hình ảnh, bạn có thể muốn biểu thị mỗi pixel dưới dạng một nút và chúng tôi biết rằng các pixel lân cận ảnh hưởng lẫn nhau, nhưng không có mối quan hệ nguyên nhân giữa các pixel; thay vào đó, sự tương tác là đối xứng. Vì vậy, chúng tôi sử dụng các mô hình đồ họa vô hướng trong các trường hợp như vậy.

Cài đặt sự cố

Chúng ta đã thảo luận về đồ thị và các biến và bảng ngẫu nhiên cho đến nay, và bạn có thể nghĩ điểm của tất cả những thứ này là gì? Chúng ta thực sự đang cố gắng làm gì? Học máy ở đâu trong tất cả những điều này - dữ liệu, đào tạo, dự đoán, v.v.? Phần này sẽ giải quyết những câu hỏi này.

Hãy quay trở lại mạng lưới sinh viên. Giả sử chúng ta có cấu trúc biểu đồ với chúng ta, cái mà chúng ta có thể tạo ra từ kiến ​​thức của chúng ta về thế giới (được gọi là kiến ​​thức tên miền của Cameron trong học máy). Nhưng chúng tôi không có bảng CPD, chỉ có kích thước của chúng. Chúng tôi có một số dữ liệu, mặc dù - đối với mười lớp khác nhau trong một trường đại học, chúng tôi có một thước đo về độ khó của chúng.

Ngoài ra, chúng tôi có dữ liệu về từng sinh viên trong mỗi khóa học: trí thông minh của họ, điểm SAT của họ là gì, họ đạt điểm nào và liệu họ có nhận được một lá thư tốt từ giáo sư hay không. Từ dữ liệu này, chúng tôi có thể ước tính các tham số của CPD. Chẳng hạn, dữ liệu có thể cho thấy những học sinh có trí thông minh cao thường đạt điểm SAT tốt và chúng ta có thể học được từ đó rằng p (SAT = s1 | Intelligence = i1) cao. Đây là giai đoạn học tập. Chúng tôi sẽ sớm thấy cách chúng tôi thực hiện ước tính tham số này trong mạng Bayesian và Markov.

Bây giờ, đối với một điểm dữ liệu mới, bạn sẽ quan sát một số biến, nhưng không phải tất cả. Ví dụ, trong biểu đồ bên dưới, bạn biết về độ khó của khóa học và điểm SAT của học sinh và bạn muốn ước tính xác suất học sinh đạt điểm cao. (Đến bây giờ, bạn đã có các giá trị trong các bảng từ giai đoạn tìm hiểu.)

Mặc dù chúng tôi không có CPD cung cấp cho chúng tôi thông tin đó trực tiếp, chúng tôi có thể thấy rằng điểm SAT cao từ học sinh sẽ cho thấy học sinh có khả năng thông minh, và do đó, xác suất đạt điểm cao là rất cao nếu độ khó của khóa học là thấp, như được hiển thị bằng cách sử dụng các mũi tên màu đỏ trong hình trên. Chúng tôi cũng có thể muốn ước tính xác suất của nhiều biến số đồng thời, như xác suất học sinh đạt điểm cao và thư tốt là gì?

Các biến có giá trị đã biết được gọi là biến quan sát, biến trong khi các biến có giá trị không quan sát được gọi là biến ẩn ẩn Biến hoặc biến biến tiềm ẩn. trong hình trên. Chúng tôi có thể quan tâm đến việc tìm kiếm các giá trị của một số hoặc tất cả các biến tiềm ẩn.

Trả lời những câu hỏi này tương tự như dự đoán trong các lĩnh vực khác của học máy - trong các mô hình đồ họa, quá trình này được gọi là suy luận.

Mặc dù chúng tôi đã sử dụng các mạng Bayes để mô tả thuật ngữ ở trên, nhưng nó cũng áp dụng cho các mạng Markov. Trước khi chúng ta đi vào các thuật toán để học và suy luận, hãy chính thức hóa ý tưởng mà chúng ta vừa xem - đưa ra giá trị của một số nút, chúng ta có thể lấy thông tin về các nút nào khác?

Độc lập có điều kiện

Các cấu trúc biểu đồ mà chúng ta đã nói đến cho đến nay thực sự nắm bắt thông tin quan trọng về các biến. Cụ thể, họ định nghĩa một tập hợp độc lập có điều kiện giữa các biến, nghĩa là các câu lệnh có dạng - Tử Nếu A được quan sát, thì B độc lập với C. Hãy xem xét một số ví dụ.

Trong mạng lưới sinh viên, giả sử bạn biết rằng một sinh viên có điểm SAT cao. Bạn có thể nói gì về lớp của cô ấy? Như chúng ta đã thấy trước đó, điểm SAT cao cho thấy học sinh thông minh, và do đó, bạn sẽ mong đợi một điểm tốt. Nếu học sinh có điểm SAT thấp thì sao? Trong trường hợp này, bạn sẽ không mong đợi một điểm tốt.

Bây giờ, hãy nói rằng bạn cũng biết rằng học sinh thông minh, ngoài điểm SAT của cô ấy. Nếu điểm SAT cao, thì bạn sẽ đạt điểm cao. Nếu điểm SAT thấp thì sao? Bạn vẫn sẽ đạt điểm cao vì bạn biết rằng học sinh đó thông minh, và bạn sẽ cho rằng cô ấy chỉ không thể hiện tốt trong SAT. Do đó, biết điểm SAT không cho chúng ta biết bất cứ điều gì nếu chúng ta thấy trí thông minh của học sinh. Để đặt điều này như một tuyên bố độc lập có điều kiện, chúng tôi sẽ nói - Kiếm Nếu thông minh được quan sát, thì SAT và Lớp là độc lập.

Chúng tôi đã nhận được thông tin độc lập có điều kiện này từ cách các nút này được kết nối trong biểu đồ. Nếu chúng được kết nối khác nhau, chúng ta sẽ có được thông tin độc lập có điều kiện khác nhau.

Hãy xem đây là một ví dụ khác.

Hãy nói rằng bạn biết rằng học sinh thông minh. Bạn có thể nói gì về độ khó của khóa học? Không có gì, phải không? Bây giờ, nếu tôi nói với bạn rằng sinh viên bị điểm kém trong khóa học thì sao? Điều này sẽ gợi ý rằng khóa học này rất khó vì chúng tôi biết rằng một học sinh thông minh bị điểm kém. Do đó, chúng tôi có thể viết tuyên bố độc lập có điều kiện như sau - Từ Nếu Lớp không được quan sát, thì Trí thông minh và Khó khăn là độc lập.

Bởi vì các tuyên bố này nắm bắt được tính độc lập giữa hai nút theo một điều kiện , nên chúng được gọi là độc lập có điều kiện . Lưu ý rằng hai ví dụ có ngữ nghĩa trái ngược nhau - trong trường hợp thứ nhất, tính độc lập giữ nếu nút kết nối được quan sát ; trong cái thứ hai, tính độc lập giữ nếu nút kết nối không được quan sát . Sự khác biệt này là do cách các nút được kết nối, nghĩa là hướng mũi tên.

Chúng tôi sẽ không đi vào tất cả các trường hợp có thể vì lợi ích của sự ngắn gọn, nhưng thật đơn giản để đưa ra những điều này bằng cách sử dụng trực giác như trên.

Trong các mạng Markov, chúng ta có thể sử dụng một trực giác tương tự, nhưng vì không có cạnh (mũi tên), nên các câu lệnh độc lập có điều kiện tương đối đơn giản - nếu không có đường dẫn giữa các nút A và B sao cho tất cả các nút trên đường dẫn không bị quan sát, thì A và B là độc lập. Nói cách khác, nếu có ít nhất một đường dẫn từ A đến B trong đó tất cả các nút trung gian không được quan sát, thì A và B không độc lập.

Chúng tôi sẽ xem xét các chi tiết về cách ước tính tham số và suy luận được thực hiện trong phần thứ hai của bài đăng blog này. Bây giờ, chúng ta hãy xem xét một ứng dụng của các mạng Bayes, nơi chúng ta có thể sử dụng ý tưởng về sự độc lập có điều kiện mà chúng ta vừa học.

Ứng dụng: Vấn đề Monty Hall

Bạn hẳn đã thấy một số phiên bản này trong một chương trình trò chơi truyền hình:

Nguồn

Chủ nhà cho bạn thấy ba cánh cửa đóng kín, với một chiếc xe phía sau một trong những cánh cửa và một cái gì đó vô giá đằng sau những cái khác. Bạn có thể chọn một cánh cửa. Sau đó, chủ nhà mở một trong những cánh cửa còn lại và cho thấy nó không chứa xe. Bây giờ, bạn có một tùy chọn để chuyển cửa từ cửa bạn chọn ban đầu sang cửa mà chủ nhà chưa mở. Bạn có chuyển đổi không?

Theo trực giác, có vẻ như chủ nhà đã không tiết lộ bất kỳ thông tin nào. Hóa ra trực giác này không hoàn toàn chính xác. Hãy sử dụng công cụ mới trong kho vũ khí của chúng tôi - mô hình đồ họa - để hiểu điều này.

Hãy bắt đầu bằng cách xác định một số biến:

  • D : Cánh cửa với chiếc xe.
  • F : Lựa chọn đầu tiên của bạn.
  • H : Cánh cửa được mở bởi chủ nhà.
  • I : Là F = D?

D, F và H lấy các giá trị 1, 2 hoặc 3 và tôi lấy các giá trị 0 hoặc 1. D và tôi không quan sát được, trong khi F được quan sát. Cho đến khi chủ nhà mở một trong những cánh cửa, H không quan sát được. Do đó, chúng tôi nhận được mạng Bayes sau cho vấn đề của mình:

Lưu ý hướng mũi tên - D và F là độc lập, tôi rõ ràng phụ thuộc vào D và F, và cánh cửa được chọn bởi chủ nhà H cũng phụ thuộc vào D và F. Cho đến nay, bạn không biết gì về D. (Đây là tương tự như cấu trúc trong mạng lưới sinh viên, nơi hiểu biết về trí thông minh của sinh viên không cho bạn biết bất cứ điều gì về độ khó của khóa học.)

Bây giờ, chủ nhà chọn một cửa H và mở nó ra. Vì vậy, H được quan sát.

Quan sát H không cho chúng tôi biết bất cứ điều gì về tôi - đó là, liệu chúng tôi đã chọn đúng cửa. Đó là những gì trực giác của chúng tôi nói với chúng tôi. Tuy nhiên, nó cho chúng ta biết đôi điều về D! (Một lần nữa, vẽ tương tự với mạng sinh viên, nếu bạn biết rằng sinh viên thông minh, và điểm số thấp, nó sẽ cho bạn biết điều gì đó về độ khó của khóa học.)

Chúng ta hãy xem điều này bằng cách sử dụng số. Các bảng CPD cho các biến như sau (đây là khi không có biến nào được quan sát):

Các bảng cho D và F rất đơn giản - cửa với ô tô có thể là bất kỳ cửa nào có xác suất bằng nhau và chúng tôi chọn một trong các cửa có xác suất bằng nhau. Bảng cho tôi chỉ đơn giản nói rằng I = 1 khi D và F giống hệt nhau và I = 0 khi D và F khác nhau. Bảng cho H nói rằng nếu D và F bằng nhau, thì chủ nhà chọn một cửa từ hai cửa còn lại với xác suất bằng nhau, trong khi nếu D và F khác nhau, thì chủ nhà chọn cửa thứ ba.

Bây giờ, giả sử rằng chúng ta đã chọn một cánh cửa, nghĩa là, F hiện đang được quan sát, giả sử F = 1. Xác suất có điều kiện của I và D, cho F là gì?

Sử dụng các phương trình này, chúng tôi nhận được các xác suất sau:

Những con số này có ý nghĩa - cho đến nay, xác suất mà chúng tôi đã chọn đúng cửa là ⅓ và chiếc xe vẫn có thể đứng sau bất kỳ cánh cửa nào có xác suất như nhau.

Bây giờ, chủ nhà mở một trong những cánh cửa khác ngoài F, vì vậy chúng tôi quan sát H. Giả sử H = 2. Hãy tính toán xác suất có điều kiện mới của I và D cho cả F và H.

Sử dụng các phương trình trên, chúng tôi nhận được các xác suất sau:

Do đó, chúng tôi không biết thêm bất cứ điều gì về tôi - lựa chọn đầu tiên của chúng tôi vẫn đúng với xác suất và đây là những gì trực giác của chúng tôi nói với chúng tôi. Tuy nhiên, bây giờ chúng ta biết rằng chiếc xe đứng sau cửa 3 với xác suất, thay vì.

Vì vậy, nếu chúng ta chuyển đổi, chúng ta sẽ có được chiếc xe với xác suất; nếu không, chúng tôi sẽ lấy xe với xác suất.

Chúng ta có thể đã nhận được câu trả lời tương tự mà không cần sử dụng các mô hình đồ họa, nhưng các mô hình đồ họa cung cấp cho chúng ta một khung có khả năng giải quyết tốt các vấn đề lớn hơn.

Phần kết luận

Trong hướng dẫn PGM này, chúng tôi đã xem xét một số thuật ngữ cơ bản trong các mô hình đồ họa, bao gồm mạng Bayes, mạng Markov, phân phối xác suất có điều kiện, hàm tiềm năng và độc lập có điều kiện. Chúng tôi cũng đã xem xét một ứng dụng của các mô hình đồ họa về vấn đề Monty Hall.

Trong phần thứ hai của bài đăng trên blog này, chúng tôi sẽ xem xét một số thuật toán để ước tính tham số và suy luận, và một ứng dụng khác. Vậy nên hãy chờ trong giây lát!

|