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

Оптимальные аппроксимирующие функции

Пусть 𝑎 – функция вида 𝑎 : 𝑋 → 𝑌 .
∀ ∈ 𝑌 запись 𝑎⁻¹() обозначает прообраз относительно 𝑎:
𝑎⁻¹() = { ∈ 𝑋 | 𝑎() = }.

→
Риск, соответствующий функции 𝑎 : 𝑋 𝑌 определяется как сред- нее значение потери при использовании 𝑎 в качестве АФ:

∑︁
𝑅(𝑎) =
,^′∈𝑌
𝜆^′ (𝑎⁻¹(^′), ). (2.105)

Если 𝜆^′ = [ ^′] , то 𝑅(𝑎) можно интерпретировать как вероят-
ность ошибки при использовании 𝑎 в качестве АФ.

Теорема 6.

Пусть заданы распределение (2.102) и функция потерь (2.104). Минимальное значение риска (2.105) достигается на функции 𝑎, сопо-

∈ ∈

∑︁
ставляющей каждому 𝑋 такой ответ 𝑌 , который минимизирует значение выражения

Доказательство.

𝜆 (, ).
∈𝑌

Согласно определению значения (𝑎⁻¹(^′), ),

,^′∈𝑌
𝑅(𝑎) = ∑︁
^𝜆′ ∑︁
(, ) = ∑︁
∑︁ ∑︁ 𝜆^′ (, ). (2.106)

∈𝑎⁻¹(^′)

^′∈𝑌 ∈𝑎⁻¹(^′) <sup>∈

′∈𝑌</sup> ∈𝑎⁻¹(^′)


∈𝑋

Заметим, что сумма вида ^{∑︀ ∑︀} . . . – это сумма вида ^∑︀ . . ., где
выражение, изображаемое многоточием во второй сумме, получается из

∑︁ ∑︁
выражения, изображаемого многоточием в первой сумме заменой всех вхождений ^′ на 𝑎(). Поэтому (2.106) можно переписать в виде
𝑅(𝑎) = 𝜆_,𝑎()(, ),
∈𝑋 ∈𝑌

∀ ∈ ^∑︀
откуда видно, что 𝑅(𝑎) достигает минимального значения в том и только в том случае, когда 𝑋 сумма 𝜆_,𝑎()(, ) достигает минималь-
∈𝑌
ного значения, что по определению возможно при 𝑎() = .

Теорема 7.

Пусть заданы распределение (2.102) и функция потерь (2.104), при- чем

• 
  ∀ ∈ 𝑌 𝜆 = 0, и
  

• 
  ∀ ∈ ̸
  

, ^′ 𝑌 , если = ^′, то значение 𝜆^′ не зависит от ^′ (обозначим это значение 𝜆).

∈ ∈
Минимальное значение риска (2.105) достигается на функции 𝑎, сопо- ставляющей каждому 𝑋 такой ответ 𝑌 , который максимизирует значение выражения 𝜆 (, ), т.е.
𝑎() = arg max 𝜆(, ). (2.107)
∈𝑌

Доказательство.

Согласно определению риска (2.105) и условиям теоремы,

∑︀
𝑅(𝑎) =

∑︀
,^′∈𝑌
𝜆^′ (𝑎⁻¹(^′), ) =

∑︀

∑︀₋
,^′∈𝑌,
𝜆(𝑎⁻¹(^′), ) =
′

= 𝜆(𝑎⁻¹(^′), ) 𝜆(𝑎⁻¹(), ) =
,^′∈𝑌 ∈𝑌
(2.108)

₌ ∑︀ ∑︀
^∑︀ 𝜆(, ) − ^{∑︀
∑︀} 𝜆(, ).

^{∈𝑌 ′∈𝑌} ∈𝑎⁻¹(^′)
Нетрудно видеть, что
^∈𝑌 ∈𝑎⁻¹()

• 
  сумму ^{∑︀ ∑︀} 𝜆(, ) можно заменить на ^∑︀ 𝜆(, ), и
  

• 
  сумму ^{∑︀ ∑︀} 𝜆(, ) можно заменить на ^∑︀ 𝜆_𝑎()(, 𝑎()),
  

^∈𝑌 ∈𝑎⁻¹()
поэтому (2.108) можно переписать в виде
∈𝑋

𝑅(𝑎) = ^{∑︀ ∑︀} 𝜆(, ) − ^∑︀ 𝜆_𝑎()(, 𝑎()) =


∈𝑌

∈𝑋
= ^∑︀ 𝜆() − ^∑︀ 𝜆_𝑎()(, 𝑎()),



∀ ∈
откуда видно, что 𝑅(𝑎) достигает минимального значения в том и только в том случае, когда 𝑋 выражение 𝜆_𝑎()(, 𝑎()) достигает макси- мального значения, что по определению возможно при 𝑎() = .

Отметим, что функция (2.107), совпадает с функцией

|
𝑎() = arg max 𝜆()( ), (2.109)
∈𝑌

|

()
где (|) = ^(,) – вероятность появления объекта в обучащей выбор- ке, при условии, что ответом на этот объект является . Значение ( ) можно понимать как приблизительную долю (или частоту появления) пары (, ) в подвыборке 𝑆, где
𝑆 = {(, ) ∈ 𝑆 | = }. (2.110) В ряде случаев вместо (2.109) более удобно использовать формулу

∈𝑌
𝑎() = arg max ln (︁𝜆()(|))︁, (2.111)
которая, как нетрудно видеть, определяет ту же функцию, что и (2.109).

3. Построение АФ по обучающей выборке

Пусть задана некоторая ДВМО, причем

• 
  распределение (2.102) неизвестно, и
  

∙
функция потерь (2.104) известна и удовлетворяет условиям теоре- мы 7.

