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

Завершаемость алгоритма Розенблатта

Завершаемость алгоритма Розенблатта обосновывается нижеследующей теоремой, которая называется теоремой Новико´ва.


Теорема 2 (А.Novikoff, 1962) [6], [7].

⊂ ×{− }
Пусть конечная выборка 𝑆 R 1, 1 такова, что свойство (2.12) выполняется для некоторого вектора ˆ, т.е.
∀ (, ) ∈ 𝑆 ⟨, ˆ⟩ > 0.
Тогда алгоритм Розенблатта, применяемый к выборке 𝑆, завершает свою работу после не более чем (𝜎/𝜌)² циклов, где

⟨ ⟩
1

𝜎 = max
(,)∈𝑆
||, 𝜌 =
min , ˆ .
|ˆ| (,)∈𝑆

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

В доказательстве данной теоремы используется неравенство Коши- Буняковского, которое верно для произвольной пары 𝑎, 𝑏 векторов из линейного пространства со скалярным произведением ⟨ ⟩, имеет вид
⟨𝑎, 𝑏⟩ ≤ |𝑎 | |𝑏 | (2.14)
и доказывается следующим образом: ∀ ∈ R
0 ≤ |𝑎 + 𝑏 |² =
= ⟨𝑎 + 𝑏, 𝑎 + 𝑏⟩ =
= ⟨𝑎, 𝑎⟩² + 2⟨𝑎, 𝑏⟩ + ⟨𝑏, 𝑏⟩ =
= |𝑎 |²² + 2⟨𝑎, 𝑏⟩ + |𝑏 |².
Соотношение
∀ ∈ R |𝑎 | + 2⟨𝑎, 𝑏⟩ + |𝑏 | ≥ 0 (2.15)
2 2 2
равносильно тому, что дискриминант
(2⟨𝑎, 𝑏⟩)² − 4 |𝑎 |² |𝑏 |² (2.16) квадратного трехчлена в (2.15) неположителен, т.е.
⟨𝑎, 𝑏⟩² − |𝑎 |² |𝑏 |² ≤ 0,

откуда следует (2.14).
Обозначим записями ⁽⁻¹⁾ и ⁽⁾ значения переменной до и после
–го выполнения цикла в (2.13). Т.к. ⁽⁾ = ⁽⁻¹⁾ + , то

⟨⁽⁾, ˆ⟩ = ⟨⁽⁻¹⁾ + , ˆ⟩ = ⟨⁽⁻¹⁾, ˆ⟩ + ⟨, ˆ⟩ ≥
≥ ⟨⁽⁻¹⁾, ˆ⟩ + |ˆ|𝜌.
Применяя (2.17) раз, и учитывая ⁽⁰⁾ = ^¯0, получаем:
(2.17)

⟨ ⟩ ≤ | | | |
⟨⁽⁾, ˆ⟩ ≥ ⟨⁽⁰⁾, ˆ⟩ + |ˆ|𝜌 = |ˆ|𝜌. (2.18) Согласно неравенству Коши-Буняковского, ⁽⁾, ˆ ⁽⁾ ˆ , по-
этому из (2.18) следует, что
|ˆ|𝜌 ≤ ⟨⁽⁾, ˆ⟩ ≤ |⁽⁾ | |ˆ|,
откуда следует неравенство 𝜌 ≤ |⁽⁾ |, или
²𝜌² ≤ |⁽⁾ |². (2.19)
С другой стороны,
|⁽⁾ |² = ⟨⁽⁻¹⁾ +, ⁽⁻¹⁾ +⟩ = |⁽⁻¹⁾ |² +2⟨, ⁽⁻¹⁾⟩+ ||², (2.20) и поскольку ⟨, ⁽⁻¹⁾⟩ ≤ 0 и || ≤ 𝜎, то из (2.20) следует, что
|⁽⁾ |² ≤ |⁽⁻¹⁾ |² + ||² ≤ |⁽⁻¹⁾ |² + 𝜎². (2.21) Применяя (2.21) раз, и учитывая ⁽⁰⁾ = ^¯0, получаем:
|⁽⁾ |² ≤ 𝜎². (2.22)
Объединяя (2.19) и (2.22) получаем:
²𝜌² ≤ |⁽⁾ |² ≤ 𝜎²,

≤ ≤ ≤
откуда следует неравенство ²𝜌² 𝜎², или 𝜌² 𝜎², или (𝜎/𝜌)².
Таким образом, число выполнений цикла в блок-схеме (2.13) не пре- восходит (𝜎/𝜌)².

3. Модификации алгоритма Розенблатта

Для ускорения процесса нахождения искомого вектора , удовлетворя- ющего условию (2.12), приведенный выше алгоритм можно модифици- ровать:

^(︂⟨ ⟩

)︂

∙
в качестве начального значения в (2.13) можно брать не ^¯0, а любой вектор, рекомендуется брать в качестве начального вектор

¹,
_{|1 |2} , . . . ,
⟨, ⟩

| |²

,
где вектора ¹, . . . , , , определяются следующим образом: если 𝑆
имеет вид {(, ) | = 1, . . . , }, и ∀ = 1, . . . , = (¹, . . . , ),

то

∀ = 1, . . . , = (₁, . . . , ), = (₁ , . . . , )
(это оптимальный выбор, если ⟨, ⟩ близко к 0 при ̸= ),

∙
действие := + можно заменить на := + 𝜂, где 𝜂 – фиксированное положительное число.

3. Метод градиентного спуска

1. Понятие градиентного спуска

{ | }
Как было отмечено в пункте 1.2.3, если задача ML заключается в нахож- дении по обучающей выборке 𝑆 = (, ) = 1, . . . такого параметра
, который минимизирует функцию риска


₁ ∑︁

𝑆










=1

𝑄(𝑎 ) = ℒ(𝑎( , ), ), (2.23)
то в том случае, когда функция (2.23) дифференцируема по , для на- хождения искомого параметра можно использовать метод градиент- ного спуска. Данный метод заключается в итеративном построении по- следовательных приближений к искомому значению параметра путем небольших изменений этого параметра. Эти изменения выбираются та- кими, чтобы на каждой итерации новое значение как можно сильнее уменьшало бы функцию (2.23).
Метод градиентного спуска не всегда обеспечивает нахождение па- раметра , минимизирующего функцию (2.23) (параметр с таким свой- ством называется глобальным минимумом). Иногда с помощью этого метода можно найти лишь локальный минимум, т.е. такое значение
, которое невозможно улучшить путем небольших изменений.

2.