Автоматический зачёт ответов

[Ur-Quan]

Попробуем разобраться с зачётов ответов на вопросы без участия человека. Возможно, это позволит выработать какие-то общие правила для зачёта ответов вообще.

Суть проблемы

Итак, у нас есть:

• вопрос, требующий ответа;
• база знаний, помогающая нам определять правильные ответы;
• набор правил, позволяющих дать ответ на вопрос, верен ли ответ;
• собственно ответ игрока.

В "Умном казино", например, база знаний представлена в виде одной строчки с правильным ответом. Правило зачёта одно - полное совпадение с авторским ответом.
Необходимо определить, можно ли засчитывать ответ, данный игроком.

Общие предпосылки решения

Здесь и далее под авторским ответом подразумевается не один ответ, а некоторое множество ответов, которые изначально определены как правильные.
Будем различать два аспекта зачёта:

1. Орфографический - вы написали ответ неправильно, но невооружённым глазом видно, но он верен (например "сабака" при правильном "собака");
2. Семантический - написали вы ответ по правилам русского языка, он не совпадает с авторским, но вы имели в виду то же самое ("Советский союз" вместо "СССР") или почти то же самое ("РСФСР" вместо "СССР", тут с зачётом надо быть аккуратнее).

Что касается орфографии, то тут сразу же можно выделить три подхода:

1. Жёсткий подход. Вы написали слово по правилам орфографии, и оно не совпадает с авторским ответом. Значит, вы имели в виду что-то совсем другое. Такой ответ не может быть засчитан с позиции орфографии ("СЕНТО" при ответе "СЕАТО").
2. Мягкий подход. Вы написали слово, которое есть в словаре, но оно мало отличается от авторского ответа. Так что, вообще говоря, ваш ответ можно и засчитать ("шубы" вместо "губы").
3. Сложный подход. Ваше слово есть в словаре, и оно засчитывается лишь тогда, когда понятно, что вы не могли ответить именно это. Например, если вопрос про части тела, а вы отвечаете "шубы", то, скорее всего, имелись в виду "губы", и надо засчитывать. Если же между вашим словом и авторским ответом есть сильная ассоциативная связь ("СЕНТО" и "СЕАТО" - два союза), то засчитывать ваш ответ нельзя.

Пока речь шла об ответах в виде одного слова. А что делать, если авторский ответ или ответ, данный игроком, состоит из ряда слов? Как тогда быть?
Здесь тоже можно подходить по-разному. Можно работать с каждым словом по отдельности, а можно со всей фразой целиком. Второе предпочтительнее, так как позволяет учитывать ситуации с разным количеством слов в авторском ответе и в ответе игрока. В любом случае ответ игрока должен быть преобразован в какую-то стандартную форму.

Если ответ игрока отсутствует в словаре, то необходимо найти слово из словаря, максимально похожее на ответ. Если был дан ответ "слан", то наиболее похожим словом из словаря будет "слон".
Отдельной проблемой являются также формы слов. При авторском ответе "мороз" можно дать ответ "мороза", и он должен быть засчитан. При этом речь идёт о правилах склонения и других способах изменения формы сова, которые также должны быть учтены.

Если орфографический подход не позволил принять ответ, на смену ему приходит семантический. Принять в таком случае ответ - куда более нетривиальная задача.
В настоящее время у меня есть идея сделать что-то вроде словаря синонимов, в котором будут указаны тождественные конструкции. Скажем, "РФ" = "Российская Федерация", "А.С. Пушкин" = "Александр Сергеевич Пушкин". Но это довольно-таки поверхностный подход.
По идее, между любыми двумя понятиями можно установить степень их связи (ассоциации между ними) и вид иерархии.

Понятие - это смысловая единица, которая воспринимается как единое целое. Может быть словом, словосочетанием, выражением, даже предложением. Скажем, понятиями будем считать следующие элементы списка: "слон", "колесо обозрения", "ни рыба ни мясо", "А судьи кто?". Авторский ответ представляет собой совокупность понятий, которые удовлетворяют вопросу. Не должно быть понятий, которые подходят в качестве ответа, не входят в авторский ответ или не являются семантически близкими к нему.
Игрок же даёт ответ не в виде понятия, а в виде строки, которая может содержать и несколько понятий. Это уже проблемы игрока; думаю, что его ответ стоит всё же считать одним понятием.
Наш словарь состоит из понятий и связей между ними. Понятное дело, что сразу такой словарь не создать, но он может расширяться с появлением новых вопросов и ответов.
На данный момент мне видятся три вида связей:

1. Иерархия "целое - часть". Нос - часть человека. Крыло - часть птицы. Это связывает понятия между собой.
2. Иерархия "общее - частное". Пушкин, Достоевский, Толстой - всё это частные случаи писателей. Здесь лежит ключ к автоматической генерации неправильных ответов. Если авторский ответ "Пушкин", то неправильным является любой другой писатель. С помощью этой иерархии понятия объединяются во множества. "Пушкин" будет принадлежать разным множествам, таким как "поэты", "русские" и пр.
3. Ассоциация. Степень смысловой связи между понятиями. Чем она выше, тем выше вероятность, что вы ответили верно. Например, степень ассоциации между понятиями "СССР" и "Советский Союз" можно считать равной 1, то есть они тождественны. Это - возможный критерий семантического зачёта ответов.

Продолжение следует
Пока же хотелось послушать ваше мнение на этот счёт.

добавлено через 7 минут

Сообщение от Strel

Так чего там улучшать: сделай ты наконец анализ по наличию подстроки! (Т.е. одной из возможных). Например:

...

Также хорошо бы убрать вопросы с описательными ответами.

Хм, мы это вроже обсуждали уже.
Вот, например, вопрос:
"Сколько колец...?" Набираю ответ: "16 17 18 19 20 21". И засчитано. Каково?
"Этот русский писатель..." Пишу: "Чехов Толстой Достоевский". Тем самым, вероятность ответа увеличивается в несколько раз. А как быть с темой "От 2 до 5"?

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

[Nikolaev N.]

Сообщение от Ur-Quan

Пока же хотелось послушать ваше мнение на этот счёт.

Короче это можно сформулировать так: "Как за две недели работы и сто рублей денег сварганить искусственный интеллект?".
ПМСМ, как бы ни плевался Анатолий Рафаилович, при ограниченных ресурсах лучше правил "Умного казино" ничего не придумаешь.

[grzegorz]

Сообщение от Nikolaev N.

Короче это можно сформулировать так: "Как за две недели работы и сто рублей денег сварганить искусственный интеллект?".
ПМСМ, как бы ни плевался Анатолий Рафаилович, при ограниченных ресурсах лучше правил "Умного казино" ничего не придумаешь.

Другая игра. Эффект присутствия рубит на корню. Мне больше по душе идея постепенного внесения зачитываемых ответов на КАЖДЫЙ вопрос. Предварительное тестирование в закрытом кругу и т.д. Вопросы с описательными ответами исключаются.

Глобальные словари синонимов нежизнеспособны. Синоним, являющийся явным зачётом на один вопрос, может быть явным незачётом на другой. СССР=Советский Союэ? А если тема - "4 буквы"?

[зам.]

Это всё имеет смысл делать только для очень серьёзного продвижения игры. ПМСМ, как водится.

[Strel]

Сообщение от Ur-Quan

Хм, мы это вроже обсуждали уже.
Вот, например, вопрос:
"Сколько колец...?" Набираю ответ: "16 17 18 19 20 21". И засчитано. Каково?
"Этот русский писатель..." Пишу: "Чехов Толстой Достоевский". Тем самым, вероятность ответа увеличивается в несколько раз. А как быть с темой "От 2 до 5"?

Так кого обманывать-то?

Это уж во всяком случае менее проблематичная ситуация, чем предлагавшаяся возможность править счёт вручную.

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

[В Молчанов]

ЗАМ, в числе наших планов (смотри соответствующую ветку) и создание и поддержка компьютерной версии СИ. Так что может быть, что усилия Володи перестанут быть частным делом, если он сам не будет возражать, конечно. Тогда ваши ремарки и правки могут оказаться весьма полезны.

[Snip1]

Я сейчас пишу пакет для этой игры.Описательных ответов практически нет.Стараюсь сделать их как можно однозначнее.Разве только в одном месте - сложная иностранная фамилия.Там я предлагаю несколько вариантов написания.Если спрашивается какой-либо человек, литературный персонаж и т.п. принимаются в равной степени фамилия и имя/фамилия.

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

Кстати, вопрос,который я снял из пакета(показалось неоднозначным).

Студенты Мельбурнского текстильного колледжа установили мировой рекорд,изготовив костюм за 1 час 34 минуты 33 секунды.Первые секунды рекорда ушли на этот процесс.

Ответ:Поимка овцы.

Я задался вопросом,какие ответы надо принимать.


Владимир,извините за задержку.Обещал давно,но никак не могу закончить.Пришлось вводить "Сборную солянку" и две мои подправленные темы с чемпионата Москвы.Но до Нового года обязательно пришлю.

[зам.]

В Молчанов, так о том и речь. Огромных успехов Володе вообще и игре в частности - кто же против-то! Я так только за, и пятью руками притом. Кроме того - слышал я краем уха, что тестированием игры озаботился некто Максимов К. Вот тут-то мы все и поймём, как же мы ни фига не понимаем...

Snip1, тоже дело хорошее. Однако, ПМСМ, не самое хорошее - игра всё-таки телевизионная. Мне кажется, тут надо не писать вопросы кому-ни-попадя (и уж особенно Байраму - из пушки на Луну у него с мыса Канаверел летали, убивать). И ты в данном случае тоже называешься кто-ни-попадя, и я, и мы все. А надо взять и тщательно подобрать подлинные вопросы из телеСИ - и именно с однозначными ответами, и составить несколько таких пакетов, и комментарии в "настоящем стиле ПБК" (да хоть и опять же подлинных подобрать), и всё такое. Есть, например, игра "О, счастливчик!" (ещё не "миллионер" - а может, и "миллионер" уже есть) с подлинными же вопросами - смотрится вполне, вполне...

[grzegorz]

Сообщение от зам.

Есть, например, игра "О, счастливчик!" (ещё не "миллионер" - а может, и "миллионер" уже есть) с подлинными же вопросами - смотрится вполне, вполне...

"КХСМ" есть. Насчёт подлинности - не знаю. С живым Галкиным. Так по выбору же ответов там, э-э-э, полегче будет. А здесь именно в зачёте проблема.

[Ur-Quan]

Nikolaev N.,
правила "Умного казино" входят в действующие. А попробовать улучшить хочется

grzegorz,
правда, я не очень представляю вопрос, на который необходим столь точный ответ...

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

В Молчанов,
ни в коем случае не буду возражать, я только за! Тем более, что это может помочь увеличению популярности телеигры.

Snip1,
ничего страшного нет. Когда напишете - тогда и выйдет. Описательные вопросы на данный момент действительно лучше исключать.

зам.,
дык где бы эти подлинные вопросы раздобыть? Там база получится приличная, на десятилетия хватит.
Да, и кто будет всё это обрабатывать?

[grzegorz]

Сообщение от Ur-Quan

grzegorz,
правда, я не очень представляю вопрос, на который необходим столь точный ответ...

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

[зам.]

Раздобыть-то не проблема - особенно если редакция не против. Да и без её содействия тоже - бери вон обзор-протоколы Фатимы и нет проблем. А вот обработка - да, работа огромная, кропотливая и квалифицированная. Я бы позанималСИ - если бы других дел не было...

[Ur-Quan]

Дальнейший текст будет слегка математизированным.
Итак, пусть у нас имеется хотя бы небольшая база понятий, содержащая правильные и неправильные ответы на вопрос. Игрок вводит ответ, и наша задача определить, какое из понятий он имел в виду.
Сама база должна постепенно расширяться с ростом числа вопросов. Изначально же она будет содержать достаточно скромное число понятий.
База B := пара (V, Q), гдее V - множество понятий vi, которые мы пока будем понимать в виде строк, и Q - множество связей между ними: Q = {(vi, vj)| vi, vj принадлежат V}. В итоге у нас выходит этакий семантический граф. На данном этапе мы пренебрежём связями между понятиями и обратим внимание на сами понятия.
Игрок может ввести и осмысленное слово, но если оно будет отсутствовать в базе, то всё равно должно будет преобразовано в одно из имеющихся там понятий. Грубо говоря, нам надо спроецировать введённое игроком на множество понятий. Если в результате мы получим понятие, являющееся правильным, то ответ игрока засчитывается. Если мы получим неправильный ответ, то, возможно, стоит попробовать какой-нибудь другой метод или проверить семантику.
Проекция определяется просто - это то понятие, расстояние от которого до введённого игроком слова минимально. Иными словами, пусть игрок ввёл строчку s. Тогда проекция P(s) = {v| d(s, v) <= d(s, w) для любого w из V}. Вообще, таких понятий может быть много. Будем исходить из либерального подхода: при попадании хотя бы одного правильного ответа в это множества ответ игрока засчитывается. Однако при этом мы должны гарантировать, что ответ игрока всё же хоть немного похож на правильный. Необходимо ввести предельное расстоние dmax, определяющие границы правильного понятия. Если расстояние между введённым игроком словом и любым из правильных понятий больше, чем dmax, то ответ не может быть засчитан.
Как же определить расстояние между словами? Необходимо учесть, что игрок может случайно нажать не на ту клавишу или нажать на лишнюю клавишу, или вообще пропустить букву. Всё это должно быть засчитано.
Наиболее удобным вариантом для определения "похожести" двух слов считаю нахождение самой длинной одинаковой подпоследовательности букв, входящей в оба слова. Вот, например, выделена общая подпоследовательность в понятиях "Медный всадник" и "Меднй всаадник". Чем длинне такая подпоследовательность, тем понятия сильнее похожи. Например, в данном примере ответ вполне можно принять, несмотря на то, что полного совпадения нет.
Расстояние вводится по формуле
d(s1, s2) = max (длина s1, длина s2) - длина общей подпоследовательности. При этом вроде бы выполнены все свойства расстояния. Таким образом, мы можем вычислить расстояние между введённым ответом и каждым из понятий и найти минимальное. Мы и получим понятие для анализа.
Надо позаботиться лишь об одном - чтобы программа не стала засчитывать всё подряд. Если ответ игрока неверен, то он не должен оказаться слишком близко к правильному. Это обеспечивается просто тем, что база вводится уже с некоторым достаточным числом понятий.

[anatbel]

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

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

Короче, так.
После сдачи ответа программа объявляет, зачтен ли он. Если зачтен - быть по сему. А вот если не зачтен - на панели игровой есть особая кнопочка:

Я это и имел в виду!!!!!

Ткнешь в нее мышкой - ответ будет зачтен.
Можно, кстати, предусмотреть такую возможность и после ответа "соперников".

[зам.]

"Соперников" - это как? Тыкать кнопку типа "это Друзь и имел в виду"? То есть зачесть им побольше, чтобы в финале было поинтереснее?