KRRGuest Jul 12 2020 at 20:20

Математика машинного обучения, основанного на теории решеток

7 min

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

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

Области применения АФП

Введение

Мы начнем с демонстрации нашего подхода в применении к школьной задаче.

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

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

Обучающая выборка включает в себя квадрат, равнобедренную трапецию, ромб и дельтоид (смотри метки строчек в таблице).

Единственный тестовый пример — прямоугольник.

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

"Есть центр симметрии" (A),
"Группа вращений тривиальна" (B),
"группа вращенией нетривиальна" (C),
"Есть диагональная ось симметрии" (D),
"Есть недиагональная ось симметрии" (E).
Они соответствуют именам столбцов в таблице.

четырехугольник	цель	A	B	C	D	E
квадрат	1	1	0	1	1	1
трапеция	1	0	1	0	0	1
ромб	0	1	0	1	1	0
дельтоид	0	0	1	0	1	0
прямоугольник	?	1	0	1	0	1

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

$\langle\{квадрат,трапеция\}, \{E\}\rangle,$

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

Так как общий фрагмент $\{E\}$ является подмножеством описания прямоугольника $\{A,C,E\}$ , программа предскажет его целевое свойство положительным, т.е. прямоугольник описываем. Это соответствует процедуре доопределения по аналогии в ДСМ-методе. Аналогами прямоугольника будут родители (квадрат и равнобедренная трапеция), которые имеют общий фрагмент, встречающийся и в прямоугольнике.

Однако мы можем поменять знаки: сходством отрицательных примеров будет

$\langle\{ромб,дельтоид\}, \{D\}\rangle,$

Это наблюдение приводит к логикам Аргументации, но мы предпочтем не погружаться здесь в детали. Заинтересованный читатель отсылается к статьям автора из сборника
Финн В.К., Аншаков О.М., Виноградов Д.В. (Ред.). Многозначные логики и их применения. Том 2: Логики в системах искусственного интеллекта, M.: URSS, 2020, 238 с. ISBN 978-5-382-01977-2

Важно, что сходство отрицательных примеров позволяет нам продемонстрировать принцип "запрета контр-примеров", так как его фрагмент $\{D\}$ вкладывается в описание $\{A,C,D,E\}$ примера противоположного знака (квадрат).

1. Анализ Формальных Понятий

Первоначально автор планировал излагать теорию в терминах ДСМ-метода автоматического порождения гипотез. Но его создатель выразил сомнение, что "можно изложить глубокие идеи ДСМ-метода популярным языком". Поэтому автор решил использовать язык АФП для этой статьи. Однако он будет использовать некоторые свои термины (наравне с оригинальными в скобках) там, где предпочтительнее сменить терминологию.

Выборка (=формальный контекст) — это тройка $inline$ , где $inline$ и $inline$ — конечные множества, а $I \subseteq G \times M$ . Элементы $inline$ и $inline$ называются объектами и признаками, соответственно. Как обычно, мы пишем $inline$ вместо $\langle g,m\rangle \in I$ , чтобы обозначить ситуацию, когда объект $inline$ обладает признаком $inline$ .

Для $A\subseteq G$ и $B\subseteq M$ определим

$A' = \{ m \in M | \forall g \in A (gIm) \}, \\ B' = \{ g \in G | \forall m \in B (gIm) \};$

так что $inline$ — это множество всех признаков, общих для всех объектов из $inline$ , а $inline$ — это множество всех объектов, обладающих всеми признаками из $inline$ . Отображения $(\cdot)': 2^G \rightarrow 2^M$ и $(\cdot)':2^M\rightarrow 2^G$ называются полярами (=операторами производной) для выборки $inline$ .

Кандидатом (=формальным понятием) для выборки $inline$ называется пара $\langle A,B \rangle$ , где $A\subseteq G$ , $B\subseteq M$ , $inline$ и $inline$ . Первая компонента $inline$ кандидата $\langle A,B \rangle$ называется списком родителей (=объемом) кандидата, а вторая компонента $inline$ называется его фрагментом (=содержанием). Множество всех кандидатов для выборки $inline$ обозначается через $inline$ .

Легким упражнением является проверка того, что $inline$ образует решетку с операциями

$\langle A_{1},B_{1}\rangle\vee\langle A_{2},B_{2}\rangle= \langle(A_{1}\cup A_{2})'',B_{1}\cap B_{2}\rangle, \\ \langle A_{1},B_{1}\rangle\wedge\langle A_{2},B_{2}\rangle= \langle A_{1}\cap A_{2},(B_{1}\cup B_{2})''\rangle.$

