Модели распознавания_ основанные на различных способах обучения. Часть 2 (2015 Лекции (Сенько)), страница 2

,

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

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

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

Рис. 3 На рисунке проиллюстрирована аппроксимирующая способность нейронных сетей. с различным числом внутренних слоёв.

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

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

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

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

4.3 Решающие деревья и леса

4.3.1 Решающие деревья

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

Рис. 4. Изображена структура решающего дерева, оценивающего стоимость квадратного метра жилых помещений. Для простоты выделяются два уровня стоимости – высокий и низкий.

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

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

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

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

При этом используется несколько видов индексов, включая:

- энтропийный индекс неоднородности,

- индекс Джини,

- индекс ошибочной классификации.

Энтропийный индекс неоднородности вычисляется по формуле

_,

_{где - доля объектов класса в выборке . При этом принимается, что . Наибольшее значение принимает при равенстве долей классов. Наименьшее значение достигается при принадлежности всех объектов одному классу.} Индекс Джини вычисляется по формуле

_.

Индекс ошибочной классификации вычисляется по формуле

_.

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

_{где и являются долями и в полной обучающей выборке .}

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

_{Одним из способов достижения более высокой обобщающей способности является использования критериев остановки, позволяющих остановит процесс построения дерева до того, как будет достигнута полная однородность концевых вершин.}

_{Рассмотри несколько таких критериев.}

_{1. Критерий остановки по минимальному допустимому числу объектов в выборках, соответствующих концевым вершинам.}

_{2. Критерий остановки по минимально допустимой величине индекса . Предположим, что некоторой вершине соответствует выборка , для которой найдены оптимальный признак вместе с оптимальным предикатом, задающим разбиение . Вершина считается внутренней, если индекс превысил пороговое значение и считается концевой в противном случае.}

_{3. Критерий остановки по точности на контрольной выборке. Исходная выборка данных}

_{случайным образом разбивается на обучающую выборку и контрольную выборку . Выборка используется для построения бинарного решающего дерева. Предположим, что некоторой вершине соответствует выборка , для которой найдены оптимальный признак вместе с оптимальным предикатом, задающим разбиение .}