Home

Отображение LaTeX-математики на GitHub’е с помощью MathJax’a: http://stackoverflow.com/questions/11255900/mathjax-support-in-github-using-a-chrome-browser-plugin

Скрипт, упомянутый в этом вопросе на Stack Overflow, теперь есть и здесь: https://github.com/myrix/mdlnerc/raw/master/mathjax-in-github.user.js

Содержание

1. Named Entity Recognition and Classification
   1. Maximum Entropy Markov Models
   2. Conditional Random Fields
   3. Персептроны, Boosting и произвольные классификаторы
2. Minimum Description Length
   1. Моделирование двоичной последовательности
   2. Байесовский вывод
   3. Колмогоровская сложнось
   4. Алгоритмическая вероятность
   5. Деревья решений
      1. Длина описания
      2. Поиск минимальной модели
      3. Возможные расширения

Named Entity Recognition and Classification (NERC)^{1 , 2 , 3}

Нужно выделить в тексте именованные сущности и указать их тип.

Jim bought 300 shares of Acme Corp (headquatered at San Francisco).

Type	Entity
Person	Jim
Organization	Acme Corp
Location	San Francisco

Возможны другие типы: Geopolitical Entity, Facility, Animal, Plant, Product, Money, Date, Quantity, ….

Машинное обучение: модель отображения “последовательность слов $\mapsto$ последовательность NE-тэгов”.

Типы NE-тэгов: Person, Organization, Location, …, None (означает, что слово не является NE).

Части (например, предложения) больших текстов моделируются независимо.

Maximum Entropy Markov Models (MEMM)^{4 , 5}

Вероятность $P(t_{1:n}|w_{1:n})$ последовательности тэгов $t_{1:n}$ в зависимости от последовательности лексем $w_{1:n}$:

$$ P(t_{1:n}|w_{1:n}) = \prod_{i=1}^{n}P(t_i|t_{i-1},w_i) $$

Тэг $t$ моделируется на основе предыдущего тэга $t’$ и текущего слова $w$ классификатором на основе максимальной энтропии⁶:

$$ P(t|t’,w) = P_{t’}(t|w) = \frac{1}{Z(t’,w)} \exp \left ( \sum_i \lambda_i f_i(t,w) \right ) $$

Функции признаков $f_i$ вычисляются на основе контекта $\langle t’, w \rangle$ (например, 1 если предыдущий тэг $t’$ равен None и текущее слово $w$ начинается с большой буквы, 0 в противном случае). Обычно принимают значения из $\{0, 1\}$, в общем случае из $\mathbb{R}$.

$Z(t’,w)$ — нормализующий множитель, $T$ — множество значений NE-тэгов:

$$ Z(t’,w) = \sum_{t \in T} \exp \left ( \sum_i \lambda_i f_i(t,w) \right ) $$

Параметры $\lambda_i$ оптимизируются для максимизации правдоподобия. Удобно оптимизировать логарифм правдоподобия, результат тот же самый.

$$ \log P(t|t’,w) = \log \left [ \frac{1}{Z(t’,w)} \exp \left ( \sum_i \lambda_i f_i(t,w) \right ) \right ] = \sum_i \lambda_i f_i(t,w) – \log Z(t’,w) $$

$Z(t’,w)$ не зависит от параметров $\lambda_i$, при оптимизации ее можно не учитывать. На полном обучающем корпусе мы оптимизируем

$$ \sum_{s \in S} \sum_{i=1}^{N_s} \sum_j \lambda_j f_j(t_{i-1},w_i) $$

$S$ — множество частей документа, $N_s$ — длина каждой части.

Найденные значения $\lambda_i$ также являются решением задачи поиска $P(t|t’,w,\lambda_i)$ с максимальной энтропией при соответствующих ограничениях, поэтому модель и называется Maximum Entropy.

Можно усложнить модель, введя признаки вида $f(t_{i-1},w_{1:n},i)$, зависящие от всей последовательности слов и индекса $i$ текущего тэга в этой последовательности. Также можно использовать признаки $f(t_{i-1}, t_{i-2}, \ldots)$, зависящие от двух и более предыдущих тэгов.

Conditional Random Fields (CRF)^{7 , 8}

Правдоподобие $P(\mathbf{Y}|X)$ набора $\mathbf{Y}$ величин в вершинах графа в зависимости от наблюдаемых переменных $X$ в предположении о разложимости в потенциалы на кликах:

$$ P(\mathbf{Y}|X) = \prod_{c \in C} P_c(Y_c|X) $$

$C$ — множество клик графа, $Y_c$ — множество величин в вершинах клики $c$. Теорема Хаммерсли-Клиффорда⁹ гарантирует, что таким образом представим достаточно широкий класс распределений на графах.

Моделируем потенциалы логарифмически-линейными функциями:
$$
P(\mathbf{Y}|X) \propto \exp \left ( \sum_{c \in C} \lambda_c f_c(Y_c|X) \right )
$$

Каждая функция признака $f_c(Y_c|X)$ зависит от всего наблюдаемого контекста $X$ и каждой из величин клики $Y_c$.

Для получения вероятностного распределения нужен нормализующий множитель:

$$ Z(X) = \sum_{\mathbf{y}} \exp \left ( \sum_{c \in C} \lambda_c f_c(Y_c|X) \right ) $$

Здесь $\mathbf{y}$ — конфигурация значений $\mathbf{Y}$ вершин графа. Если каждая величина может принимать $N$ значений, то таких всевозможных конфигураций $N^{|\mathbf{Y}|}$, и уже небольшое $N$ даже при относительно малом размере графа $|\mathbf{Y}|$ делают прямое вычисление $Z(X)$ невозможным. К счастью, при оптимизации, как для MEMM, $Z(x)$ можно не учитывать.

Для NERC’а в простейшем случае мы используем линейную CRF, состоящую из потенциалов пар последовательных тэгов $t_{i-1}, t_i$ и потенциалов отдельных тэгов $t_i$:

\begin{align*}
P(t_{1:n}|w_{1:n}) & = \prod_{i=1}^{n} P(t_i,t_{i-1}|w_{1:n},i) P(t_i|w_{1:n},i) \\ & \propto \prod_{i=1}^n \exp \left ( \sum_j \lambda^a_{ij} f^a_j(t_i,t_{i-1}|w_{1:n},i) + \sum_k \lambda^b_{ik} f^b_k(t_i|w_{1:n},i) \right )
\end{align*}

Введем упрощающее предположение, что параметры $\lambda^a_{ij}$ и $\lambda^b_{ik}$ совпадают для различных $i$, и будем оптимизировать относительно параметров логарифм

$$ \log P(t_{1:n}|w_{1:n}) = \sum_{i=1}^n \left [ \sum_j \lambda^a_{j} f^a_j(t_i,t_{i-1}|w_{1:n},i) + \sum_k \lambda^b_{k} f^b_k(t_i|w_{1:n},i) \right ] – \log Z(w_{1:n}) $$

Как и в MEMM, отбрасываем $\log Z(w_{1:n})$ и суммируем по всей обучающей коллекции:

$$ \sum_{s \in S} \sum_{i=1}^{N_s} \left [ \sum_j \lambda^a_{j} f^a_j(t_i,t_{i-1}|w_{1:N_s},i) + \sum_k \lambda^b_{k} f^b_k(t_i|w_{1:N_s},i) \right ] $$

Также как и в MEMM, можно усложнить модель, добавив зависимости между тройками тэгов, и вообще, зависимости между любыми подмножествами тэгов. В пределе придем к модели, в которой все $t_i$ связяны между собой:

$$ P(t_{1:n}|w_{1:n}) \propto \exp \left ( \sum_j \lambda_j f(t_{1:n}|w_{1:n}) \right ) $$

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

Персептроны^{10 , 11}, Boosting¹² и произвольные классификаторы

И для MEMM, и для CRF мы оптимизируем функцию вида

$$ \sum_{\langle T, W \rangle \in D} \sum_j \lambda_j f_j(T, W) $$

$T$ — набор тэгов части текста, $W$ — последовательность слов, наблюдаемый контекст части текста, $D$ — множество элементов обучающих данных.

Каждый элемент $T, W$ представляется вектором признаков $[f_j(T, W)]$. Фактически, мы подбираем веса $\lambda_j$ линейного классификатора на обучающем множестве векторов $[f_j(T, W)], \langle T, W \rangle \in D$, т.е. выполняем тренировку персептрона.

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

Классификация на основе векторов признаков также возможна с помощью моделей, построенных на основе boosting’а. Boosting строит агрегированный классификатор на основе признаков как простых классификаторов.

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

Minimum Description Length (MDL)^{13 , 14}

MDL (и родственный ему MML, Minimum Message Length¹⁵) применяется для поиска моделей, наиболее точно описывающих данные.

Мера качества модели $M$ по отношению к данным $D$:

$$ L(D,M) = L(D|M) + L(M) $$

$L(D|M)$ — длина описания данных $D$ на основе модели $M$, $L(M)$ — длина описания модели $M$.

Наиболее качественной моделью $\mathcal{M}$ является модель с наименьшей общей длиной описания:

$$\mathbf{M} = \operatorname*{arg\,min}_{M} L(D,M)$$

Моделирование двоичной последовательности

Данные — $0$/$1$-последовательность $x_1, \ldots, x_n$. Возможные модели:

1. $M^*$, предполагает, что $0$ и $1$ равновероятны.
2. $M_k$, $k$ может принимать значения $0, \ldots, n$, вероятности задаются как $P(0|M_k) = k/n, P(1|M_k) = (n-k)/n$

Всего $2$ возможных типа моделей, длина описания моделей $L(M)$ вычисляется следующим образом:

1. Для описания $M^*$ нужно лишь задать ее тип, для этого достаточно $\log 2$ бит.
2. При описании $M_k$ мы также задаем ее тип $\log 2$ битами, после чего кодируем $k$ как один из $n+1$ вариантов $\log [n+1]$ битами.

Для кодировки $n$ элементов данных требуется $n_0 \log [1/p_0] + n_1 \log [1/p_1]$ бит, $n_0$ и $n_1$ — количества нулей и единиц.

1. $L(D[n_0, n_1]|M^*) = n_0 \log 2 + n_1 \log 2 = n$
2. $L(D[n_0, n_1]|M_k) = n_0 \log [n/k] + n_1 \log [n/(n-k)]$

Минимум $L(D[n_0, n_1]|M_k)$ по $k$ достигается на $n_0$ (неравенство Гиббса). Длина описания данных в этом случае равна $n_0 \log [n/n_0] + n_1 \log [n/n_1]$.

Общая длина описания $L(D,M)$ выглядит так:

1. $\log 2 + n$ для $M^*$.
2. $\log 2 + \log [n+1] + n_0 \log [n/n_0] + n_1 \log [n/n_1]$ для $M_{n_0}$.

При $n$, равном $100$, первая модель предпочтительнее при $35 \le n_0 \le 65$, при $n$, равном $1000$ — при $442 \le n_0 \le 558$, при $10000$ — при $4786 \le n_0 \le 5214$. Если же нулей значительно больше или меньше, чем единиц, предпочтительнее будет модель второго типа.

Можно изменить кодировку, выбирая $k$ второго типа моделей не из $n+1$-го варианта, а из $\lceil \sqrt{n} \rceil + 1$. В этом случае описания моделей второго типа имеют меньшую длину, в то время как вероятности значений данных задаются более грубо, и, как следствие, для описания данных нужно больше бит. Cоответствующие интервалы для $100$, $1000$, $10000$ значений имеют вид $[39, 61]$, $[456, 544]$, $[4844, 5156]$.

Можно ввести новый класс моделей, задающих условные вероятности $P(x_i|x_{i-1})$. Эти модели параметризуются тремя числами: количество $N$ пар $x_{i-1}, x_i$, начинающихся с нуля, и два значения $N_1, N_2$, задающих вероятности $P(0|0), P(1|0), P(0|1), P(1|1)$ как $N_1/N, (N-N_1)/N, N_2/(n-N), (n-N-N_2)/(n-N)$. Модели их этого класса будут предпочтительнее, если в данных присутствуют выраженные зависимости $x_i$ от $x_{i-1}$.

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

Вообще, разнообразие возможных структур моделей велико.

Байесовский вывод¹⁶

По однозначному префиксному коду, сопоставляющему объектам $x$ битовые строки длины $L(x)$, можно определить вероятностную меру на объектах $x$:

$$ P(x) = 2^{-L(x)} $$

Формуле $L(D,M) = L(D|M) + L(M)$ длины описания данных $D$ на основе модели $M$ соответствует формула совместной вероятности данных и модели:

$$ 2^{-L(D,M)} = 2^{-L(D|M)} 2^{-L(M)} $$ $$ P(D,M) = P(D|M) P(M) $$

Критерию выбора модели по минимальной длине совместного описания соответствует критерий модели по максимальной совместной вероятности:

$$\mathbf{M} = \operatorname*{arg\,max}_{M} P(D,M)$$

Если мы рассматриваем фиксированный набор данных $D$, его вероятность $P(D)$ - константа, и этот критерий эквивалентен байесовскому критерию выбора модели по максимальной постериорной вероятности:

$$ \mathbf{M} = \operatorname*{arg\,max}_{M} P(M|D) $$ $$ P(M|D) = \frac{P(D|M) P(M)}{P(D)} $$

Аддитивная величина $v(M)$, определенная на моделях, может быть оценена усреднением по всем моделям по вероятности на основе имеющихся данных $D$:

$$ v {\bigg |}_D = \int\limits_{M \in \mathcal{M}} v(M) P(M|D) dM $$

Интегрирование идет по множеству моделей $\mathcal{M}$, в конечном дискретном случае превращается в суммирование. Такая оценка в общем случае точнее, чем оценка $v(\mathbf{M})$ лишь на основе самой вероятной по отношению к имеющимся данным модели.

Расширим MDL по аналогии. При работе с моделями, оценивающими некоторую величину, например, вероятность $0$ или $1$ в последовательности, или вероятность различных последовательностей тэгов $t_{1:n}$ для данной последовательности слов $w_{1:n}$, агрегируем оценки различных моделей:

$$ P(x) = \sum_{M \in \mathcal{M}’} P_M(x) P(M|D) $$ $$ P(M|D) \propto 2^{-L(D,M)} $$

В отличие от байесовского вывода, мы используем модели из некоторого множества $\mathcal{M}’$, не обязательно совпадающего с полным пространством моделей $\mathcal{M}$.

Колмогоровская сложнось^{17 , 18}

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

$$ K_U(x) = \min_{U(q) \mapsto x} L(q) $$

Сложность любого объекта для двух разных архитектур $U_1$ и $U_2$ отличается не более чем на константу (вследствие универсальности для $U_1$ существует конечный интерпретатор $U_2$), и можно отвлечься от архитектуры $U$, рассматривая общую сложность $K(x)$.

Будем моделировать набор данных $D$ произвольными программами $q$. Естественно предположить, что наиболее подходящей для описания данных является наиболее короткая программа $\mathbf{q}$, дающая на выходе эти данные $D$:

$$ \mathbf{q} = \operatorname*{arg\,min}_{q \mapsto D} L(q) $$

В ситуации, когда конкретный набор данных $D$ является одним из множества $\mathcal{D}$ возможных наборов данных, будем рассмотривать программы $q$, состоящие из двух частей $q_1 q_2$. Первая часть $q_1$ представляет собой декодер, вторая часть $q_2$, зависящая от данных $D$ — эти данные, закодированные некоторым образом. Выберем наиболее короткую программу $q_1 q_2$, вычисляющуюся в $D$:

$$ \mathbf{q}_1 \mathbf{q}_2 = \operatorname*{arg\,min}_{q_1 q_2 \mapsto D} L(q_1 q_2) $$

Длина выбранной программы $\mathbf{q}_1 \mathbf{q}_2$ равна алгоритмической сложности данных $D$. Выбранная программы $q_1 q_2$ была получена оптимизацией по совместной длине описания $L(q_1 q_2)$, которая складывается из длины описания способа кодировки $L(q_1)$ и длины закодированных данных $L(q_2)$:

$$ L(q_1 q_2) = L(q_1) + L(q_2) $$

Длина закодированных данных зависит от собственно данных и способа кодировки:

$$ L(q_1 q_2) = L(q_1) + L(D|q_1) $$

Принцип MDL является аппроксимацией метода выбора модели на основе алгоритмической сложности, в MDL вместо всех вычислимых моделей мы рассматриваем модели из некоторого ограниченного класса $\mathcal{M}$. Связано это в том числе с тем, что $K(x)$ не является эффективно вычислимой, и нет гарантии, что искомая программа $\mathbf{q}$, минимизирующая длину описания данных, будет найдена.

Алгоритмическая вероятность^{17 , 19}

При условии, что вычислительная архитектура $U$ префиксная (ни одна программа не является префиксом другой), можно определить вероятность программ $P(q)$ на основе их длины:

$$ P(q) \propto 2^{-L(q)} $$

Используя эту вероятность, можно определить вероятность любого вычислимого объекта $x$ на основе вероятности программ, вычисляющихся в этот объект:

$$ P(x) \propto \sum_{q \mapsto x} 2^{-L(q)} $$

Моделируем набор данных $D$ всевозможными вычислимыми функциями $q_1$. Вероятность модели $P(q_1)$ определяется на основе программ $q$, вычисляющихся в данные $D$ и состоящих из функции $q_1$ и битовой строки $q_2(D|q_1)$, являющейся данными $D$, закодированными для распаковки этой функцией:

$$ P(q_1) \propto \sum_{q \mapsto D} 2^{-L(q)} $$ $$ q = q_1 q_2(D|q_1) $$ $$ L(q) = L(q_1) + L(D|q_1) $$

Используя эту вероятность, мы можем оценивать величины $v$ на основе имеющихся данных $D$ как

$$ v {\bigg |}_D = \frac{1}{Z(D)} \displaystyle \sum_{q \mapsto D} v(q) 2^{-L(q)} $$ $$ Z(D) = \sum_{q \mapsto D} 2^{-L(q)} $$

Можно сказать, что точно так же как выбор модели на основе MDL является аппроксимацией выбора модели-программы на основе алгоритмической сложности, оценка на основе расширенного MDL * является аппроксимацией оценки на основе алгоритмической вероятности.

Деревья решений^{20 , 21}

Деревья решений (Decision Trees, DT) применяются для классификации объектов на основе атрибутов. Объекты характеризуются $N$ атрибутами $F_1, \ldots, F_N$ и относятся к одному из $M$ классов $C_1, \ldots, C_M$.

Рекурсивное определение дерева решений:

1. Узел-лист, помеченный классом $C$.
2. Узел решения, помеченный атрибутом $F$ и имеющий $|F|$ узлов-потомков, $|F|$ — число возможных значений атрибута $F$.

Классификация объекта на основе значений $f_1, \ldots, f_N$ его атрибутов по дереву решений $t$:

1. Если $t$ — узел-лист, помеченный классом $C$, результатом классификации является класс $C$.
2. Если $t$ — узел решения, помеченный атрибутом $F_i$ с узлами-потомками $t_1, \ldots, t_{|F_i|}$, мы выбираем узел-потомок в зависимости от значения $f_i$ и продолжаем классификацию объекта по этому узлу-потомку.

Деревья решений задают функции классификации $C(f_1, \ldots, f_N)$. Деревья аналогичной структуры также могут задавать функции правдоподобия $P(c|f_1, \ldots, f_N)$, для этого узлы-листья вместо классов $C$ помечаются распределениями классов $P( c )$.

Рассмотрим обучение с учителем на основе принципа MDL. Каждый объект из набора $n$ объектов харатеризуется вектором атрибутов $\mathbf{f}$ и классом $c$. Необходимо выбрать дерево решений, задающее функцию правдоподобия $P(c|\mathbf{f})$, наиболее точно описывающую имеющиеся у нас данные.

Зададим способ описания моделей и данных на основе моделей и определим соответствующие длины $L(M)$ и $L(D|M)$, после чего предложим процедуру поиска модели с наименьшей длиной описания.

Длина описания

Задаем пространство моделей и определяем длину их описания $L(M)$. Для описания узла-листа нужно задать распределение $P( c )$. Как и при моделировании двоичной последовательности *, есть два варианта:

1. Равновероятное распределение $P(C_i) = 1/M$.
2. Распределение, характеризующееся параметрами $k_1, \ldots, k_M$:

$$ P(C_i) = \frac{k_i}{k} $$ $$ k = \sum_{i=1}^{M} k_i $$

$k$ — число объектов из обучающей выборки, которые при классификации попадают в рассматриваемый узел-лист, $k_i$ — число таких объектов, имеющих класс $C_i$.

Задание варианта требует $\log 2$ бит, задание коэффициентов $k_i$ второго варианта при известном $k$ и $M$ требует $\log K(M, k)$ бит. $K(M, k)$ — количество композиций $k$ из $M$ неотрицательных слагаемых ²²:

$$ K(M, k) = {M+k-1 \choose k-1} $$

Для описания узла решения необходимо задать его атрибут и описать его узлы-потомки. Для задания атрибута требуется $\log N^{*}$ бит, $N^{*}$ — число атрибутов, еще не использовавшихся на пути от корня дерева к рассматриваемому узлу решения.

Зададим описание данных на основе модели и опишем его длину $L(D|M)$. Дерево решений разделяет обучающие данные на непересекающиеся множества, по множеству на каждый узел-лист.

Описанием множества из $n$ объектов является последовательность $c_1 \ldots c_n$ классов этих объектов. Длина такого описания:

$$ - \sum_{i=1}^{n} \log P(c_i) $$

$P(c_i)$ — вероятность класса $i$-го объекта в соответствие с распределением $P( C )$, заданным в листе.

Вполне возможно, что в большинстве листьев большая часть значений векторов-параметров будет равна 0. В этом случае можно сменить схему кодирования на следующую:

• Задаем с помощью $\log [M+1]$ бит число $m$ от $0$ до $M$, $0$ — равномерная модель, от $1$ до $M$ — число ненулевых компонент вектора параметров.
• Если $1 \le m \le M$, задаем положительные значения вектора параметров $k_{i_1}, \ldots, k_{i_m}$ с помощью $\log C(m-1, k-1)$ бит. $C(m-1, k-1)$ — биномиальный коэффициент, количество композиций $k$ из $m$ положительных слагаемых ²³.

Поиск минимальной модели

Используем для выбора минимальной модели жадный поиск. Общая схема:

1. На шаге $1$ выбираем из первичных альтернатив:

$$ \mathbf{T}_1 = \operatorname*{arg\,min}_{T_1, \ldots, T_{k_1}} L(D,T_i) $$

2. На шаге $n+1$ выбираем из вариантов преобразования выбора на шаге $n$:

$$ \mathbf{T}_{n+1} = \operatorname*{arg\,min}_{T_1, \ldots, T_{k_{n+1}}} L(D,T_i) $$ $$ T_i = A_i(\mathbf{T}_{n}) $$

Выполняем шаги поиска, пока $L(D,\mathbf{T}_{n+1}) < L(D,\mathbf{T}_{n})$. Результатом поиска объявляем
$$
\mathbf{T}^* = \operatorname*{arg\,min}_{\mathbf{T}_i} L(D, \mathbf{T}_i)
$$

Начинаем с обучающего множества из $n$ объектов $\langle \mathbf{f}_1, c_1 \rangle, \ldots, \langle \mathbf{f}_n, c_n \rangle$. Первичными альтернативами являются деревья, состоящие из одного узла-листа. Узлы-листья задают распределения классов $P( C )$. Варианты:

1. $T_1$, равномерное распределение.
2. $T_2$, распределение, заданное с помощью вектора параметров.

Для каждого из вариантов $T_1, T_2$ мы вычисляем длину описания данных $L(D|T_i)$ и выбираем вариант с наименьшим значением длины описания.

Построим множество преобразований модели-дерева $\mathbf{T}_{n}$, рассматривая узлы-листья с непустыми множествами $F$ и $O$. $F$ — множество атрибутов, еще не использовавшихся на пути от корня дерева к узлу-листу, $O$ — множество объектов обучающей выборки, отправляемых деревом в узел-лист.

• Для каждого такого узла-листа перебираем атрибуты $F_i \in F$. По каждому атрибуту строим узел решения, разделяющий множество $O$ на подмножества $O_1, \ldots, O_{|F_i|}$ по числу возможных значений атрибута. Каждому подмножеству соответствует узел-лист с двумя вариантами модели распределения $P( c )$ классов этого подмножества.
• Атрибуту $F_i$ узла-решения и моделям $T_{1}, \ldots, T_{|F_i|}$ распределений в узлах-листьях соответствует преобразование модели $\mathbf{T}_{n}$, получаемое заменой рассмотриваемого узла-листа на дерево высоты $2$ из построенных узла решения и узлов-листьев.
• Длины описаний узлов-листьев этих деревьев высоты $2$ и множеств объектов данных, относящихся к этим узлам-листьям, входят в итоговую длину описания как независимые слагаемые, и мы можем выбирать модели распределений $T_{1}, \ldots, T_{|F_i|}$ независимо друг от друга.
• Длины описаний этих деревьев высоты $2$ и множеств объектов данных, относящихся к этим деревьям, также входят в итоговую длину описаний как независимые слагаемые, и мы можем рассматривать преобразования узлов-листьев модели $\mathbf{T}_{n}$ независимо друг от друга.

Общее число вариантов преобразований модели $\mathbf{T}_{n}$:

$$ \sum_{k} \sum_{i=1}^{|F^k|} 2 |F_i| $$

$k$ пробегает подходящие узлы-листья модели, $i$ идет по множествам $F^k$ подходящих атрибутов этих узлов-листьев.

Возможные расширения

Графы решений ²⁴.

Расширенный MDL *. В этом случае при выборе следующей модели $\mathbf{T}_{n+1}$ мы не отбрасываем неподошедшие варианты, а сохраняем их вместе с их итоговыми длинами описаний для последующего использования.

Ссылки

¹ Wikipedia: Named entity recognition.

² David Nadeau and Satoshi Sekine. A survey of named entity recognition and classification. Lingvisticae Investigationes, 30(1):3–26, January 2007.

³ Lev Ratinov and Dan Roth. Design Challenges and Misconceptions in Named Entity Recognition. Proceedings of the Thirteenth Conference on Computational Natural Language Learning, pages 147–155, 2009.

⁴ Wikipedia: Maximum-entropy Markov model.

⁵ Andrew McCallum, Dayne Freitag, and Fernando Pereira. Maximum Entropy Markov Models for Information Extraction and Segmentation. Proceedings of the 17th International Conference on Machine Learning, pages 591–598, 2000.

⁶ Wikipedia: Maximum entropy classifier.

⁷ Wikipedia: Conditional random field.

⁸ Lafferty, J., McCallum, A. and Pereira, F., 2001. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. Proceedings of the Eighteenth International Conference on Machine Learning, pp. 282 – 289.

⁹ Wikipedia: Hammersley–Clifford theorem.

¹⁰ Collins, M., 2002. Discriminative training methods for hidden Markov models: theory and experiments with perceptron algorithms. Proceedings of the ACL-02 conference on Empirical methods in natural language processing, pp.1–8.

¹¹ Collins, M., 2004. Presentation on discriminative training methods for hidden Markov models: theory and experiments with perceptron algorithms.

¹² Friedman, J., Hastie, T. and Tibshirani, R., 2000. Additive Logistic Regression: A Statistical View of Boosting. The Annals of Statistics, 28(2), pp.337–407.

¹³ Wikipedia: Minimum description length.

¹⁴ Rissanen, J., 1983. A Universal Prior for Integers and Estimation by Minimum Description Length. The Annals of Statistics, 11(2), pp.416–431.

¹⁵ Wikipedia: Minimum message length.

¹⁶ Wikipedia: Bayesian inference.

¹⁷ Li, M. and Vitányi, P., 2008. An Introduction to Kolmogorov Complexity and Its Applications 3rd ed., Springer.

¹⁸ Wikipedia: Kolmogorov complexity.

¹⁹ Wikipedia: Algorithmic probability.

²⁰ Wikipedia: Decision tree learning.

²¹ Wallace, C.S. and Patrick, J.D. 1993. Coding Decision Trees. Machine Learning, 11, 7–22.

²² Wikipedia: Композиция числа, “…разрешить нулевые части, то…”.

²³ Wikipedia: Композиция числа, Количество композиций.

²⁴ Tan, P.J. and Dowe, D.L. 2002. MML Inference of Decision Graphs with Multi-Way Joins. Proceedings of the 15th Australian Joint Conference on Artificial Intelligence, 131–142.