"Взлом" теста "1С:Профессионал" методом машинного обучения

Программирование - Практика программирования

72
Нейронные сети – не единственная модель, реализующая принципы машинного обучения. Есть еще байесовская модель, которая математически строже и определеннее, поскольку построена на надежном фундаменте теории вероятностей. Применению байесовского вывода к решению интересной теоретической задачи и посвящена данная статья. Слово "взлом" в заголовке использовано для привлечения внимания. Речь идет исключительно о математическом методе, показанном на примере знакомой всем задачи. 

1. Задача

2. Немного теории

3. Алгоритм решения

4. Подробности реализации

5. Практическая проверка

6. Выводы

 

1. Задача

Суть решаемой задачи заключается в следующем:

Имеются вопросы теста 1С: Профессионал, поделенные, как правило,  на 14 разделов. В каждом разделе заключено конкретное количество различных вопросов. На каждый вопрос имеется 5 (для определенности) вариантов ответов, один из которых является правильным. Прохождение теста заключается в выборе одного варианта ответа на каждый из 14 вопросов. Вопросы для каждого теста выбираются случайным образом - по одному из каждого раздела. По окончании прохождения теста испытуемому сообщается только количество правильных ответов. Какие именно ответы были правильными, не раскрывается. Требуется построить алгоритм, позволяющий определить правильные ответы на все вопросы тестов путем многократного прохождения теста методом проб и ошибок без какого-либо анализа сути вопросов.

2. Немного теории

В основе байесовской модели лежит понятие распределения вероятностей. Оно определяет вероятность каждого из возможных исходов некоторого "случайного" события. Например, бросание игрального кубика характеризуется распределением вероятностей (1/6, 1/6, 1/6, 1/6, 1/6, 1/6), а правильность выбранного "вслепую" варианта ответа описывается распределением (1/5, 1/5, 1/5, 1/5, 1/5). Исходное распределение вероятностей, называемое априорным, может впоследствии уточняться при поступлении дополнительной информации о событии. Например, если стало известно, что число, выпавшее при бросании кубика, четное, то уточненным распределением вероятностей будет распределение вероятностей (0, 1/3, 0, 1/3, 0, 1/3). Уточненное распределение вероятностей называется апостериорным, а процесс расчета апостериорного распределения на основе дополнительной информации и на основе априорного распределения называется байесовским выводом. Вывод производится на основе формулы условной вероятности или формулы Байеса:

Р( А | Б) = Р( АБ ) / Р( Б ) = Р( Б | А ) Р( А ) / Р( Б ),

где А - исследуемое событие, Б - зависимое событие, которое оказывается произошедшим в свете полученной дополнительной информации.

В одной этой формуле и заключается вся суть байесовской модели.

В следующий раз апостериорное распределение, полученное на предыдущем шаге, считается уже априорным и с получением следующей порции информации оно опять пересчитывается. До тех пор пока не будет достигнута максимальная определенность, например, распределение вероятностей не выродится в единичный вектор вида ( ..., 0, 1,  0, ...), что означает, что вероятен один единственный исход исследуемого события.

Мера неопределенности по ходу обучения может оцениваться формулой для расчета энтропии:

Σj = 1,n | - Pj log(Pj) |

В процессе обучения эта мера должна снижаться, что характеризует прогресс обучения.

3. Алгоритм решения

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

Количество правильных ответов K пройденного теста (событие Б) естественно зависит от того, какие ответы были выбраны и какова была вероятность, что они правильные. Если число К становится известно (событие Б произошло), то из априорных распределений легко рассчитать знаменатель в формуле Байеса (вероятность события Б). Это будет сумма вероятностей всех комбинаций ответов, в которых К вопросов выбрано правильно, а (14 - К) - неправильно. Числителем для каждого вопроса пройденного теста будет сумма вероятностей тех комбинаций, в которых выбранный ответ на этот вопрос правильный (вероятность совместной реализации А и Б).  Зная числитель и знаменатель, легко пересчитать апостериорную вероятность того, что выбранный вариант ответа на соответствующий вопрос действительно правильный. Вероятности для оставшихся вариантов ответов пересчитываются пропорционально их старым значениям с учетом условия равенства суммы вероятностей единице.

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

4. Подробности реализации

