Руководство хакера по нейронным сетям. Глава 2: Машинное обучение. Обучение сети на основе метода опорных векторов (SVM)

http://karpathy.github.io/neuralnets/
  • Перевод
Содержание:
Глава 1: Схемы реальных значений
Часть 1:
   Введение   
      Базовый сценарий: Простой логический элемент в схеме
      Цель
         Стратегия №1: Произвольный локальный поиск

Часть 2:
         Стратегия №2: Числовой градиент

Часть 3:
         Стратегия №3: Аналитический градиент

Часть 4:
      Схемы с несколькими логическими элементами
         Обратное распространение ошибки

Часть 5:
         Шаблоны в «обратном» потоке 
      Пример "Один нейрон"

Часть 6:
      Становимся мастером обратного распространения ошибки


Глава 2: Машинное обучение
Часть 7:
      Бинарная классификация

Часть 8:
      Обучение сети на основе метода опорных векторов (SVM)

Часть 9:
      Обобщаем SVM до нейронной сети

Часть 10:
      Более традиционный подход: Функции потерь



В качестве конкретного примера давайте рассмотрим SVM. SVM – это очень популярный линейный классификатор. Его функциональная форма имеет именно такой же вид, как я описывал в предыдущем разделе — f(x,y)=ax+by+c. На данном этапе, если вы видели описание SVM, вы наверняка ожидаете, что я буду определять функцию потерь SVM и погружаться в пояснения свободных переменных, геометрических понятий больших полей, ядер, двойственности и пр. Но здесь я бы хотел воспользоваться другим подходом.

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

«Характеристика силы»:
Если мы пропускаем положительную точку ввода данных через схему SVM, и выходное значение меньше 1, нужно потянуть схему с силой +1. Это положительный пример, поэтому нам нужно, чтобы его значение было выше.

С другой стороны, если мы пропускаем отрицательную точку ввода данных через SVM, и выходное значение больше чем -1, тогда схема дает этой точке ввода данных опасно высокое значение: Необходимо потянуть схему вниз с силой -1.

Кроме натяжения вверх, всегда нужно добавлять небольшое натяжение для параметров a,b (обратите внимание, не на c!), которое будет тянуть их в направлении нуля. Можете представить, будто a,b привязаны к физической пружине, которая привязана к нулю. Как и в случае с физической пружиной, это сделает натяжение пропорциональным значению каждого элемента a,b (закон Гука в физике, кто-нибудь знает?). Например, если a принимает слишком высокое значение, оно будет испытывать сильное натяжение с величиной |a| обратно в сторону нуля. Это натяжение – это то, что мы называем регуляризацией, и оно обеспечивает, чтобы ни один из наших параметров a или b не стал непропорционально большим. Это может быть нежелательно, так как оба параметра a,b умножаются на характеристики ввода x,y (вспоминаем, что наше уравнение имеет вид a*x + b*y + c), поэтому, если какой-либо из них имеет слишком высокое значение, наш классификатор будет слишком чувствительным по отношению к этим параметрам. Это не очень хорошее свойство, так как характеристики могут зачастую быть неточными на практике, поэтому нам нужно, чтобы наш классификатор изменялся относительно гладко, если они раскачиваются в стороны.

Давайте быстро пройдемся по небольшому, но конкретному примеру. Предположим, что мы начали с настройки произвольного параметра, скажем, a = 1, b = -2, c = -1. Тогда, если мы подаем точку [1.2, 0.7],SVM вычислит значение 1 * 1.2 + (-2) * 0.7 — 1 = -1.2. Эта точка помечена как +1 в обучающих данных, поэтому мы хотим, чтобы значение было больше чем 1. Градиент в верхней части схемы будет в таком случае положительным: +1, и будет выполнять обратное распространение ошибки к a,b,c. Кроме того, будет иметь место регуляризационное натяжение на a с силой -1 (чтобы сделать его меньше) и регуляризационное натяжение на b с силой +2, чтобы сделать его больше, в направлении нуля.

Вместо этого предположим, что мы подаем на SVM точку ввода данных [-0.3, 0.5]. Она вычисляет 1 * (-0.3) + (-2) * 0.5 — 1 = -2.3. Метка для этой точки имеет значение -1, а так как -2.3 меньше, чем -1, мы понимаем, что в соответствии с нашей характеристикой силы SVM должна радоваться: вычисленное значение будет крайне отрицательным и будет соответствовать отрицательной метке в этом примере. В конце схемы не будет натяжения (т.е. оно будет нулевым), так как изменения не нужны. Однако, все равно будет присутствовать регуляризационное натяжение на a с силой -1 и на b с силой +2.

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

// Схема берет 5 элементов (x,y,a,b,c), а выдает один элемент
// Она также может рассчитать градиент по отношению к собственным исходным значениям
var Circuit = function() {
  // создаем несколько логических элементов
  this.mulg0 = new multiplyGate();
  this.mulg1 = new multiplyGate();
  this.addg0 = new addGate();
  this.addg1 = new addGate();
};
Circuit.prototype = {
  forward: function(x,y,a,b,c) {
    this.ax = this.mulg0.forward(a, x); // a*x
    this.by = this.mulg1.forward(b, y); // b*y
    this.axpby = this.addg0.forward(this.ax, this.by); // a*x + b*y
    this.axpbypc = this.addg1.forward(this.axpby, c); // a*x + b*y + c
    return this.axpbypc;
  },
  backward: function(gradient_top) { // принимает натяжение сверху
    this.axpbypc.grad = gradient_top;
    this.addg1.backward(); // устанавливает градиент в axpby и c
    this.addg0.backward(); // устанавливает градиент в ax и by
    this.mulg1.backward(); // устанавливает градиент в b и y
    this.mulg0.backward(); // устанавливает градиент в a и x
  }
}


Это схема, которая просто вычисляет a*x + b*y + c и может также рассчитать градиент. В ней используется код логических элементов, который мы создали в Главе 1. Теперь давайте запишем SVM, которая не зависит от фактической схемы. Для нее важны только значения, которые выходят из нее, и она подтягивает схему.

// SVM класс
var SVM = function() {

  // произвольные значения первоначального параметра
  this.a = new Unit(1.0, 0.0); 
  this.b = new Unit(-2.0, 0.0);
  this.c = new Unit(-1.0, 0.0);

  this.circuit = new Circuit();
};
SVM.prototype = {
  forward: function(x, y) { // представим, что x и y являются сегментами
    this.unit_out = this.circuit.forward(x, y, this.a, this.b, this.c);
    return this.unit_out;
  },
  backward: function(label) { // метка равна +1 или -1

    // сбрасываем натяжение на a,b,c
    this.a.grad = 0.0; 
    this.b.grad = 0.0; 
    this.c.grad = 0.0;

    // вычисляем натяжение на основании того, каким был результат схемы
    var pull = 0.0;
    if(label === 1 && this.unit_out.value < 1) { 
      pull = 1; // значение было слишком низким: подтягиваем вверх
    }
    if(label === -1 && this.unit_out.value > -1) {
      pull = -1; // значение было слишком высоким для положительного примера, подтягиваем вниз
    }
    this.circuit.backward(pull); // записывает градиент в x,y,a,b,c

    // добавляем регуляризационное натяжение для параметров: в сторону нуля и пропорционально значению 
    this.a.grad += -this.a.value;
    this.b.grad += -this.b.value;
  },
  learnFrom: function(x, y, label) {
    this.forward(x, y); // проход вперед (устанавливаем .value во все сегменты)
    this.backward(label); // обратный проход (устанавливаем .grad во все сегменты)
    this.parameterUpdate(); // параметры отвечают на толчок 
  },
  parameterUpdate: function() {
    var step_size = 0.01;
    this.a.value += step_size * this.a.grad;
    this.b.value += step_size * this.b.grad;
    this.c.value += step_size * this.c.grad;
  }
};


Теперь давайте используем SVM с помощью спуска стохастического градиента:
var data = []; var labels = [];
data.push([1.2, 0.7]); labels.push(1);
data.push([-0.3, -0.5]); labels.push(-1);
data.push([3.0, 0.1]); labels.push(1);
data.push([-0.1, -1.0]); labels.push(-1);
data.push([-1.0, 1.1]); labels.push(-1);
data.push([2.1, -3]); labels.push(1);
var svm = new SVM();

// функция, которая рассчитывает точность классификации
var evalTrainingAccuracy = function() {
  var num_correct = 0;
  for(var i = 0; i < data.length; i++) {
    var x = new Unit(data[i][0], 0.0);
    var y = new Unit(data[i][1], 0.0);
    var true_label = labels[i];

    // смотрим, совпадает ли прогноз с имеющейся меткой
    var predicted_label = svm.forward(x, y).value > 0 ? 1 : -1;
    if(predicted_label === true_label) {
      num_correct++;
    }
  }
  return num_correct / data.length;
};

// петля обучения
for(var iter = 0; iter < 400; iter++) {
  // подбираем произвольную точку ввода данных
  var i = Math.floor(Math.random() * data.length);
  var x = new Unit(data[i][0], 0.0);
  var y = new Unit(data[i][1], 0.0);
  var label = labels[i];
  svm.learnFrom(x, y, label);

  if(iter % 25 == 0) { // каждые 10 повторений... 
    console.log('training accuracy at iter ' + iter + ': ' + evalTrainingAccuracy());
  }
}


Этот код выводит следующий результат:

