Онлайн
Alvaros
.
- Регистрация
- 14.05.16
- Сообщения
- 21.452
- Реакции
- 101
- Репутация
- 204
Это третья статья серии работ (ссылки на
Введение
Мы начнем с демонстрации нашего подхода в применении к школьной задаче.
Она состоит в отыскании достаточных условий на выпуклый четырехугольник, чтобы вокруг него можно было описать окружность и предсказать это свойство у прямоугольника.
Следовательно, имеются два класса: позитивный (можно описать окружность вокруг четырехугольника) и негативный.
Обучающая выборка включает в себя квадрат, равнобедренную трапецию, ромб и дельтоид (смотри метки срочек в таблице)
Единственный тестовый пример — прямоугольник.
Мы представляем каждый четырехугольник множеством признаков, связанных с его симметриями:
"Есть центр симметрии" (A),
"Группа вращений тривиальна" (B),
"группа вращенией нетривиальна" (C),
"Есть диагональная ось симметрии" (D),
"Есть недиагональная ось симметрии" (E).
Они соотвествуют именам столбцов в таблице.
Чтобы обнаружить возможные причины (в териминах симметрий) программа вычисляет сходства (общие признаки) между обучающими примерами одного знака. Поэтому мы имеем
где первое подмножество содержит родителей (все обучающие примеры, сходство которых вычислялось), а второе — общий фрпагмент этих примеров.
Так как общий фрагмент
является подмножеством описания прямоугольника
, программа предскажет его целевое свойство положительным, т.е. прямоугольник описываем. Это соответсвует процедуре доопределения по аналогии в ДСМ-методе. Аналогами прямоугольника будут родители (квадрат и равнобедренная трапеция), которые имеют общий фрагмент, встречающийся и в прямоугольнике.
Однако мы можем поменять знаки: сходством отрицательных примеров будет
Это наблюдение приводит к логикам Аргументации, но мы предпочтем не погружаться здесь в детали. Заинтересованный читатель отсылается к статьям автора из сборника
Финн В.К., Аншаков О.М., Виноградов Д.В. (Ред.). Многозначные логики и их применения. Том 2: Логики в системах искусственного интеллекта, M.: URSS, 2020, 238 с. ISBN 978-5-382-01977-2
Важно, что сходство отрицательных примеров позволяет нам продемострировать принцип "запрета контр-примеров", так как его фрагмент
вкладывается в описание
примера противоположного знака (квадрат).
1 Анализ Формальных Понятий
Первоначально автор планировал излагать теорию в терминах ДСМ-метода автоматического порождения гипотез. Но его создатель выразил сомнение, что "можно изложить глубокие идеи ДСМ-метода популярным языком". Поэтому автор решил использовать язык АФП для этой статьи. Однако он будет использовать некоторые свои термины (наравне с оригинальными в скобках) там, где предпочтительнее сменить терминологию.
Выборка (=формальный контекст) — это тройка
, где
и
— конечные множества, а
. Элементы
и
наызваются объектами и признаками, соответственно. Как обычно, мы пишем
вместо
, чтобы обозначить ситуацию, когда объект
обладает признаком
.
Для
и
определим
так что
— это множество всех признаков, общих для всех объектов из
, а
— это множество всех объектов, обладающих всеми признаками из
. Отображения
и
называются полярами (=операторами производной) для выборки
.
Кандидатом (=формальным понятием) для выборки
называется пара
, где
,
,
и
. Первая компонента
кандидата
называется списком родителей (=объемом) кандидата, а вторая компонента
называется его фрагментом (=содержанием). Множество всех кандидатов для выборки
обозначается через
.
Легким упражнением является проверка того, что
образует решетку с операциями
Мы используем специальный случай: для
,
и
определим
Мы называем эти операции CbO, так как первая из них использовалась в известном алгоритме "Замыкай-по-одному" (Close-by-One (CbO)), чтобы породить все элементы
.
Наиболее важное свойство монотонности операций CbO составляет следующую лемму
Путь
— выборка,
,
и
. Тогда
2 Проблемы с АФП
К несчастью, автор и его коллеги обнаружили некоторые теоретические недостатки непосредственного применения АФП к машинному обучению:
Чтобы продемонстрировать недостаток 1 нам нужна Булева алгебра с выборкой, задаваемой коатомами (как позитивными примерами):
Легко проверить, что любая пара
является кандидатом. Поэтому существует
кандидатов.
Чтобы оценить экспоненциальный взрыв выхода от размера входа, оценим память, нужную для хранения выборки для
, как 128 байт, а память для сохранения
кандидатов потребуется
бит, т.е. 16 Гигабайт!
Недостаток 2 был обнаружен проф. С.О. Кузнецовым (НИУ-ВШЭ Москва).
Недостатки 3 и 4 были открыты автором во время его работы над диссертацией. Он рассмотрел несколько вероятностных моделей, чтобы породить "фантомые" сходства вместе с контр-примерами, могущими их отвергнуть. Наиболее прозрачный результат — это асимптотическая теорема, которая утверждает, что вероятность порождения "фантомного" сходства двух родителей без контр-примеров стремится к
когда вероятность появления каждого признака (рассматриваемого как н.о.р. переменные Бернулли)
, число контр-примеров
, а число признаков
.
Отметим, что даже меньшее число
явяляется положительным, так как совпадает с вероятностью того, что Пуассоновская величина со средним
примет значение >1.
Можно обраиться к
3 Вероятностные алгоритмы
Ключевая идея ВКФ=метода случайным образом порожить малое подмножество решетки кандидатов и использовать его элементы как гипотетические причины целевошго свойства. С помощью этого трюка мы избегаем экпоненциально высокой вычислительной сложности обычных алгоритмов АФП (и ДСМ-метода тоже).
Так что нам нужны алгоритмы, подобные случайным блужданиям на ограмной решетке, с порождением кандидата только тогда, когда он нам потребуется.
Автор придумал и исследовал математические свойства нескольких таких алгоритмов (немонотонной, монотонной, спаренной, ленивой спаренной и рстановленной спаренной цепей Маркова). Детали могут найдены в
Мы теперь представим алгоритм спаренной цепи Маркова, которая явлется основой вероятностного подхода к машинному обучени, онованному на АФП (ВКФ-метода).
input: выборка (G,M,I), внешние операции CbO( , )
result: случайный кандидат
X=G U M;
A = M'; B = M;
C = G; D = G';
while (A!=C || B!= D) {
выбрать случайный элемент x из X;
= CbO(,x);
= CbO(,x);
}
Существует ленивый вариант спаренной цепи Маркова. Автор доказал, что ленивые вычисления приводят к ускорению (по сравнению с классической схемой) до
раз, где
— число признаков, а
— число обучающих примеров.
Этот результат находится в замечательном соответствии с экспериментальными оценками, полученными бывшей студенткой РГГУ Л.А. Якимовой.
4 Общая структура ВКФ-метода
В машинном обучении с учителем обычно имеются две выборки, называемые обучающей и тестовой, соответственно.
Из положительных примеров обучающей выборки образуют
. Отрицательные обучающие примеры формируют множество
контр-примеров (препятствий для превращение в ВКФ-гипотезы).
Множество
тестов содежат все элементы тестовой выборки для предсказания целевого свойства.
Программа вызывает алгоритм ленивой спаренной цепи Маркова, чтобы породить случайного кандидата
. Программа сохраняет его как ВКФ-гипотезу VKF-hypothesis
, если не найдется такого контр-примера
, что
.
Основной алгоритм индуктивного обобщения таков
input: число N ВКФ-гипотез для порождения
result: случайная выборка S затребованных гипотез
while (i для (G,M,I);
hasObstacle = false;
for (o in O) {
if (B включается в {o}') hasObstacle = true;
}
if (hasObstacle == false) {
S = S U {};
i = i+1;
}
}
Условие
означает включение фрагмента
кандидата
во фрагмент (подмножество признаков) контр-примера
.
Если кандидат избегает все такие препятствия, он добавляется к списку порожденных ВКФ-гипотез.
Мы заменили детерминистский потребляющий много времени алгоритм (например, хорошо известный алгоритм "Замыкай-по-одному") для порождения всех кандидатов на вероятностный, котороый порождает случайное подмножество ВКФ-гипотез заданного объема.
После этого система машинного обучения предсказывает целевое свойство у тестов и сравнивает результаты предсказания с оригинальными значениями целевого свойства.
input: список T тестовых примеров для предсказания уелевого свойства
input: случайная выборка S порожденных индукцией ВКФ-гипотез
for (x in T) {
target(x) = false;
for ( in S) {
if (B is a part of {x}') target(x) = true;
}
}
Худшая ситуация случается, когда некоторый важный положительный тестовый пример пропустит все порожденные ВКФ-гипотезы и доопределится отрицательно.
Тестовый пример
называется
-важным, если вероятность всех ВКФ-гипотез
с
превосходит
.
Автор доказал теорему об оценке параметра
из алгоритма индуктивного обобщения, чтобы избежать худший случай.
Для
, для любого
и любого
случайная выборка
ВКФ-гипотез мощности
с вероятностью
имеет свойство, что каждый
-важный объект $x$ содержит фрагмент некоторой ВКФ-гипотезы
, т.е.
.
Эта теорема является аналогом известных результатов проф. В.Н. Вапника и проф. А.Я. Червоненкиса из статистической теории обучения.
Заключение
Эта заметка описывает главные математические характеристики системы машинного обучения, основанной на теории решеток. Автор назвал ее "ВКФ-системой" в честь своего учителя проф. В.К. Финна.
Последняя статья цикла будет посвящена представлениям объектов с признаками различных типов для примения описываемой здесь машины обучения.
Дискретные признаки снова потребуют некоторую технику из АФП. Непрерывным признакам потребуется логистическая регрессия, энтропийные принципы разделения диапазонов на подынтервалы и представление, порождающее выпуклую оболочку интервалов, чье сходство вычисляется.
Автор рад возможности поблагодарить своих коллег и студентов за поддержку и стимулы.
You must be registered for see links
и
You must be registered for see links
работы), описывающих систему машинного обучения, основанного на теории решеток, озаглавленную "ВКФ-система". Она использует структурный (теоретико-решеточной) подход к представлению обучающих примеров и их фрагментов, рассматриваемых как причины целевого свойства. Система вычисляет эти фрагменты как сходства между некоторыми подмножествами обучающих примеров. Существует алгебраическая теория таких представлений, называемая Анализом формальных понятий (АФП). Однако описываемая система использует вероятностные алгоритмы, чтобы устранить недостатки неограниченного подхода. Подробности ниже…
Введение
Мы начнем с демонстрации нашего подхода в применении к школьной задаче.
Она состоит в отыскании достаточных условий на выпуклый четырехугольник, чтобы вокруг него можно было описать окружность и предсказать это свойство у прямоугольника.
Следовательно, имеются два класса: позитивный (можно описать окружность вокруг четырехугольника) и негативный.
Обучающая выборка включает в себя квадрат, равнобедренную трапецию, ромб и дельтоид (смотри метки срочек в таблице)
Единственный тестовый пример — прямоугольник.
Мы представляем каждый четырехугольник множеством признаков, связанных с его симметриями:
"Есть центр симметрии" (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 |
Чтобы обнаружить возможные причины (в териминах симметрий) программа вычисляет сходства (общие признаки) между обучающими примерами одного знака. Поэтому мы имеем
где первое подмножество содержит родителей (все обучающие примеры, сходство которых вычислялось), а второе — общий фрпагмент этих примеров.
Так как общий фрагмент
Однако мы можем поменять знаки: сходством отрицательных примеров будет
Это наблюдение приводит к логикам Аргументации, но мы предпочтем не погружаться здесь в детали. Заинтересованный читатель отсылается к статьям автора из сборника
Финн В.К., Аншаков О.М., Виноградов Д.В. (Ред.). Многозначные логики и их применения. Том 2: Логики в системах искусственного интеллекта, M.: URSS, 2020, 238 с. ISBN 978-5-382-01977-2
Важно, что сходство отрицательных примеров позволяет нам продемострировать принцип "запрета контр-примеров", так как его фрагмент
1 Анализ Формальных Понятий
Первоначально автор планировал излагать теорию в терминах ДСМ-метода автоматического порождения гипотез. Но его создатель выразил сомнение, что "можно изложить глубокие идеи ДСМ-метода популярным языком". Поэтому автор решил использовать язык АФП для этой статьи. Однако он будет использовать некоторые свои термины (наравне с оригинальными в скобках) там, где предпочтительнее сменить терминологию.
Выборка (=формальный контекст) — это тройка
Для
так что
Кандидатом (=формальным понятием) для выборки
Легким упражнением является проверка того, что
Мы используем специальный случай: для
Мы называем эти операции CbO, так как первая из них использовалась в известном алгоритме "Замыкай-по-одному" (Close-by-One (CbO)), чтобы породить все элементы
Наиболее важное свойство монотонности операций CbO составляет следующую лемму
Путь
2 Проблемы с АФП
К несчастью, автор и его коллеги обнаружили некоторые теоретические недостатки непосредственного применения АФП к машинному обучению:
Число гипоез может оказаться экспоненциально велико по отношению к размеру входных данных (обучающей выборки) в худшем случае.
Проблема обнаружения больших гипотез вычислительно (NP-)трудная.
Переобучение неизбежно и возникает на практике.
Существуют 'фантомные' сходства между обучающими примерами, где каждый такой родитель имеет альтернативную гипотезу о причине целевого свойства.
Чтобы продемонстрировать недостаток 1 нам нужна Булева алгебра с выборкой, задаваемой коатомами (как позитивными примерами):
|
|
|
|
|
|---|---|---|---|---|
| 0 | 1 |
| 1 |
| 1 | 0 |
| 1 |
|
|
| 
|
|
| 1 | 1 |
| 0 |
Легко проверить, что любая пара
Чтобы оценить экспоненциальный взрыв выхода от размера входа, оценим память, нужную для хранения выборки для
Недостаток 2 был обнаружен проф. С.О. Кузнецовым (НИУ-ВШЭ Москва).
Недостатки 3 и 4 были открыты автором во время его работы над диссертацией. Он рассмотрел несколько вероятностных моделей, чтобы породить "фантомые" сходства вместе с контр-примерами, могущими их отвергнуть. Наиболее прозрачный результат — это асимптотическая теорема, которая утверждает, что вероятность порождения "фантомного" сходства двух родителей без контр-примеров стремится к
когда вероятность появления каждого признака (рассматриваемого как н.о.р. переменные Бернулли)
Отметим, что даже меньшее число
Можно обраиться к
You must be registered for see links
за дополнительными деталями и результатами.3 Вероятностные алгоритмы
Ключевая идея ВКФ=метода случайным образом порожить малое подмножество решетки кандидатов и использовать его элементы как гипотетические причины целевошго свойства. С помощью этого трюка мы избегаем экпоненциально высокой вычислительной сложности обычных алгоритмов АФП (и ДСМ-метода тоже).
Так что нам нужны алгоритмы, подобные случайным блужданиям на ограмной решетке, с порождением кандидата только тогда, когда он нам потребуется.
Автор придумал и исследовал математические свойства нескольких таких алгоритмов (немонотонной, монотонной, спаренной, ленивой спаренной и рстановленной спаренной цепей Маркова). Детали могут найдены в
You must be registered for see links
.Мы теперь представим алгоритм спаренной цепи Маркова, которая явлется основой вероятностного подхода к машинному обучени, онованному на АФП (ВКФ-метода).
input: выборка (G,M,I), внешние операции CbO( , )
result: случайный кандидат
X=G U M;
A = M'; B = M;
C = G; D = G';
while (A!=C || B!= D) {
выбрать случайный элемент x из X;
= CbO(,x);
= CbO(,x);
}
Существует ленивый вариант спаренной цепи Маркова. Автор доказал, что ленивые вычисления приводят к ускорению (по сравнению с классической схемой) до
раз, где
Этот результат находится в замечательном соответствии с экспериментальными оценками, полученными бывшей студенткой РГГУ Л.А. Якимовой.
4 Общая структура ВКФ-метода
В машинном обучении с учителем обычно имеются две выборки, называемые обучающей и тестовой, соответственно.
Из положительных примеров обучающей выборки образуют
Множество
Программа вызывает алгоритм ленивой спаренной цепи Маркова, чтобы породить случайного кандидата
Основной алгоритм индуктивного обобщения таков
input: число N ВКФ-гипотез для порождения
result: случайная выборка S затребованных гипотез
while (i для (G,M,I);
hasObstacle = false;
for (o in O) {
if (B включается в {o}') hasObstacle = true;
}
if (hasObstacle == false) {
S = S U {};
i = i+1;
}
}
Условие
Если кандидат избегает все такие препятствия, он добавляется к списку порожденных ВКФ-гипотез.
Мы заменили детерминистский потребляющий много времени алгоритм (например, хорошо известный алгоритм "Замыкай-по-одному") для порождения всех кандидатов на вероятностный, котороый порождает случайное подмножество ВКФ-гипотез заданного объема.
После этого система машинного обучения предсказывает целевое свойство у тестов и сравнивает результаты предсказания с оригинальными значениями целевого свойства.
input: список T тестовых примеров для предсказания уелевого свойства
input: случайная выборка S порожденных индукцией ВКФ-гипотез
for (x in T) {
target(x) = false;
for ( in S) {
if (B is a part of {x}') target(x) = true;
}
}
Худшая ситуация случается, когда некоторый важный положительный тестовый пример пропустит все порожденные ВКФ-гипотезы и доопределится отрицательно.
Тестовый пример
Автор доказал теорему об оценке параметра
Для
с вероятностью
Эта теорема является аналогом известных результатов проф. В.Н. Вапника и проф. А.Я. Червоненкиса из статистической теории обучения.
Заключение
Эта заметка описывает главные математические характеристики системы машинного обучения, основанной на теории решеток. Автор назвал ее "ВКФ-системой" в честь своего учителя проф. В.К. Финна.
Последняя статья цикла будет посвящена представлениям объектов с признаками различных типов для примения описываемой здесь машины обучения.
Дискретные признаки снова потребуют некоторую технику из АФП. Непрерывным признакам потребуется логистическая регрессия, энтропийные принципы разделения диапазонов на подынтервалы и представление, порождающее выпуклую оболочку интервалов, чье сходство вычисляется.
Автор рад возможности поблагодарить своих коллег и студентов за поддержку и стимулы.