Русский
Русский
English
Авторизация
Ip-адрес
Восстановление пароля
Регистрация
Статистика
Реклама

Решетка

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

12.07.2020 20:15:48 | Автор: admin

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


Введение


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


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


Мы представляем каждый четырехугольник множеством признаков, связанных с его симметриями:
"Есть центр симметрии" (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\{diamond,deltoid\}, \{D\}\rangle,$


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


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


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


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


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


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


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


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


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


Легким упражнением является проверка того, что $L(G,M,I)$ образует решетку с операциями


$\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)), чтобы породить все элементы $L(G,M,I)$.


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


Путь $(G,M,I)$ выборка, $\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 Проблемы с АФП


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


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


  2. Проблема обнаружения больших гипотез вычислительно (NP-)трудная.


  3. Переобучение неизбежно и возникает на практике.


  4. Существуют 'фантомные' сходства между обучающими примерами, где каждый такой родитель имеет альтернативную гипотезу о причине целевого свойства.



Чтобы продемонстрировать недостаток 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$ является кандидатом. Поэтому существует $2^n$ кандидатов.


Чтобы оценить экспоненциальный взрыв выхода от размера входа, оценим память, нужную для хранения выборки для $n=32$, как 128 байт, а память для сохранения $2^n$ кандидатов потребуется $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}}$ явяляется положительным, так как совпадает с вероятностью того, что Пуассоновская величина со средним $a$ примет значение >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 $


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


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


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


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


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


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


Программа вызывает алгоритм ленивой спаренной цепи Маркова, чтобы породить случайного кандидата $\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\}'$ означает включение фрагмента $B$ кандидата $\langle{A,B}\rangle$ во фрагмент (подмножество признаков) контр-примера $o$.


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


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


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


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;        }}

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


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


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


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


$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\}'$.


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


Заключение


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


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


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


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

Подробнее..
Категории: Математика , Машинное обучение , Решетка , Цепь маркова , Индукция , Аналогия

Представление объектов для машинного обучения, основанного на теории решеток

14.07.2020 12:05:49 | Автор: admin

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


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\testbf{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$ "алкоголь").


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

Подробнее..
Категории: Математика , Машинное обучение , Энтропия , Решетка , Логистическая регрессия

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru