Разработка алгоритма из 20 вопросов

Это очень интересный вопрос. К сожалению, у меня нет полного ответа, позвольте мне просто записать идеи, которые я мог бы придумать через 10 минут:

• Если вы можете вдвое сократить набор доступных ответов по каждому вопросу, вы можете различить 2 ^ 20 ~ 1 млн "объектов". Ваш набор, вероятно, будет больше, поэтому можно предположить, что иногда вам приходится делать предположения.
• Вы хотите максимизировать полезность. Некоторые объекты выбираются чаще других. Если вы хотите сделать хорошие догадки, вы должны учитывать вес каждого объекта (= вероятность того, что этот объект будет выбран) при создании дерева.
• Если вы доверяете своим пользователям, вы можете получить знания, основанные на их ответах. Это также означает, что вы не можете использовать статическое дерево, чтобы задавать вопросы, потому что тогда вы получите ответы на одни и те же вопросы.. и вы не узнаете ничего нового, если столкнулись с одним и тем же объектом.
• Если простой вопрос не может разделить набор на две половины, вы можете комбинировать их для получения лучших результатов: например: "это объект зеленый или синий?". "зеленый или имеет круглую форму?"

Я пытаюсь написать реализацию python, используя наивную байесовскую сеть для обучения и минимизации ожидаемой энтропии после ответа на вопрос как критерий выбора вопроса (с вероятностью epsilon выбрать случайный вопрос, чтобы узнать подробнее об этом вопросе), следуя идеям http://lists.canonical.org/pipermail/kragen-tol/2010-March/000912.html. Я поставил то, что получил до сих пор на github.

• Предпочтительно выбирать вопросы с низким остаточным ожиданием энтропии. (Чтобы собрать что-то быстро, я украл у е-жадного многорукого бандита обучение и использование: с вероятностью 1-ε: задайте вопрос с наименьшим оставшимся ожиданием энтропии. С вероятностью ε: задайте любой случайный вопрос. Однако этот подход кажется далеко не оптимальным.)
• Так как мой подход - байесовская сеть, я получаю вероятности объектов и могу запросить наиболее вероятный объект.
  • Новый объект добавляется как новый столбец к матрице вероятностей с низкой априорной вероятностью и ответами на вопросы, заданные, если они даны или как предполагалось сетью Байеса, если они не указаны. (Я ожидаю, что эта вторая часть будет работать намного лучше, если я добавлю обучение сетевой сети Байеса вместо того, чтобы просто использовать наивные байесов.)
  • Аналогично, новый вопрос представляет собой новую строку в матрице. Если это происходит от ввода пользователем, вероятно, известно только очень мало вероятности ответа, остальное нужно угадать. (В общем случае, если вы можете получить объекты, попросив свойства, вы можете получить свойства, спросив, есть ли у них эти объекты или нет, а трансформация между ними по существу является теоремой Байеса и разбивается на транспозицию в самом простом случае. качество должно улучшиться снова, как только сеть будет иметь соответствующую структуру.)
• (Это проблема, так как я вычисляю множество вероятностей. Моя цель - сделать это с использованием базисных разреженных тензорных вычислений, оптимизированных для работы с взвешенными направленными ациклическими графами.)

Было бы интересно посмотреть, насколько хороший алгоритм, основанный на решениях, послужит вам. Трюк здесь заключается исключительно в изучении/сортировке дерева. Я хотел бы отметить, что это то, что я помню из класса AI и студенческой работы в рабочей группе AI, и его следует использовать с полумалым зерном (или самородом) соли.

Чтобы ответить на вопросы:

• Вы просто ходите по дереву:)
• Это большой недостаток деревьев решений. У вас будет только одна догадка, которая может быть прикреплена к конечным узлам дерева на глубине 20 (или раньше, если дерево все еще разрежено).
• Есть целые книги, посвященные этой теме. Насколько я помню из класса AI, вы всегда стараетесь минимизировать энтропию, поэтому вы хотите задать вопросы, которые идеально разделяют набор оставшихся объектов на два набора равного размера. Боюсь, вам придется искать это в книгах AI.
• Деревья принятия решений очень эффективны во время фазы запроса, так как вы буквально проходите дерево и следуете ветке "да" или "нет" на каждом node. Эффективность обновления зависит от применяемого алгоритма обучения. Вы могли бы сделать это в автономном режиме, как в ночном пакетном обновлении или что-то в этом роде.