Более конкретно на языке системы "1С: Предприятие" для работы алгоритма необходимо определить таблицу значений, число строк в которой равно общему числу имеющихся вопросов во всех разделах теста. Сами вопросы в таблице хранить не нужно, их содержание значения не имеет. Если возможно пять вариантов ответа, то в таблице нужно завести пять колонок с именами Р1 - Р5 числового типа достаточной точности для представления вероятностей. Например, типа Число(10, 9). Первоначально все ответы равновероятны, поэтому все колонки заполняются значением 0,2 (= 1 / 5). Также в таблице заводится колонка "НомерТеста" для отметки вопросов текущего теста, колонка номера выбранного ответа и служебная колонка "Числитель" для расчета числителя формулы Байеса. В результате прохождения теста соответствующие строки отмечаются номером текущего теста, заполняется номер выбранного ответа, а также становится известным число правильных ответов.

Для выбора варианта ответа и пересчета вероятностей Р1 - Р5 в выбранных по номеру текущего теста строках таблицы используется следующая процедура:

Процедура Тестирование(ПараметрыТестирования)
	
	ГСЧ = Новый ГенераторСлучайныхЧисел();
	ПравильныхОтветов = 0;
	Код = "";
	Для НомерВопроса = 0 По Отчет.ЧислоВопросовТеста - 1 Цикл
		НомерВарианта = ГСЧ.СлучайноеЧисло(0, Отчет.ЧислоВариантовОдногоВопроса - 1);
		ВопросТеста = Отчет. Вопросы[НомерВопроса * Отчет.ЧислоВариантовОдногоВопроса + НомерВарианта];
		ВопросТеста.НомерТеста = ПараметрыТестирования.НомерТеста;
		ВопросТеста.ВыбранныйОтвет = ВыборПоВероятности(ВопросТеста, ГСЧ);
		ВопросТеста.Числитель = 0;
		ПравильныхОтветов = ПравильныхОтветов + (ВопросТеста.ВыбранныйОтвет = ВопросТеста.ПравильныйОтвет); //только для подсчета!!!
		Код = "0" + Код + "1"
	КонецЦикла;
	
	ПараметрыТестирования.ЧислоПравильныхОтветов = ПравильныхОтветов;
	Знаменатель = 0;
	Код = Сред(Код, ПравильныхОтветов + 1, Отчет.ЧислоВопросовТеста); // инициализация перебора комбинаций расположения правильных ответов
	ВопросыТеста = Отчет.Вопросы.НайтиСтроки(Новый Структура("НомерТеста", ПараметрыТестирования.НомерТеста));
	Пока СтрЧислоВхождений(Код, "1") = ПравильныхОтветов Цикл // перебор комбинаций 
		ВероятностьКомбинации = 1;
		Для Сч = 0 По Отчет.ЧислоВопросовТеста - 1 Цикл
			ВероятностьПравильностиОтвета = ВопросыТеста[Сч]["Р" + ВопросыТеста[Сч].ВыбранныйОтвет];
			ВероятностьКомбинации = ВероятностьКомбинации * ?(Сред(Код, Сч + 1, 1) = "1", ВероятностьПравильностиОтвета, 1 - ВероятностьПравильностиОтвета)
		КонецЦикла;
		Для Сч = 0 По Отчет.ЧислоВопросовТеста - 1 Цикл                                                                                                                        
			ВопросыТеста[Сч].Числитель = ВопросыТеста[Сч].Числитель + ?(Сред(Код, Сч + 1, 1) = "1", ВероятностьКомбинации, 0) 	
		КонецЦикла;
		Знаменатель = Знаменатель + ВероятностьКомбинации;
		Код = СледующийКод(Код)
	КонецЦикла;
	
	Для Каждого Вопрос ИЗ ВопросыТеста Цикл // пересчет вероятностей
		ЭнтропияДо = Энтропия(Вопрос);
		УсловнаяВероятность = Вопрос.Числитель / Знаменатель;
		БылаВероятность = Вопрос["Р" + Вопрос.ВыбранныйОтвет];
		Если БылаВероятность = 1 Тогда
			ПараметрыТестирования.Энтропия = ПараметрыТестирования.Энтропия + 0 - ЭнтропияДо;
			Продолжить
		КонецЕсли;
		Вопрос["Р" + Вопрос.ВыбранныйОтвет] = 1;
		Для Ответ = 1 По Отчет.ЧислоВариантовОтвета Цикл
			Если Ответ <> Вопрос.ВыбранныйОтвет Тогда
				Вопрос["Р" + Ответ] = Вопрос["Р" + Ответ] * (1 - УсловнаяВероятность) / (1 - БылаВероятность);
				Вопрос["Р" + Вопрос.ВыбранныйОтвет] = Вопрос["Р" + Вопрос.ВыбранныйОтвет] - Вопрос["Р" + Ответ]
			КонецЕсли
		КонецЦикла;
		ПараметрыТестирования.Энтропия = ПараметрыТестирования.Энтропия + Энтропия(Вопрос) - ЭнтропияДо;
	КонецЦикла
	
