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

12.03.18

Разработка - Математика и алгоритмы

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

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

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

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) и предложена им в ходе обсуждения реальных практических задач для нейронных сетей. Решение, найденное в ходе обсуждения,  показалось настолько поучительным, что была высказана просьба и получено согласие использовать эту задачу для публикации найденного решения.

машинное обучение байесовский вывод теория вероятностей

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1753    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4415    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7455    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7854    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8832    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7797    dusha0020    8    

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

К счастью, для подготовленного пользователя, на сайте http://edu.1c.ru/ очень легко получить ответы, без взлома БД и прочих противоправных действий.
SGordon1; khabibullin.tu; formica32; +3 Ответить
2. ildarovich 7850 12.03.18 18:02 Сейчас в теме
(1) Да, о таком пути знающие люди мне уже рассказали, но тут вся суть в практическом применении математического метода, который может пригодиться и там, где интересующие зависимости спрятаны более тщательно.
user717534; JohnyDeath; +2 Ответить
23. siamagic 06.02.23 18:25 Сейчас в теме
Почему никто не видит очевидный бред? 700 вопросов по 5 вариантов = 3500 вариантов при условии что вам при каждой попытке сообщают верно или нет.

В примере вам показывают 14 вопросов из 50ти - однозначно увидеть достоверность не получится
(2)
24. ildarovich 7850 07.02.23 09:42 Сейчас в теме
(23) Не понял, где вы увидели бред...

Если бы мы сразу получали информацию о том, правильно ли мы ответили на вопрос, то для того, чтобы таким образом узнать правильные ответы требуется максимум 700 * (5 - 1) = 700 * 4 = 2800 проверочных попыток ответа на один вопрос или 2800 / 14 = 200 прохождений теста, если в каждом прохождении будут строго разные вопросы. (5 - 1) потому, что если мы проверили 4 варианта, то пятый проверять не нужно. Это максимально, а среднем 2,8 попытки.

В реальном тесте мы не получаем информацию правильно ли мы ответили на конкретный вопрос, а получаем информацию только косвенно позволяющую судить о том, какие ответы были правильные. При этом для распознавания правильных ответов требуется примерно 2500 прохождений теста из 14-ти вопросов, то есть примерно 35000 попыток ответа на вопросы. В 10 раз больше! Именно из-за отсутствия информации о том, какие ответы были правильные.
3. пользователь 12.03.18 21:50
Сообщение было скрыто модератором.
...
4. пользователь 13.03.18 10:03
Сообщение было скрыто модератором.
...
5. пользователь 13.03.18 10:44
Сообщение было скрыто модератором.
...
19. Shaldryn 13.03.18 15:07 Сейчас в теме
(1) а можете мне рассказать?.)
21. Nikola23 696 15.03.18 22:13 Сейчас в теме
(19) Не уверен, что формат форума позволяет открыто публиковать ответ на ваш вопрос.
6. TODD22 18 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 7850 13.03.18 11:20 Сейчас в теме
(6)
И результат следующего броска не зависит от результата пред идущего броска.
В данном случае два события (отдельные броски кубика) независимы, что как раз и определяется равенством условного и безусловного распределения вероятностей. Но вот любой результат броска (один из шести вариантов) и четный результат того же броска связаны. Поэтому если известно, что результат броска будет четным (например, четные грани красные, мы видим только цвет, а число разобрать не можем), то распределение вероятностей можно уточнить.
9. TODD22 18 13.03.18 11:27 Сейчас в теме
(8)
Но вот любой результат броска (один из шести вариантов) и четный результат того же броска связаны.

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

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

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

Ок. Теперь понятно :) Я не так понял. .
20. ser6702 165 14.03.18 08:58 Сейчас в теме
Кончайте девочки любить хороших мальчиков, любите девочки летчиков и моряков ;-) Автор рассказывает метод отношения максимального правдоподобия. Подход изначально не академический, а инженерный. Называется относительно-частотный. Есть ещё аксиоматический подход. И там и там по моим остаточным знаниям рассчитывается
отношение апостериорной плотности вероятности к априорной. В качестве расширения задачи можно предложить задаться вопросом, а что если номер правильного ответа будет случайным образом изменяться, но например не по гауссовскому закону, а будет задана телеметрическая модель. И так вы плавно перейдете к Винеру и далее к Калмановской фильтрации и теории оптимального управления, и вперёд, создавать алгоритмы для "кинжалов" )))
7. pm74 199 13.03.18 11:14 Сейчас в теме
(0) интересная тема спасибо
12. spezc 782 13.03.18 11:43 Сейчас в теме
Круто. А я только только начал погружаться в статистику)
17. TODD22 18 13.03.18 11:57 Сейчас в теме
Надо на досуге почитать учебники по тер. веру и статистики, нашёл пару хороших, а то последний раз открывал их лет 15 назад когда учился. Как раз курс по модным нынче ML и DS прохожу.
18. Evil Beaver 8107 13.03.18 14:57 Сейчас в теме
С возвращением, маэстро!
akR00b; SagittariusA; eugeniezheludkov; maxopik2; Dem1urg; Dach; +6 Ответить
22. user1119853 02.01.20 15:19 Сейчас в теме
Интересная статья, спасибо!
25. siamagic 07.02.23 12:26 Сейчас в теме
(24) берем типовой тест 1с - 50 вопросов в разделе, рандомно по 14 выходят.
Что у вас означает "варианты Вопросов" так и не понял.

Вышло вам первый раз 1-14, вопросы, второй раз 15-27 и 2ой вопросы. С помощью этой информации по своей модели вы вообще никак не приблизитесь к верному результату.
26. ildarovich 7850 07.02.23 15:12 Сейчас в теме
(25) Попробую объяснить...

Вышло в первый раз вопросы 1-14. Вы ответили, запомнили ответы. Экзаменатор сказал, что все ответы неверные.

Вышло во второй раз вопросы 2, 15-27. Опять ответили, запомнили ответы. В вопросе 2 оставалось только четыре непроверенных варианта. Поэтому проверили еще один. Экзаменатор сказал, что все ответы неверные.

Вышло в третий раз 1 - 13 и 15. Опять ответили. Для вопроса 2 выбрали один из трех оставшихся непроверенных варианта ответа. А для вопроса 14 - один из четырех. Экзаменатор сказал, что все ответы неверные.

...

И так далее. Постепенно вы проверите все варианты ответов в вопросах, повторяющихся в тестах пять раз и найдете среди них верные.

Но это если "везет" и все ответы в тестах были неверными. Неопределенность сужается максимально быстро. А если экзаменатор говорит, что только один (два, три, ...) из вопросов отвечен правильно. Дает ли это какую-то информацию? - В статье говорится о том, что дает и приведен метод, позволяющий использовать эту нечеткую информацию для четких выводов путем ее накопления.
27. siamagic 07.02.23 16:45 Сейчас в теме
(26)

Вышло в первый раз вопросы 1-14. Вы ответили, запомнили ответы. Экзаменатор сказал, что все ответы неверные.

Вышло во второй раз вопросы 2, 15-27. Опять ответили, запомнили ответы. В вопросе 2 оставалось только четыре непроверенных варианта. Поэтому проверили еще один. Экзаменатор сказал, что все ответы неверные.


Неизвестно какой ответ неверный, а какой верный. Из двух выборок вы не определите был верный во втором или в 15-27
28. ildarovich 7850 07.02.23 16:56 Сейчас в теме
(27) Хм... выборка {2, 15-27} одна, в ней 14 вопросов. 2, 15-27 это номера вопросов.
29. siamagic 07.02.23 17:16 Сейчас в теме
(28)
выборка 1: вопросы 1-14, 5 не верно.
выборка 2: вопросы 2,15-27, 7 не верно.

Какие выводы можно сделать?
30. ildarovich 7850 08.02.23 16:28 Сейчас в теме
(29)
Какие выводы можно сделать?
Так именно об этом и написана вся эта статья!!!

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

Обработку можете скачать или прислать могу, если скажете куда.
31. siamagic 08.02.23 17:14 Сейчас в теме
(30) у вас одно событие зависит от другого и через шаг который я вам изложил выше вероятность меняется - хотя по факту конечно же нет.

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

Обработку скачал - завис на месте "варианты вопросов" - вы их умножаете на вопросы - что за ерунда?
32. ildarovich 7850 08.02.23 22:13 Сейчас в теме
(31) Меняется не вероятность, а условная вероятность, что не одно и то же.

Примерно как если раскрасить четные грани кубика белым, а нечетные черным и издалека вы не видите, какое число очков выпало, но видите, что выпала белая грань, то безусловная вероятность будет (1/6, 1/6, 1/6, 1/6, 1/6, 1/6), а условная (0, 1/3, 0, 1/3, 0, 1/3).

От предыдущего броска, ясно, ничего не зависит. Но у нас нет последовательности бросков! Бросок всего 1. Бросили за один раз пятнадцать пятигранных кубиков, затем их накрыли покрывалом и задаем вопросы: на первом кубике 1? на втором кубике1? ... На пятнадцатом кубике 1? Нам отвечают, что мы не угадали 5 кубиков. И оказывается, что хотя исходные вероятности всех 5 в 15-ой степени комбинаций были равны, после получения этой информации, мы уже так думать не можем, так как некоторые комбинации придется исключить. И можно будет определить условную вероятность. И так далее.
33. siamagic 09.02.23 05:51 Сейчас в теме
(32) вернемся к конкретике

"выборка 1: вопросы 1-14, 5 не верно.
выборка 2: вопросы 2,15-27, 7 не верно. "

Как меняется ваша условная вероятность после выборки 1? после выборки 2?
34. ildarovich 7850 09.02.23 09:34 Сейчас в теме
(33) Нужны конкретные числа?
35. siamagic 09.02.23 10:13 Сейчас в теме
(34)Статьи интересна тем что берет данные из реальности.

С моей точки зрения в разделе 50 вопросов, по 14 в тесте - это сочетания 14 из 50 = 937845656300. из эитх сочетаний верно только 1 когда все ответы верны. + 14 для одной ошибки и 14*13 для двух.
Но это как вы заметили безусловная вероятность.

далее к практике

Для НомерВопроса = 1 По Отчет.ЧислоВопросовТеста Цикл
Для НомерВариантаВопроса = 1 По Отчет.ЧислоВариантовОдногоВопроса Цикл
НовыйВопрос = Отчет.Вопросы.Добавить();
НовыйВопрос.ПравильныйОтвет = ГСЧ.СлучайноеЧисло(1, Отчет.ЧислоВариантовОтвета);
//новыйВопрос.ПравильныйОтвет = НомерВопроса%3+1;
Для НомерОтвета = 1 По Отчет.ЧислоВариантовОтвета Цикл
НовыйВопрос["Р" + НомерОтвета] = 1 / Отчет.ЧислоВариантовОтвета
КонецЦикла
КонецЦикла
КонецЦикла


"ЧислоВариантовОдногоВопроса " - что это??? Вхождения вопроса в сочетания ?
36. ildarovich 7850 09.02.23 18:08 Сейчас в теме
(35)
С моей точки зрения в разделе 50 вопросов, по 14 в тесте - это сочетания 14 из 50 = 937845656300. из эитх сочетаний верно только 1 когда все ответы верны. + 14 для одной ошибки и 14*13 для двух.
Тут путаница. Можно поправить, но эти расчеты делать незачем. Число вопросов в разделе ни на что не влияет.
Важно общее число вопросов - 700. И число вопросов в тесте - 14. И число вариантов ответа на один вопрос (ЧислоВариантовОдногоВопроса) - 5. Один правильный, четыре неправильных.
НовыйВопрос["Р" + НомерОтвета] = 1 / Отчет.ЧислоВариантовОтвета

так определяется вероятность того, что конкретный вариант (из пяти) ответа будет правильным. Это безусловная вероятность. Распределение вероятностей по ответам (начальное или безусловное) задается вектором (1/5 1/5 1/5 1/5 1/5). Мы не знаем какой ответ правильный. Поэтому предполагаем, что любой из них может быть правильным с равной вероятностью. Таких векторов 700. Столько, сколько всего вопросов. Они инициализированы значениями (1/5 1/5 1/5 1/5 1/5).

Для простоты предположим, что в тесте участвуют первые 14 вопросов. Забудем про разделы, они вообще не важны.
Мы выбрали для всех 14 вопросов первый вариант ответа.

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

Если оказалось, что все ответы неверные. То апостериорная вероятность будет определяться четырнадцатью векторами (0 1/4 1/4 1/4 1/4). То есть исключена (оказалось равна нулю) вероятность, что правильный ответ - первый.

Промежуточные случаи.

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

Один ответ верный. Вектора будут все такие (0.04 0.24 0.24 0.24 0.24). То есть данный первый вариант ответов скорее всего неверен (маловероятно верен), остальные равновероятно верны.

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

Интересно, что интуитивно кажется, что случай 7 правильных ответов не должен менять исходную вероятность. Но на самом деле минимальную новую информацию приносит случай 3-х правильных ответов . Потому что именно столько в среднем мы наберем, выбирая ответы наугад.
37. siamagic 09.02.23 19:21 Сейчас в теме
(36) "Тут путаница. Можно поправить, но эти расчеты делать незачем. Число вопросов в разделе ни на что не влияет.
Важно общее число вопросов - 700."
Поправляю, число вопросов в разделе 50, выдются порциями по 14. зачем перемножать это? Что это за метрика?

про все верные, неверные смысла комментировать не вижу.

"
Один ответ верный. Вектора будут все такие (0.04 0.24 0.24 0.24 0.24). То есть данный первый вариант ответов скорее всего неверен (маловероятно верен), остальные равновероятно верны. " - у 13ти?
38. ildarovich 7850 10.02.23 12:36 Сейчас в теме
(37) Предлагаю упростить задачу объяснения/понимания. Для этого необходимо сначала рассмотреть упрощенный вариант. Который сохраняет суть (математическую основу) алгоритма.

Пусть в каждом разделе будет ровно по одному вопросу! То есть разделов 14 и всего вопросов 14. Значит раз за разом мы будем проходить один и тот же тест, отвечать на одни и те же вопросы. На каждый вопрос будет пять вариантов ответа. Один из них правильный. А обратную связь также будем получать о количестве правильных ответов.

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

Изначально вся таблица будет равномерно серой.

После первого прохождения выбрали везде ответы из первого столбика и получили:

Все ответы верные. Покрасили черным ответы в первом столбике, в остальных карандаш стерли. Закончили алгоритм. Получили шпаргалку.

Если оказалось, что все ответы неверные. Стерли цвет в первом столбике, в остальных сделали цвет чуть потемнее (с 0.2 до 0.24 черного).

Промежуточные случаи.

Один ответ неверный. В первом столбике цвет почти черный, в остальных светло-серый.

Один ответ верный. В первом столбике цвет почти белый, в остальных чуть посветлее, чем раньше.

Промежуточные случаи тоже меняют оттенок серого в каждой клеточке (кажется, в этом вы сомневались).

Проходим тест снова, если алгоритм не закончен.

С незаконченной шпаргалкой поступаем так: чаще выбираем ответы из столбика потемнее (в статье говорится, что это не единственная стратегия).

Каждое прохождение теста меняет оттенки серого в клетках, отражающие нашу уверенность в том, что именно этот ответ правильный!

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

Осталось заменить оттенки на вероятности и все.
39. siamagic 13.02.23 08:34 Сейчас в теме
(11)

