Размещено на http://www.allbest.ru/

ПРАВИТЕЛЬСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет компьютерных наук

Выпускная квалификационная работа

На тему: «Построение архитектуры глубокой нейронной сети с помощью решётки формальных понятий»

По направлению подготовки 01.04.02 «Науки о данных»

Научный руководитель

Профессор, Департамент анализа данных и искусственного интеллекта

Доктор физико-математических наук

Кузнецов Сергей Олегович

Выполнил студент группы мНоД15_ИССА

2 курса магистратуры образовательной программы «Науки о данных»

Ушаков Максим Николаевич

Москва 2017



Оглавление

Введение

1. Теоретическая часть

1.1 Формальные понятия. Решётки формальных понятий

1.2 Монотонное соответствие Галуа

1.3 Классификация данных на основе замкнутых подмножеств

1.4 Меры качества формальных понятий

1.5 Нейронная сеть

1.6 Обучение нейронной сети. Градиентный спуск

2. Построение архитектуры нейронной сети

2.1 Общий вид нейронной сети, построенной по решётке формальных понятий

2.2 Выбор оптимального набора формальных понятий

3.Оптимизация архитектуры нейронной сети из конъюнктивных понятий

3.1 Выбор глубины нейронной сети

3.2 Сравнение мер качества формальных понятий

3.3 Преобучение нейронной сети с использованием формальных понятий

4. Оптимизация архитектуры нейронной сети из дизъюнктивных понятий

4.1 Сравнение нейронной сети и диаграммы формальных понятий

4.2 Сравнение мер качества формальных понятий

4.3 Преобучение нейронной сети

5. Сравнение с другими методами классификации данных

5.1 Описание наборов используемых данных и схемы проводимых экспериментов

5.2 Сравнение нейронной сети на основе формальных понятий с другими методами классификации данных

6. Описание программной реализации

Заключение

Список литературы

Приложение

Введение

Нейронные сети - один из наиболее эффективных методов классификации данных. Он использует некоторую архитектуру, на вход которой подаются атрибуты объектов, а на выходе выводятся классы, для обучения её весами. Построение такой архитектуры требует экспертного знания об исследуемом наборе данных, а в случае его отсутствия она выбирается экспериментальным путём, то есть перебором нескольких стандартных структур. При этом если архитектура получится достаточно маленькой, то нейронная сеть не сможет на её основе описать входной набор данных. Если же архитектура сети будет слишком большой, то наличие большого количества параметров может привести к вычислительным проблемам, вплоть до того, что сеть перестанет обучаться. В связи с этим становится актуальной задача построения архитектуры сети по исходному набору данных.

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

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

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



1. Теоретическая часть

В данном разделе будут рассмотрены некоторые базовые понятия из теории формальных понятий и нейронных сетей, используемых в работе. В данной части будут дано классическое определение формального понятия, а также формального понятия, основанного на монотонном соответствии Галуа. Будут рассмотрены некоторые свойства формальных понятий, характеризующие их качество в роли классификаторов, а также построение решётки формальных понятий для дальнейшего исследования взаимосвязей между замкнутыми подмножествами с помощью нейронных сетей. Из теории нейронных сетей будет дано описание модели, с указанием используемых в работе функций активации нейронов. Также будут рассмотрены методы обучения нейронных сетей, основанные на градиентном спуске.

1.1 Формальные понятия. Решётки формальных понятий

Формальным контекстом [3,4] называется тройка , где - это множество объектов, - множество признаков, - бинарное отношение, заданное на декартовом произведении , . Пример формального контекста показан в Таблице 1 (пример взят из работы [3]).

Таблица 1. Пример формального контекста.

M G

color

form

firm

smooth

1

apple

x

x

x

x

2

grapefruit

x

x

x

x

3

kiwi

x

x

x

x

4

plum

x

x

x

x

5

toy cube

x

x

x

x

6

egg

x

x

x

x

7

tennis ball

x

x

x

x

8

mango

x

x

x

x

В данном примере множество состоит из 8 объектов (фруктов и пр.), а множество состоит из 10 атрибутов (белый цвет, круглая форма и пр.). При этом пара объект-признак принадлежит бинарному отношению, если объект обладает данным признаком. Например, яблоко является жёлтым фруктом, поэтому пара принадлежит бинарному отношению . Заметим, что изначально не все признаки объектов были бинарными (цвет - категориальный признак), однако они были преобразованы в бинарные путём рассмотрения каждой категории в отдельности. Аналогично, к бинарным можно привести порядковые и количественные признаки, с помощью номинального шкалирования [5].

Перейдём к рассмотрению формальных понятий на заданном контексте. Чтобы определить формальное понятие, необходимо ввести понятие соответствия Галуа.

Соответствием Галуа [3,4], заданном на формальном контексте , называется отношение:

,

.

Иными словами, данное отношение ставит в соответствие множеству объектов множество всех признаков , которые есть у каждого объекта из , а множеству признаков - множество всех объектов , каждый из которых удовлетворяет признакам из . Например, соответствием Галуа для множества объектов является множество признаков (яйцо и теннисный шар имеют общие признаки “белый цвет” и “круглая форма”). Соответствие Галуа является антимонотонным, то есть чем меньше множество объектов, тем больше его признаковое описание.

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

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

,

Последняя эквивалентность следует из антимононотонности соответствия Галуа. Формальные понятия с заданным отношением порядка образуют решётку формальных понятий ([6]). Ниже изображена диаграмма решётки формальных понятий, построенная для контекста из Таблицы 1 (диаграмма взята из статьи [3]).

Рисунок 1. Диаграмма решётки формальных понятий.

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

Общее число формальных понятий на некотором контексте ограничено сверху числом . Для нахождения всех формальных понятий разработано множество алгоритмов, которые работают по-разному в зависимости от свойств входных данных. В рамках данной работы использовался алгоритм AddIntent [7], поскольку он обладает рядом преимуществ:

1. Высокой скоростью;

2. Возможностью эффективно находить все понятия, размер содержания которых не превосходит некоторого значения (тем самым мы можем заранее исключить формальные понятия, в которых мало объектов);

3. Построением диаграммы на найденном множестве формальных понятий.

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

Поскольку формальное понятие определяется своим содержанием:

,

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

1.2 Монотонное соответствие Галуа

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

Определим монотонное соответствие Галуа [8,9] следующим образом:

,

.



Монотонное соответствие Галуа ставит множеству признаков в соответствие множество всех объектов , удовлетворяющих хотя бы одному признаку из . Множеству объектов оно ставит в соответствие все признаки , которыми обладают только объекты из . Заметим, что в отличие от обычного соответствия Галуа, монотонное соответствие Галуа определено по-разному для множества объектов и множества признаков.

Формальное понятие, основанное на монотонном соответствии Галуа, определяется по аналогии с обычным формальным понятием, как пара , , . Для контекста, изображённого на Таблице 1, таким формальным понятием является пара .

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

,

и при этом данное множество формальных понятий с заданным порядком также образуют решётку.

Рассмотрим формальные понятия , и , построенные с помощью антимонотонного соответствия Галуа, такие что , . Чтобы объект принадлежал множеству необходимо, чтобы он принадлежал множествам и , то есть удовлетворял описаниям и . Таким образом, объём формального понятия состоит только из объектов, которые удовлетворяют всем описаниям .

Теперь предположим, что формальные понятия , и были порождены монотонным соответствием Галуа, вместе с этим мы условие , всё ещё выполнено. Тогда, для того чтобы объект принадлежал множеству достаточно, чтобы он принадлежал хотя бы одному из множеств и , то есть удовлетворял описанию или .

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

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

Действительно, если взять произвольное дизъюнктивное формальное понятие в контексте , то для дополнения будут верны следующие равенства:

,

.

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

1.3 Классификация данных на основе замкнутых подмножеств

Предположим, что в нашем контексте есть некоторый целевой признак (класс объекта). Для простоты будем считать, что целевой признак - бинарный (случай, когда он имеет несколько значений, рассматривается аналогично). Так, в контекст из Таблицы 1 можно добавить признак “является ли объект фруктом?”, и получить следующую таблицу (пример взят из работы [3]):

Таблица 2. Пример формального контекста с целевым признаком.

M G

color

form

firm

smooth

is fruit?

1

apple

x

x

x

x

+

2

grapefruit

x

x

x

x

+

3

kiwi

x

x

x

x

+

4

plum

x

x

x

x

+

5

toy cube

x

x

x

x

-

6

egg

x

x

x

x

-

7

tennis ball

x

x

x

x

-

8

mango

x

x

x

x

?

Мы знаем значение целевого признака для некоторых объектов из (в примере для объектов 1-7), и хотим определить его для остальных объектов (8-ого объекта) на основе имеющегося признакового описания.

Обозначим за множество всех объектов, класс которых равен (положительные примеры), а за - множество объектов с классом (отрицательные примеры), и рассмотрим все формальные понятия на контексте (то есть исключаем из контекста объекты, для которых класс не определён). Формальное понятие в новом контексте называется гипотезой, если , . Для примера, изображённого на Таблице 2, формальное понятие является положительной гипотезой, а формальное понятие - отрицательной.

Возьмём объект , для которого значение целевого признака неизвестно (в нашем примере это будет 8-ой объект - “манго”), и рассмотрим множество всех гипотез , для которых выполнено условие . Тогда мы можем определить класс объекта следующим образом



,

где - оценка класса , - гипотеза, - её класс, - некоторая агрегирующая функция. В качестве агрегирующей функции можно взять, например, среднее значение от , и округлить его (чтобы оценка значения целевого признака получилась бинарной).

Для примера из Таблицы 2 объект удовлетворяет 4 гипотезам:

,

,

,

.

Все указанные гипотезы классифицируют объект как положительный, поэтому вне зависимости от выбора агрегирующей функции мы присвоим объекту “манго” класс “фрукт”.

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

1.4 Меры качества формальных понятий

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

1. Меры, характеризующие качество классификации формального понятия;

2. Меры, характеризующие значимость формального понятия.

Для первой группы метрик мы будем предполагать, что на множестве объектов нашего формального контекста задано отношение

,

определяющее класс каждого объекта.

Чистота формального понятия

Чистотой формального понятия назовём максимальную долю объектов одного класса в формальном понятии.

,

Иными словами, чистота является полнотой следующего классифицирующего правила:

,

где - наиболее распространённый класс на множестве .

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

Заметим, что если условие не выполнено, то мы не получаем никакой информации о классе объекта .

F-мера

Рассмотрим некоторое формальное понятие , и зададим на его основе классифицирующее правило:

,

где - наиболее часто встречаемый класс в множестве :

,

- любой другой класс, кроме класса .

Точность такого классификатора определяется как

,

а его полнота как

,

где - количество объектов класса , для которых выполнено ,

- количество объектов любого класса кроме , для которых выполнено ,

- количество объектов класса , для которых не выполнено .

Тогда F-мерой [10] классификатора называется выражение

,

Отметим ещё раз, что чистота формального понятия и полнота соответствующего классифицирующего правила эквиваленты. В связи с этим F-меру можно рассматривать как смещение чистоты с учётом классов других объектов. Так, в случае с конъюнктивными формальными понятиями, в общем случае чистота будет высокой у “узких” формальных понятий с маленьким объёмом . Однако, в силу учёта других объектов, F-мера будет выше у более общих формальных понятий, пускай и с большей долей контрпримеров в объёме.

Таким образом, в случае с F-мерой мы получаем некоторую информацию о классе даже тогда, когда условие не выполнено.

Точность

Для определения точности будем использовать то же классифицирующее правило, что использовали для F-меры. Точностью формального понятия назовём меру

,

Данная мера также характеризует способность формального понятия “отрицать” класс для объекта , если не выполнено , но в отличие от F-меры она учитывает объекты разных классов с одинаковыми весами. Однако это является и недостатком данной меры: в случае, когда в исходном наборе данных один класс будем сильно доминировать над другим, данная мера будет выбирать формальные понятия, которые плохо классифицируют объекты меньшего класса.

Устойчивость формального понятия

Данная мера не имеет отношение к задаче классификации объектов и характеризует случайность образования некоторого формального понятия. Устойчивость формального понятия [11] считается по формуле

,

то есть рассматриваются все подмножества объёма формального понятия, и считается доля подмножеств, содержание которых не изменилось.

Таблица 3. Пример устойчивого формального понятия (конъюнктивного и дизъюнктивного)

M G
.	x	x	x
.	x	x	x
.				x	x
.				x

Например, формальное понятие , представляющего собой “прямоугольник” (объекты из имеют признаки только из множества ), имеет устойчивость . В случае с дизъюнктивными формальными понятиями устойчивость равна , если все объекты из имеют все признаки из (то есть в контексте мы получаем тот же “прямоугольник”). Действительно, такое формальное понятие вряд ли образовалось случайно, и скорее всего признаки определяют некоторый класс объектов. В случае, когда формальное понятие получено случайным пересечением строк, мера устойчивости принимает низкие значения (например, ). Поскольку указанная выше формула требует перебора всех подмножеств объёма формального понятия (которых ), то мы будем использовать оценку устойчивости снизу, полученную в работе [16].

,

где - множество всех формальных понятий, являющихся “соседями снизу” формального понятия на диаграмме решётки формальных понятий, .

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

,

Поддержка характеризует “распространённость” формального понятия среди объектов из .

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

1.5 Нейронная сеть

Нейронная сеть [5] - это модель, которая представляет функцию , где - пространство входных параметров, - множество значений класса объекта, в виде сети с последовательной активацией нейронов. Нейронная сеть имеет архитектуру, которая в общем виде представляет собой последовательность слоёв, соединённых между собой рёбрами.

Рисунок 2. Пример архитектуры нейронной сети.

Как видно на Рисунке 2, все слои делятся на три типа:

1. Входной слой. Данный слой представляет собой набор атрибутов исходного набора данных.

2. Скрытые слои. Слои, в которых происходят промежуточные вычисления активации нейронов.

3. Выходной слой. Данный слой определяет класс подаваемого на вход объекта. В нашем случае число выходных нейронов равно числу всех возможных классов в наборе.

Каждое ребро, соединяющее нейроны, имеет свой вес. Активация нейронов скрытых и выходного слоёв определяется как некоторая монотонная функция от линейной свёртки активаций предыдущих нейронов с соответствующими весами .

,

где - активация нейрона, - функция активации, - множество соседних с нейронов с предыдущего слоя, - вес соответствующей связи.

Существует много разных функций активации нейронов [5], в рамках данной работы будут рассмотрены следующие из них:

1. Sigmoid

,

Сигмоида переводит линейную свёртку весов в отрезок .

2. Hyperbolic tangent

,

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

3. Rectify

,

Сохраняет линейность, при этом всем не активированным нейронам присваивает 0 (тем самым, отрицательная активация не влияет на дальнейшее распределение весов).

4. Softmax

,

Нормирует активацию, благодаря чему норма активаций в слоях не меняется.

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

1.6 Обучение нейронной сети. Градиентный спуск

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

,

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

Данную функцию можно минимизировать из условия равенства 0 первых производных

.

Метод градиентного спуска [12] делает это итерационно, на каждом шаге вычисляя направление градиента целевой функции и изменяя параметры в противоположном направлении. Начальные веса, как правило, назначаются произвольно из некоторого распределения с маленькой дисперсии, однако в рамках данной работы мы будем также рассматривать вариант преобучения нейронной сети начальными весами, полученными исходя из свойств формальных понятий.

Существуют различные вариации данного метода, в рамках данной работы мы будет рассматривать следующие:

1. Momentum

,

,

В градиентном спуске с моментом мы запоминаем общую траекторию спуска и корректируем её в соответствии с текущим направлением градиента.

2. RMSProp

,

,

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

3. Adadelta



,

,

,

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

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



2. Построение архитектуры нейронной сети

В данном разделе мы опишем общий принцип построения архитектуры нейронной сети на основе диаграммы решётки формальных понятий.

2.1 Общий вид нейронной сети, построенной по решётке формальных понятий

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

,

Иными словами, мы рассматриваем подмножество всех формальных понятий, количество признаков в которых либо не превосходит , либо среди них можно выбрать признаков, которым будет удовлетворять всё тоже множество объектов. Это позволяет исключить слишком специфичные (для конъюнктивных) или слишком общие (для дизъюнктивных) формальные понятия, а также существенно уменьшает время нахождения формальных понятий и построения диаграммы. Напомним, что алгоритм AddIntent позволяет нам эффективно находить формальные понятия с необходимым размером содержания, а также строить по ним диаграмму. Диаграмму решётки, построенной на множестве , мы в дальнейшем будем называть диаграммой уровня .



Рисунок 3. Диаграмма и архитектура сети

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

,

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

1. Построить диаграмму уровня ;

2. Исключить все несодержательные понятия из диаграммы;

3. Соединить нижние формальные понятия с классами объектов.

2.2 Выбор оптимального набора формальных понятий

Выше в теоретической части мы рассмотрели пять мер качества формальных понятий:

1. Чистота;

2. -мера;

3. Точность;

4. Устойчивость;

5. Поддержка.

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

,

,

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

Кроме этого, формальные понятия, которые будут находиться в последнем скрытом слое, и соединяться с классами объектов, должны хорошо определять класс объектов. Поэтому из последнего слоя дополнительно выбирается подмножество понятий из условия максимизации меры классификации (чистоты, F-меры или точности).

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

Алгоритм 1

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

Шаг 1:

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

Шаг 2:

Пусть - множество объектов, правильно классифицируемых понятием . Исключим из объёма всех формальных понятий и из , после чего заново пересчитаем меру и переходим к шагу 1.

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

Алгоритм 2

Данный алгоритм назначает веса объектам и пересчитывает меру в зависимости от частоты встречаемости объекта.

При инициализации алгоритма всем объектам присваивается вес , при этом мера считается с учётом этих весов:

,

.

Также при инициализации алгоритма мы выбираем параметр .

Шаг 1:

Среди всех формальных понятий выбираем максимальное по мере с учётом весов , обозначим его за . Добавляем к множеству лучших классификаторов. Если количество отобранных классификаторов равно , то заканчиваем алгоритм.

Шаг 2:

Обновляем веса по следующей формуле:



,

где , если верно классифицируется ,

, если неверно классифицируется ,

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

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

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

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



3. Оптимизация архитектуры нейронной сети из конъюнктивных понятий

В данной главе мы будем рассматривать классические формальные понятия, построенные с помощью антимонотонного соответствия Галуа. Сравнение различных моделей построения архитектуры нейронной сети будет производиться экспериментальным путём. Качество построенной архитектуры будет определяться двумя метриками: точностью классификации и скоростью сходимости нейронной сети.

Для сравнения мы будем использовать сгенерированные данные различной плотности, а также наборы данных “Титаник” и “Mammographic Masses”. Сгенерированные наборы данных будут трёх типов:

1. Разреженные (плотность “единиц” в контексте = ) - набор данных ;

2. Средней плотности (плотность = ) - набор данных ;

3. Плотные (плотность = ) - набор данных .

При этом количество объектов в наборах равно , количество атрибутов - 15 + 1 целевой признак (бинарный). Выбранное количество объектов и атрибутов обусловлено средними размерами реальных наборов данных, которые будут использоваться в дальнейшем для сравнения с другими моделями.

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

1. Сначала была составлена матрица корреляций размера :

,

где - сгенерированный на предыдущем этапе контекст.

2. Затем был сгенерирован вектор-столбец , состоящий из значений из равномерного распределения на . Чтобы учесть корреляцию между объектами, считалось его произведение с матрицей корреляции:

,

3. В итоге значение целевого признака определялось функцией:

,

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

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

Описывая реальные датасеты, количество объектов в наборе “Титаник” равно 890, количество атрибутов (с учётом приведения в бинарные) - 14. В наборе всего два класса, доля объектов одного класса составляет . Данный набор мы будем в дальнейшем обозначать буквой . Другой реальный набор данных - “Mammographic Masses” - состоит из 961 объекта и 18 атрибутов, доля объектов одного класса составляет . Этот набор мы будем обозначать буквой , соответственно.

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

Все объекты исходного набора данных мы будем разделять случайным образом на 3 выборки: обучающую (), валидационную () и тестовую (). На основе обучающей выборки мы будем строить архитектуру сети и обучать веса. Валидационную выборку будем использовать для контроля переобучения нейронной сети. На тестовой выборке будем считать метрики качества модели.

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

3.1 Выбор глубины нейронной сети

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

Рассмотрим четыре модели:

Сеть строится только из понятий с двумя признаками и их замыканием (используется 2-х уровневая диаграмма);

Сеть строится из понятий с не более тремя признаками и их замыканием;

Сеть строится из понятий с не более четырьмя признаками и их замыканием;

Сеть строится из понятий с не более пятью признаками и их замыканием.

Теперь посмотрим, насколько с увеличением уровня глубины строимой диаграммы будет увеличиваться точность, и расти количество шагов, необходимых для обучения модели. Результаты занесены в Таблицу 4. Точность и F-мера измеряются в процентах, и округлены до десятых долей процента. Количество итераций, необходимых для обучения весов нейронной сети, округлено до целого числа.

Таблица 4. Результаты сравнения глубины построенной сети.

набор данных	точность	F-мера	число итераций
	I	II	III	IV	I	II	III	IV	I	II	III	IV
53.5	53.6	48.4	48.4	52.8	52.7	32.6	32.6	45	77	32	32
57.5	58.0	58.0	48.8	50.0	51.3	51.3	32.6	44	97	106	36
55.5	56.4	56.4	44.5	48.2	49.1	49.1	30.8	55	112	115	34
77.1	78.5	78.7	60.4	76.4	76.7	76.7	37.6	54	122	140	35
76.8	78.9	78.9	51.2	51.4	78.9	78.9	33.8	48	105	131	34

Заметим, что почти на всех наборах точность и F-мера практически не увеличивались от модели II к модели III, то есть при добавлении третьего слоя, состоящего из формальных понятий с четырьмя признаками качество классификации не сильно увеличивалось. На случайных наборах качество классификации и вовсе оставалось на одном уровне, начиная с однослойной нейронной сети. На основании этого можно сделать предположение, что глубина архитектуры сети зависит от кластерной структуры входного набора данных (чем больше кластеров в наборе и чем глубже их иерархия, тем глубже стоит строить диаграмму решётки формальных понятий). Также хорошим критерием выбора глубины может служить средняя чистота формальных понятий на последнем скрытом уровне. Так, судя по графику на Рисунке , можно заметить, что она начинает падать, когда рассматривается слишком глубокая часть диаграммы.



Рисунок 4. Зависимость чистоты ФП последнего слоя от глубины рассматриваемой диаграммы.

К сожалению, автору неизвестно, почему при рассмотрении диаграммы большей глубины нейронная сеть перестаёт сходиться (это видно по результатам модели IV). В дальнейшем выбор глубины решётки будет производиться на основании динамики изменения чистоты формальных понятий с ростом уровня построенной диаграммы.

3.2 Сравнение мер качества формальных понятий

В теоретической части мы ввели три меры, характеризующие формальные понятия по качеству классификации, а именно:

1. Чистоту

,

2. Точность

,

3. -меру

.

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

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

Таблица 5. Сравнение различных методов фильтрации формальных понятий.

набор данных	алгоритм	точность	F-мера
.	1	53.6	53.2	53.3	52.4	52.5	53.3
	2	53.6	53.7	53.7	52.7	52.8	53.3
.	1	57.5	59.3	59	50.9	51	56.2
	2	58.0	59.3	59.1	51.3	51.0	56.6
.	1	56.9	55.0	56.5	49.2	42.2	51.9
	2	56.4	54.9	56.7	49.1	42.1	52.3
.	1	78.4	79.2	78.8	77.2	75.7	78.3
	2	78.7	79.2	79.4	77.7	76.5	78.1
.	1	78.1	74.8	78.6	77.9	74.4	78.6
	2	78.3	74.5	78.7	76.2	74.3	78.7

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

В дальнейшем при выборе лучших формальных понятий мы будем использовать 2-ой алгоритм (основанный на переназначении весов) с F-мерой. Выбор второго алгоритма обуславливается тем, что он требует меньше вычислений (ему не нужно пересекать объёмы понятий), и поэтому работает быстрее.

3.3 Преобучение нейронной сети с использованием формальных понятий

В данном разделе мы рассмотрим использование формальных понятий для назначения начальных весов связям между нейронами. Обычно нейронная сеть инициализируется со случайными весами, что в итоге приводит к тому, что модель может сходиться совсем по-разному на двух одинаковых наборах данных. Чтобы уменьшить фактор случайности выбора и не установить заведомо ложные веса, параметры модели инициализируются из некоторого распределения с нулевым средним и очень маленькой дисперсией. Существуют алгоритмы преобучения модели [13,14], однако они требуют дополнительных итераций для обучения весов без информации о классе объектов. В рамках данной работы мы предлагаем несколько простых методов для назначения начальных весов сети, построенной по формальным понятиям. Ниже представлен список методов.

a. Вероятность перехода:



,

где - объём формального понятия, соответствующего нейрону , - объём формального понятия, соответствующего нейрону , - вес ребра от нейрона к нейрону . При этом вес связи от понятия к классу определяется как

.

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

b. Нормированная мощность объёма следующего формального понятия:

,

где - next neighbors of - все соседи нейрона выше по архитектуре сети. То есть мы берём все нейроны, в которых входит ребро из , считаем мощность объёмов соответствующих понятий и нормируем их на общую сумму. В итоге мы получаем, что сумма всех весов, выходящих из одного нейрона, равняется 1. При этом для связей с классами объектов начальные веса останутся прежними (в силу того, что множества объектов, принадлежащих разным классам, не пересекаются):

,



c. Коэффициент Кетле [5] для чистоты формального понятия:

,

Данный коэффициент показывает, насколько увеличивается вероятность объекта из принадлежать классу , если добавить условие принадлежности объёму , где класс - наиболее вероятный класс для формального понятия . При этом верны следующие равенства для связей с классами:

,

,

Такой коэффициент сильно отличается от предыдущих двух. Его основное правило - давать больший вес тем рёбрам, которые соединены с чистыми формальными понятиями, при условии совпадения наиболее вероятного класса для понятий и . Если же наиболее распространённые классы в двух понятиях различаются, то вес получается отрицательными. Чем сильнее разница в классификации объектов для понятий и , тем больше начальный вес по модулю.

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

· Sigmoid;

· Tanh;

· Rectify.

Результаты проведённых экспериментов записаны в Таблицу 6. Для того чтобы полученные результаты не были слишком объёмными, мы исключили из рассмотрения случайные наборы и , так как полученные на них результаты не дают нам дополнительной информации о том, какой из методов назначения весов лучше. Символами , и обозначены методы назначения начальных весов, символ соответствует случайной инициализации весов из нормального распределения с .

Таблица 6. Результаты сравнения функций активации и методов выбора начальных весов.

набор данных	функция активации	точность	F-мера	число итераций
.	sigmoid	56.1	54.7	54.7	56.2	38.9	39.2	39.2	46.6	62	63	55	56
	tanh	56.0	55.3	51.7	56.5	47.3	46.1	39.6	51.8	87	84	61	56
	rectify	54.6	54.8	50.2	54.7	43.3	43.2	37.4	42.8	52	52	53	54
.	sigmoid	69.9	67.2	62.0	79.4	61.1	59.7	50.0	77.0	102	94	55	93
	tanh	74.6	73.1	64.1	80.3	71.6	70.8	51.7	78.9	103	107	57	95
	rectify	68.2	68.1	63.5	61.4	58.7	57.3	47.1	40.7	57	56	54	53
.	sigmoid	80.4	80.2	67.4	78.7	80.3	80.0	63.1	78.7	89	91	56	86
	tanh	81.0	79.5	67.3	81.1	80.9	79.4	63.1	81.0	94	83	56	72
	rectify	68.0	67.3	65.2	64,8	61.0	62.4	62.7	62.6	54	54	54	54

Как видно из полученных результатов, гиперболический тангенс даёт лучшие результаты в плане точности построенной модели. В то время как c функцией активации rectify полученная сеть практически никогда не сходится, и выдаёт результат чуть лучше произвольного выбора классов. Вместе с тем можно заметить, что назначение начальных весов, особенно по методу "", в данном случае сильно увеличивает точность модели. Это связано с тем, что начальные веса из модели назначались таким образом, что для каждого объекта , подаваемого на нейронную сеть, активировались в большей степени именно те нейроны, формальным понятиям которых принадлежит объект . В итоге, даже без обучения весов, мы получали модель, которая способна классифицировать объекты (не случайным образом), пускай и с плохой точностью.

В случае с другими функциями активации случайное назначение весов сработало лучше (дало лучшую точность за меньшее количество итераций). Это объясняется тем, что в случае со случайными (маленькими) весами нейронная сеть сама выбирает, как изменить параметры, чтобы минимизировать функцию потерь. В случае с назначенными весами нейронная сеть вынуждена искать локальный минимум функции потерь вблизи с инициализированными весами, и данный локальный минимум далеко не всегда является глобальным для функции потерь. Несмотря на это, результат, получаемый от обучения нейронной сети с заранее выбранными начальными весами, получается более стабильным. Так, например, на Рисунке 5 изображён бокс плот точностей полученных моделей нейронной сети с гиперболическим тангенсом в качестве функции активации. На графике видно, что хоть точность нейронной сети с начальными весами, инициализированными по модели “” и ниже, она находится в узком интервале, когда точность модели со случайно заданными начальными весами сильно колеблется.

Рисунок 5. Сравнение полученной точности для случайных начальных весов и весов, взятых по модели "a", на примере набора D ("Титаник").



4. Оптимизация архитектуры нейронной сети из дизъюнктивных понятий

В данной главе, по аналогии с предыдущей, мы будем сравнивать различные модели построения архитектуры нейронной сети, построенной на основе диаграммы решётки дизъюнктивных формальных понятий. Сравнение будет производиться на данных , , . В силу того, что дизъюнктивные понятия следует рассматривать на разреженных данных (на плотных наборах объёмы дизъюнктивных формальных понятий содержат все объекты), то наборы и в данной главе мы не будем использовать.

4.1 Сравнение нейронной сети и диаграммы формальных понятий

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

Рассмотрим простой пример, возьмём часть диаграммы решётки конъюнктивных формальных понятий, и соответствующую ей часть архитектуры нейронной сети.

Рисунок 6. Сравнение подходов различных моделей

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

Данное различие обуславливается тем, что в нейронной сети отдельно взятый нейрон активируется, если хотя бы один соседней нейрон до него активировался. Если же смотреть на диаграмму формальных понятий, то принадлежность объекта формальному понятию означает, что он должен принадлежать всем формальным понятиям выше на диаграмме. Разница в подходах этих двух моделей не означает, что мы не можем использовать формальные понятия для построения архитектуры нейронной сети. Смысл нашей модели в том, что с помощью АФП мы оцениваем глубину иерархии кластерной структуры в исходном наборе данных, что позволяет определить количество скрытых слоёв и исключить лишние рёбра между узлами. Однако, в силу разницы моделей, начальные веса, что мы хотим назначить нейронной сети на основе характеристик соответствующих формальных понятий, ей не подходят. Поэтому при обучении таких начальных весов мы получили в предыдущем разделе точность и скорость сходимости хуже, чем при случайном назначении весов.

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



4.2 Сравнение мер качества формальных понятий

В данной части мы проверим, какая из мер качества лучше работает для фильтрации дизъюнктивных формальных понятий. Как и раньше мы рассматриваем три меры:

1. Чистота;

2. Точность;

3. -мера.

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

,

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

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

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

набор данных	точность	F-мера
.	56.0	52.7	51.5	48.5	45.8	34.0
.	80.3	79.4	77.2	79.0	78.5	75.8
.	82.0	79.9	81.1	82.0	79.6	80.9

Как видно из Таблицы 7, все меры дают схожие результаты. Чуть лучше показывает себя фильтрация понятий на основе их чистоты. В отличие от модели с конъюнктивными понятиями, F-мера работает не лучше других мер. Скорее всего, это связано с тем, что в случае с конъюнктивными формальными понятиями самыми чистыми были понятия, в которых было мало объектов (в связи с чем доля объектов одного класса была высокой). В то же время такие формальные понятия могли быть плохими классификаторами. В случае же с дизъюнктивными формальными понятиями, чем глубже (ниже) находится понятие на диаграмме решётки, тем больше в нём объектов. Поэтому мера чистоты в данном случае не коррелировала с “узкостью” понятия, и выбранные на её основе понятия оказались хорошими классификаторами.

4.3 Преобучение нейронной сети

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

Поскольку диаграмма решётки понятий, построенных с помощью монотонного соответствия Галуа, строится от частных понятий к более общим, в отличие от диаграммы конъюнктивных формальных понятий, то и методы назначения начальных весов будут отличаться:

a. Достоверность перехода:

,

то есть теперь мы делим мощность объёма текущего формального понятия к мощности объёма следующего. Вес связи от понятия к классу при этом не меняется:

,

b. Нормированная мощность объёма предыдущего формального понятия:

,

где - previous neighbors of - все соседи нейрона ниже по архитектуре сети. Вес связи от понятия к классу также не меняется.

,

c. Коэффициент Кетле.

Преобучение мы будем сравнивать со случайным назначением весов (модель ). Как и в предыдущий раз, мы также параллельно будем сравнивать три функции активации:

· Sigmoid;

· Tanh;

· Rectify.

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

Результаты проведённых экспериментов занесены в Таблицу 8.



Таблица 8. Результаты преобучения нейронной сети из дизъюнктивных формальных понятий.

набор данных	функция активации	точность	F-мера	число итераций
sigmoid	56.2	56.0	54.2	56.0	46.3	46.1	42.0	48.5	88	87	61	133
	tanh	56.1	56.3	53.9	56.7	46.3	46.4	41.9	49.1	94	98	57	128
	rectify	55.3	55.3	53.7	52.1	44.8	44.7	41.3	40.7	56	56	53	54
sigmoid	78.0	78.1	67.3	80.3	76.5	76.5	52.4	79.0	76	79	58	91
	tanh	78.4	77.9	71.2	80.8	76.3	75.8	61.5	78.9	89	88	63	83
	rectify	66.4	66.4	65.2	65.3	47.6	47.6	48.9	49.4	56	55	53	53
sigmoid	76.7	76.9	72.8	82.0	75.4	75.1	69.9	82.0	99	103	121	114
	tanh	78.7	78.6	69.7	82.3	77.8	77.5	65.0	82.3	82	81	64	82
	rectify	58.9	58.8	58.0	57.9	46.0	45.7	45.1	45.4	56	54	54	53

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

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



5. Сравнение с другими методами классификации данных

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