КонецПроцедуры

В качестве вспомогательной здесь используется функция генерации всех возможных строк из "0" и "1" заданной длины в порядке увеличения количества "1". Задав в качестве начального кода строку вида "000...111", содержащую число единиц, соответствующую числу правильных ответов, можно получить все комбинации расположения правильных ответов в тесте.

Функция СледующийКод(Код)
	
	Возврат Прав(СтрЗаменить(Код, "1", "0") + Лев("1" + Код, Найти(Код, "0")) 
    + ?(Найти(Код, "01"), "0", "") + Сред(Код, Найти(Код + "01", "01") + 2), СтрДлина(Код))
	
КонецФункции

Для четырех знаков эта простая функция порождает последовательность "0000", "0001", "0010", "0100", "1000", "0011", "0101", "1001", "0110", "1010", "1100", "0111", "1011", "1101", "1110", "1111", "0000" и так далее.

5. Практическая проверка

К статье приложена обработка "Угадайка правильных ответов теста" для испытания алгоритма. В обработке можно задать число вопросов теста, число различных вопросов в разделе, число возможных ответов на один вопрос. Случайным образом генерируется номер правильного ответа на каждый вопрос. Обработка не обращается напрямую к этой информации, а получает только количество правильных ответов. При этом обработка  шаг за шагом сужает неопределенность в отношении правильности разных вариантов ответов и в конечном итоге определяет правильные ответы на все вопросы в соответствии с предложенным алгоритмом. Это можно увидеть на Фиг.1 для задачи небольшой размерности с параметрами: 6 вопросов по два варианта в разделе и пять вариантов ответа на каждый вопрос.

Для 14-ти вопросов, 50 вопросов в каждом разделе, 5-ти вариантах ответов обработке необходимо примерно 2500 прохождений теста для завершения обучения. Это не так уж много, учитывая, что в конечном итоге определяются правильные ответы на каждый из 700 вопросов теста с пятью вариантами ответов на каждый вопрос.

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

На Фиг.3 изображено соответствующее постоянное и равномерное снижение энтропии в определенности правильности разных вариантов ответов на вопросы по мере обучения.

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

6. Выводы

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

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

Эта замечательная задача была придумана Максимом Б (Xershi) и предложена им в ходе обсуждения реальных практических задач для нейронных сетей. Решение, найденное в ходе обсуждения,  показалось настолько поучительным, что была высказана просьба и получено согласие использовать эту задачу для публикации найденного решения.

72

Скачать файлы

Наименование Файл Версия Размер
Обработка для тестирования алгоритма обучения:
.erf 12,41Kb
11.12.17
48
.erf 12,41Kb 48 Скачать бесплатно

См. также

Комментарии
Сортировка: Древо
1. Nikola23 379 12.03.18 17:33 Сейчас в теме
Хорошее решение в плане освоения академических знаний. Но, для выбранного примера - не оптимальное (вероятно, поиск оптимального решения не ставился в задачу)

К счастью, для подготовленного пользователя, на сайте http://edu.1c.ru/ очень легко получить ответы, без взлома БД и прочих противоправных действий.
khabibullin.tu; formica32; +2 Ответить
2. ildarovich 6087 12.03.18 18:02 Сейчас в теме
(1) Да, о таком пути знающие люди мне уже рассказали, но тут вся суть в практическом применении математического метода, который может пригодиться и там, где интересующие зависимости спрятаны более тщательно.
JohnyDeath; +1 Ответить
19. Shaldryn 13.03.18 15:07 Сейчас в теме
(1) а можете мне рассказать?.)
21. Nikola23 379 15.03.18 22:13 Сейчас в теме
(19) Не уверен, что формат форума позволяет открыто публиковать ответ на ваш вопрос.
6. TODD22 17 13.03.18 11:01 Сейчас в теме
В основе байесовской модели лежит понятие распределения вероятностей. Оно определяет вероятность каждого из возможных исходов некоторого "случайного" события. Например, бросание игрального кубика характеризуется распределением вероятностей (1/6, 1/6, 1/6, 1/6, 1/6, 1/6), а правильность выбранного "вслепую" варианта ответа описывается распределением (1/5, 1/5, 1/5, 1/5, 1/5). Исходное распределение вероятностей, называемое априорным, может впоследствии уточняться при поступлении дополнительной информации о событии. Например, если стало известно, что число, выпавшее при бросании кубика, четное, то уточненным распределением вероятностей будет распределение вероятностей (0, 1/3, 0, 1/3, 0, 1/3)

Байес и тер вер конечно был у меня давно. Но разве после броска кубика распределение не останется таким же? Кубик не запоминает своё состояние. И результат следующего броска не зависит от результата пред идущего броска.

С ответами на тест понятно. Мы отбрасываем неверный ответ и вероятность распределяется между оставшимися.
8. ildarovich 6087 13.03.18 11:20 Сейчас в теме
(6)
И результат следующего броска не зависит от результата пред идущего броска.
В данном случае два события (отдельные броски кубика) независимы, что как раз и определяется равенством условного и безусловного распределения вероятностей. Но вот любой результат броска (один из шести вариантов) и четный результат того же броска связаны. Поэтому если известно, что результат броска будет четным (например, четные грани красные, мы видим только цвет, а число разобрать не можем), то распределение вероятностей можно уточнить.
9. TODD22 17 13.03.18 11:27 Сейчас в теме
(8)
Но вот любой результат броска (один из шести вариантов) и четный результат того же броска связаны.

Не очень понял.

Бросаем кубик один раз. Получаем чётное число. При повторном броске выпадение чётного или не чётного равновероятно. Или нет?
11. ildarovich 6087 13.03.18 11:37 Сейчас в теме
13. TODD22 17 13.03.18 11:44 Сейчас в теме
(11)Тогда не понимаю как мы после первого броска уточняем вероятность, если события равновероятны?
15. ildarovich 6087 13.03.18 11:52 Сейчас в теме
(13) Кубик приведен как пример для объяснение исходного понятия условной вероятности и формулы Байеса. Решаемая задача чуть сложнее, лучше думать прямо над ней.
10. TODD22 17 13.03.18 11:28 Сейчас в теме
(8)
Поэтому если известно, что результат броска будет четным

Так пока не бросим нам это не известно.
14. ildarovich 6087 13.03.18 11:47 Сейчас в теме
(10) Я в (8) описал гипотетическую ситуацию, когда кубик бросили ОДИН раз, из-за того, что четные грани кубика красные издалека уже будет видно, что результат четный, а 2, 4 или 6 выпало еще непонятно (пока не видно). Вот в этом случае и нужно использовать условное распределение вероятностей (при условии четности результата).
В случае с тестом известно количество правильных ответов. Например, семь. Их расположение (какие конкретно были правильные) может быть самым разным. Всего столько, сколько комбинаций выбрать семь из четырнадцати (число сочетаний). Четных три комбинации, а там 7 из 14 - это 3432 комбинации. В расчете на них и пересчитывается распределение.
16. TODD22 17 13.03.18 11:53 Сейчас в теме
(14)
Я в (8) описал гипотетическую ситуацию, когда кубик бросили ОДИН раз, из-за того, что четные грани кубика красные издалека уже будет видно, что результат четный, а 2, 4 или 6 выпало еще непонятно (пока не видно). Вот в этом случае и нужно использовать условное распределение вероятностей (при условии четности результата).

Ок. Теперь понятно :) Я не так понял. .
20. ser6702 78 14.03.18 08:58 Сейчас в теме
Кончайте девочки любить хороших мальчиков, любите девочки летчиков и моряков ;-) Автор рассказывает метод отношения максимального правдоподобия. Подход изначально не академический, а инженерный. Называется относительно-частотный. Есть ещё аксиоматический подход. И там и там по моим остаточным знаниям рассчитывается
отношение апостериорной плотности вероятности к априорной. В качестве расширения задачи можно предложить задаться вопросом, а что если номер правильного ответа будет случайным образом изменяться, но например не по гауссовскому закону, а будет задана телеметрическая модель. И так вы плавно перейдете к Винеру и далее к Калмановской фильтрации и теории оптимального управления, и вперёд, создавать алгоритмы для "кинжалов" )))
7. pm74 125 13.03.18 11:14 Сейчас в теме
(0) интересная тема спасибо
12. spezc 484 13.03.18 11:43 Сейчас в теме
Круто. А я только только начал погружаться в статистику)
17. TODD22 17 13.03.18 11:57 Сейчас в теме
Надо на досуге почитать учебники по тер. веру и статистики, нашёл пару хороших, а то последний раз открывал их лет 15 назад когда учился. Как раз курс по модным нынче ML и DS прохожу.
18. Evil Beaver 5195 13.03.18 14:57 Сейчас в теме
С возвращением, маэстро!
maxopik2; Dem1urg; Dach; +3 Ответить
Оставьте свое сообщение