Translate

понедельник, 5 января 2015 г.

Полное описание теории обобщающей способности завершено

Сегодня завершил полное описание теории обобщающей способности.

Краткий список вопросов на которые теория даёт ответы:

  1. Почему максимальная обучающая способность не не всегда соответствует максимальной обобщающей способности?
  2. Как отличить информативные факторы от неинформативных?
  3. Что делать, если решение неоднозначно?
  4. Как получить неизменное качество классификации при наличии инвариантных искажений информации в выборке и каковы допустимые пределы инвариантности?
  5. Где и в каких случаях искать причины низкой обобщающей способности: в выборке или в алгоритме?
Текст с полным описанием и небольшим примером в формате PDF можно скачать через торрент: http://rutracker.org/forum/viewtopic.php?t=4906858

среда, 31 декабря 2014 г.

Реализация векторной машины на основе библиотеки libVMR

На данный момент реализована библиотека libVMR на Java для решения стандартной задачи машинного обучения в области бинарной классификации:

  • Имеется выборка с примерами и ответами на них.
  • Необходимо по выборке получить адекватную модель бинарной классификации.
Структура векторной машины выглядит так:


  1. Первоначально информация, из которой необходимо будет построить модель для бинарного классификатора, храниться в файле в формате CSV.
  2. C помощью Парсера можно выбрать файл и преобразовать его в двумерный числовой массив, где строки массива - это примеры, а ячейки каждой строки - объясняющие переменные (начальные ячейки) и одна независимая переменная (последняя ячейка)
  3. Двумерный массив с числовыми данными подается на вход векторной машины VMR
    1. Сначала массив поступает в Сепаратор, задачей которого разбить строки на две части: обучающую и контрольную.
    2. Обучающая часть выборки передаётся в Нормировщик, целью которого преобразовать все числа к диапазону от -1 до 1 включительно.
    3. Нормированные данные поступают в Ядерную машину, где из различных комбинаций объясняющих переменных  происходит формирование членов для полинома математической модели.
    4. В конечном итоге, члены полинома передаются Векторной машине, задачей которой является подбор коэффициентов для них. В результате чего, на выходе векторной машины получается математическая модель бинарного классификатора в виде готового полинома
  4. Однако полученная в векторной машине модель не вовсе не обязательно будет пригодной для прикладного применения. Чтобы проверить её на пригодность, необходимо выяснить обобщающую способность модели, Для этой цели предусмотрен Тестер. Тестер берёт модель и проверяет её результативность на контрольной части выборки, ранее полученной путем разделения общих данных в Сепараторе.
Одно дело создать библиотеку для каких нибудь методов машинного обучения, другое дело ей воспользоваться. Чтобы было проще пользоваться библиотекой libVMR, не прибегая к программированию, необходимо создать какой нибудь юзабельный интерфейс, способный решать задачи с помощью библиотеки.

Собственно решение задачи бинарной классификации делится на несколько этапов:

1. Выбор предметной области, в рамках которой будут проводиться исследования.
2. Сбор информации — генеральная выборка
3. Анализ информации — машинное обучение с целью построения модели на одной части выборки (обучающая часть) с последующей проверкой на второй части выборки (контрольная часть).
4. Принятие решения о том, подходит ли построенная модель для прикладного решения задачи или необходимо продолжить исследования в данной области.

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

Имея собранные согласно п. 2, информационные данные для решаемой задачи размещаются в электронной таблице в формате CSV.

После того, как приложение с графическим интерфейсом запущено, можно загрузить информацию в приложение, воспользовавшись пунктом меню File > Open. После загрузки данных, сразу же запускается процесс предобработки и машинного обучения — построения модели на одной части выборки. После завершения построения модели, она проверяется на второй части выборки и выдаются характеристики обобщающей способности (The quality of modeling): чувствительность(Sensitivity of generalization ability), специфичность (Specificity of generalization ability)  и обобщающая способность (Generalization ability) в процентах.