Мы используем специальный случай: для $\langle A,B \rangle\in L(G,M,I)$ , $g\in G$ и $m\in M$ определим

$CbO(\langle A,B\rangle,g) = \langle(A\cup\{g\})'',B\cap\{g\}'\rangle,\\ CbO(\langle A,B\rangle,m) = \langle A\cap\{m\}',(B\cup\{m\})''\rangle.$

Мы называем эти операции CbO, так как первая из них использовалась в известном алгоритме "Замыкай-по-одному" (Close-by-One (CbO)), чтобы породить все элементы $inline$ .

Наиболее важное свойство монотонности операций CbO составляет следующую лемму

Путь $inline$ — выборка, $\langle A_{1},B_{1}\rangle, \langle A_{2},B_{2}\rangle\in L(G,M,I)$ , $g\in G$ и $m\in M$ . Тогда

$\langle A_{1},B_{1}\rangle\leq \langle A_{2},B_{2}\rangle\Rightarrow CbO(\langle A_{1},B_{1}\rangle,g)\leq CbO(\langle A_{2},B_{2}\rangle,g), \\ \langle A_{1},B_{1}\rangle\leq\langle A_{2},B_{2}\rangle\Rightarrow CbO(\langle A_{1},B_{1}\rangle,g)\leq CbO(\langle A_{2},B_{2}\rangle,g).$

2. Проблемы с АФП

К несчастью, автор и его коллеги обнаружили некоторые теоретические недостатки непосредственного применения АФП к машинному обучению:

Число гипотез может оказаться экспоненциально велико по отношению к размеру входных данных (обучающей выборки) в худшем случае.
Проблема обнаружения больших гипотез вычислительно (NP-)трудная.
Переобучение неизбежно и возникает на практике.
Существуют 'фантомные' сходства между обучающими примерами, где каждый такой родитель имеет альтернативную гипотезу о причине целевого свойства.

Чтобы продемонстрировать недостаток 1 нам нужна Булева алгебра с выборкой, задаваемой коатомами (как позитивными примерами):

$M\\G$	$m_{1}$	$m_{2}$	$\ldots$	$m_{n}$
$g_{1}$	0	1	$\ldots$	1
$g_{2}$	1	0	$\ldots$	1
$\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$
$g_{n}$	1	1	$\ldots$	0

Легко проверить, что любая пара $\langle G\setminus \{g_{i_{1}},\ldots,g_{i_{k}}\},\{m_{i_{1}},\ldots,m_{i_{k}}\}\rangle$ является кандидатом. Поэтому существует $inline$ кандидатов.

Чтобы оценить экспоненциальный взрыв выхода от размера входа, оценим память, нужную для хранения выборки для $inline$ , как 128 байт, а память для сохранения $inline$ кандидатов потребуется $2^{37}$ бит, т.е. 16 Гигабайт!

Недостаток 2 был обнаружен проф. С.О. Кузнецовым (НИУ-ВШЭ Москва).

Недостатки 3 и 4 были открыты автором во время его работы над диссертацией. Он рассмотрел несколько вероятностных моделей, чтобы породить "фантомые" сходства вместе с контр-примерами, могущими их отвергнуть. Наиболее прозрачный результат — это асимптотическая теорема, которая утверждает, что вероятность порождения "фантомного" сходства двух родителей без контр-примеров стремится к

$1-e^{-a}-a\cdot{e^{-a}}\cdot\left[1-e^{-c\cdot\sqrt{a}}\right],$

когда вероятность появления каждого признака (рассматриваемого как н.о.р. переменные Бернулли) $p=\sqrt{a/n}\to 0$ , число контр-примеров $m=c\cdot\sqrt{n}\to\infty$ , а число признаков $n\to\infty$ .

Отметим, что даже меньшее число $1-e^{-a}-a\cdot{e^{-a}}$ является положительным, так как совпадает с вероятностью того, что Пуассоновская величина со средним $inline$ примет значение >1.

Можно обратиться к диссертации автора за дополнительными деталями и результатами.

3. Вероятностные алгоритмы

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

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

Автор придумал и исследовал математические свойства нескольких таких алгоритмов (немонотонной, монотонной, спаренной, ленивой спаренной и рстановленной спаренной цепей Маркова). Детали могут найдены в диссертации автора.

Мы теперь представим алгоритм спаренной цепи Маркова, которая явлется основой вероятностного подхода к машинному обучени, онованному на АФП (ВКФ-метода).

input: выборка (G,M,I), внешние операции CbO( , )
result: случайный кандидат <A,B>
X=G U M; 
A = M'; B = M;  
C = G; D = G';
while (A!=C || B!= D) {
        выбрать случайный элемент x из X;
        <A,B> = CbO(<A,B>,x);
        <C,D> = CbO(<C,D>,x);
}

Существует ленивый вариант спаренной цепи Маркова. Автор доказал, что ленивые вычисления приводят к ускорению (по сравнению с классической схемой) до

$\frac{(n+k)^2}{2k\cdot n}=2+\frac{(n-k)^2}{2k\cdot n} \geq 2$

раз, где $inline$ — число признаков, а $inline$ — число обучающих примеров.

Этот результат находится в замечательном соответствии с экспериментальными оценками, полученными бывшей студенткой РГГУ Л.А. Якимовой.

4. Общая структура ВКФ-метода

В машинном обучении с учителем обычно имеются две выборки, называемые обучающей и тестовой, соответственно.

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

Множество $inline$ тестов содержат все элементы тестовой выборки для предсказания целевого свойства.

Программа вызывает алгоритм ленивой спаренной цепи Маркова, чтобы породить случайного кандидата $\langle A,B\rangle\in L(G,M,I)$ . Программа сохраняет его как ВКФ-гипотезу VKF-hypothesis $\langle A,B\rangle$ , если не найдется такого контр-примера $o\in O$ , что $B\subseteq \{o\}'$ .

Основной алгоритм индуктивного обобщения таков

input: число N ВКФ-гипотез для порождения
result: случайная выборка S затребованных гипотез 
while (i<N) {
        породить случайного кандидата <A,B> для (G,M,I);
        hasObstacle = false;
        for (o in O) {
            if (B включается в {o}') hasObstacle = true;
        }
        if (hasObstacle == false) {
                S = S U {<A,B>};
                i = i+1;
        }
}

Условие $B\subseteq\{o\}'$ означает включение фрагмента $inline$ кандидата $\langle{A,B}\rangle$ во фрагмент (подмножество признаков) контр-примера $inline$ .

Если кандидат избегает все такие препятствия, он добавляется к списку порожденных ВКФ-гипотез.

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

После этого система машинного обучения предсказывает целевое свойство у тестов и сравнивает результаты предсказания с оригинальными значениями целевого свойства. Вот алгоритм предсказания по аналогии

input: список T тестовых примеров для предсказания уелевого свойства 
input: случайная выборка S порожденных индукцией ВКФ-гипотез
for (x in T) {
        target(x) = false;
        for (<A,B> in S) {
            if (B is a part of {x}') target(x) = true;
        }
}

Худшая ситуация случается, когда некоторый важный положительный тестовый пример пропустит все порожденные ВКФ-гипотезы и доопределится отрицательно.

Тестовый пример $inline$ называется $\varepsilon$ -важным, если вероятность всех ВКФ-гипотез $\langle A,B\rangle$ с $B\subseteq\{x\}'$ превосходит $\varepsilon$ .

Автор доказал теорему об оценке параметра $inline$ из алгоритма индуктивного обобщения, чтобы избежать худшего случая.

Для $n=\left|{M}\right|$ , для любого $\varepsilon>0$ и любого $1>\delta>0$ случайная выборка $inline$ ВКФ-гипотез мощности

$N\geq{\frac{2\cdot(n+1)-2\cdot\log_{2}{\delta} }{\varepsilon}}$

с вероятностью $>{1-\delta}$ имеет свойство, что каждый $\varepsilon$ -важный объект $x$ содержит фрагмент некоторой ВКФ-гипотезы $\langle A,B\rangle\in{S}$ , т.е. $B\subseteq\{x\}'$ .

Эта теорема является аналогом известных результатов проф. В.Н. Вапника и проф. А.Я. Червоненкиса из статистической теории обучения.

Заключение

Эта заметка описывает главные математические характеристики системы машинного обучения, основанной на теории решеток. Автор назвал ее "ВКФ-системой" в честь своего учителя проф. В.К. Финна.

Последняя статья цикла будет посвящена представлениям объектов с признаками различных типов для примения описываемой здесь машины обучения.

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

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

Tags:

Hubs: