엄청나게 정확한 AI로 구동되는 20 개의 질문으로 구성된 간단한 온라인 게임.
그들은 어떻게 그렇게 잘 추측합니까?
답변
이진 검색 알고리즘이라고 생각할 수 있습니다. 각 반복에서 우리는 가능한 단어 선택의 대략 절반을 제거해야하는 질문을합니다. 총 N 개의 단어가있는 경우 log2 (N) 질문 후에 답을 얻을 수 있습니다.
20 개의 질문으로 2 ^ 20 = 100 만 단어 중 단어를 최적으로 찾을 수 있어야합니다.
이상 값 (잘못된 답변)을 제거하는 쉬운 방법 중 하나는 아마도 RANSAC 와 같은 것을 사용하는 것 입니다. 즉, 답변 된 모든 질문을 고려하는 대신 무작위로 작은 하위 집합을 선택하여 단일 답변을 제공 할 수 있습니다. 이제 다른 임의의 질문 하위 집합으로 몇 번 반복하여 대부분의 경우 동일한 결과를 얻습니다. 그러면 정답이 있다는 것을 알게됩니다.
물론 이것은이 문제를 해결하는 여러 방법 중 하나 일뿐입니다.
답변
의사 결정 트리는 이러한 종류의 응용 프로그램을 직접 지원합니다. 의사 결정 트리는 일반적으로 인공 지능에서 사용됩니다.
의사 결정 트리는 왼쪽 및 오른쪽 자식이 나타내는 컬렉션을 구분하기 위해 각 분기에서 “가장 좋은”질문을 묻는 이진 트리입니다. 가장 좋은 질문은 20 개의 질문 응용 프로그램의 작성자가 트리를 작성하는 데 사용하는 학습 알고리즘에 의해 결정됩니다. 그런 다음 다른 포스터에서 지적했듯이 20 층 깊이의 나무는 백만 가지를 제공합니다.
각 지점에서 “가장 좋은”질문을 정의하는 간단한 방법은 컬렉션을 가장 균등하게 절반으로 나누는 속성을 찾는 것입니다. 이렇게하면 해당 질문에 대한 예 / 아니요 답변을받을 때 각 단계에서 수집품의 약 절반이 제거됩니다. 이렇게하면 이진 검색을 근사화 할 수 있습니다.
Wikipedia는보다 완전한 예를 제공합니다.
http://en.wikipedia.org/wiki/Decision_tree_learning
일반적인 배경 :
http://en.wikipedia.org/wiki/Decision_tree
답변
여기에서 게임에 대해 읽어 볼 것을 권장합니다 : http://en.wikipedia.org/wiki/Twenty_Questions
특히 컴퓨터 섹션 :
이 게임은 임의의 물체를 식별하는 데 필요한 정보 (Shannon의 엔트로피 통계로 측정)가 약 20 비트라고 제안합니다. 이 게임은 사람들에게 정보 이론을 가르 칠 때 종종 예로 사용됩니다. 수학적으로 각 질문이 대상의 절반을 제거하도록 구성된 경우 20 개의 질문을 통해 질문자는 2 개 20 개 또는 1,048,576 개의 주제 를 구분할 수 있습니다. 따라서 20 문항의 가장 효과적인 전략은 남은 가능성의 영역을 매번 대략 절반으로 나누는 질문을하는 것입니다. 이 프로세스는 컴퓨터 과학의 이진 검색 알고리즘과 유사합니다.
답변
그것은 스스로를 “인터넷상의 신경망”이라고 부르며 그 안에 핵심이있다. 질문 / 답변 확률을 예비 행렬에 저장합니다. 이러한 확률을 사용하여 의사 결정 트리 알고리즘을 사용하여 다음 질문을 가장 잘 좁힐 수있는 질문을 추론 할 수 있습니다. 가능한 답변의 수를 수십 개로 좁히거나 이미 20 개의 질문에 도달하면 가장 가능성이 높은 것을 읽기 시작합니다.
20q.net의 정말 흥미로운 점은 제가 아는 대부분의 의사 결정 트리 및 신경망 알고리즘과 달리 20q는 희소 행렬과 증분 업데이트를 지원한다는 것입니다.
편집 : 대답이 이번 내내 인터넷에 있었다는 것이 밝혀졌습니다. 발명가 인 Robin Burgener는 2005 년 특허 출원 에서 그의 알고리즘을 자세히 설명했습니다 .