Если характеристики обобщающей способности модели являются подходящими для решения задачи, то готовую модель можно записать в текстовый файл, воспользовавшись пунктом меню File > Save model. Сама модель будет записана в файл в виде формул: нормирования входных данных и формулы принятия решения, где зависимая переменная обозначена, как y. Если значение в формуле принятия решения больше нулевого, то распознаваемый объект принадлежит к классу в выборке со значением зависимой переменной помеченной единицей. Если значение в формуле принятия решения меньше нулевого, то объект принадлежит к классу со значением в выборке значением зависимой переменной помеченной нулём.

 Скачать свежую версию скомпилированного JAR архива для запуска графического приложения, а также исходные коды библиотеки и приложения можно на сайте: http://libvmr.sourceforge.net/

Юрий Решетов

среда, 10 декабря 2014 г.

VMR supplant SVM


At the moment, the most common implementation for an one artificial neuron learning used by support vector machine — SVM by Vladimir Vapnik. SVM's algorithm find a minimum of structural risk. In order to obtain the nonlinearity of input vectors in SVM used kernel tricks, but very carefully. Incorrectly chosen kernel tricks can cause overfitting.

вторник, 9 декабря 2014 г.

Машинное обучение с оппонентом


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

Также нам уже известно, что задачу классификации можно представить в виде системы линейных неравенств.

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

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

Почему?

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

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

Если наш водитель будет многократно ездить от пункта А до пункта Б, то рано или поздно он переобучится. Почему не обучится, а именно переобучится? Дело в том, что когда человек что-то многократно вызубривает, то он запоминает некоторые признаки, способствующие улучшению памяти, но не имеющие отношения к предмету обучения. В более наглых случаях он не только запоминает, но и записывает на какие нибудь, например, бумажные носители такую информацию — шпаргалки, чтобы впоследствии ими воспользоваться.

Если водитель уже многократно проезжал по одной и той же трассе, то он запомнил много различных шпаргалок, которые никакого отношения к дорожному движению не имеют, т. к. не находятся на дорожном покрытии и не являются дорожными знаками или другими автотранспортными средствами. Шпаргалками в этом случае являются различные, хорошо  визуально различимые объекты расположенные вдоль обочины. Это самые настоящие шпаргалки, которые даже записывать нет необходимости, т. к. уже где-то расположены и прекрасно видимы. С помощью этих шпаргалок водитель начинает не только лучше ориентироваться, но и получает более высокие прогнозные способности. Например, увидев возле обочины раскидистый дуб, он уже заранее знает, что далее последует крутой поворот вправо и необходимо притормозить, хотя сам поворот находится вне пределов видимости. Или разглядев на обочине другой хорошо запоминающийся объект, может заранее предположить, что впереди особых препятствий не предвидится, а потому можно прибавить скорость.

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

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

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

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

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

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

Как работает такой алгоритм обучения с оппонентом:

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

Такой алгоритм называется минимаксной стратегией и его эффективность доказана теоремой фон Неймана — Моргенштерна (Математическая теория некооперативных антагонистических игр для двух лиц с нулевой суммой).

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

воскресенье, 7 декабря 2014 г.

Инвариантность - основа обобщающей способности


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

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

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

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

Математический смысл инвариантности основан на том, что если правую и левую часть неравенства умножить на некую отрицательную константу, то знак неравенства изменится на противоположный. При этом само неравенство останется истинным:

A > B
-A < -B

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

a11 * w1 + a12 * w2 + … + a1n * wn Z y1
a21 * w1 + a22 * w2 + … + a2n * wn Z y2
am1 * w1 + am2 * w2 + … + amn * wn Z ym

где:

aij – значение j-го фактора (предиктора - объясняющей переменной) для i-го примера в диапазоне от -1 до 1 включительно
wj – значение j-го весового коэффициента
yi – значение зависимой переменной для i-го примера в диапазоне от -1 до 1 включительно
Z – знак неравенства, принимающий значения: больше, если yi > 0 и меньше, если yi < 0

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

Но мы можем изменить систему линейных неравенств таким образом, чтобы сама система стала инвариантной, но при этом оставалась по прежнему истинной:

(a11 * w1 + a12 * w2 + … + a1n * wn) / y1 > Const
(a21 * w1 + a22 * w2 + … + a2n * wn) / y2 > Const
(am1 * w1 + am2 * w2 + … + amn * wn) / ym > Const

где:

Const – некое константное значение, одинаковое для всех уравнений системы

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

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

Птица:

Крылья = 1
Хвост = 1
Клюв = 1
Оперение = 1
Двигатель = -1
Шасси = -1

Планер:

Крылья = 1
Хвост = 1
Клюв = -1
Оперение = -1
Двигатель = -1
Шасси = 1

Самолёт:

Крылья = 1
Хвост = 1
Клюв = -1
Оперение = -1
Двигатель = 1
Шасси = 1

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

  1. Птица
  2. Планер и Самолёт

  Выполним инвариант для второго класса, т. е. для планера и самолёта:

НЕ Планер:

Крылья = -1
Хвост = -1
Клюв = 1
Оперение = 1
Двигатель = 1
Шасси = -1

НЕ Самолёт:

Крылья = -1
Хвост = -1
Клюв = 1
Оперение = 1
Двигатель = -1
Шасси = -1

Найдём общие признаки для объектов Птица, НЕ Планер и НЕ самолёт. Ими являются признаки: клюв и оперение. Остальные признаки можно удалить, как незначимые, т. е. понизить размерность.

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

Код на Java:

    /**
     * Инвариантное преобразование выборки в результате чего два бинарных класса после преобразования становятся одним общим классом
     * @param sample выборка для инварианта
     * @return инвариантная выборка
     */
    private double[][] getInvariant(double[][] sample) {
     double[][] result = new double[sample.length][sample[0].length];
     for (int i = 0; i < result.length; i++) {
      for (int j = 0; j < result[0].length; j++) {
       result[i][j] = sample[i][j] / this.ideals[i];
      }
     }
     return result;
    }

Получение результатов обученного нейрона


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

Код на Java:



    private KernelTrick trick = null;
    /**
     * Весовые коэффициенты нейронной сети
     */
    private double[] weights = null;
    
    /**
     * Получение результатов обученного искусственного нейрона
     * @param pattern ненормированные входные значения для предъявления нейрону 
     * @return результат
     */
    public double getDecision(double[] pattern) {
        double[] sample = new double[this.maxs.length];
        for (int i = 0; i < sample.length; i++) {
            sample[i] = this.convertToRange(pattern[i], this.maxs[i], this.mins[i]);
            if (sample[i] > 1d) {
                sample[i] = 1d;
            }
            if (sample[i] < -1d) {
                sample[i] = -1d;
            }
        }
        
        sample = this.trick.getTransformData(sample);
        
        double result = 0d;
        for (int i = 0; i < sample.length; i++) {
            result = result + sample[i] * this.weights[i];
        }
        return result;
    }

Сложное полиноминальное ядерное преобразование


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

Код на Java:



package libvmr;

/**
 * Сложное полиминальное ядерное преобразование
 * @author Yury V. Reshetov
 * @version 1.0
 */
public class BigKernelTrick implements KernelTrick{
 
 /**
  * Идентификаторы используемых переменных
  */
 private String[] variables = null;
 
 /**
  * Возвращает идентификаторы используемых переменных
  * @return идентификаторы переменных
  */
 public String[] getVariables() {
  return this.variables;
 }

 /**
  * Преобразовать двумерный массив
  * @return
  */
    public double[][] getTransformData(double[][] samples, double[] results) {
        int count = 1;
        for (int i = 0; i < (samples[0].length); i++) {
            count = count * 2;
        }
        double[][] result = new double[samples.length][count];
        this.variables = new String[count];
        for (int i = 0; i < samples.length; i++) {
            for (int j = 0; j < count; j++) {
             this.variables[j] = "";
                double pp = 1d;
                int z = j;
                for (int n = 0; n < samples[0].length; n++) {
                    if ((z % 2) == 1) {
                        pp = pp * samples[i][n];
                        this.variables[j] = this.variables[j] + " * x" + n;
                    }
                    z = z / 2;
                }
                result[i][j] = pp;                
            }
        }
        return result;
    }

 /**
  * Преобразовать одномерный массив
  * @return
  */
    public double[] getTransformData(double[] sample) {
        int count = 1;
        for (int i = 0; i < (sample.length); i++) {
            count = count * 2;
        }
        double[] result = new double[count];
        for (int i = 0; i < count; i++) {
            double pp = 1d;
            int z = i;
            for (int n = 0; n < sample.length; n++) {
                if ((z % 2) == 1) {
                    pp = pp * sample[n];
                } 
                z = z / 2;
            }
            result[i] = pp;
        }

        return result;
    }
}