Книга представляет собой введение в основные понятия, методы и ал

Элементарные методы и алгоритмы машинного обучения 16

1. 
   Линейно разделимые выборки 16
   
2. 
   Алгоритм обучения Розенблатта 19
   
   1. 
      Описание алгоритма обучения Розенблатта 20
      
   2. 
      Завершаемость алгоритма Розенблатта 21
      
   3. 
      Модификации алгоритма Розенблатта 23
      
3. 
   Метод градиентного спуска 23
   
   1. 
      Понятие градиентного спуска 23
      
   2. 
      Описание метода градиентного спуска 24
      
   3. 
      Модификации метода градиентного спуска 27
      

Метод стохастического градиента 27
Регуляризация 28

4. 
   Метод обратного распространения ошибки для обучения нейронных сетей 29
   
   1. 
      Идея метода 29
      
   2. 
      Описание метода 30
      
   3. 
      Достоинства и недостатки метода 32
      
5. 
   Метод опорных векторов 33
   
   1. 
      Оптимальность аппроксимирующих функций 33
      
   2. 
      Построение оптимальной разделяющей гиперплос- кости для строго линейно разделимой выборки 35
      

Описание задачи 35
Метод решения оптимизационной задачи 37
Применение метода 44

3. 
   Построение оптимальной разделяющей гиперплос- кости по зашумленной выборке 47
   
1. 
   Ядерный метод машинного обучения 51
   
   1. 
      Спрямляющие пространства 51
      
   2. 
      Примеры ядер 55
      
   3. 
      Каноническое гильбертово пространство, определя-
      

емое ядром 57

7. 
   Задача регрессии 60
   
   1. 
      Линейная регрессия 60
      
8. 
   Метрическая модель обучения 63
   
   1. 
      Понятие метрики 63
      
   2. 
      Метод ближайших соседей 64
      
   3. 
      Метод окна Парзена 65
      
   4. 
      Метод потенциалов 66
      
   5. 
      Метод эталонов 67
      
9. 
   Вероятностные модели обучения 68
   
   1. 
      Дискретная вероятностная модель обучения 68
      
   2. 
      Оптимальные аппроксимирующие функции 69
      
   3. 
      Построение АФ по обучающей выборке 72
      
   4. 
      Непрерывная вероятностная модель обучения 72
      
   5. 
      EM-алгоритм 76
      

Число компонентов смеси известно 77
Число компонентов смеси неизвестно 79

Глава 1

Задачи и модели машинного обучения

1. Задачи машинного обучения

   1. Предмет машинного обучения

Машинное обучение (Machine Learning, ML) – это раздел теории искусственного интеллекта, предметом которого является поиск методов решения задач путем обучения в процессе решения сходных задач.
Для построения таких методов используются средства алгебры, ма- тематической статистики, дискретной математики, теории оптимизации, численных методов, и других разделов математики.

2. Обучение функциональным зависимостям

Одно из направлений ML связано с задачами следующего вида: имеются

• 
  множество 𝑋 объектов, и
  
• 
  множество 𝑌 ответов.
  

Предполагается, что существует функциональная зависимость
𝑓 : 𝑋 → 𝑌
между объектами и ответами, но она неизвестна. Известна лишь совокуп- ность 𝑆 пар вида (объект, ответ), называемая обучающей выборкой (training sample):
𝑆 = {(, = 𝑓 ()) ∈ 𝑋 × 𝑌 | = 1, . . . , }.

→
Требуется найти приближенный вид этой 𝑓 путем построения аппрок- симирующей функции (АФ) 𝑎_𝑆 : 𝑋 𝑌 (decision function), такой, что
∀ ∈ 𝑋 𝑎_𝑆() ≈ 𝑓 ().

3. Способ описания объектов

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

• 
  
  • 
    ∈ ℑ
    
  задается множество ℑ признаков объектов (features), каждому признаку сопоставляется множество 𝐷 значений
  

этого признака, и

• 
  ∈ ∈ ℑ
  

каждому объекту 𝑋 и каждому признаку сопоставляется
значение –го признака на объекте .
Множество признаков объектов определяется решаемыми задачами ML. Адекватный выбор этого множества для каждой конкретной задачи ML – нетривиальная проблема, от правильного решения которой суще- ственно зависит успех в решении этой задачи ML.

∈ ℑ
Каждый признак имеет определенный тип. Ниже мы пере- числяем некоторые из таких типов и указываем соответствующие им множества значений 𝐷:

• 
  бинарный: 𝐷 = {−1, 1} или {0, 1},
  
• 
  номинальный: 𝐷 – конечное множество,
  
• 
  порядковый: 𝐷 – конечное линейно упорядоченное множество,
  
• 
  количественный: 𝐷 = R (множество действительных чисел).
  

Для удобства мы будем предполагать, что

• 
  ℑ
  

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

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

∀ ∈

∈ { }
Описание объекта 𝑋 относительно множества 1, . . . , при- знаков – это кортеж (¹, . . . , ) значений каждого из признаков 1, . . . , . Т.к. по предположению = 1, . . . , R, то описание объекта можно рассматривать как элемент векторного пространства R.

∀ ∈
Напомним, что R состоит из всех векторов размерности , т.е. по- следовательностей вида (𝛼₁, . . . , 𝛼), где = 1, . . . , 𝛼 R, операции сложения на данных последовательностях и умножения их на действи-
тельные числа определяются стандартным образом:

(𝛼₁, . . . , 𝛼) + (𝛼^′ , . . . , 𝛼^′
def
𝛼₁ + 𝛼^′ , . . . , 𝛼 + 𝛼^′ ),

1 ^{) = (} 1

= (
𝛼(𝛼₁, . . . , 𝛼) = (𝛼₁, . . . , 𝛼)𝛼 ^def 𝛼𝛼₁, . . . , 𝛼𝛼).

4. Пример задачи машинного обучения

{− }
В этом пункте мы приведем пример одной задачи ML и связанного с ней описания объектов. Данная задача называется задачей кредитно- го скоринга. Объектами в ней являются заявки на выдачу кредита в некотором банке, а ответами – элементы множеста 1, 1 . Для каждого объекта ответ 𝑓 () интепретируется как решение банка:

• 
  ответ «1»: выдать кредит по заявке ,
  
• 
  ответ «−1»: отказать в удовлетворении заявки .
  

Решение банка по удовлетворению заявки является правильным, если

∙
клиент, подавший эту заявку, и получивший кредит, вернет его в должный срок, или

∙
клиент, которому было отказано в удовлетворении заявки , в слу- чае получения этого кредита с высокой вероятностью может не вер- нуть его в должный срок.
Известно множество 𝑆 = {(, ) | = 1, . . . } где ∀ = 1, . . .

• 
  – некоторая заявка на выдачу кредита,
  
• 
  – решение банка по этой заявке, которое является правильным.
  

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

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

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

5.