algorithm - programas - ¿Cómo funcionan 20 algoritmos de IA de preguntas?
programar inteligencia artificial python (5)
Está usando un algoritmo de aprendizaje.
k-NN es un buen ejemplo de uno de estos.
Juegos en línea sencillos de 20 preguntas con una IA misteriosamente precisa.
¿Cómo lo adivinan tan bien?
Puedes pensar que es el algoritmo de búsqueda binaria. En cada iteración, hacemos una pregunta, que debería eliminar aproximadamente la mitad de las opciones de palabras posibles. Si hay un total de N palabras, entonces podemos esperar obtener una respuesta después de las preguntas de log2 (N).
Con 20 preguntas, deberíamos poder encontrar una palabra entre 2 ^ 20 = 1 millón de palabras de manera óptima.
Una manera fácil de eliminar valores atípicos (respuestas incorrectas) sería probablemente usar algo como RANSAC . Esto significa que, en lugar de tener en cuenta todas las preguntas que han sido respondidas, escoge al azar un subconjunto más pequeño, que es suficiente para darle una respuesta única. Ahora lo repites unas cuantas veces con un subconjunto de preguntas al azar, hasta que ves que la mayoría de las veces obtienes el mismo resultado. Entonces sabes que tienes la respuesta correcta.
Por supuesto, esta es solo una de las formas de resolver este problema.
Recomiendo leer sobre el juego aquí: http://en.wikipedia.org/wiki/Twenty_Questions
En particular, la sección de Computadoras:
El juego sugiere que la información (medida por la estadística de entropía de Shannon) requerida para identificar un objeto arbitrario es de aproximadamente 20 bits. El juego se usa a menudo como ejemplo cuando se enseña a las personas sobre la teoría de la información. Matemáticamente, si cada pregunta está estructurada para eliminar la mitad de los objetos, 20 preguntas permitirán al interrogador distinguir entre 2 20 o 1,048,576 sujetos. En consecuencia, la estrategia más efectiva para Veinte Preguntas es hacer preguntas que dividirán el campo de posibilidades restantes aproximadamente en la mitad cada vez. El proceso es análogo a un algoritmo de búsqueda binario en ciencias de la computación.
Se anuncia a sí mismo como "la red neuronal en Internet", y ahí radica la clave. Es probable que almacene las probabilidades de pregunta / respuesta en una matriz adicional. Usando esas probabilidades, es capaz de usar un algoritmo de árbol de decisión para deducir qué pregunta preguntar que mejor limitaría la siguiente pregunta. Una vez que reduce el número de respuestas posibles a unas pocas docenas, o si ya se han cumplido 20 preguntas, comienza la lectura más probable.
El aspecto realmente intrigante de 20q.net es que, a diferencia de la mayoría de los algoritmos de árbol de decisión y redes neuronales que conozco, 20q admite una matriz dispersa y actualizaciones incrementales.
Editar: Resulta que la respuesta ha estado en la red todo este tiempo. Robin Burgener, el inventor, describió su algoritmo en detalle en su presentación de patente de 2005 .
Un árbol de decisión admite este tipo de aplicación directamente. Los árboles de decisión se usan comúnmente en inteligencia artificial.
Un árbol de decisión es un árbol binario que formula la pregunta "mejor" en cada rama para distinguir entre las colecciones representadas por sus hijos izquierdo y derecho. La mejor pregunta está determinada por algún algoritmo de aprendizaje que los creadores de la aplicación de 20 preguntas usan para construir el árbol. Entonces, como señalan otros carteles, un árbol de 20 niveles de profundidad te da un millón de cosas.
Una manera simple de definir "la mejor" pregunta en cada punto es buscar una propiedad que divida la colección en la mitad. De esa manera, cuando obtiene una respuesta de sí / no a esa pregunta, se deshace de la mitad de la colección en cada paso. De esta forma puede aproximar la búsqueda binaria.
Wikipedia da un ejemplo más completo:
http://en.wikipedia.org/wiki/Decision_tree_learning
Y algunos antecedentes generales: