HMM Scalable

16 mins read time
байесовские методы открытый исходный код большие данные

Код: GitHub

Этот инструмент командной строки разработан для построения скрытых марковских моделей (HMM) на основе больших наборов данных. В частности, он ориентирован на специфический тип HMM, применяемый в сфере образования и известный как модель байесовского отслеживания знаний (Bayesian Knowledge Tracing, BKT). Утилита написана на языках C/C++. Работа над проектом началась в то время, когда автор занимал должность постдока в Институте человеко-машинного взаимодействия при Университете Карнеги — Меллона. Исходный код проекта распространяется под лицензией BSD-new (3-пунктная лицензия BSD).

Байесовское отслеживание знаний

Байесовское отслеживание знаний (BKT) — это подход к моделированию поведения пользователей, широко применяемый в области интеллектуальных обучающих систем (ITS). В ITS принято присваивать задачам (а также отдельным шагам решения задач), над которыми работают учащиеся, специальные метки, обозначающие «кванты знаний» (их также называют навыками). Когда учащийся пытается решить задачу или выполнить отдельный шаг решения, считается, что он практикует определенный навык (или навыки). Модель учащегося (одной из разновидностей которой является BKT) выполняет логический вывод, определяя, был ли усвоен тот или иной навык, на основе последовательности правильных и неправильных попыток решения задач (или их отдельных шагов). Для оценки степени усвоения навыков учащегося в модели BKT используется математический аппарат скрытых марковских моделей. В структуре BKT выделяются два типа узлов: узлы бинарного состояния (по одному на каждый навык), которые отражают степень усвоения навыка и могут принимать значения «усвоен» или «не усвоен», а также узлы бинарных наблюдений (также по одному на каждый навык), которые фиксируют результат попытки и могут принимать значения «правильно» или «неправильно». Каждый навык в стандартной модели BKT характеризуется следующими параметрами:

  1. $p-init$ или $p(Lo)$ — вероятность того, что навык был известен априори;
  2. $p-learn$ или $p(T)$ — вероятность того, что навык перейдет в состояние «усвоен» после попытки выполнения упражнения;
  3. $p-forget$ или $p(F)$ — вероятность того, что навык перейдет в состояние «не усвоен» после попытки выполнения упражнения. Традиционно параметр $p-forget$ принимается равным нулю и не учитывается при подсчете общего числа параметров модели;
  4. $p-slip$ или $p(S)$ — вероятность того, что усвоенный навык будет применен неверно;
  5. $p-guess$ или $p(G)$ — вероятность того, что неусвоенный навык будет применен верно.

Параметры модели BKT могут быть представлены в векторной или матричной форме. Вектор априорных вероятностей $\Pi$ содержит параметр $p-init$. Вектор априорных вероятностей состоит из $N$ элементов (в стандартной модели BKT $N=2$). В рамках данного обсуждения мы будем исходить из того, что $p-init$ является первым элементом вектора $\Pi$. Параметр $p-learn$ входит в состав матрицы переходов $A$, которая описывает вероятности смены состояний усвоения навыка и имеет размерность $N \times N$. Отсутствие забывания моделируется путем присвоения нулевого значения элементу $A[1,2]$ (переход из состояния «усвоен» в состояние «не усвоен»). Параметр $p-learn$ соответствует элементу $A[2,1]$ (переход из состояния «не усвоен» в состояние «усвоен»). Параметры $p-guess$ и $p-slip$ задаются в матрице наблюдений $B$, имеющей размерность $N \times M$, где $M$ — количество возможных наблюдений (в стандартной модели BKT $M=2$). Первый столбец этой матрицы соответствует наблюдению «верный ответ», второй — наблюдению «неверный ответ». В стандартной модели BKT с двумя возможными наблюдениями параметр $p-guess$ соответствует элементу $B[2,1]$ (неусвоенный навык, но верный ответ), а параметр $p-slip$ — элементу $B[1,2]$ (усвоенный навык, но неверный ответ).

$$ \Pi= \begin{bmatrix} p(L_0)& 1-p(L_0) \end{bmatrix} $$
$$ A = \begin{bmatrix} 1 & 0 \\ p(T) & 1-p(T) \end{bmatrix} $$
$$ B = \begin{bmatrix} 1-p(S) & p(S) \\ p(G) & 1-p(G) \end{bmatrix} $$

Более подробную информацию о BKT см. в [1]. В источнике [2], среди прочего, обсуждается, как может быть реализована подгонка параметров HMM (скрытой марковской модели) с использованием градиентных методов. В [3] и [4] рассматриваются дополнительные темы, имеющие отношение к реализации данной модели.

Получение и компиляция кода

Открытая версия стандартного кода BKT доступна в виде репозитория в GitHub: https://github.com/myudelson/hmm-scalable. Если у вас установлена ​​утилита git, используйте следующую команду для получения исходного кода:

git clone https://github.com/myudelson/hmm-scalable

Для компиляции выполните команду make all. Если вы работаете в среде Linux, компиляторы g++/gcc и библиотека Open MP, скорее всего, уже установлены в вашей системе. Пользователям Mac OS потребуется установить инструменты командной строки Xcode (Xcode command line tools), выполнив команду xcode-select --install. Компиляторы g++/gcc с поддержкой Open MP (которые по умолчанию больше не входят в стандартную поставку Mac OS X) можно загрузить с сайта hpc.sourceforge.net. Если вы используете Windows, вам может потребоваться установить среду cygwin, чтобы обеспечить доступность компиляторов g++/gcc; при этом не забудьте также установить утилиту make.

Данные

Входной файл данных должен представлять собой текстовый файл с кодировкой концов строк в формате Unix. Формат файла — четыре столбца, разделенных символами табуляции: наблюдение, студент, задача/шаг задачи, навык(и). «Наблюдение» — это целочисленное значение, нумерация которого начинается с 1. Для модели BKT с двумя наблюдениями мы рекомендуем использовать значение 1 для правильного ответа и 2 — для неправильного. «Студент» — это строковая метка; такой же меткой является «задача» или «шаг задачи» (в зависимости от того, какой уровень детализации вы предпочитаете). «Навык» — это также строковая метка. Если для одной записи указано несколько навыков, их метки должны быть разделены выбранным вами символом-разделителем (не используйте символ табуляции). Ниже приведен пример входного файла, содержащий несколько строк. В данном примере в качестве разделителя используется символ ~ (тильда).

-- входной файл --
2   student_001 unit1-section1-problem5-step1  addition~multiplication
1   student_001 unit1-section1-problem5-step2  multiplication
1   student_001 unit1-section1-problem5-step3  addition
-- входной файл --

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

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

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

-- файл модели --
SolverId    1.1
nK    1
nG    1
nS    2
nO    2
Null skill ratios      1.0000000      0.0000000
0    multiplication-skill
PI    0.45000000    0.55000000
A    1.00000000  0.00000000    0.40000000    0.60000000
B    0.79000000    0.21000000    0.22000000    0.78000000
-- файл модели --

В приведенном выше примере файла модели мы видим спецификацию алгоритма решателя (которая будет рассмотрена ниже), один навык (nK=1), одного учащегося в наборе данных (nG=1), а также два скрытых состояния и два наблюдения (nS и nO соответственно). Нумерация навыков начинается с нуля. Название навыка — «multiplication-skill». Строки с префиксами PI, A и B соответствуют матрицам априорных вероятностей, переходов и наблюдений, записанным построчно. Таким образом, первый элемент матрицы PI — это p(Lo)=0,45; третий элемент матрицы A — это p(T)=0,4; а второй и третий элементы матрицы B — это p(S)=0,21 и p(G)=0,22 соответственно.

Файл прогнозов для стандартной модели BKT с nO=2 наблюдениями будет содержать две колонки, разделенные символами табуляции. Первая колонка соответствует оцененной моделью априорной вероятности того, что учащийся даст правильный ответ для данного конкретного наблюдения. Вторая колонка представляет собой дополнение к вероятности правильного ответа — то есть вероятность ошибки (см. пример ниже).

-- файл прогнозов --
0.73    0.27
0.88    0.12
0.94    0.06
0.99    0.01
-- файл прогнозов --

Обучение моделей BKT

Утилита trainhmm имеет следующую сигнатуру запуска:

trainhmm [опции] входной_файл [[файл_модели] файл_прогнозов]

Опции:

-s : структура.метод[.настройка метода]; структуры: 1 — по навыкам, 2 — по пользователям; методы: 1 — Баума-Велша, 2 — градиентный спуск, 3 — метод сопряженных градиентов; для метода сопряженных градиентов доступны 4 настройки: 1 — Полака-Рибьера, 2 — Флетчера-Ривза, 3 — Хестенеса-Штифеля, 4 — Дая-Юаня. Например, -s 1.3.1 означает структуру по навыкам (классическую) с использованием метода сопряженных градиентов и формулы Хестенеса-Штифеля; -s 2.1 означает структуру по пользователям, подгоняемую с помощью метода Баума-Велша.

-S : выполнение масштабирования прямых/обратных переменных: 0 — выключено (по умолчанию), 1 — включено. Допустимо только для метода Баума-Велша (настройка -s 1.1); в противном случае автоматически устанавливается значение «выключено».

-e : допустимое отклонение для критерия останова (по умолчанию: 0.01 для изменения параметров); может быть задано как изменение логарифмического правдоподобия в пересчете на одну точку данных, например: -e 0.00001,l.

-i : максимальное количество итераций (по умолчанию: 200).

-q : тихий режим (без вывода информации): 0 — нет (по умолчанию), 1 — да.

-n : количество скрытых состояний; должно быть равно 2 или более (по умолчанию: 2).

-0 : начальные значения параметров (разделенные запятыми) для априорных вероятностей, вероятностей переходов и вероятностей эмиссии; при этом последнее значение из каждого вектора (строки матрицы) пропускается, так как сумма значений в каждом наборе должна быть равна 1. Значение по умолчанию: 0.5,1.0,0.4,0.8,0.2.

-l : нижние границы для параметров (разделенные запятыми) — для априорных вероятностей, вероятностей переходов и вероятностей эмиссии (без пропуска значений). Значение по умолчанию: 0,0,1,0,0,0,0,0,0,0.

-u : верхние границы для параметров (разделенные запятыми) — для априорных вероятностей, вероятностей переходов и вероятностей эмиссии (без пропуска значений). Значение по умолчанию — 1,1,1,1,1,1,1,0.3,0.3,1, при этом параметры $p-slip$ (ошибка по невнимательности) и $p-guess$ (угадывание) ограничены сверху значением 0.3.

-c : задание весового коэффициента C и центроидов для L2-регуляризации; пустое значение (по умолчанию). Для стандартной модели BKT — 4 числа, разделенных запятыми: весовой коэффициент C для штрафа и центроиды для матриц PI, A и B соответственно. Если используется для модели iBKT с учетом индивидуальных особенностей учащихся (student effects), используются 8 значений: 4 основных и 4 дополнительных значения для матриц, специфичных для учащихся. Например: -c 1.0,0.5,0.5,0.0.

-f : режим подгонки модели подразумевая, что есть всего один навык: 0 — нет (по умолчанию); 1 — выполнить подгонку как для одного навыка и использовать полученные параметры в качестве начальной точки для многонавыковой модели; 2 — принудительно выполнить подгонку только для одного навыка.

-m : вывод метрик качества подгонки модели (AIC, BIC, RMSE): 0 — нет (по умолчанию); 1 — да. Чтобы указать, для какого наблюдения следует выводить метрики, перечислите его номер после запятой. Например: -m 0; -m 1 (по умолчанию подразумевается наблюдение 1); -m 1,2 (вычислить метрики для наблюдения 2). Несовместимо с опцией -v.

-v : параметры кросс-валидации: количество блоков данных, тип стратификации и целевое состояние для валидации, а также файл ввода/вывода для блоков данных. Значение по умолчанию — 0 (кросс-валидация не выполняется). Примеры: -v 5,i,2 — 5 блоков данных, стратификация по задачам/шагам (item-stratified), прогнозирование состояния 2; -v 10 — 10 блоков данных, стратификация по учащимся (subject-stratified), прогнозирование состояния 1 (по умолчанию) — или, как вариант, -v 10,g,1; -v 5,n,2,folds.txt,o — 5 блоков данных без стратификации (unstratified), прогнозирование состояния 2, [o]вывод информации о фолдах в файл folds.txt; в случае же -v 5,n,2,folds.txt,i информация о фолдах, наоборот, [i]считывается из указанного файла.

-p : вывод прогнозов модели для обучающей выборки: 0 — нет (по умолчанию); 1 — да, 2 — да, с дополнительным выводом вероятностей состояний; работает совместно с параметрами -v и -m.

-U : управляет тем, как обновляется распределение вероятностей состояний. Использует следующий формат: -U r|g[,t|g], где первый символ определяет, как при прогнозировании обрабатываются известные наблюдения; второй — как обрабатываются неизвестные наблюдения; а третий — нужно ли выводить априорные вероятности. Обработка известных наблюдений: r — использовать (раскрывать) фактические наблюдения для обновления распределения вероятностей состояний (имеет смысл при моделировании работы реальной системы); g — «угадывать» наблюдение на основе прогнозируемых исходов (arg max) — более уместно при сравнении моделей (чтобы никакая информация о фактическом наблюдении не использовалась). Обработка неизвестных наблюдений (обозначенных символом . — точка): t — использовать только матрицу переходов; g — «угадывать» наблюдение. Значение по умолчанию (если параметр опущен) — -U r,t. Например, параметр -U g,g потребует «угадывания» того, каким было наблюдение, на основе параметров модели и текущих значений вероятностей распределения состояний.

-d : разделитель для случаев, когда одному наблюдению соответствует несколько навыков; по умолчанию — один навык на одно наблюдение; в противном случае указывается символ-разделитель (например, -d ~).

-b : интерпретировать входной файл как бинарный файл, созданный из текстового файла с помощью утилиты inputconvert.

-B : блокировать переоценку параметров априорных вероятностей, переходов или эмиссий соответственно (значение по умолчанию — -B 0,0,0); например, чтобы заблокировать переоценку вероятностей переходов, укажите -B 0,1,0.

-P : использовать параллельную обработку. Значение по умолчанию — 0 (параллельная обработка отключена); 1 — выполнять подгонку параметров для отдельных навыков/студентов независимо друг от друга; 2 — выполнять подгонку для отдельных последовательностей внутри каждого навыка/студента независимо друг от друга.

-o : помимо вывода информации в консоль, записывать результаты в файл, указанный в данном параметре (по умолчанию параметр пуст, и дополнительный вывод в файл не выполняется). # Использование моделей для прогнозирования

Утилита predicthmm имеет следующий синтаксис запуска:

predicthmm [options] input_file model_file [predicted_response_file]

Опции:

-q : тихий режим (без вывода информации); 0 — нет (по умолчанию), или 1 — да

-m : вывод метрик качества подгонки модели (AIC, BIC, RMSE); 0 — нет (по умолчанию), 1 — да. Чтобы указать, для какого наблюдения следует выводить метрики, перечислите его номер после запятой. Например: -m 0, -m 1 (по умолчанию подразумевается наблюдение 1), -m 1,2 (вычислить метрики для наблюдения 2). Несовместимо с опцией -v.

-d: разделитель для случаев, когда одному наблюдению соответствует несколько навыков; если указано одно наблюдение на навык — значение по умолчанию; в противном случае указывается символ-разделитель, например: -d ~.

-b: рассматривать входной файл как бинарный файл, созданный из текстового файла с помощью утилиты inputconvert.

-p: выводить прогнозы модели для обучающей выборки. 0 — нет (по умолчанию), 1 — да; 2 — да, с дополнительным выводом вероятностей состояний; работает совместно с параметрами -v и -m.

-U: управляет способом обновления распределения вероятностей состояний. Использует следующий формат: -U r|g[,t|g], где первый символ определяет, как при прогнозировании обрабатываются известные наблюдения; второй — как обрабатываются неизвестные наблюдения; а третий — следует ли выводить априорные вероятности. Обработка известных наблюдений: r — использовать фактические наблюдения для обновления распределения вероятностей состояний (имеет смысл при моделировании работы реальной системы); g — «угадывать» наблюдение на основе прогнозируемых исходов (arg max) — более уместно при сравнении моделей (чтобы никакая информация о фактическом наблюдении не использовалась). Обработка неизвестных наблюдений (обозначенных символом . — точка): t — использовать только матрицу переходов; g — «угадывать» наблюдение. Значение по умолчанию (если параметр опущен): -U r,t. Например, параметр -U g,g потребует «угадывания» того, каким было наблюдение, на основе параметров модели и текущих значений распределения вероятностей состояний.

Примеры

Небольшой файл с примером данных toy_data.txt сгенерирован с использованием следующих параметров BKT: pLo=0.4, pT=0.35, pS=0.25, pG=0.12. Чтобы построить BKT-модель для этих данных с использованием EM-алгоритма, выполните следующую команду:

./trainhmm -s 1.1 -m 1 -p 1 toy_data.txt model.txt predict.txt

Точность полученной модели составит 90%, среднеквадратичная ошибка (RMSE) — 0,302691, а найденные параметры BKT будут следующими: pLo=0,00000000, pT=0,16676161, pS=0,00044059, pG=0,00038573. Общее значение логарифмического правдоподобия при этом возрастает с 9,3763477 до 10,4379501 ​​за 3 итерации.

Если же строить BKT-модель методом градиентного спуска, используя аргумент -s 1.2, то найденные параметры составят: pLo=0,00000000, pT=0,3095828498, pS=0,18955371, pG=0,16195590; точность при этом останется на уровне 90%, а RMSE составит 0,344145. Логарифмическое правдоподобие изменится с 9,3763477 до 8,0992564 после 19 итераций.

Чтобы сгенерировать прогнозы на основе ранее построенной модели, выполните следующую команду:

./predicthmm -p 1 toy_data_test.txt model.txt predict.txt

Для полноценного тестирования этого инструмента можно попробовать применить его к набору данных KDD Cup 2010, предоставленному Центру наук об обучении Питтсбурга (Pittsburgh Science of Learning Center) компанией Carnegie Learning Inc. Этот набор данных можно скачать (после быстрой регистрации) по ссылке: http://pslcdatashop.web.cmu.edu/KDDCup/. Данный набор включает в себя обучающую выборку и набор данных для соревнований (challenge set). Для тестирования инструмента загрузите набор данных Algebra I challenge set, содержащий около 9 миллионов транзакций, выполненных более чем 3300 студентами. Файл с обучающими данными необходимо преобразовать в формат, требуемый инструментом. См. приведенные ниже команды оболочки (shell), выполняющие это преобразование.

gawk -F"\t" 'BEGIN{OFS="\t"} {if(NR==1)next; skill=$20; gsub("~~", "~", skill); if(skill=="") skill="."; else { skill=$3"__"skill; gsub(/~/, "~"$3"__",skill);} print 2-$14,$2,$3"__"$4,skill;}' algebra_2008_2009_train.txt > a89_kts_train.txt

Чтобы построить модель BKT (отслеживания знаний) для этого набора данных с использованием метода градиентного спуска, а также вычислить метрики качества подгонки и выполнить прогнозирование, выполните следующую команду:

./trainhmm -s 1.2 -d ~ -m 1 -p 1 a89_kts_train.txt model.txt predict.txt

В зависимости от конфигурации вашего оборудования, построение модели должно занять примерно 1–2 минуты.

Литература

  1. Corbett, A. T., and Anderson, J. R.: Knowledge tracing: Modeling the acquisition of procedural knowledge. User Modeling and User-Adapted Interaction, 4(4), 253-278. (1995)

  2. Levinson, S. E., Rabiner, L. R., and Sondhi, M. M.: An Introduction to the Application of the Theory of Probabilistic Functions of a Markov Process to Automatic Speech Recognition. Bell System Technical Journal, 62(4): 1035-1074. (1983)

  3. Условия Вольфе. (20 января 2016). В: Википедия — свободная энциклопедия. http://en.wikipedia.org/wiki/Wolfe_conditions

  4. Нелинейный метод сопряжённых градиентов. (22 февраля 2016). В: Википедия — свободная энциклопедия. http://en.wikipedia.org/wiki/Nonlinear_conjugate_gradient_method