Акинатор и математика

[Frodo]

ru.wikipedia.org/wiki/Экспертные_системы

[Danov]

и чего?

[hr0nix]

Да, это определенно экспертная система, если вы об этом. Существует много способов построения экспертных систем, и это — один из них.

[Bytexpert]

Блин, ребят, вам еще не надоело? Какой Байес? Это веб интерпретация игры «угадай животное». Алгоритм встречался практически в каждом старом учебнике по программированию. Вот здесь есть реализация на VBA для Excel: www.pcmag.ru/library/detail.php?ID=11018

[BearUA]

Случай о котором вы говорите автор тоже описал в самом начале. Игра «угадай животное» построена на простом бинарном дереве. И этот механизм ничего не сможет угадать если пользователь даст хотя бы один неправильный ответ.

Автору большое спасибо. Статья интересная. Вроде все простые вещи, а получается маленькое волшебство :) Такими примерами хорошо школьников заинтересовывать математикой…

[Bytexpert]

Упс… точно, впредь наука — сначала прочитай потом коммент пиши. Только вот не всегда получается, исправляюсь — прочитал, таки автор прав — плюсанул…

[AbnormalUnit]

Написание подобного рода программ на Prolog входит у нас в курс Искусственного Интеллекта.

[hr0nix]

Вы допускаете ту же ошибку, что и комментатор выше. Пролог — это язык логического программирования. На нем очень легко сделать экспертную систему поверх базы знаний, где характеристики объектов задаются областями истинности предикатов. Но Пролог никак (насколько мне известно) не помогает при реализации вероятностной интерпретации этой задачи (которая, в свою очередь, куда как более устойчива к неточностям).

[Levsha100]

Как я далек от всего этого… )

[foxweb]

5 курс специальности 230105?

[Alt_F4]

Программы (подобного рода), которые входили у вас в курс СИИ, входили туда последний год. Со след. года введем что-нибудь посерьёзнее :) Вероятностной интерпретации, естественно, там не было.
А представленная выше байесовская модель входила у вас в курс Распознавания образов :)

[Sonic_SE]

Я удивлен. Акинатор угадал Ноама Хомского.
Может им можно Хауса заменить?

[hr0nix]

Я так понимаю, про это вот тут можно почитать, если на Springer есть доступ.

[ivlis]

Это не статья, это список публикаций по теме. И тысячи их.

[hr0nix]

Ну я и имел в виду, что по ссылке нечто, что содержит в себе информацию о том, что можно почитать по теме. Забыл упомянуть про один уровень косвенности.

[rg_software]

Медицина — это едва ли не первое (исторически) применение экспертным системам, семидесятые годы.
Я не помню, как там конкретно происходила история, но «золотой век» экспертных систем считается уже прошедшим. То есть создали какие-то программы, они до сих пор работают. Но дальше какой-то теоретический потолок.

[father_gorry]

Потолок такой, что их алгоритмы создаются не командой, а отдельными особо одаренными личностями. ЭС MYCIN писалась на lisp'е кандидатом наук в течение шести лет. В иных случаях доходило и до десятилетия.

[verych]

Почему нельзя опираться? Я думаю что с такой же процентной долей вероятности как и на первом приеме у доктора.
Знаете как врачи у нас в больницах диагнозы ставят?
— Болит живот?
— Да
— Воду из под крана пил?
— Да
— Волчанка Гастрит

зы
Идея для стартапа, кстати, неплохая.

[hr0nix]

Так вроде есть таких сервисов куча. Вот например.

[verych]

эта штука за 5 минут отгадала то что мне врач говорил (3 дня обследований) +1

[Halt]

Полагаю, что врач во время вашего отсутствия шарился по интернету :) Или просил сына это сделать :)

[father_gorry]

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

[Regis]

А есть ли для таких сервисов какое-то общее название?

[vgrichina]

Я подозреваю что это было реализовано еще в 80-х :)

[Danov]

В начале 70-х. Классика MYCIN

[Halt]

Я думаю любая область поиска на основании дерева вопросов может быть реализована подобным образом. Взять тот же самый виндовый траблшутер. Идея вроде неплохая и чайникам может быть помогла бы. Но существующая реализация (точнее та, которую я видел лет 8 назад :) это просто ппц.

А тут можно сделать вполне себе толковую систему, которую кстати можно было бы использовать не только чайникам но и соображающим людям.

Вообще, подобный механизм очень хорошо подходит для задач «ищу то, сам не знаю чего»

[Goodkat]

Буратино угадал только с третьей попытки, сперва предложив Ивана-дурака и Щелкунчика.

[Dragonizer]

У меня с первого раза. Может, Вы его слишком давно смотрели?

[XaBoK]

Скорее всего основа там Ensemble, так как проще заточить какой-нибудь лёгкий Байес на конкретный тип/случай, чем пытаться простым алгоритмом охватить все варианты.

[Davidov]

Удивительно, как быстро все забыли про 20q.net.

[Leksisi]

Когда натыкаюсь на Акинатор мечтаю о том, что бы кто нибудь сделал такой же или подобный инструмент в современных ОС. Чтобы путем ответа на вопросы он подсказывал как настроить ту или иную программу или железку или как избавиться от определенной ошибки.

[Ten]

Проблема пользователей как раз в том, что они не знают, что им надо в большинстве случаев. Поэтому ответы на вопросы, по меньшей мере, будут не точны. А для админов — нас тогда не надо будет в природе

[Halt]

Так система и ориентирована на нечеткие вопросы. Более того, апроксимируя вопросы по «среднестатистическому чайнику», можно в итоге получить более эффективную систему.

Ну например, известная шутка про то, что для пользователя монитор — это и есть компьютер. Соответственно, экспертная система может заранее быть готова к вопросам «у меня компьютер сломался» или «процессор пищит», подразумевая что проблема вовсе не там, где думает пользователь.

[rg_software]

Ну так а troubleshooting wizard в винде — это не оно?

Не помню, чтобы он мне хоть раз помог толком, но старался :)

[Halt]

Почитайте мои посты выше. Проблема в том, что его составляли люди. Просто эмпирически. И вопросов там от силы сотня. А если бы система была составлена большой толпой и оформлена в виде веб сервиса, то тогда вообще была бы очень ценным инструментом.

[fogx]

Дело в том, что в Акинаторе ты изначально знаешь ответ на свой вопрос. И если Акинатор не угадает — ты его обучишь. И за счет миллионов таких вот пользователей он и учится, и показывает такие выдающиеся результаты.

А если миллион пользователей напишет «у меня пищит процессор» — то ничем это, увы, не закончится. Так же как и в медицине. А если держать админов/докторов, которые после списка вопросов будут реально обследовать пациента и вводить в базу правильный ответ на каждый конкретный user case — и поток информации для обучения сократится в сотни раз.

[rg_software]

За Холдена стало обидно :(

[hr0nix]

Такова жизнь =(

[fllln]

Формула Байеса — это да! Недавно был на одной конференции, там был больше всего был впечатлен докладом о разработке системы подбора отелей. Разработчики использовали Байесовы нейронные сети для того, чтобы попытаться угадать, что же на самом деле хотел пользователь (а не что он ввел в качесте параметров поиска). И в итоге пользователь мог пометить, что хочет жить на берегу моря, а получить предложение об отеле чуть ли не в горах, — и с радостью забронировать номер!

[hr0nix]

Что за Байесовские нейронные сети? Я знаю Байесовские сети и нейронные сети, но не вместе.

[alcsan]

А как называется эта система, если не секрет?
PS. Сорян за некропостинг.

[Flying]

Огромное спасибо за статью!

[dushes]

Я фигею! Загадал Ельцына и после вопросов о русской национальности и принадлежности к политике, спросил много ли пьют мой персонаж… Вот так вот разработчики думают о русских политиках.

[ivlis]

Вот и отличный пример почему обычное дерево тут не применимо.

[zxm]

Скорее пользователи, а не разработчики.

[Dragonizer]

Нет, вопросы подбираются в зависимости от имеющейся информации. Ну или как написано в топике, вопрос выбирается из условия минимизации ожидания энтропии.
Таким образом, у него бывают вопросы, содержащие половину ответа.

[ivlis]

Спасибо за статью, очень интересно! Побольше бы таких на хабре.

[hr0nix]

Не за что. Буду стараться =)

[savostin]

я так понимаю программу Вы написали?
И просить исходники просто глупо, да?

[hr0nix]

Нет, совсем не глупо =) Просто она пока далека от идеала, и я ее выкладывать не стал. Но исходники и прилагающуюся к ним базу знаний могу выслать всем желающим, отписывайтесь тут.

Точнее будет сказать, что от идеала далека база знаний, потому что почти всю ее составлял один человек (которому за это была обещана и впоследствии куплена бас-гитара) =) В любом случае, решающий движок реализован и работает по формулам, описанным в статье.

[Dragonizer]

А не хотите запустить аналогичный Акинатору сервис?

[hr0nix]

Ну, прям аналогичный Акинатору наверное не стоит. Все-таки есть уже сам Акинатор =) А вот почитав комментарии выше, я подумал, что идея онлайн-траблшутера, который будет не только подсказывать решения проблем, но и самостоятельно обучаться, не так уж плоха. Надо об этом интенсивней поразмыслить на досуге.

[Dragonizer]

Хм, даже еще лучше. Желаю успехов!
P.S. Ну и добавлю спасибо за статью, не знал, что формула Байеса применяется где-то кроме задачек по терверу. :)

[hr0nix]

Про формулу Байеса — это вы зря :) Она, например, лежит в основе подавляющего большинства методов, используемых в современном компьютерном зрении. Ну и еще в миллионе других областей используется.

[seiros]

А можно мне исходники? ^_^
Я димплом пишу по матметодам. Мне эти вещи будут ооочень полезны.
За статью спасибо. Весьма интересно.

[hr0nix]

Скажите мне свой адрес, и я отправлю.

А диплом по матметодам — это как? По всем матметодам? :)

[seiros]

Ответил в личку

[Zubchick]

Очень круто! Поздравляю с успешной реализацией :)

[PASSTor]

А откуда брали списки персонажей и списки вопросов?
Неужели вбивали руками с нуля?

[hr0nix]

Я пообещал купить другу бас-гитару, если он добавит в базу знаний 500 персонажей вместе с вопросами. Ну и сам еще постарался немного =)

[Serzhenko]

Гитару-то купили? :))

[hr0nix]

Купили =)

[mr_avi]

Я писал не так давно систему очень подобную этой, более похожую на Яндекс-гуру. В принципе смысл тот же, только система работает не за счет существующей базы, а база наполняется за счет ответов пользователей. На самом деле всё просто, если кого заинтересует могу поделиться идеей.

[Hest]

Великолепная статья, я восхищен красотой математического решения.

А есть ли тут кто-нибудь умный, кто подсказал бы, как программе вычислить P(<Qj,Ans>|Ai)?

[hr0nix]

Не знаю, насколько я умный, но подсказать могу.

P(<Qj,Ans>|Ai) дословно читается как «вероятность того, что на вопрос Qj был дан ответ Ans при условии, что загадан был Ai. Эту вероятность мы оцениваем на основе предыдущих ответов пользователей как долю ответов Ans на вопрос Qj про Ai среди всех возможных ответов на этот вопрос для Ai.

[Hest]

Вы умный. Спасибо.

[Hest]

А не подскажете ли еще насчет вот какого момента. В статье говорится, что для того, чтобы выбрать вопрос, который выгоднее всего задать, следует, перебирая j, вычислить суммы H[P(Ai|B, <Qj,Yes>)]P(<Qj,Yes>) + … + H[P(Ai|B, <Qj,No>)]P(<Qj,No>) и потом найти минимальную из них. А какое значение i тут следует подставлять? «Sum(i)» в формуле нет, а подставлять какое-то одно конкретное значение i вроде бы нелогично, потому что в момент выбора вопроса еще неизвестно с достаточной вероятностью, какой персонаж загадан. Как же быть?

[hr0nix]

Я вас отправлю вот сюда =)

[Hest]

Спасибо! С помощью этого документа смог полностью разобраться.

[Compazavr]

Я надеюсь, автор статьи еще читает комментарии.
Спасибо за интересный материал!

Хотел бы тоже попросить у вас исходники и базу знаний, если можно.
Адрес почты, куда высылать, отправил вам в сообщения с пометкой «Код «Акинатор и математика»».
Извиняюсь за беспокойство!

[hr0nix]

Господа, я попал в дурацкую ситуацию: в процессе переезда между компами я потерял исходники и базу знаний от этого проекта. Не мог бы кто-нибудь из тех, кому я отправлял исходники и базу, переслать мне их обратно? =)

[hr0nix]

Нашлось.

[archerl]

Скиньте, пожалуйста, если можете, исходники и базу знаний на [e-mail]. Заранее спасибо.

[artemev]

А у кого есть идеи насчет того как Акинатор сохраняет промежуточный результат при «общении» с конкретным пользователем? То есть, допустим, я ответил на 1-й вопрос. Алгоритм просчитал вероятности для персонажей из своей базы, исходя из этого просчитал, какой вопрос задать следующим, ну и задал его :)

Я снова ответил. Он вновь пересчитал вероятности и так далее пока вероятность какого-либо персонажа не станет больше какой-то определенной величины (допустим 95%), ну или пока количество заданных вопросов не станет равно 20.

Так вот где он эти вероятности хранит?

[Wouw]

Скорее всего у себя в памяти хранит сессию по вашей партии.
Так же допустим вариант, что набор ответов хранится у вас и каждый раз передается ему, где он накатывает ответы на всю базу персонажей.