⊆ ×
Также задана некоторая обучающая выборка 𝑆 𝑋 𝑌 , построенная в соответствии с этой ДВМО.
Требуется построить 𝑎_𝑆 вида (2.109), где вместо неизвестных истин- ных значений вероятностей () и (|) должны быть использованы оценки ˆ() и ˆ(|) этих вероятностей, вычисленные по 𝑆.

| |
В качестве оценки ˆ() можно взять, например, ^{|𝑆 |} .

Для вычисления оценки
𝑆
ˆ(|) обозначим записью ₁, . . . ,
после-

довательность первых компонентов пар, входящих в 𝑆, и полагаем

ˆ(|
def ¹
) =

∑︁
[
=1

= ] .

4. Непрерывная вероятностная модель обучения

Во многих задачах машинного обучения множеством объектов 𝑋 яв- ляется R или R. Для данного случая можно определить аналог рас- смотренного выше понятия ДВМО, который называется непрерывной вероятностной моделью обучения (НВМО). В НВМО вместо по- нятия вероятностного распределения используется понятие плотности вероятности (обычно называемой просто плотностью), которая пред- ставляет собой функцию вида
: 𝑋 × 𝑌 → [0, 1],

∈ ×
имеющую излагаемый ниже смысл. Для каждой пары (, ) 𝑋 𝑌

|
значение на паре (, ) будем обозначать записью ( ).
Предполагается, что

• 
  на множестве 𝑋 задана мера Лебега 𝜇,
  
• 
  ∀ ∈ 𝑌 функция вида 𝑋 → R_≥0, отображающая каждый ∈ 𝑋 в
  

(|), предполагается интегрируемой по Лебегу, и

∫︁𝑋
(|)𝑑𝜇 = 1. (2.112)

теграл

_𝑋′ (|)𝑑𝜇 интерпретируется как вероятность появления в обу-
Для_∫︀каждого измеримого подмножества 𝑋^′ ⊆ 𝑋 и каждого ∈ 𝑌 ин-



∫︀ _|
чающей выборке 𝑆 пары с первой компонентой из множества 𝑋^′, при условии, что вторая компонента этой пары равна . Так же, как и в ДВМО, мы предполагаем, что все пары в 𝑆 появляются независимо друг от друга. Если выборка 𝑆 большая, то число _𝑋′ ( )𝑑𝜇 можно пони- мать как приблизительную

• 
  долю тех пар (, ) в 𝑆 (см. (2.110)), у которых ∈ 𝑋^′, или
  
• 
  частоту появления в 𝑆 пар с первой компонентой из 𝑋^′.
  

Множество 𝑌 ответов предполагается конечным или счетным.

∀ ∈
Одной из компонентов НВМО является распределение (обозначаемое тем же символом ) на 𝑌 . 𝑌 число () имеет тот же смысл, что и в ДВМО.
Как и выше, в НВМО можно

• 
  определить понятие риска, соответствующего функции 𝑎 : 𝑋 → 𝑌 ,
  

∙
и доказать, что если функция потерь (2.104) известна и удовлетво- ряет условиям теоремы 7, то оптимальная АФ имеет вид (2.109), где (|) понимается как плотность в точке .
Таким образом, если

• 
  задана некоторая НВМО, причем
  
  • 
    
    |
    плотность ( ) либо неизвестна, либо известна лишь частич- но (например, известно, что она имеет вид 𝜙(, 𝜃), где функция
    

𝜙 известна, а 𝜃 – неизвестный параметр), и

• 
  функция потерь (2.104) известна и удовлетворяет условиям теоремы 7,
  

• 
  ⊆ ×
  

и задана некоторая обучающая выборка 𝑆 𝑋 𝑌 , построенная в соответствии с этой НВМО,
то оптимальную АФ 𝑎_𝑆 можно искать в виде (2.109), где вместо неизвест- ных истинных значений вероятностей () и (|) используются оценки
ˆ() и ˆ(|) этих вероятностей, вычисленные по 𝑆,

| |

𝑆
Как и выше, в качестве оценки ˆ() можно взять ^{|𝑆 |} .

|
Ниже излагаются различные варианты вычисления оценки ˆ( ), в зависимости от вида множества объектов 𝑋 и предположений о классе функций, в котором содержится функция (|) : 𝑋 → [0, 1].
Обозначим записью 𝑋_𝑆 множество первых компонентов пар, входя- щих в 𝑆. Элементы 𝑋_𝑆 будем обозначать записями ₁, . . ., .
Рассмотрим различные виды, которые может иметь множество 𝑋.
1. 𝑋 = R.

• 
  Согласно определению плотности, при небольшом числе ℎ > 0 произведение ()· 2ℎ приблизительно равно количеству точек из 𝑋_𝑆 , попавших в отрезок [ − ℎ, + ℎ].
  

Поэтому ˆ(|) можно определить как долю точек из 𝑋_𝑆 , ле- жащих внутри отрезка [ − ℎ, + ℎ]:




2ℎ




=1

ˆ(|) = ¹ ∑︁[ | − | < ℎ] . (2.113)

• 
  Другой вид оценки (|) – оценка Парзена-Розенблатта:
  

ˆ(|) =



ℎ



^∑︁ 1
ℎ
=1
_𝐾^(︁ − ^)︁

(2.114)

где 𝐾() – четная функция, называемая ядром, такая, что

𝐾() 𝑑 = 1,

^∫︁ +∞

и ℎ – параметр, называемый шириной окна, небольшое по- ложительное число.

𝑆
АФ, построенную в соответствии с приведенным выше определени- ем, будем обозначать записью 𝑎^ℎ, явно указывая ширину окна ℎ. Оптимальным является такое ℎ, которое минимизирует риск

^(,∑︁^)∈𝑆