машинное обучение. А. М. Миронов Московский Государственный Университет Механикоматематический факультет Кафедра математической теории интеллектуальных систем Введение Книга
 Скачать 1.05 Mb.
|
|
1.2.3 Алгоритмы обучения Алгоритм обучения (learning algorithm) представляет собой алго- ритм нахождения по обучающей выборке 𝑆 такой АФ 𝑎 𝑆 : 𝑋 → 𝑌 , ко- торая обладает описываемыми ниже свойствами оптимальности. Все эти свойства оптимальности являются детализацией следующего требо- вания: 𝑎 𝑆 должно как можно лучше приближать исходную неизвестную функцию 𝑓 : 𝑋 → 𝑌 на всем 𝑋. Для точного описания свойств оптимальности алгоритмов обучения используется понятие функции потерь (loss function), которая сопо- ставляет паре (𝑎 𝑆 , 𝑥), где 𝑥 ∈ 𝑋, число ℒ(𝑎 𝑆 , 𝑥), выражающее величину ошибки аппроксимации 𝑎 𝑆 на объекте 𝑥 ∈ 𝑋. Приведем некоторые примеры функций потерь. ∙ ℒ(𝑎 𝑆 , 𝑥) = [[𝑎 𝑆 (𝑥) ̸= 𝑓 (𝑥)]] (для задач классификации), где для каж- дого утверждения 𝛽 запись [[𝛽]] обозначает – значение 1, если утверждение 𝛽 истинно, и – значение 0, если утверждение 𝛽 ложно, ∙ ℒ(𝑎 𝑆 , 𝑥) = |𝑎 𝑆 (𝑥) − 𝑓 (𝑥)| или (𝑎 𝑆 (𝑥) − 𝑓 (𝑥)) 2 (для задач регрессии). ∙ Пусть 𝑎 𝑆 имеет вид 𝑠𝑖𝑔𝑛(⟨𝑥, 𝑤⟩). 12 Обозначим записью 𝑀 𝑥 (𝑤) число ⟨𝑥, 𝑤⟩𝑓 (𝑥) (эта величина называ- ется отступом (margin)). ℒ(𝑎 𝑆 , 𝑥) может иметь вид [[𝑀 𝑥 (𝑤) < 0]], (1 − 𝑀 𝑥 (𝑤)) 2 , 𝑒 −𝑀 𝑥 (𝑤) , 2 1 + 𝑒 𝑀 𝑥 (𝑤) , log 2 (1 + 𝑒 −𝑀 𝑥 (𝑤) ). Если 𝑆 ′ = {(𝑥 ′ 𝑖 , 𝑦 ′ 𝑖 ) | 𝑖 = 1, . . . , 𝑙 ′ } – какая-либо обучающая выборка, соответствующая той же исходной функции 𝑓 : 𝑋 → 𝑌 , что и 𝑆, то запись ℒ(𝑎 𝑆 , 𝑆 ′ ) обозначает число 1 𝑙 ′ 𝑙 ′ ∑︁ 𝑖=1 ℒ(𝑎 𝑆 , 𝑥 ′ 𝑖 ). В описаниях свойств оптимальности алгоритмов обучения использу- ется понятие функционала эмпирического риска (называемого ни- же просто риском) аппроксимации 𝑎 𝑆 , который определяется как число 𝑄(𝑎 𝑆 ) = ℒ(𝑎 𝑆 , 𝑆). Если 𝑎 𝑆 имеет вид 𝑎(𝑥, 𝑤), где 𝑎 : 𝑋 ×𝑊 → 𝑌 и 𝑤 ∈ 𝑊 (т.е. риск 𝑄(𝑎 𝑆 ) является функцией от 𝑤), то одно из свойств оптимальности алгоритма обучения по обучающей выборке 𝑆 имеет следующий вид: значение па- раметра 𝑤 ∈ 𝑊 , определяющее наилучшую аппроксимацию 𝑎 𝑆 , должно удовлетворять соотношению 𝑤 = arg min 𝑤∈𝑊 𝑄(𝑎 𝑆 ) (1.3) т.е. решение задачи ML сводится к оптимизационной задаче: требуется найти такой параметр 𝑤 ∈ 𝑊 , который минимизирует риск 𝑄(𝑎 𝑆 ). Данная задача лучше всего решается в том случае, когда функция ℒ(𝑎(𝑥, 𝑤), 𝑥) является дифференцируемой по 𝑤, т.к. в этом случае функ- ция 𝑄(𝑎 𝑆 ) тоже является дифференцируемой по 𝑤, и для ее оптимиза- ции можно применять простые методы: находить минимумы с помощью приравнивания к нулю частных производных, использовать методы гра- диентного спуска, и т.п. Если ℒ разрывна, то для решения задачи оптимизации 𝑄(𝑎(𝑥, 𝑤)) лучше всего аппроксимировать ℒ сверху какой-либо непрерывной функ- цией ˜ ℒ ≥ ℒ, и использовать в выражении 𝑄(𝑎(𝑥, 𝑤)) функцию ˜ ℒ вместо функции ℒ. 13 1.3 Проблема переобучения Переобучение – это чрезмерно точная подгонка АФ 𝑎 𝑆 под обучаю- щую выборку 𝑆, которая дает сильные отклонения значений 𝑎 𝑆 (𝑥) от правильных значений (т.е. от 𝑓 (𝑥)) для многих объектов 𝑥, не входящих в обучающую выборку 𝑆. Причины возникновения переобучения: ∙ излишние степени свободы в предсказательной модели 𝑎(𝑥, 𝑤), при- водящие к учету при построении 𝑎 𝑆 различных шумов, неточностей и ошибок в данных, ∙ неполнота обучающей выборки 𝑆. Переобучение можно обнаружить следующими способами. 1. Cкользящий контроль (LOO, leave-one-out). Пусть задана обучающая выборка 𝑆 = {(𝑥 𝑖 , 𝑦 𝑥 𝑖 ) | 𝑖 = 1, . . . , 𝑙}. ∀ 𝑖 = 1, . . . , 𝑙 обозначим записью 𝑆 − 𝑖 выборку {(𝑥 𝑖 , 𝑦 𝑥 𝑖 ) | 𝑖 = 1, . . . , 𝑖 − 1, 𝑖 + 1, . . . , 𝑙}. Признаком переобучения является высокое значение выражения 1 𝑙 𝑙 ∑︁ 𝑖=1 ℒ(𝑎 𝑆−𝑖 , 𝑥 𝑖 ) Данный способ контроля переобучения можно представить в ви- де одного из условий оптимальности алгоритма обучения: данное условие имеет вид 1 𝑙 𝑙 ∑︁ 𝑖=1 ℒ(𝑎 𝑆−𝑖 , 𝑥 𝑖 ) → min 2. Кросс-проверка (cross-validation). Делается разбиение выборки на две части 𝑆 1 и 𝑆 2 , обучение идет по 𝑆 1 , а 𝑆 2 используется для проверки качества обучения. Признаком переобучения является высокое значение выражения 𝑄(𝑎 𝑆 1 , 𝑆 2 ). 14 Данный способ контроля переобучения тоже можно представить в виде одного из условий оптимальности алгоритма обучения: выби- рается 𝑁 различных разбиений обучающей выборки 𝑆 на две части (︁ 𝑆 (1) 1 , 𝑆 (1) 2 )︁ , . . . , (︁ 𝑆 (𝑁 ) 1 , 𝑆 (𝑁 ) 2 )︁ , и одно из условий оптимальности алгоритма обучения имеет вид 𝑁 ∑︁ 𝑖=1 𝑄(𝑎 𝑆 (𝑖) 1 , 𝑆 (𝑖) 2 ) → min 1.4 Основные этапы решения задач машин- ного обучения Решение каждой задачи машинного обучения состоит из следующих ос- новных этапов: ∙ адекватное понимание задачи и данных, ∙ предобработка данных и изобретение признаков и множеств значе- ний каждого из этих признаков, ∙ построение предсказательной модели 𝑎(𝑥, 𝑤), ∙ сведение обучения к оптимизации, ∙ решение проблем оптимизации и переобучения, ∙ оценивание качества, ∙ внедрение и эксплуатация. 15 Глава 2 Элементарные методы и алгоритмы машинного обучения 2.1 Линейно разделимые выборки Во многих задачах ML ∙ множества объектов и ответов имеют вид 𝑋 = R 𝑛 , 𝑌 = {−1, 1}, и ∙ задача обучения заключается в нахождении по выборке 𝑆 АФ 𝑎 𝑆 вида 𝑎 𝑆 (𝑥) = 𝑠𝑖𝑔𝑛 (︁ 𝑛 ∑︁ 𝑖=1 𝑥 𝑖 𝑤 𝑖 − 𝑤 0 )︁ , где 𝑤 1 , . . . , 𝑤 𝑛 , 𝑤 0 ∈ R, (2.1) которая минимизирует риск 𝑄(𝑎 𝑆 ). В некоторых случаях задача нахождения функции 𝑎 𝑆 вида (2.1) име- ет наилучшее решение: можно найти такие значения 𝑤 1 , . . . , 𝑤 𝑛 , 𝑤 0 , для которых 𝑄(𝑎 𝑆 ) = 0. Из определения 𝑄(𝑎 𝑆 ) следует, что равенство 𝑄(𝑎 𝑆 ) = 0 равносильно свойству ∀ (𝑥, 𝑦) ∈ 𝑆 𝑎 𝑆 (𝑥) = 𝑦, т.е. если функция 𝑎 𝑆 имеет вид (2.1), то ∀ ((𝑥 1 , . . . , 𝑥 𝑛 ), 𝑦) ∈ 𝑆 𝑠𝑖𝑔𝑛 (︁ 𝑛 ∑︁ 𝑖=1 𝑥 𝑖 𝑤 𝑖 − 𝑤 0 )︁ = 𝑦. (2.2) Выборка 𝑆, для которой существуют числа 𝑤 1 , . . . , 𝑤 𝑛 , 𝑤 0 ∈ R, удов- летворяющие условию (2.2), называется линейно разделимой. Условие (2.2) можно переписать в виде: ∀ ((𝑥 1 , . . . , 𝑥 𝑛 ), 𝑦) ∈ 𝑆 (︁ 𝑛 ∑︁ 𝑖=1 𝑥 𝑖 𝑤 𝑖 − 𝑤 0 )︁ 𝑦 ≥ 0. (2.3) 16 Если ∃ 𝑤 1 , . . . , 𝑤 𝑛 , 𝑤 0 ∈ R: ∀ ((𝑥 1 , . . . , 𝑥 𝑛 ), 𝑦) ∈ 𝑆 неравенство (2.3) строгое, то выборка 𝑆 называется строго линейно разделимой. Понятие строгой линейной разделимости имеет геометрическую ин- терпретацию: если выборка 𝑆 ⊆ R 𝑛 × {−1, 1} строго разделима, т.е. ∃ 𝑤 1 , . . . , 𝑤 𝑛 , 𝑤 0 ∈ R: ∀ ((𝑥 1 , . . . , 𝑥 𝑛 ), 𝑦) ∈ 𝑆 (︁ 𝑛 ∑︁ 𝑖=1 𝑥 𝑖 𝑤 𝑖 − 𝑤 0 )︁ 𝑦 > 0, (2.4) то гиперплоскость 𝑃 , определяемая уравнением 𝑛 ∑︀ 𝑖=1 𝑥 𝑖 𝑤 𝑖 − 𝑤 0 = 0, разде- ляет множества 𝑆 + def = {𝑥 ∈ R 𝑛 | (𝑥, 1) ∈ 𝑆} и 𝑆 − def = {𝑥 ∈ R 𝑛 | (𝑥, −1) ∈ 𝑆} (2.5) т.е. 𝑆 + и 𝑆 − содержатся в разных полупространствах, на которые 𝑃 де- лит пространство R 𝑛 . Верно и обратное: если для выборки 𝑆 можно най- ти гиперплоскость 𝑃 , такую, что множества (2.5) содержатся в разных полупространствах, на которые 𝑃 делит пространство R 𝑛 , то 𝑆 строго линейно разделима. Напомним, что ∀ 𝑋 ⊆ R 𝑛 ∙ множество 𝑋 называется выпуклым, если ∀ 𝑥, 𝑥 ′ ∈ 𝑋 {𝛼𝑥 + (1 − 𝛼)𝑥 ′ | 𝛼 ∈ [0, 1]} ⊆ 𝑋, (2.6) множество в левой части (2.6) называется отрезком, соединяющим точки 𝑥 и 𝑥 ′ , и обозначается записью [𝑥𝑥 ′ ], ∙ выпуклой оболочкой 𝐶𝑜𝑛𝑣(𝑋) множества 𝑋 называется наи- меньшее (по включению) выпуклое множество, содержащее 𝑋, ∙ 𝐶𝑜𝑛𝑣(𝑋) совпадает с пересечением совокупности всех выпуклых подмножеств R 𝑛 , содержащих 𝑋, ∙ если 𝑋 – конечное множество и имеет вид {𝑥 1 , . . . , 𝑥 𝑛 }, то 𝐶𝑜𝑛𝑣(𝑋) = 𝑛 ∑︁ 𝑖=1 𝛼 𝑖 𝑥 𝑖 , где ∀ 𝑖 = 1, . . . , 𝑛 𝛼 𝑖 ∈ R, 𝛼 𝑖 ≥ 0, 𝑛 ∑︁ 𝑖=1 𝛼 𝑖 = 1, и, кроме того, 𝐶𝑜𝑛𝑣(𝑋) – компактное множество (т.к. оно замкнуто и ограничено). 17 ∀ 𝑥, 𝑥 ′ ∈ R 𝑛 запись |𝑥𝑥 ′ | обозначает длину отрезка [𝑥𝑥 ′ ], которую мы понимаем как евклидову норму ||𝑥 − 𝑥 ′ || вектора 𝑥 − 𝑥 ′ Теорема 1. Конечная выборка 𝑆 ⊆ R 𝑛 × {−1, 1} строго линейно разделима тогда и только тогда, когда 𝐶𝑜𝑛𝑣(𝑆 + ) ∩ 𝐶𝑜𝑛𝑣(𝑆 − ) = ∅. (2.7) Доказательство. Пусть выборка 𝑆 строго линейно разделима, т.е. существует гипер- плоскость 𝑃 , разделяющая 𝑆 + и 𝑆 − . Обозначим записями 𝑍 1 , 𝑍 2 полу- пространства, на которые 𝑃 делит R 𝑛 , и записями ∘ 𝑍 1 , ∘ 𝑍 2 – внутренние части этих полупространств, т.е. ∘ 𝑍 𝑖 = 𝑍 𝑖 ∖ 𝑃 (𝑖 = 1, 2). Строгая раздели- мость множеств 𝑆 + и 𝑆 − гиперплоскостью 𝑃 выражается утверждением 𝑆 + ⊆ ∘ 𝑍 1 , 𝑆 − ⊆ ∘ 𝑍 2 (2.8) Нетрудно доказать, что множества ∘ 𝑍 1 и ∘ 𝑍 2 выпуклы, поэтому из (2.8) и из определения выпуклой оболочки следует, что 𝐶𝑜𝑛𝑣(𝑆 + ) ⊆ ∘ 𝑍 1 , 𝐶𝑜𝑛𝑣(𝑆 − ) ⊆ ∘ 𝑍 2 (2.9) Поскольку ∘ 𝑍 1 ∩ ∘ 𝑍 2 = ∅, то из (2.9) следует (2.7). Докажем обратную импликацию. Предположим, что верно (2.7). Поскольку множество 𝑆 конечно, то 𝑆 + и 𝑆 − тоже конечны. Как было отмечено выше, в этом случае множества 𝐶𝑜𝑛𝑣(𝑆 + ) и 𝐶𝑜𝑛𝑣(𝑆 − ) компакт- ны. Следовательно, множество 𝐷 𝑆 def = 𝐶𝑜𝑛𝑣(𝑆 + ) × 𝐶𝑜𝑛𝑣(𝑆 − ) тоже компактно. Обозначим символом 𝜌 функцию вида 𝐷 𝑆 → R, которая сопоставля- ет паре точек (𝑥, 𝑦) ∈ 𝐷 𝑆 длину |𝑥𝑦| отрезка, соединяющего эти точки. Функция 𝜌 непрерывна, и ее область определения – компакт, поэтому 𝜌 принимает наименьшее значение в некоторой точке (𝑥 + , 𝑥 − ) ∈ 𝐷 𝑆 . Ес- ли бы 𝜌(𝑥 + , 𝑥 − ) было равно 0, т.е. 𝑥 + = 𝑥 − , то это бы противоречило предположению (2.7). Следовательно, 𝜌(𝑥 + , 𝑥 − ) > 0. Обозначим записями 𝑃 𝑆 + и 𝑃 𝑆 − гиперплоскости, проходящие через 𝑥 + и 𝑥 − соответственно, и ортогональные отрезку [𝑥 + , 𝑥 − ]. Гиперплоскости 𝑃 𝑆 + и 𝑃 𝑆 − параллельны и разбивают R 𝑛 на три множества: 18 ∙ два полупространства (обозначим их записями 𝑍 𝑆 + и 𝑍 𝑆 − ), и ∙ полосу (𝑃 𝑆 + , 𝑃 𝑆 − ) между этими полупространствами (не содержа- щую точек из 𝑃 𝑆 + и 𝑃 𝑆 − ). Нетрудно видеть, что 𝑍 𝑆 + = {𝑥 ∈ R 𝑛 | 𝑥 = 𝑥 + или \ 𝑥𝑥 + 𝑥 − ≥ 𝜋 2 } и аналогичное свойство верно для 𝑍 𝑆 − Докажем, что 𝑆 + ⊆ 𝑍 𝑆 + , т.е. ∀ 𝑥 ∈ 𝑆 + ∖ {𝑥 + } \ 𝑥𝑥 + 𝑥 − ≥ 𝜋 2 . Если бы это было неверно, т.е. \ 𝑥𝑥 + 𝑥 − < 𝜋 2 , то на отрезке [𝑥 + 𝑥] была бы точка 𝑥 ′ , такая, что |𝑥 ′ 𝑥 − | < |𝑥 + 𝑥 − |. Т.к. [𝑥 + 𝑥] ⊆ 𝐶𝑜𝑛𝑣(𝑆 + ), то 𝑥 ′ ∈ 𝐶𝑜𝑛𝑣(𝑆 + ). Таким образом, (𝑥 ′ , 𝑥 − ) ∈ 𝐷 𝑆 и 𝜌(𝑥 ′ , 𝑥 − ) < 𝜌(𝑥 + , 𝑥 − ). Это противоречит тому, что 𝜌 принимает наименьшее значение на паре (𝑥 + , 𝑥 − ). Аналогично доказывается включение 𝑆 − ⊆ 𝑍 𝑆 − Из доказанного выше следует, что (𝑆 + ∪ 𝑆 − ) ∩ (𝑃 𝑆 + , 𝑃 𝑆 − ) = ∅. В качестве гиперплоскости, строго разделяющей 𝑆 + и 𝑆 − , можно взять, например, гиперплоскость 𝑃 , проходящую через любую внутрен- нюю точку отрезка [𝑥 + 𝑥 − ] и ортогональную этому отрезку (т.е. 𝑃 будет параллельна 𝑃 𝑆 + и 𝑃 𝑆 − ). Поскольку ∙ 𝑃 ⊆ (𝑃 𝑆 + , 𝑃 𝑆 − ), и ∙ полупространства 𝑍 𝑆 + и 𝑍 𝑆 − содержатся в разных полупростран- ствах, на которые 𝑃 делит R 𝑛 , то, следовательно, 𝑆 + и 𝑆 − содержатся в разных полупространствах, на которые 𝑃 делит R 𝑛 Для задачи классификации в случае строго разделимой выборки 𝑆 существует алгоритм нахождения функции 𝑎 𝑆 вида (2.1) со свойством 𝑄(𝑎 𝑆 ) = 0, который называется алгоритмом обучения Розенблатта и излагается в следующем параграфе. 2.2 Алгоритм обучения Розенблатта В этом параграфе рассматривается задача классификации, в которой ∙ множества объектов и ответов имеют вид 𝑋 = R 𝑛 , 𝑌 = {−1, 1}, и 19 ∙ задача обучения заключается в нахождении по выборке 𝑆 АФ 𝑎 𝑆 вида 𝑎 𝑆 (𝑥) = 𝑠𝑖𝑔𝑛 (︁ 𝑛 ∑︁ 𝑖=1 𝑥 𝑖 𝑤 𝑖 − 𝑤 0 )︁ , где 𝑤 1 , . . . , 𝑤 𝑛 , 𝑤 0 ∈ R, (2.10) которая минимизирует риск 𝑄(𝑎 𝑆 ). 2.2.1 Описание алгоритма обучения Розенблатта Пусть выборка 𝑆 строго линейно разделима, т.е. ∃ 𝑤 1 , . . . , 𝑤 𝑛 , 𝑤 0 ∈ R: ∀ (𝑥, 𝑦) ∈ 𝑆 (︁ 𝑛 ∑︁ 𝑖=1 𝑥 𝑖 𝑤 𝑖 − 𝑤 0 )︁ 𝑦 > 0, где (𝑥 1 , . . . , 𝑥 𝑛 ) = 𝑥. (2.11) Нетрудно видеть, что неравенство в (2.11) равносильно неравенству ⟨(𝑥 1 , . . . , 𝑥 𝑛 , −1), (𝑤 1 , . . . , 𝑤 𝑛 , 𝑤 0 )⟩𝑦 > 0, поэтому задача нахождения для строго разделимой выборки 𝑆 такого вектора (𝑤 1 , . . . , 𝑤 𝑛 , 𝑤 0 ), который удовлетворяет условию (2.11), сводится к задаче нахождения вектора 𝑤 ∈ R 𝑛+1 , такого, что ∀ (𝑥, 𝑦) ∈ 𝑆 ⟨(𝑥, −1), 𝑤⟩𝑦 > 0, где (𝑥, −1) ∈ R 𝑛+1 получается из 𝑥 добавлением компоненты, равной −1. Таким образом, задача нахождения для строго разделимой выбор- ки АФ 𝑎 𝑆 со свойством 𝑄(𝑎 𝑆 ) = 0 сводится к следующей задаче: пусть выборка 𝑆 такова, что существует вектор 𝑤, обладающий свойством ∀ (𝑥, 𝑦) ∈ 𝑆 ⟨𝑥, 𝑤⟩𝑦 > 0. (2.12) Требуется найти хотя бы один вектор 𝑤, обладающий свойством (2.12). Для поиска такого вектора 𝑤 можно использовать излагаемый ни- же алгоритм, называемый алгоритмом Розенблатта [5]. Данный ал- горитм можно представить в виде следующей блок-схемы: ∙ - 𝑤 := ¯ 0 - ? ' & $ % ∃ (𝑥, 𝑦) ∈ 𝑆 : ⟨𝑥, 𝑤⟩𝑦 ≤ 0 - ? 0 1 𝑤 := 𝑤 + 𝑥𝑦 @ @ (2.13) 20 где ¯ 0 – вектор, компоненты которого равны 0, и 𝑥, 𝑦 в правом прямоуголь- нике – компоненты какой-либо пары (𝑥, 𝑦) ∈ 𝑆, такой, что ⟨𝑥, 𝑤⟩𝑦 ≤ 0. Нетрудно видеть, что после завершения работы данного алгоритма значение переменной 𝑤 будет обладать свойством (2.12). 2.2.2 Завершаемость алгоритма Розенблатта Завершаемость алгоритма Розенблатта обосновывается нижеследующей теоремой, которая называется теоремой Новик´ ова. Теорема 2 (А.Novikoff, 1962) [6], [7]. Пусть конечная выборка 𝑆 ⊂ R 𝑛 × {−1, 1} такова, что свойство (2.12) выполняется для некоторого вектора ˆ 𝑤, т.е. ∀ (𝑥, 𝑦) ∈ 𝑆 ⟨𝑥, ˆ 𝑤⟩𝑦 > 0. Тогда алгоритм Розенблатта, применяемый к выборке 𝑆, завершает свою работу после не более чем (𝜎/𝜌) 2 циклов, где 𝜎 = max (𝑥,𝑦)∈𝑆 ||𝑥||, 𝜌 = 1 || ˆ 𝑤|| min (𝑥,𝑦)∈𝑆 ⟨𝑥, ˆ 𝑤⟩𝑦. Доказательство. В доказательстве данной теоремы используется неравенство Коши- Буняковского, которое верно для произвольной пары 𝑎, 𝑏 векторов из линейного пространства со скалярным произведением ⟨ ⟩, имеет вид ⟨𝑎, 𝑏⟩ ≤ ||𝑎|| ||𝑏|| (2.14) и доказывается следующим образом: ∀ 𝑡 ∈ R 0 ≤ ||𝑎𝑡 + 𝑏|| 2 = = ⟨𝑎𝑡 + 𝑏, 𝑎𝑡 + 𝑏⟩ = = ⟨𝑎, 𝑎⟩𝑡 2 + 2⟨𝑎, 𝑏⟩𝑡 + ⟨𝑏, 𝑏⟩ = = ||𝑎|| 2 𝑡 2 + 2⟨𝑎, 𝑏⟩𝑡 + ||𝑏|| 2 Соотношение ∀ 𝑡 ∈ R ||𝑎|| 2 𝑡 2 + 2⟨𝑎, 𝑏⟩𝑡 + ||𝑏|| 2 ≥ 0 (2.15) равносильно тому, что дискриминант (2⟨𝑎, 𝑏⟩) 2 − 4||𝑎|| 2 ||𝑏|| 2 (2.16) квадратного трехчлена в (2.15) неположителен, т.е. ⟨𝑎, 𝑏⟩ 2 − ||𝑎|| 2 ||𝑏|| 2 ≤ 0, 21 откуда следует (2.14). Обозначим записями 𝑤 (𝑘−1) и 𝑤 (𝑘) значения переменной 𝑤 до и после 𝑘–го выполнения цикла в (2.13). Т.к. 𝑤 (𝑘) = 𝑤 (𝑘−1) + 𝑥𝑦, то ⟨𝑤 (𝑘) , ˆ 𝑤⟩ = ⟨𝑤 (𝑘−1) + 𝑥𝑦, ˆ 𝑤⟩ = ⟨𝑤 (𝑘−1) , ˆ 𝑤⟩ + ⟨𝑥, ˆ 𝑤⟩𝑦 ≥ ≥ ⟨𝑤 (𝑘−1) , ˆ 𝑤⟩ + || ˆ 𝑤||𝜌. (2.17) Применяя (2.17) 𝑘 раз, и учитывая 𝑤 (0) = ¯ 0, получаем: ⟨𝑤 (𝑘) , ˆ 𝑤⟩ ≥ ⟨𝑤 (0) , ˆ 𝑤⟩ + 𝑘|| ˆ 𝑤||𝜌 = 𝑘|| ˆ 𝑤||𝜌. (2.18) Согласно неравенству Коши-Буняковского, ⟨𝑤 (𝑘) , ˆ 𝑤⟩ ≤ ||𝑤 (𝑘) || || ˆ 𝑤||, по- этому из (2.18) следует, что 𝑘|| ˆ 𝑤||𝜌 ≤ ⟨𝑤 (𝑘) , ˆ 𝑤⟩ ≤ ||𝑤 (𝑘) || || ˆ 𝑤||, откуда следует неравенство 𝑘𝜌 ≤ ||𝑤 (𝑘) ||, или 𝑘 2 𝜌 2 ≤ ||𝑤 (𝑘) || 2 (2.19) С другой стороны, ||𝑤 (𝑘) || 2 = ⟨𝑤 (𝑘−1) +𝑥𝑦, 𝑤 (𝑘−1) +𝑥𝑦⟩ = ||𝑤 (𝑘−1) || 2 +2⟨𝑥, 𝑤 (𝑘−1) ⟩𝑦 +||𝑥|| 2 , (2.20) и поскольку ⟨𝑥, 𝑤 (𝑘−1) ⟩𝑦 ≤ 0 и ||𝑥|| ≤ 𝜎, то из (2.20) следует, что ||𝑤 (𝑘) || 2 ≤ ||𝑤 (𝑘−1) || 2 + ||𝑥|| 2 ≤ ||𝑤 (𝑘−1) || 2 + 𝜎 2 (2.21) Применяя (2.21) 𝑘 раз, и учитывая 𝑤 (0) = ¯ 0, получаем: ||𝑤 (𝑘) || 2 ≤ 𝑘𝜎 2 (2.22) Объединяя (2.19) и (2.22) получаем: 𝑘 2 𝜌 2 ≤ ||𝑤 (𝑘) || 2 ≤ 𝑘𝜎 2 , откуда следует неравенство 𝑘 2 𝜌 2 ≤ 𝑘𝜎 2 , или 𝑘𝜌 2 ≤ 𝜎 2 , или 𝑘 ≤ (𝜎/𝜌) 2 Таким образом, число выполнений цикла в блок-схеме (2.13) не пре- восходит (𝜎/𝜌) 2 22 |