1. Ваше решение ломается на моменте когда вопросы идут рандомно.
2. Вы описали перебор сочетаний выше я писал что для одного раздела там будет далеко не 2500.
40. ildarovich 7850 13.02.23 11:25 Сейчас в теме
(39)
1. Ваше решение ломается на моменте когда вопросы идут рандомно.
Нет, это не так. В приведенной обработке вопросы идут рандомно, решение не ломается, неопределенность постепенно снижается, в конце концов, примерно после 2500 прохождений теста мы получаем искомую шпаргалку с правильными ответами на все 700 вопросов теста.
(39)
2. Вы описали перебор сочетаний выше я писал что для одного раздела там будет далеко не 2500.
Не смог понять, что вы хотели этим сказать, нужны пояснения. Слово "сочетания" я вроде бы вообще не использовал. Что значит "для одного раздела"? "Далеко не 2500" это примерно сколько?
41. siamagic 13.02.23 12:55 Сейчас в теме
(40) Определимся с задачей - смотрим только один раздел. Всего 50 вопросов. Вывод по 14ть. 5 ответов.
Выпадают вопросы рандомно.

1-14 - 9 верно, пять нет. - Чего вы после этого собрались "красить"?

2,3 15-22 7 верно 7 нет - Чего вы после этого собрались "красить"?
42. ildarovich 7850 13.02.23 13:55 Сейчас в теме
(41) Все просто: Я завожу картонку из 50 строк и 5 столбцов. Каждая строка соответствует одному вопросу. Столбец - варианту ответа с соответствующим номером.

1-14 9 верно, пять нет. Будут перекрашены клеточки в строчках с 1-ой по 14-ую. Более темный цвет получат столбцы, соответствующие выбранным вариантам ответов. Можно точно посчитать насколько. Мат.аппарат и соответствующие формулы приведены в статье и обработке.

2,3 15-26 7 верно 7 нет. Будут перекрашены клеточки в строчках 2,3 15-26. При этом в строчках 15-26 несколько более темный цвет получат клетки сделанных ответов. В строчках 2, 3 будет так: если был выбран тот же ответ, что и в первый раз, то он еще чуточку потемнеет. Если ответ был другим, то потемнеет клетка нового ответа, а старого несколько посветлеет вместе с другими (но не станет с ними одного цвета).

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

Главное здесь в том, что расчет вероятностей идет не от исходной полной неопределенности, а уже от того распределения, которое было перед тестом. Именно это обеспечивает накопление информации. Например, если вы отвечали "1" на этот вопрос в каком-то тесте, где все ответы посчитались неверными, то к следующему тесту вы уже не будете такой ответ выбирать. Это крайний случай, но в промежуточных так же, только вероятности не единичные.

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

Очень грубо оценить число попыток можно так: исходная неопределенность кодируется log2(5) * 50 = 115 бит. Каждый ответ дает примерно 4 бита информации. Значит всего необходимо 29 прохождений теста для того, чтобы узнать какие ответы для каждого из 50-ти вопросов правильные.
43. siamagic 13.02.23 14:20 Сейчас в теме
Возможно сильно туплю.

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

"снова и снова его перекрашивать. При чем в направлении бОльшей определенности какой ответ правильный."
"Будут перекрашены клеточки в строчках с 1-ой по 14-ую. Более темный цвет получат столбцы, соответствующие выбранным вариантам ответов. "
"В строчках 2, 3 будет так: если был выбран тот же ответ, что и в первый раз, то он еще чуточку потемнеет." - почему не наоборот?
44. ildarovich 7850 13.02.23 14:45 Сейчас в теме
(43)
я вывожу вам 14 из 14 - через 29 раз будет достоверно известно про 7 вопросов
Просто не понял, поясните...

"В строчках 2, 3 будет так: если был выбран тот же ответ, что и в первый раз, то он еще чуточку потемнеет." - почему не наоборот?
Конечно, нужно считать, но интуитивно кажется так:
Если угадано 3 ответа из 14, то распределение практически не меняется, поскольку большинство способов расположения правильных ответов на картонке даст такой результат.
Но если угадано 7, то в бОльшем количестве вариантов расположения правильных ответов они должны находиться на местах, указанных нами в тесте .

Если угадано 14 - все ответы верные.
Если угадано 13 - почти все ответы верные.
Если угадано 12 - почти-почти все ответы верные.
...
Если угадано 3 - почти та же неопределенность, что и исходная ситуация.
Если угадано 2 - почти-почти все ответы неверные.
Если угадано 1 - почти все ответы неверные.
Если угадано 0 - все ответы неверные.

К счастью, вместо этих оценочных рассуждений есть точные формулы и можно не гадать на кофейной гуще.
45. siamagic 13.02.23 15:13 Сейчас в теме
(44) "Просто не понял, поясните..." для 14 из 50 у вас 29 попыток.

Я упрощаю пример до 14 из 14 и гарантирую что 29 попыток не хватит.

Если угадано 14 - все ответы верные.
...
Если угадано 0 - все ответы неверные.

в какой цвет красите при 7 и 7?
46. ildarovich 7850 13.02.23 16:23 Сейчас в теме
(45) Да, 29 попыток маловато. Это была грубая оценка. Тем не менее я запустил обработку для предложенного случая.
Нажал +100 (это значит сделать плюс 100 попыток). И в статистике посмотрел, что поиск заканчивается после: 43, 44, 35, 115, 35, >400 попыток. Это все разные серии прохождения тестов. То есть может хватить и 35 попыток.

Если посмотреть, что происходит в неудачной серии, то видно, что многие правильные ответы довольно точно определены. Вероятность некоторых ответов 0.95 и больше. Но несколько ответов медленно доопределяются. Это может быть как ошибка в программе (потеря точности скорее всего). Так и неудачная стратегия.

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

Но сначала проверю вариант с потерей точности. Так как энтропия не должна расти.
Прикрепленные файлы:
47. ildarovich 7850 27.02.23 17:35 Сейчас в теме
(45)
Я упрощаю пример до 14 из 14 и гарантирую что 29 попыток не хватит


Перепроверил работу метода. Все в нем правильно. Кроме того, что стратегия выбора ответа с учетом текущей рассчитанной вероятности его правильности не самая лучшая. Она рабочая, но не самая быстрая. Это и приводило к лишним попыткам.

Получается, что для того, чтобы набрать максимум правильных ответов, нужно выбирать ответы с наибольшей вероятностью. А чтобы разведать, какие ответы правильные, ответы нужно выбирать случайным образом. Без учета рассчитанной вероятности, равновероятно. Такая стратегия быстрее сходится. Такой вот интересный контринтуитивный вывод. При переходе на эту стратегию для теста из 14 вопросов с 5 вариантами ответов метод сходится примерно за 35 - 65 прохождений теста. В среднем за 50.

Это что касается рандомизированных стратегий.

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

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

В первом прохождении теста выбираем везде первые ответы.

Во втором для вопросов 1 и 2 выбираем ответы номер 2, а остальных также первые ответы. Сравниваем число правильных ответов. Если оно не изменилось, то и первые и вторые ответы (для вопросов 1 и 2) были неверными. Если уменьшилось на два - верными были первые ответы. Если увеличилось, то верными - вторые в обоих вопросах. Если число правильных ответов выросло на один, то верным был один ответ во второй колонке, уменьшилось - в первой.

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

Еще четыре прохождения теста понадобится для вопросов 3 и 4, так как самый первый тест повторять не нужно. Итого 5 + 4 + 4 + 4 + 4 + 4 + 4 = 29 в самом худшем случае при применении этой стратегии. Которая заключается в том, что вопросы разбиваем на пары и меняем сначала только ответы на них. Следя за изменением числа правильных ответов.

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

Ну а этот спор вы проспорили.
Оставьте свое сообщение