training accuracy at iteration 0: 0.3333333333333333
training accuracy at iteration 25: 0.3333333333333333
training accuracy at iteration 50: 0.5
training accuracy at iteration 75: 0.5
training accuracy at iteration 100: 0.3333333333333333
training accuracy at iteration 125: 0.5
training accuracy at iteration 150: 0.5
training accuracy at iteration 175: 0.5
training accuracy at iteration 200: 0.5
training accuracy at iteration 225: 0.6666666666666666
training accuracy at iteration 250: 0.6666666666666666
training accuracy at iteration 275: 0.8333333333333334
training accuracy at iteration 300: 1
training accuracy at iteration 325: 1
training accuracy at iteration 350: 1
training accuracy at iteration 375: 1 


Мы видим, что изначально точность обучения нашего классификатора была всего 33%, но к концу обучения примеры правильно классифицируются по мере того, как параметры a,b,c настраивают свои значения в соответствии с приложенной силой натяжения. Мы только что обучили SVM! Но пожалуйста, никогда не используйте этот код на деле:) Мы увидим, как можно сделать все намного эффективнее, когда разберемся, что, по сути, происходит.

Количество повторений необходимо. С данными этого примера, с инициализацией этого примера, и с настройкой используемого размера шага, для обучения SVM потребовалось 300 повторений. На практике их может быть намного больше или намного меньше, в зависимости от того, насколько сложной или крупной является проблема, как вы инициализируете, нормализуете данные, какой размер шага используете и так далее. Это модельный пример, но позже я пройдусь по всем лучшим методикам для реального обучения этих классификаторов на практике. Например, окажется, что настройка размера шага является крайне важной и сложной. Небольшой размер шага сделает вашу модель медленной в обучении. Большой размер шага будет обучать быстрее, но если он слишком большой, он сделает так, что ваш классификатор будет хаотически скакать, и это не приведет к хорошему конечному результату. Мы, в конечном итоге, воспользуемся отложенной проверкой данных для более точной настройки, чтобы занять наиболее выгодную позицию для ваших данных.

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

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

var a = 1, b = -2, c = -1; // изначальные параметры
for(var iter = 0; iter < 400; iter++) {
  // подбираем произвольную точку ввода данных
  var i = Math.floor(Math.random() * data.length);
  var x = data[i][0];
  var y = data[i][1];
  var label = labels[i];

  // рассчитываем натяжение
  var score = a*x + b*y + c;
  var pull = 0.0;
  if(label === 1 && score < 1) pull = 1;
  if(label === -1 && score > -1) pull = -1;

  // вычисляем градиент и обновляем параметры
  var step_size = 0.01;
  a += step_size * (x * pull - a); // -a получено в результате регуляризации
  b += step_size * (y * pull - b); // -b получено в результате регуляризации
  c += step_size * (1 * pull);
}


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

Сделаем небольшие пометки по этому поводу: Возможно, вы заметили, что натяжение всегда равно 1,0 или -1. Вы можете представить себе другие варианты, например, натяжение пропорционально тому, насколько серьезной была ошибка. Это приводит к вариации на SVM, которую некоторые люди называют квадратной кусочно-линейной функцией потерь SVM, почему – вы поймете немного позже. В зависимости от различных характеристик вашего набора данных, она может работать лучше или хуже. Например, если у вас очень плохие показатели данных, к примеру, отрицательная точка ввода данных, которая имеет значение +100, ее влияние на классификатор будет относительно незначительным, так как мы будем просто тянуть с силой -1 вне зависимости от того, насколько серьезной была ошибка. На практике мы воспринимаем это свойство классификатора как устойчивость к показателям.

Давайте вкратце повторим. Мы ввели проблему бинарной классификации, где нам даны N D-мерные векторы и метка +1/-1 для каждого. Мы увидели, что мы можем комбинировать эти характеристики с набором параметров внутри схемы с реальными значениями (например, схемы Машины опорных векторов, как в нашем примере). Потом мы можем многократно проводить наши данные через схему и каждый раз изменять параметры таким образом, чтобы выходное значение схемы соответствовало указанным меткам. Изменение зависит, что особенно важно, от нашей способности выполнять обратное распространение ошибки градиентов через схему. В конечном итоге, окончательную схему можно использовать для прогнозирования значений неизвестных примеров!
  • +11
  • 11,6k
  • 3
PAYSTO 53,33
Компания
Поделиться публикацией
Комментарии 3
  • –1
    Отличная статья, спасибо! Но все таки стоит уточнить, что вы тренируете именно линейные SVM, так как они бывают не только таковыми. Это скорее крик души моего перфекциониста. В остальном, у вас замечательные статьи :)
    • 0
      Статьи, к сожалению, не мои, это перевод. Насчет линейности SVM косвенно упоминается во втором предложении этой статьи.
      • +2
        ну таки если говорить о перфекционизме, то свм — это именно линейный классификатор, а то что там применяется кернел трик для нелинейности, так это не фишка а свма, а трюк многих алгоритмов, обоснованный в теореме Ковера

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

      Самое читаемое