Làm cách nào để 20 câu hỏi về thuật toán AI hoạt động?

Question

Trò chơi trực tuyến đơn giản gồm 20 câu hỏi được hỗ trợ bởi AI đơn giản chính xác.

Làm thế nào để họ đoán rất tốt?

Answer 1

Bạn có thể coi đó là Thuật toán tìm kiếm nhị phân. Trong mỗi lần lặp lại, chúng tôi đặt một câu hỏi, điều này sẽ loại bỏ gần một nửa số lựa chọn từ có thể. Nếu có tổng cộng N từ, thì chúng ta có thể mong đợi để có được một câu trả lời sau khi log2 (N) câu hỏi.

Với 20 câu hỏi, chúng ta nên tối ưu có thể tìm một từ trong số 2^20 = 1 triệu từ.

Một cách dễ dàng để loại bỏ các ngoại lệ (câu trả lời sai) có thể là sử dụng một cái gì đó như RANSAC. Điều này có nghĩa là, thay vì tính đến tất cả các câu hỏi đã được trả lời, bạn chọn ngẫu nhiên một tập con nhỏ hơn, đủ để cung cấp cho bạn một câu trả lời duy nhất. Bây giờ bạn lặp lại một vài lần với các tập con ngẫu nhiên khác nhau của câu hỏi, cho đến khi bạn thấy rằng hầu hết thời gian, bạn đang nhận được kết quả tương tự. sau đó bạn biết bạn có câu trả lời đúng.

Tất nhiên đây chỉ là một trong nhiều cách giải quyết vấn đề này.

Answer 2

Đang sử dụng thuật toán học tập.

k-NN là một ví dụ điển hình về một trong số này.

Wikipedia: k-Nearest Neighbor Algorithm

Answer 3

tôi khuyên bạn nên đọc về các trò chơi ở đây: http://en.wikipedia.org/wiki/Twenty_Questions

Đặc biệt các máy tính phần:

Các trò chơi gợi ý rằng các thông tin (được đo bằng entropy của Shannon Thống kê) cần thiết để xác định một đối tượng tùy ý là khoảng 20 bit. Trò chơi thường được sử dụng làm ví dụ khi hướng dẫn mọi người về thông tin lý thuyết. Về mặt toán học, nếu mỗi câu hỏi được cấu trúc để loại bỏ một nửa đối tượng, 20 câu hỏi sẽ cho phép người hỏi phân biệt giữa 2 hoặc 1.048.576 đối tượng. Theo đó, chiến lược hiệu quả nhất cho Hai mươi câu hỏi là đặt câu hỏi sẽ chia tách các trường các khả năng còn lại khoảng một nửa mỗi lần. Quá trình tương tự như tìm kiếm nhị phân thuật toán trong khoa học máy tính.

Answer 4

Cây quyết định hỗ trợ loại ứng dụng này trực tiếp. Cây quyết định thường được sử dụng trong trí tuệ nhân tạo.

Cây quyết định là cây nhị phân yêu cầu câu hỏi "tốt nhất" tại mỗi chi nhánh để phân biệt giữa các bộ sưu tập được thể hiện bởi con trái và phải của nó. Câu hỏi hay nhất được xác định bởi một số thuật toán học tập mà những người sáng tạo trong số 20 câu hỏi sử dụng ứng dụng để xây dựng cây. Sau đó, như các áp phích khác chỉ ra, một cây 20 cấp độ sâu mang lại cho bạn một triệu điều.

Cách đơn giản để xác định câu hỏi "tốt nhất" ở mỗi điểm là tìm một thuộc tính chia đều bộ sưu tập nhất thành một nửa. Bằng cách đó, khi bạn nhận được câu trả lời có/không cho câu hỏi đó, bạn sẽ loại bỏ khoảng một nửa bộ sưu tập ở mỗi bước. Bằng cách này bạn có thể ước tính tìm kiếm nhị phân.

Wikipedia đưa ra một ví dụ hoàn chỉnh hơn:

http://en.wikipedia.org/wiki/Decision_tree_learning

Và một số nền tảng chung:

http://en.wikipedia.org/wiki/Decision_tree

Answer 5

Nó hóa đơn chính nó như là "lưới thần kinh trên internet", và trong đó sự dối trá chìa khóa. Nó có khả năng lưu trữ các câu hỏi/câu trả lời xác suất trong một ma trận dự phòng. Sử dụng những xác suất đó, nó có thể sử dụng một thuật toán cây quyết định để suy luận câu hỏi nào sẽ yêu cầu tốt nhất nên thu hẹp câu hỏi tiếp theo. Một khi nó thu hẹp số lượng câu trả lời có thể cho vài chục, hoặc nếu nó đã đạt đến 20 câu hỏi rồi, thì nó bắt đầu đọc ra nhiều khả năng nhất.

Khía cạnh thực sự hấp dẫn của 20q.net là không giống như hầu hết các cây quyết định và thuật toán mạng nơron mà tôi biết, 20q hỗ trợ ma trận thưa thớt và cập nhật gia tăng.

Chỉnh sửa: Tắt câu trả lời trên mạng trong toàn bộ thời gian này. Robin Burgener, nhà phát minh, đã mô tả chi tiết thuật toán của mình trong số 2005 patent filing.