14.07.2020 08:40
0 1200 Источник

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


got idea!


1 Дискретные признаки


Чтобы закодировать объект, описываемый только дискретными признаками, нам нужно вычислить вспомогательные битово-строчные представления значений каждого признака. Мы предполагаем, что эксперт в состоянии связать эти значения в отношении "общий"/"частный". Упорядочение должно образовывать нижнюю полурешетку после добавления специального значения 'null' (с сокращением '_' в некоторых случаях), чтобы обозначить тривиальное (отсутствующее) сходство между значениями заданного признака у сравниваемых объектов.


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


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


Современная формулировка фундаментальной теоремы АФП утверждает


Для каждой конечной решетки $\langle{L,\wedge,\vee}\rangle$ пусть $G$ будет (над)множеством всех $\wedge$-неразложимых элементов и $M$ будет (над)множеством всех $\vee$-неразложимых элементов. Для $gIm\Leftrightarrow{g\geq{m}}$ выборка $(G,M,I)$ породит решетку всех кандидатов $L(G,M,I)$, которая изоморфна первоначальной решетке $\langle{L,\wedge,\vee}\rangle$.


Элемент $x\in{L}$ решетки $\langle{L,\wedge,\vee}\rangle$ называется $\vee$-неразложимым, если $x\neq\emptyset$ и для всех $y,z\in{L}$ $y<x$ и $z<x$ влекут $y\vee{z}<x$.
Элемент $x\in{L}$ решетки $\langle{L,\wedge,\vee}\rangle$ называется $\wedge$-неразложимым, если $x\neq\textbf{T}$ и для всех $y,z\in{L}$ $x<y$ и $x<z$ влекут $x<y\wedge{z}$.


Решетка ниже содержит $\wedge$-неразложимые элементы, отмеченные красным цветом, $\vee$-неразложимые элементы, отмеченные синим.


irreducible elements


Фундаментальная теорема (первоначально доказанная проф. Рудольфом Вилле с помощью выборки $(L,L,\geq)$) задает минимальную выборку вида


G\M h i j k
a 1 1 1 0
b 0 1 1 1
c 1 1 0 0
d 1 0 1 0
f 0 1 0 1
g 0 0 1 1

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


Отметим, что выборка Вилле требует 121 бит, а новая выборка нуждается только в 24 битах!


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


  1. Топологически сортируем элементы нижней полурешетки.
  2. В матрице порядка $\geq$ ищем столбцы, которые совпадают с побитовым умножением предыдущих (каждый такой столбец соответствует $\vee$-приводимому элементу).
  3. Все найденные ($\vee$-приводимые) столбцы удаляются.
  4. Строки оставшейся матрицы задают коды соответствующих значений.

Этот алгоритм являются частью обеих CPython-библиотек: 'vkfencoder' внутри конструктора класса vkfencoder.XMLImport и 'vkf' внутри конструктора класса vkf.FCA. Разница — в источнике данных: vkf.FCA читает такблицу БД под управлением MariaDB, а vkfencoder.XMLImport читает XML файл.


2 Непрерывные признаки


Мы обсуждаем шаги кодирования непрерывных признаков в соответствии с порядком их изобретения. Сначала мы применим идею системы C4.5 обучения деревьям решений для разделения области значений переменной на подынтервалы с использованием энтропийных методов.
После этого мы закодируем появление значения в некотором подынтервале битовой строкой таким образом, чтобы побитовое умножение соответствовало выпуклой оболочке сравниваемых подынтервалов.
Наконец, мы рассмотрим, как комбинировать несколько признаков, чтобы получить их дизъюнкцию или импликации. Ключом является логистическая регрессия между признаками.


2.1 Энтропийный подход


Когда мы имеем непрерывный признак, его область значений должна быть разбита на несколько подынтерваловв с различным влиянием на целевое свойство. Чтобы выбрать корректные пороги мы свяжем этот признак и целевое свойство через энтропию.


Путь $E=G\cup{O}$ будет дизъюнктным объединением обучающих примеров $G$ и контр-примеров $O$. Интервал $[a,b)\subseteq\textbf{R}$ значений непрерывного признака $V:G\to\textbf{R}$ порождает три подмножества $G[a,b)=\lbrace{g\in{G}: a\leq{V(g)}<b}\rbrace,$ $O[a,b)=\lbrace{g\in{O}: a\leq{V(g)}<b}\rbrace$ и
$E[a,b)=\lbrace{g\in{E}: a\leq{V(g)}<b}\rbrace$.


Энтропия интервала $[a,b)\subseteq\textbf{R}$ значений непрерывного признака $V:G\to\textbf{R}$ равна


${\rm{ent}}[a,b)=-\frac{\vert{G[a,b)}\vert}{\vert{E[a,b)}\vert}\cdot\log_{2}\left(\frac{\vert{G[a,b)}\vert}{\vert{E[a,b)}\vert}\right)-\frac{\vert{O[a,b)}\vert}{\vert{E[a,b)}\vert}\cdot\log_{2}\left(\frac{\vert{O[a,b)}\vert}{\vert{E[a,b)}\vert}\right)$


Средняя информация разбиения $a<r<b$ интервала $[a,b)\subseteq\textbf{R}$ значений непрерывного признака $V:G\to\textbf{R}$ равна


${\rm{inf}}[a,r,b)=\frac{\vert{E[a,r)}\vert}{\vert{E[a,b)}\vert}\cdot{\rm{ent}}[a,r)+\frac{\vert{E[r,b)}\vert}{\vert{E[a,b)}\vert}\cdot{\rm{ent}}[r,b).$


Порог — это значение $V=r$ с минимальной средней информацией.


Для непрерывного признака $V:G\to\textbf{R}$ обозначим $a=\min\{V\}$ через $v_{0}$, и пусть $v_{l+1}$ будет произвольным числом, превосходящим $b=\max\{V\}$. Пороги $\lbrace{v_{1}<\ldots<v_{l}}\rbrace$ вычисляются последовательно расщеплением подынтервала с наибольшей энтропией.


2.2 Кодирование битовыми строками для выпуклой оболочки


Мы представляем значение непрерывного признака битовой строкой длины $2l$, где $l$ — число порогов. Битовые строки могут рассматриваться как строки индикаторных (Булевских) переменных


$\delta_{i}^{V}(g)=1 \Leftrightarrow V(g)\geq{v_{i}} \\ \sigma_{i}^{V}(g)=1 \Leftrightarrow V(g)<v_{i},$


где $1\leq{i}\leq{l}$.


Тогда строка $\delta_{1}^{V}(g)\ldots\delta_{l}^{V}(g)\sigma_{1}^{V}(g)\ldots\sigma_{l}^{V}(g)$ является битовым представлением непрерывного признака $V$ на объекте $g\in{E}$.


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


Путь $\delta_{1}^{(1)}\ldots\delta_{l}^{(1)}\sigma_{1}^{(1)}\ldots\sigma_{l}^{(1)}$ представляет $v_{i}\leq{V(A_{1})}<v_{j}$ и $\delta_{1}^{(2)}\ldots\delta_{l}^{(2)}\sigma_{1}^{(2)}\ldots\sigma_{l}^{(2)}$ предстваляет $v_{n}\leq{V(A_{2})}<v_{m}$. Тогда


$(\delta_{1}^{(1)}\cdot\delta_{1}^{(2)})\ldots(\delta_{l}^{(1)}\cdot\delta_{l}^{(2)})(\sigma_{1}^{(1)}\cdot\sigma_{1}^{(2)})\ldots(\sigma_{l}^{(1)}\cdot\sigma_{l}^{(2)})$


соответствует $\min\lbrace{v_{i},v_{n}}\rbrace\leq{V((A_{1}\cup{A_{2}})'')}<\max\lbrace{v_{j},v_{m}}\rbrace$.


Отметим, что тривиальное сходство $0\ldots00\ldots0$ соответствует тривиальному условию $\min\{V\}\leq{V((A_{1}\cup{A_{2}})'')}\leq\max\{V\}$.


2.3 Отношения между непрерывными признаками


Подход к машинному обучению на основании АФП естественно рассматривает конъюнкцию нескольких бинарных аттрибутов как возможную причину целевого свойства. В случае дискретных признаков эксперт имеет возможность выразить дизъюнкцию значений путем добавления новых значений (в решеточных структурах параграфа 1). Случай непрерывных признаков отличается. Так что мы нуждаемся в некоторой технике, чтобы включить и этот случай.


Ключевой является следующая лемма


Дизъюнкция пропозициональных переменных $p_{i_{1}}\vee\ldots\vee{p_{i_{k}}}$ эквивалентна выполнимости неравенства $p_{i_{1}}+\ldots+{p_{i_{k}}}>\sigma$ для любого $0<\sigma<1$.


Так как мы ограничиваемся двумя целевыми классами, то мы ищем классификатор


Классификатор — это отображение $c:$R$^{d}\to\lbrace{0,1}\rbrace$, где $\textbf{R}^{d}$ — область объектов классификации (описываемых $d$ непрерывными признаками) и $\lbrace{0,1}\rbrace$ — метки целевых классов.


Как обычно, мы предположим существование некоторого вероятностного распределения $\langle{\vec{X},K}\rangle\in\text{R}^{d}\times\lbrace{0,1}\rbrace$, которое может быть разложено как


$p_{\vec{X},K}(\vec{x},k)=p_{\vec{X}}(\vec{x})\cdot{p_{K\mid\vec{X}}(k\mid\vec{x})},$


где $p_{\vec{X}}(\vec{x})$ — побочное (маргинальное) распределение объектов, a $p_{K\mid\vec{X}}(k\mid\vec{x})$ — условное распределение меток на заданном объекте, т.е. для каждого $\vec{x}\in\text{R}^{d}$ выполняется следующее разложение


$p_{K\mid\vec{X}}(k\mid\vec{x})=\textbf{P}\lbrace{K=k\mid\vec{X}=\vec{x}}\rbrace.$


Вероятность ошибки классификатора $c:\textbf{R}^{d}\to\lbrace{0,1}\rbrace$ равна


$ R(c)=\textbf{P}\left\lbrace{c(\vec{X})\neq{K}}\right\rbrace. $


Байесовский классификатор $b:\textbf{R}^{d}\to\lbrace{0,1}\rbrace$ относительно $p_{K\mid\vec{X}}(k\mid\vec{x})$
задается правилом


$ b(\vec{x})=1 \Leftrightarrow p_{K\mid\vec{X}}(1\mid\vec{x})>\frac{1}{2}>p_{K\mid\vec{X}}(0\mid\vec{x}) $


Мы напомним хорошо известную теорему об оптимальности Байесовского классификатора


Байесовский классификатор $b$ имеет наименьшую ошибку классификации:


$ \forall{c:\textbf{R}^{d}\to\lbrace{0,1}\rbrace}\left[R(b)=\textbf{P}\lbrace{b(\vec{X})\neq{K}}\rbrace\leq{R(c)}\right] $


Теорема Байеса влечет


$ p_{K\mid\vec{X}}(1\mid\vec{x})=\frac{p_{\vec{X}\mid{K}}(\vec{x}\mid{1})\cdot\textbf{P}\lbrace{K=1}\rbrace}{p_{\vec{X}\mid{K}}(\vec{x}\mid{1})\cdot\textbf{P}\lbrace{K=1}\rbrace+p_{\vec{X}\mid{K}}(\vec{x}\mid{0})\cdot\textbf{P}\lbrace{K=0}\rbrace}= \\ =\frac{1}{1+\frac{p_{\vec{X}\mid{K}}(\vec{x}\mid{0})\cdot\textbf{P}\lbrace{K=0}\rbrace}{p_{\vec{X}\mid{K}}(\vec{x}\mid{1})\cdot\textbf{P}\lbrace{K=1}\rbrace}}=\frac{1}{1+\exp\lbrace{-a(\vec{x})}\rbrace}=\sigma(a(\vec{x})), $


где $a(\vec{x})=\log\frac{p_{\vec{X}\mid{K}}(\vec{x}\mid{1})\cdot\textbf{P}\lbrace{K=1}\rbrace}{p_{\vec{X}\mid{K}}(\vec{x}\mid{0})\cdot\textbf{P}\lbrace{K=0}\rbrace}$ и $\sigma(y)=\frac{1}{1+\exp\lbrace{-y}\rbrace}$ — хорошо известная логистическая функция.


2.4 Логистическая регрессия между непрерывными признаками


Давайте приблизим неизвестную $a(\vec{x})=\log\frac{p_{\vec{X}\mid{K}}(\vec{x}\mid{1})\cdot\textbf{P}\lbrace{K=1}\rbrace}{p_{\vec{X}\mid{K}}(\vec{x}\mid{0})\cdot\textbf{P}\lbrace{K=0}\rbrace}$ линейной комбинацией $\vec{w}^{T}\cdot\varphi(\vec{x})$ базисных функций $\varphi_{i}:\textbf{R}^{d}\to\textbf{R}$ ($i=1,\ldots,m$) относительно неизвестных весов $\vec{w}\in\textbf{R}^{m}$.


Для обучающей выборки $\langle\vec{x}_{1},k_{1}\rangle,\dots,\langle\vec{x}_{n},k_{n}\rangle$ введем знаки $t_{j}=2k_{j}-1$. Тогда


$ \log\lbrace{p(t_{1},\dots,t_{n}\mid\vec{x}_{1},\ldots,\vec{x}_{n},\vec{w})}\rbrace=-\sum_{j=1}^{n}\log\left[1+\exp\lbrace{-t_{j}\sum_{i=1}^{m}w_{i}\varphi_{i}(\vec{x}_{j})}\rbrace\right]. $


Заметим, что логарифм правдоподобия


$ L(w_{1},\ldots,w_{m})=-\sum_{j=1}^{n}\log\left[1+\exp\lbrace{-t_{j}\sum_{i=1}^{m}w_{i}\varphi_{i}(\vec{x}_{j})}\rbrace\right]\to\max $


является вогнутой функцией.


Метод Ньютона-Рафсона приводит к итеративной процедуре


$ \vec{w}_{t+1}=\vec{w}_{t}-(\nabla_{\vec{w}^{T}}\nabla_{\vec{w}}L(\vec{w}_{t}))^{-1}\cdot\nabla_{\vec{w}}L(\vec{w}_{t}). $


С помощью $s_{j}=\frac{1}{1+\exp\lbrace{t_{j}\cdot{(w^{T}\cdot\Phi(x_{j}))}}\rbrace}$ мы получаем


$ \nabla{L(\vec{w})}=-\Phi^{T}{\rm{diag}}(t_{1},\ldots,t_{n})\vec{s}, \nabla\nabla{L(\vec{w})}=\Phi^{T}R\Phi, $


где $R={\rm{diag}}(s_{1}(1-s_{1}), s_{2}(1-s_{2}), \ldots, s_{n}(1-s_{n}))$ — диагональная матрица с элементами
$s_{1}(1-s_{1}), s_{2}(1-s_{2}), \ldots, s_{n}(1-s_{n})$ и ${\rm{diag}}(t_{1},\ldots,t_{n})\vec{s}$ — вектор с координатами $t_{1}s_{1}, t_{2}s_{2}, \ldots, t_{n}s_{n}$.


$ \vec{w}_{t+1}=\vec{w}_{t}+\left(\Phi^{T}R\Phi\right)^{-1}\Phi^{T}{\rm{diag}}(t)\vec{s}= (\Phi^{T}R\Phi)^{-1}\Phi^{T}R\vec{z}, $


где $\vec{z}=\Phi\vec{w}_{t}+R^{-1}{\rm{diag}}(t_{1},\ldots,t_{n})\vec{s}$ — итеративно вычисляемые веса.


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


$ \vec{w}_{t+1}=(\Phi^{T}R\Phi+\lambda\cdot{I})^{-1}\cdot(\Phi^{T}R\vec{z}). $


В компьютерной программе "ВКФ-система" мы используем стандартный базис: константу 1 и сами признаки.


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


Критерий Кокса-Снелла объявляет признак $V_{k}$ значимым, если


$ R^{2}=1-\exp\lbrace{2(L(w_{0},\ldots, w_{k-1})-L(w_{0},\ldots,w_{k-1},w_{k}))/n}\rbrace\geq\sigma $


Критерий МакФаддена объявляет признак $V_{k}$ значимым, если


$ 1-\frac{L(w_{0},\ldots,w_{k-1},w_{k})}{L(w_{0},\ldots,w_{k-1})}\geq\sigma $


Заключение


"ВКФ-система" была применена к массиву Wine Quality из репозитория данных для машинного обучения (Универсистет Калифорнии в г. Ирвайн). Эксперименты продемонстрировали перспективы предложенного подхода. Для высококачественных красных вин (с оценкой >7), все примеры были классифицированы корректно.


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


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


Автор выражает благодарности своим коллегам и студентам за поддержку и стимулы.