Принцип максимальне значення. Практичне застосування принципу максимуму при математичному моделюванні процесів

ПРИНЦИП МАКСИМУМУ

У ряді практичних завданьоптимізації об'єктів керування екстремум функціоналу (3.91) при заданих рівняннях об'єкта (3.92) забезпечується під час керування u(t), що має розриви першого роду. При цьому координати також мають розриви, положення та кількість яких наперед невідомі. Ці обставини ускладнюють застосування класичного варіаційного обчислення деяких завдань оптимізації, які можна вирішити методом, розробленим акад. Л.С.Понтрягін та названим принципом, максимуму.

Завданням оптимізації є визначення оптимальних управлінь u°( t) та траєкторії Х°( t) за умови мінімуму функціоналу (3.91) для заданих рівнянь об'єкта (3.92) при початкових X(t 0) і кінцевих X(tк) значеннях, заданому інтервалі часу t 0 t tдо з урахуванням обмежень виду X(t) x , u(t) u .

Функції керування u(t) допускають розриви першого роду (див. криву 1 на рис. 3.6). Оскільки координати виходу x i (t) не є гладкими, то канонічні рівняння (3.78) та (3.80) при введених множниках Лагранжа (3.76) та функції Гамільтона (3.77) не можуть бути безпосередньо застосовані для визначення оптимальних управлінь. Пояснюється це тим, що через розриви першого роду варіація функції u(t) може бути великою, отже, великою буде і варіація функціоналу. Внаслідок цього у виразі (3.56) вже не можна обмежуватися лише лінійними щодо варіацій функцій u(t) та х(t) членами, а слід враховувати також нелінійні члени. У зв'язку з цим було запроваджено поняття голчастої варіації.

Голкова варіація являє собою збільшення варіюється функції оптимального управління u°( t) на нескінченно малому відрізку часу у вигляді імпульсу обмеженої величини (див. криву 4 на рис. 3.6) з урахуванням u(t) u. Вплив такої варіації на рух об'єкта управління в інтервалі< t < tдо нескінченно мало, оскільки вплив будь-якого імпульсу оцінюється величиною його площі ( u - u°) е, яка в даному випадкунескінченно мала. Отже, збільшення функціоналу при голчастій варіації управління буде нескінченно малим. Воно звертається в нуль, тобто виконується умова екстремуму (3.58) функціоналу (3.54), коли голчаста варіація проводиться щодо оптимального керування u°( t).

Основні рівняння та їх застосування для синтезу оптимальних систем.Розглянемо коротко сутність принципу максимуму. Нехай математична модель об'єкта оптимізації задана у вигляді рівнянь стану

де i = 1, 2, ..., n; r- кількість координат керування. Рівняння (3.113) можна подати в векторної форми

Сигнали керування можуть мати обмеження для всіх координат

Задамося деякою функцією f 0 (Х, u) і вважатимемо, що мету управління об'єктом буде досягнуто, якщо зображуюча точка з початкового положення Х 0 з координатами ( х 10 , х 20 , ..., х n 0) у n-мірному фазовому просторі переміститься в положення Х 1 з координатами ( x 11 , x 21 , …, x n 1).

При оптимізації об'єкта потрібно знайти вектор керуючого впливу u(t) з урахуванням зазначених обмежень за умови мінімуму функціоналу

Спочатку розглянемо завдання за однієї координати управління ( r=1) у просторі ( n+1) координат, ввівши додаткову змінну х 0 , що визначається рівнянням оптимізація принцип максимум

При цьому для виведення принципу максимуму використовуємо варіацію голки.

Якщо керуючому впливу u°( t) відповідає оптимальне рух об'єкта Х°( t), то після голчастої варіації подальший рух X(t) відрізнятиметься від оптимального. Різниця між ними в момент t= , Визначається різницею швидкостей

Ця різниця нескінченно мала, тому що - нескінченно мала величина. Тому для інтервалу t Tвведемо вектор варіації траєкторії

Закон зміни варіації, що є нескінченно малою величиною, може бути знайдений із рівнянь, записаних для малих змін X(t), які називають рівняннями у варіаціях. Ці рівняння можна отримати з (3.113) або (3.114), якщо замінити x iна x i + х iа потім після розкладання f iу ряд за ступенями x iвідкинути члени вищих порядків дещиці. Далі віднімемо рівняння виду (3.113) і отримаємо лінійне рівняння у варіаціях

де j = 0, 1, 2..., n.

Вектор варіацій Xпри t = Тхарактеризує зміну критерію оптимальності J. Для будь-яких неоптимальних управлінь u(t) ця величина визначається скалярним творомвектор варіацій X(T) та допоміжного вектора ( Т) і є негативною:

Рівняння (3.119) дозволяє знайти X(T) залежно від початкової умови X(), що визначається значенням u().

Якщо підібрати такий ( n+1)-мірний вектор ( t), який при< t Tзадовольняє умову

де ( t) = [ 0 (t) 1 (t) … n (t)] T , замість прийнятої в класичному варіаційному обчисленні функції Гамільтона (3.77) можна скласти функцію Гамільтона для некласичних варіаційних завдань:

Ця функція досягає максимуму при оптимальному керуванні u°( t), звідки слідує принцип максимуму: потрібно так підібрати u(t) u, щоб величина Н * досягала максимального значення. При цьому можна записати (для відкритої множини u)

Н*/ u = 0. (3.122)

Використовуючи вираз (3.121) та рівняння об'єкта управління (3.113) з урахуванням (3.116), можна скласти аналогічно рівнянням (3.81) канонічні рівняння Гамільтона для некласичних варіаційних завдань:

де i = 0, 1, 2, ..., n.

Рівняння (3.123) при rкоординатах управління доповнюються рівняннями

Нехай існує допустиме управління u(t) u, то відповідна йому фазова траєкторія проходить через фіксовану початкову X(t 0) та кінцеву X(Т) Точки. Тоді u°( t) визначається за теоремою Л. С. Понтрягіна :

для того, щоб управління u(t) було оптимальним, необхідне існування такої ненульової вектор-функції ( t), що відповідає чинності рівнянь (3.123) функцій u(t) та X(t), щоб:

1) при t 0 t Тфункція H* досягла максимуму при u°( t)

2) у кінцевий момент часу t = Твиконувалися б співвідношення

У більшості випадків (3.126) можна прийняти 0 ( Т) = - 1.

Постановка задачі.Нехай стан керованої системи характеризується п-вимірним вектором стану x(t). Цілеспрямований вплив на процес можна здійснювати за допомогою m-вимірного вектора управління u(t). На вектори керування та стану можуть накладатися обмеження: x(t)eX, u(t)eU,де Uі х- відповідно області допустимих управлінь та станів. Вважатимемо допустимими керуючими впливами шматково-безперервні функціїна відрізку управління , в точках розриву першого роду безперервні праворуч і кінцях відрізка. Між x(t) та u(t)існує залежність, що записується у вигляді системи диференціальних рівнянь

Задано граничні умови: початковий стан керованої системи x,(t 0) = *f і кінцевий стан -х ((??) = **, i = l,2,...,n в n-мірному фазовому просторі. часу п вважаємо незафіксованим, а що характеризує лише момент переходу в кінцевий стан х 1 .Критерій якості перебігу процесу управління описується функціоналом

Тепер постановку завдання оптимального управління можна сформулювати в такий спосіб. У п-мірному фазовому просторі Xдано дві точки, х° і х 1 . Серед усіх допустимих управлінь, для яких фазова траєкторія, що виходить в момент часу t 0 з точки х °, приходить в точку х 1 знайти таке управління, для якого функціонал Iнабуває екстремального значення. Таке управління називається оптимальним управлінням, а відповідна йому траєкторія – оптимальною траєкторією.

Постановку завдання можна змінити, ввівши на розгляд ще одну координату вектора стану, що характеризує поточне значення функціоналу:

Диференціюючи, отримуємо рівняння щодо нової координативектор стану

I

з граничними умовами

Тепер йтиметься про (п + 1)-мірний фазовий простір стану X,а постановку завдання, еквівалентну попередньої, можна сформулювати в такий спосіб.

В (п + 1)-мірному фазовому просторі Xзадані: точка з координатами (0,х°) та пряма П, що проходить паралельно осі х 0 через точку (0,х х). Серед усіх допустимих управлінь, для яких відповідна фазова траєкторія, виходячи в момент часу з точки (0,х°), перетне пряму П, знайти управління, що забезпечує найменше можливе значення координати перетину з прямою П вздовж осі х 0 .

Постановка задачі геометрично інтерпретована для випадку п = 2 на рис. 2.3.

Крім основної системи диференціальних рівнянь (2.22) та (2.24), які разом запишуться як

введемо на розгляд додаткову системудиференціальних рівнянь щодо допоміжної векторної функції |/(t)

Мал. 2.3.

Після введення поняття функції Гамільтона

системи (2.25) та (2.26) можна об'єднати записом у вигляді так званої гамільтонової системи

Позначимо через М(х, i)максимальне значення функції Гамільтона

чи, точніше, значення її верхньої грані - супремуму.

Основна теорема.Нехай u(t) на відрізку - допустиме керування, що задовольняє постановку задачі. Тоді для оптимальності вектора управління u(t) необхідно, щоб існувала ненульова вектор-функція |/(t), така, що:

1) для всіх tна відрізку] функція Гамільтона як функція і, ueUдосягала максимуму

2) у кінцевий момент часу t = П виконувались співвідношення

Зважаючи на важливість першого пункту для змісту теореми, остання названа авторами принципом максимуму,який у цьому загальному випадкудає необхідні умови визначення оптимального управління.

Таким чином, ми маємо 2(п + 1) + ш співвідношень (2.25), (2.26) та (2.29), між 2(п + 1) + ш координатами векторів x(t), p(t) та u(t ). Так як тспіввідношень не диференціальні, то рішення системи (2.25), (2.26) і (2.29) залежить від 2(n + 1) невідомих параметрів, крім того, >t 0 або ti-t 0= т також параметром. Один із параметрів несуттєвий, оскільки v|/(t) визначається з точністю до спільного множниказ однорідності Я щодо |/. Таким чином, для знаходження 2(n + 1) параметрів маємо (2n + 1) граничних умов на функцію x(t) та другий пункт принципу максимуму.

Принцип максимуму для оптимальної швидкодії.Важливим для технічних додатків є клас завдань на оптимальну швидкодію: потрібно знайти управління u(t), що переводить фазову точку стану х° в момент часу t 0 в х 1 за мінімальний час, тобто. функціонал у разі запишеться як

тобто. /0 (x,u)sl. Функція Гамільтона набуває вигляду

де

Таким чином, величина р 0 не впливає значення u(t), при якому досягається максимум, а впливає тільки на величину максимуму. У силу сказаного в принципі максимуму для оптимальної швидкодії можна говорити про функції Н(х, ц/, і)і М(х, |/, і)= max Н(х, |/, і),тому рівність (2.29) основної теореми матиме вигляд

а рівність (2.30) матиме вигляд

Застосуємо принцип максимуму оптимального швидкодії до керованим системам, які описуються системою лінійних диференціальних рівнянь з постійними параметрами. Таке завдання називається завданням на лінійну оптимальну швидкодію. Система записується як

Вважаємо, що керуючі впливи підпорядковані обмеженням виду

Потрібно мінімізувати час переходу з х в х 1 , тобто. I= t x -t 0. Складемо функцію Гамільтона:

Змінимо порядок підсумовування у другій групі доданків:

На підставі принципу максимуму u(t) слід шукати, виходячи з максимуму Н(х, |/, і) щодо u (Про для всіх f з урахуванням обмеження (2.31). Неважко бачити (рис. 2.4), що значення, -

маємо u; (t) у кожен момент t визначається знаком?b^|/,-(t), тобто. зміна u, (t) відбувається за законом, = 1

Таким чином, першу властивість управління в задачах на лінійну оптимальну швидкодію можна сформулювати наступним чином: керуючі впливу являють собою кусковопостійні функції, які приймають або максимально, або мінімально допустиме для них значення.

Змінимо порядок підсумовування у першій групі доданків виразу (2.32)

Рівняння гамільтонової системи щодо допоміжної функції j/(t) (2.26) матиме вигляд

Мал. 2.4.

t*, t**- Точки перемикання управління

Система рівнянь є однорідною, отже, загальне рішення можна записати як

де [Ху] - сукупність коренів характеристичного рівнянняабо власні значення матриці А= [а,-у].

Вважаємо, що Xj,j=l,2,...,nє простим речовим корінням. Тоді кожна з функцій v|/, (t) як сума п монотонних функційне більше (п- 1) рази перетинає вісь t. Оскільки функція

Cy(t) = ^byyl|/y(t) є сумою пмонотонних функцій, можна 1=1

сформулювати другу властивість задачі на лінійну оптимальну швидкодію систем n-го порядку, коріння характеристичного рівняння яких речові: керуючі впливи мають не більше ппроміжків знакостійності чи більше (п - 1) перемикання.

Пояснимо результат на конкретному прикладі. Нехай керована система є подвійне інтегруюче ланка, тобто.

з обмеженням на керуючий вплив| u(t) |

Потрібно знайти u(t), що переводить фазову точку з довільного положення х ° початок координат фазового простору за мінімальний час.

1. Введемо фазові координати:

Тоді у нормальній формі рівняння системи запишуться як

2. Запишемо вираз для функції Гамільтона:

Гамільтонова система щодо допоміжної вектор-функції j/(t) має вигляд

Звідси

3. На підставі властивостей управління:

Рівняння сімейств фазових траєкторій (рис. 2.5, а, б):

Під дією управління н = ±1 фазова точка може потрапити на початок координат лише з виділеної траєкторії (рис. 2.6). Щоб фазова точка потрапила на початок координат лише за одне перемикання, рух має бути організовано, як показано на рис. 2.6.

Завдання оптимального керування кінцевим станом.Завдання управління кінцевим станом за відсутності обмежень на вектор управління завдання Майєракласичного варіаційного обчислення У цих завданнях функціонал визначає значення функції від координат стану на момент часу t = t bтобто.

Мал. 2.5.

а- u(t) = + 1; б - u(t) = -1

Мал. 2.6.

Нехай керована система описується системою диференціальних рівнянь n-го порядку

з граничними умовами

Ці рівняння лінійні щодо m-вимірного вектора управління u(t). На керуючі дії накладаються обмеження виду

Потрібно визначити вектор управління, що мінімізує функціонал

Введемо нову координату

Додаткове диференціальне рівняннящодо x 0 (t) запишеться у вигляді

з граничними умовами

Функція Гамільтона для даної системи

Виконаємо такі перетворення:

За виконання перетворень з ф; = 0 і | / 0 (П) = -1 вважаємо v | / 0 (t) = -l. На підставі принципу максимуму при зазначених обмеженнях на керування оптимальне керування кінцевим станом для даної системи визначається виразом

Таким чином, керування є кусково-постійною функцією зі значеннями на межі області допустимих управлінь. Оптимальна функція перемикання

може бути обчислена після розв'язання гамільтонової системи рівнянь за заданих граничних умов.

Завдання управління щонайменше витрати енергії.Це завдання оптимального управління має велике практичне значення. Витрата енергії, витраченої управління, пропорційний інтегралу за часом від квадрата управляючого впливу. Якщо витрати енергії по всіх входах брати з однаковими вагами, то функціонал можна записати у вигляді

де коефіцієнт 1/2 введено зручності наступних викладок.

Розглянемо систему, що описується системою диференціальних рівнянь п-го порядку:

Розглянемо два випадки визначення оптимального управління з витрат енергії на управління:

1) коли вектор управління не накладається обмежень;

2) коли керуючі впливи підкоряються обмеженням виду

Введемо нову координату

Відповідне цій координаті диференціальне рівняння за граничних умов

Функція Гамільтона для цієї системи має вигляд

Змінюємо порядок підсумовування останній групідоданків і вважаємо, як і раніше, j/0=-1. Тоді

1-й випадок.Вектор u(t) не накладається обмежень.

Максимум функції Гамільтона Н(х, |/, і) щодо іможе бути знайдений на підставі необхідної умови екстремуму функції класичного аналізу

Диференціюємо по п; :

Звідси оптимальне управління

2-й випадок.Керуючі впливи підкоряються обмеженню

З попереднього випадку ясно, що якщо | З; (?) | Uj(t) = З іншого боку, для тих t,для яких | Cj(t) | > Mj, звраховуючи обмеження на Uj(t)функція Гамільтона максимальна, якщо Uj(t) = MjSignCj(t).Звідси укладаємо, що оптимальне управління може бути записане у вигляді

Для визначення Cj(t)необхідно вирішити гамільтонову систему рівнянь.

Принцип максимуму визначає необхідні умови оптимальності управління нелінійних керуючих системах. Він поширений і на випадки, коли координати стану системи накладаються обмеження. Розглянемо основну теорему принципу максимуму і дамо зручніше формулювання оптимального управління.

Нехай оптимальне керування описується системою нелінійних диференціальних рівнянь:

(1)

або у векторній формі:

--мірний вектор стану об'єкта

--мірний вектор керуючих впливів

- функція правої частини рівняння (1)

Вважаємо, що вектор управління набуває значень із деякої замкнутої області Ur-мірного простору управлінь. Припустимо, що функції
безперервні за всіма аргументами і мають безперервні похідні за змінними станами . Назвемо допустимими управліннями ті управління
, які є шматково-безперервними функціями часу і набувають значення з множини U.

Основне завдання оптимального управління формулюється наступним чином: серед усіх допустимих управління, що приводять зображувальну точку у фазовому просторі X з початкового положення у кінцеве якщо ці управління існують. І потрібно знайти такі управління, для яких функціонал:

(2)

досягає мінімуму.

Введемо нову змінну яка визначається наступним диференціальним рівнянням:

(3)

Тут
- Підінтегральна функція функціоналу (2).

Приєднавши рівняння (3) до системи рівнянь (1), отримаємо:

(4)

Запишемо (4) у векторній формі. Для цього введемо в розгляд (n+1) вектор координат стану:
тоді у векторній формі запису це рівняння запишеться наступним чином:

(5)

Вектор правих частин системи (5).

Зауважимо, що вектор-функція
не залежить від координати вектора . Позначимо через точку з координатами
в (n+1)-му фазовому просторі . Нехай
- деяке допустиме управління, для якого відповідна фазова траєкторія (1) проходить при
через точку . А при виконанні рівності
через точку .

З рівняння (2) випливає, що координата визначається рівністю:

Якщо
, то матимемо:

Таким чином, у просторі фазова траєкторія системи (5), що відповідає тому ж управлінню
, проходить за
через точку
, а при
через точку
. Це ілюструє наступний малюнок:

Позначимо через П пряму у просторі , що проходить через точку
та паралельну осі . Тоді основне завдання оптимального управління можна сформулювати наступним чином:

У (n+1)-мірному просторі задані початкова точка
та пряма П, паралельна осі і проходить через точку
. Серед усіх допустимих управлінь, що мають ту властивість, що рішення системи (5) з початковими умовами
проходить через точку прямої П, необхідно вибрати таке управління, для якого координата точки мало б мінімальне значення.

Сформульована задача є завданням Майєра на умовний екстремум. Проте з обмежень, накладених на допустиме управління методами класичного варіаційного обчислення, це завдання вирішується.

Формулювання теореми, що дає необхідну умову екстремуму:

Введемо на розгляд допоміжні змінні
, які задовольняю наступній системі рівнянь:

(6)

Система (6) називається сполученою стосовно системи рівнянь (5). Якщо вибрати деяке допустиме керування
на відрізку
та знайти відповідне йому рішення
із заданими початковими умовами
, то при підстановці в систему рівнянь (6) управління
та рішення
, Отримаємо лінійну однорідну систему рівнянь:

(7)

Система (7) задовольняє умов існування та єдиності рішення системи диференціальних рівнянь. Системи рівнянь (5) і (6) можна поєднати однією формою запису, для цього треба ввести в розгляд функцію H:

(8)

Тоді системи (5) та (6) запишуться наступним чином:

(9)

(10)

Зазначимо, що вектор функцій
і
безперервні всюди, крім точок розриву допустимого управління
. Ці векторні функції мають безперервні похідні. При фіксованих значеннях
і
функція H стає функцією тільки керування
.

Метод найменших квадратів

Розповідь про лінійні моделі ми розпочнемо з лінійної регресії. У першу чергу, необхідно задати модель залежності пояснюваної змінної від факторів, що її пояснюють, функція залежності буде лінійною: . Якщо ми додамо фіктивну розмірність кожному за спостереження, тоді лінійну форму можна переписати трохи компактніше, записавши вільний член під суму: . Якщо розглядати матрицю спостереження-ознаки, у якій у рядках є приклади з набору даних, то нам необхідно додати одиничну колонку зліва. Задамо модель так:

Можемо виписати вираз для кожного конкретного спостереження

Також на модель накладаються такі обмеження (інакше це буде якась інша регресія, але точно не лінійна):

Оцінка ваг називається лінійною, якщо

де залежить лише від даних і майже напевно нелінійно. Так як розв'язанням задачі пошуку оптимальних ваг буде саме лінійна оцінка, то і модель називається лінійною регресією. Введемо ще одне визначення. Оцінка називається незміщеною тоді, коли маточування оцінки дорівнює реальному, але невідомому значеннюоцінюваного параметра:

Один із способів обчислити значення параметрів моделі є метод найменших квадратів(МНК), який мінімізує середньоквадратичну помилку між реальним значенням залежної змінної та прогнозом, виданим моделлю:

Для вирішення даної оптимізаційної задачі необхідно обчислити похідні за параметрами моделі, прирівняти їх до нуля та вирішити отримані рівняння щодо (матричне диференціювання непідготовленому читачеві може здатися скрутним, спробуйте розписати все через суми, щоб переконатися у відповіді):

Шпаргалка по матричних похідних

Отже, маючи на увазі всі визначення та умови, описані вище, ми можемо стверджувати, спираючись на теорему Маркова-Гаусса, що оцінка МНК є кращою оцінкою параметрів моделі, серед усіх лінійнихі незміщенихоцінок, тобто має найменшу дисперсію.

Метод максимальної правдоподібності

У читача цілком резонно могли виникнути питання: наприклад, чому ми мінімізуємо середньоквадратичну помилку, а чи не щось інше. Адже можна мінімізувати середнє абсолютне значення нев'язки чи ще щось. Єдине, що станеться у разі зміни мінімізованого значення, так це те, що ми вийдемо з умов теореми Маркова-Гаусса, і наші оцінки перестануть бути кращими серед лінійних та незміщених.

Давайте перед тим, як продовжити, зробимо ліричний відступ, щоб проілюструвати метод максимальної правдоподібності на прикладі.

Якось після школи я помітив, що всі пам'ятають формулу етилового спирту. Тоді я вирішив провести експеримент: чи пам'ятають люди простішу формулу метилового спирту: . Ми опитали 400 осіб і виявилося, що формулу пам'ятають лише 117 осіб. Розумно припустити, що можливість того, що наступний опитаний знає формулу метилового спирту – . Покажемо, що така інтуїтивно зрозуміла оцінка не просто хороша, а ще й оцінка максимальної правдоподібності.

Розберемося, звідки береться ця оцінка, а для цього згадаємо визначення розподілу Бернуллі: випадкова величина має розподіл Бернуллі, якщо вона набирає всього два значення (і з ймовірностями і відповідно) і має наступну функціюрозподілу ймовірності:

Схоже, це розподіл – те, що нам потрібно, а параметр розподілу є та оцінка ймовірності того, що людина знає формулу метилового спирту. Ми зробили незалежнихекспериментів, позначимо їх результати як . Запишемо правдоподібністьнаших даних (спостережень), тобто можливість спостерігати 117 реалізацій випадкової величинита 283 реалізації:

Тепер ми хочемо знайти таке значення, яке максимізує правдоподібність, для цього ми візьмемо похідну по, прирівняємо до нуля і вирішимо отримане рівняння:

Виходить, що наша інтуїтивна оцінка є оцінкою максимальної правдоподібності. Застосуємо тепер самі міркування для завдання лінійної регресії і спробуємо з'ясувати, що лежить за середньоквадратичною помилкою. Для цього нам доведеться подивитися на лінійну регресію з імовірнісної точки зору. Модель, природно, залишається такою ж:

але тепер вважатимемо, що випадкові помилки беруться з центрованого нормального розподілу :

Перепишемо модель у новому світлі:

Так як приклади беруться незалежно (помилки не скорельовані - одна з умов теореми Маркова-Гаусса), то повна правдоподібність даних буде виглядати як добуток функцій щільності. Розглянемо логарифм правдоподібності, що дозволить нам перейти від твору до суми:

Ми хочемо визначити гіпотезу максимальної правдоподібності, тобто. нам потрібно максимізувати вираз, а це те саме, що і максимізація його логарифму. Зверніть увагу, що при максимізації функції за якимсь параметром можна викинути всі члени, які не залежать від цього параметра:

Таким чином, ми побачили, що максимізація правдоподібності даних – це те саме, що й мінімізація середньоквадратичної помилки (за справедливості зазначених вище припущень). Виходить, що саме така функція вартості є наслідком того, що помилка розподілена нормально, а не інакше.

Розкладання помилки на зміщення та розкид (Bias-variance decomposition)

Поговоримо трохи про властивості помилки прогнозу лінійної регресії (у принципі ці міркування вірні всім алгоритмів машинного навчання). У світлі попереднього пункту ми з'ясували, що:

Тоді помилка в точці розкладається так:

Для наочності опустимо позначення аргументу функцій. Розглянемо кожен член окремо, перші два розписуються легко за такою формулою:

Пояснення:

І тепер останній членсуми. Ми пам'ятаємо, що помилка та цільова змінна незалежні один від одного:

Зрештою, збираємо всі разом:

Отже, ми досягли мети всіх обчислень, описаних вище, остання формула говорить нам, що помилка прогнозу будь-якої моделі виду складається з:

Якщо з останньої ми нічого зробити не можемо, то на перші два доданки ми можемо якось впливати. В ідеалі, звичайно ж, хотілося б звести нанівець обидва ці доданки (лівий верхній квадрат малюнка), але на практиці часто доводиться балансувати між зміщеними та нестабільними оцінками (висока дисперсія).

Як правило, зі збільшенням складності моделі (наприклад, зі збільшенням кількості вільних параметрів) збільшується дисперсія (розкид) оцінки, але зменшується зміщення. Через те, що тренувальний набір даних повністю запам'ятовується замість узагальнення, невеликі зміни призводять до несподіваних результатів (перенавчання). Якщо модель слабка, вона неспроможна вивчити закономірність, у результаті вивчається щось інше, зміщене щодо правильного рішення.

Теорема Маркова-Гаусса стверджує, що МНК-оцінка параметрів лінійної моделі є найкращою в класі незміщених лінійних оцінок, тобто з найменшою дисперсією. Це означає, що й існує якась інша незміщена модель теж із класу лінійних моделей, ми можемо бути певні, що .

Регулярування лінійної регресії

Іноді бувають ситуації, ми навмисно збільшуємо зміщеність моделі заради її стабільності, тобто. заради зменшення дисперсії моделі. Однією з умов теореми Маркова-Гаусса є повний стовпцевий ранг матриці. Інакше рішення МНК немає, т.к. Іншими словами, матриця буде сингулярна, або вироджена. Таке завдання називається некоректно поставленим. Завдання потрібно скоригувати, а саме зробити матрицю невиродженою, або регулярною (саме тому цей процес називається регуляризацією). Найчастіше у даних ми можемо спостерігати так звану мультиколінеарність- коли дві або кілька ознак сильно корелювані, у матриці це проявляється у вигляді "майже" лінійної залежності стовпців. Наприклад, у задачі прогнозування ціни квартири за її параметрами "майже" лінійна залежність буде у ознак "площа з урахуванням балкона" та "площа без урахування балкона". Формально таких даних матриця буде оборотна, але через мультиколлинеарности у матриці деякі власні значення будуть близькі до нуля, а зворотній матриці з'являться екстремально великі власні значення, т.к. власні значення зворотної матриці - це. Підсумком такого хитання власних значеньстане нестабільна оцінка властивостей моделі, тобто. додавання нового спостереження в набір тренувальних даних призведе до іншого рішення. Ілюстрації зростання коефіцієнтів ви знайдете в одному з наших попередніх постів. Одним із способів регуляризації є регуляризація Тихонова, яка в загальному виглядівиглядає як додавання нового члена до середньоквадратичної помилки:

Нерідко матриця Тихонова виражається як добуток деякого числа на одиничну матрицю: . І тут завдання мінімізації среднеквадратичной помилки стає завданням з обмеженням норму. Якщо продиференціювати нову функціювартості за параметрами моделі, прирівняти отриману функцію до нуля і виразити , ми отримаємо точне рішення задачі.

Така регресія називається гребеневою регресією (ridge regression). А гребенем є саме діагональна матриця, яку ми додаємо до матриці, в результаті виходить гарантовано регулярна матриця.

Таке рішення зменшує дисперсію, але стає усунутим, т.к. мінімізується також норма вектора параметрів, що змушує рішення зрушуватися в бік нуля. На малюнку нижче на перетині білих пунктирних ліній знаходиться МНК-рішення. Блакитними крапкамипозначені різні рішення гребеневої регресії. Видно, що при збільшенні параметра регулювання рішення зсувається в бік нуля.

Радимо звернутися до нашого минулого посту за прикладом того, як регуляризація справляється з проблемою мультиколінеарності, а також щоб освіжити в пам'яті ще кілька інтерпретацій регуляризації.

2. Логістична регресія

Лінійний класифікатор

Основна ідея лінійного класифікатораполягає в тому, що ознаковий простір може бути розділений гіперплощиною на два напівпростори, у кожному з яких прогнозується одне з двох значень цільового класу.
Якщо це можна зробити без помилок, то навчальна вибірка називається лінійно розділеною.

Ми вже знайомі з лінійною регресією та методом найменших квадратів. Розглянемо завдання бінарної класифікації, причому мітки цільового класу позначимо "+1" ( позитивні приклади) та "-1" (негативні приклади).
Один з найпростіших лінійних класифікаторів виходить на основі регресії таким чином:

Логістична регресія як лінійний класифікатор

Логістична регресія є окремим випадком лінійного класифікатора, але вона має гарне "вміння" – прогнозувати ймовірність віднесення прикладу до класу "+":

Прогнозування не просто відповіді ("+1" або "-1"), а саме ймовірностівіднесення до класу "+1" у багатьох завданнях є дуже важливою бізнес-вимогою. Наприклад, завдання кредитного скорингу, де традиційно застосовується логістична регресія, часто прогнозують ймовірність неповернення кредиту (). Клієнтів, які звернулися за кредитом, сортують за цією передбаченою ймовірністю (за спаданням), і виходить скоркарта - по суті рейтинг клієнтів від поганих до хороших. Нижче наведено іграшковий приклад такої скоркарти.

Банк вибирає собі поріг передбаченої ймовірності неповернення кредиту (на малюнку – ) і з цього значення не видає кредит. Більше того, можна помножити передбачену ймовірність на видану суму і отримати маточкування втрат з клієнта, що теж буде гарною бізнес-метрикою ( Далі в коментарях фахівці зі скорингу можуть виправити, але головна сутьприблизно така).

Отже, хочемо прогнозувати можливість , а поки вміємо будувати лінійний прогноз з допомогою МНК: . Як перетворити отримане значення на ймовірність, межі якої – ? Зрозуміло, цього потрібна деяка функція У моделі логістичної регресії при цьому береться конкретна функція: . І тепер розберемося, які для цього причини.

Позначимо ймовірністю події, що відбувається. Тоді відношення ймовірностей визначається з , а це - відношення ймовірностей того, чи станеться подія чи не станеться. Очевидно, що ймовірність та відношення шансів містять однакову інформацію. Але коли знаходиться в межах від 0 до 1, знаходиться в межах від 0 до .

Якщо вирахувати логарифм (тобто називається логарифм шансів, або логарифм відношення ймовірностей), то легко помітити, що . Його ми й прогнозуватимемо за допомогою МНК.

Подивимося, як логістична регресія робитиме прогноз (поки вважаємо, що ваги ми якось отримали (тобто навчили модель), далі розберемося, як саме).

У правій частині ми отримали якраз сигмоїд-функцію.

Отже, логістична регресія прогнозує ймовірність віднесення прикладу до класу "+" (за умови, що ми знаємо його ознаки та ваги моделі) як сигмоїд-перетворення лінійної комбінації вектора ваг моделі та вектора ознак прикладу:

Наступне питання: як модель навчається? Тут ми знову звертаємось до принципу максимальної правдоподібності.

Принцип максимальної правдоподібності та логістична регресія

Тепер подивимося, як із принципу максимальної правдоподібності виходить оптимізаційне завдання, яке вирішує логістична регресія, а саме – мінімізація логістичноїфункції втрат.
Щойно ми побачили, що логістична регресія моделює можливість віднесення прикладу до класу "+" як

Тоді для класу "-" аналогічна ймовірність:

Обидва ці вирази можна спритно об'єднати в одне (стежте за моїми руками – чи не обманюють вас):

Вираз називається відступом (margin) класифікації на об'єкті (не плутати із зазором (теж margin), про який найчастіше говорять у контексті SVM). Якщо він невід'ємний, модель не помиляється на об'єкті, якщо ж негативний - значить, клас для спрогнозований неправильно.
Зауважимо, що відступ визначений об'єктів саме навчальної вибірки, котрим відомі реальні мітки цільового класу .

Щоб зрозуміти, чому це ми зробили такі висновки, звернемося до геометричної інтерпретаціїлінійного класифікатора. Докладно про це можна почитати у матеріалах Євгена Соколова.

Відповідь

Коли отримаємо (або подивимося) відповідь, то зрозуміємо, що чим більше за модулем вираз , тим далі точка знаходиться від площини

Значить, вираз - це свого роду "впевненість" моделі в класифікації об'єкта:

Тепер розпишемо правдоподібність вибірки, а саме, можливість спостерігати даний вектор у вибірки. Робимо сильне припущення: об'єкти приходять незалежно, з одного розподілу ( i.i.d.). Тоді

де - Довжина вибірки (число рядків).

Як водиться, візьмемо логарифм цього виразу (суму оптимізувати набагато простіше, ніж твір):

Тобто в даному випадку принцип максимізації правдоподібності призводить до мінімізації виразу

Це логістичнафункція втрат, підсумована за всіма об'єктами навчальної вибірки.

Подивимося нову функцію як у функцію від отступа: . Намалюємо її графік, а також графік 1/0 функцій втрат ( zero-one loss), яка просто штрафує модель на 1 за помилку кожному об'єкті (відступ негативний): .

Картинка відбиває загальну ідею, що у завдання класифікації, не вміючи безпосередньо мінімізувати кількість помилок (принаймні, градієнтними методами це зробити – похідна 1/0 функцій втрат у нулі звертається у нескінченність), ми мінімізуємо деяку її верхню оцінку. В даному випадку це логістична функція втрат (де логарифм двійковий, але це не є принциповим), і справедливо

де - Просто число помилок логістичної регресії з вагами на вибірці.

Тобто зменшуючи верхню оцінку на кількість помилок класифікації, ми таким чином сподіваємося зменшити і кількість помилок.

-регуляризація логістичних втрат

L2-регуляризація логістичної регресії влаштована майже так само, як і у випадку з гребеневою (Ridge регресією). Замість функціоналу мінімізується наступний:

У разі логістичної регресії прийнято запровадження зворотного коефіцієнтарегуляризації. І тоді вирішенням завдання буде

3. Наочний прикладрегуляризації логістичної регресії

У статті вже наводився приклад того, як поліноміальні ознаки дозволяють лінійним моделям будувати нелінійні розділяючі поверхні. Покажемо це у картинках.

Подивимося, як регуляризація впливає якість класифікації на наборі даних із тестуванню мікрочіпів з курсу Andrew Ng з машинного навчання.
Будемо використовувати логістичну регресію з поліноміальними ознаками та варіюватимемо параметр регуляризації C.
Спочатку подивимося, як регуляризація впливає на роздільну межу класифікатора, інтуїтивно розпізнаємо перенавчання та недонавчання.
Потім чисельно встановимо близький до оптимального параметра регуляризації за допомогою крос-валідації (cross-validation) і перебору по сітці (GridSearch).

Підключення бібліотек

від __future__ import division, print_function # відключимо будь-які попередження Anaconda import warnings warnings.filterwarnings("ignore") Features from sklearn .linear_model import LogisticRegression, LogisticRegressionCV з sklearn.model_selection import cross_val_score, StratifiedKFold з sklearn.model_selection import GridSearchCV

Завантажуємо дані за допомогою методу read_csv бібліотеки pandas. У цьому наборі даних для 118 мікрочіпів (об'єкти) вказано результати двох тестів з контролю якості (дві числові ознаки) і сказано, чи мікрочіп пустили у виробництво. Ознаки вже центровані, тобто від усіх значень віднімають середні по стовпцям. Таким чином, "середньому" мікрочіпу відповідають нульові значення результатів тестів.

data = pd.read_csv("../../data/microchip_tests.txt", header=None, names = ("test1","test2","released")) # інформація про набір даних data.info()

RangeIndex: 118 entries, 0 to 117
Data columns (total 3 columns):
test1 118 non-null float64
test2 118 non-null float64
released 118 non-null int64
dtypes: float64(2), int64(1)
memory usage: 2.8 KB

Подивимося на перші та останні 5 рядків.

Збережемо навчальну вибірку та мітки цільового класу в окремих масивах NumPy. Відобразимо дані. Червоний колір відповідає бракованим чіпам, зелений – нормальним.

Код

X = data.ix[:,:2].values ​​y = data.ix[:,2].values
plt.scatter(X, X, c="green", label="Випущений") plt.scatter(X, X, c="red", label="Бракований") plt.xlabel("Тест 1") plt .ylabel("Тест 2") plt.title("2 тести мікрочіпів") plt.legend();

Визначаємо функцію для відображення роздільної кривої класифікатора

Код

def plot_boundary(clf, X, y, grid_step=.01, poly_featurizer=None): x_min, x_max = X[:, 0].min() - .1, X[:, 0].max() + .1 y_min, y_max = X[:, 1].min() - .1, X[:, 1].max() + .1 xx, yy = np.meshgrid(np. np.arange(y_min, y_max, grid_step)) # кожній точці в сітці x # ставимо у відповідність свій колір Z = clf.predict(poly_featurizer.transform(np.c_)) Z = Z.reshape(xx.shape) plt. contour(xx, yy, Z, cmap=plt.cm.Paired)

Поліноміальними ознаками до ступеня для двох змінних і ми називаємо такі:

Наприклад, для цього будуть такі ознаки:

Намалювавши трикутник Піфагора, Ви зрозумієте, скільки таких ознак буде для і взагалі для будь-якого.
Просто кажучи, таких ознак експоненційно багато, і будувати, скажімо, для 100 ознак поліноміального ступеня 10 може виявитися затратно (а більш того, і не потрібно).

Створимо об'єкт sklearn, який додасть до матриці поліноміальних ознак аж до ступеня 7 і навчимо логістичну регресію з параметром регуляризації. Зобразимо межу, що розділяє.
Також перевіримо частку правильних відповідей класифікатора на навчальній вибірці. Бачимо, що регуляризація виявилася надто сильною, і модель "недонавчилась". Частка правильних відповідей класифікатора на навчальній вибірці дорівнювала 0.627.

Код

poly = PolynomialFeatures(degree=7) X_poly = poly.fit_transform(X)
C = 1e-2 logit = LogisticRegression(C=C, n_jobs=-1, random_state=17) logit.fit(X_poly, y) plot_boundary(logit, X, y, grid_step=.01, poly_featurizer=poly) plt.scatter (X, X, c="green", label="Випущений") plt.scatter(X, X, c="red", label="Бракований") plt.xlabel("Тест 1") plt.ylabel( "Тест 2") plt.title("2 тести мікрочіпів. Логит з C=0.01") plt.legend(); print("Частка правильних відповідей класифікатора на навчальній вибірці:", round(logit.score(X_poly, y), 3))

Збільшимо до 1. Тим самим ми послаблюєморегуляризацію, тепер у вирішенні значення ваги логістичної регресії можуть виявитися більше (по модулю), ніж у минулому випадку. Тепер частка правильних відповідей класифікатора на навчальній вибірці – 0.831.

Код

C = 1 logit = LogisticRegression(C=C, n_jobs=-1, random_state=17) logit.fit(X_poly, y) plot_boundary(logit, X, y, grid_step=.005, poly_featurizer=poly) plt.scatter(X , X, c="green", label="Випущений") plt.scatter(X, X, c="red", label="Бракований") plt.xlabel("Тест 1") plt.ylabel("Тест 2") plt.title("2 тести мікрочіпів. Логит з C=1") plt.legend(); print("Частка правильних відповідей класифікатора на навчальній вибірці:", round(logit.score(X_poly, y), 3))

Ще збільшимо – до 10 тисяч. Тепер регуляризації явно недостатньо, і ми спостерігаємо перенавчання. Можна помітити, що в минулому випадку (при =1 і "гладкому" кордоні) частка правильних відповідей моделі на навчальній вибірці не набагато нижче, ніж у 3 випадку, зате на новій вибірці, можна собі уявити, 2 модель спрацює набагато краще.
Частка правильних відповідей класифікатора на навчальній вибірці – 0.873.

Код

C = 1e4 logit = LogisticRegression(C=C, n_jobs=-1, random_state=17) logit.fit(X_poly, y) plot_boundary(logit, X, y, grid_step=.005, poly_featurizer=poly) plt.scatter(X , X, c="green", label="Випущений") plt.scatter(X, X, c="red", label="Бракований") plt.xlabel("Тест 1") plt.ylabel("Тест 2") plt.title("2 тести мікрочіпів. Логит з C=10k") plt.legend(); print("Частка правильних відповідей класифікатора на навчальній вибірці:", round(logit.score(X_poly, y), 3))

Щоб обговорити результати, перепишемо формулу для функціонала, який оптимізується в логістичній регресії, у такому вигляді:

Проміжні висновки:

Налаштування параметра регулювання

Тепер знайдемо оптимальне (у цьому прикладі) значення параметра регуляризації . Зробити це можна за допомогою LogisticRegressionCV - перебору параметрів по сітці з наступною крос-валідацією. Цей клас створений спеціально для логістичної регресії (для неї відомі ефективні алгоритми перебору параметрів), для довільної моделі ми використовували б GridSearchCV, RandomizedSearchCV або, наприклад, спеціальні алгоритми оптимізації гіперпараметрів, реалізовані в hyperopt.

Код

skf = StratifiedKFold(n_splits=5, shuffle=True, random_state=17) c_values ​​= np.logspace(-2, 3, 500) logit_searcher = LogisticRegressionCV(Cs=c_values, cv=skf, verbose=1 logit_searcher.fit(X_poly, y)

Подивимося, як якість моделі (частка правильних відповідей на навчальній та валідаційній вибірках) змінюється при зміні гіперпараметра.

Виділимо ділянку з "найкращими" значеннями C.

Як ми пам'ятаємо, такі криві називаються валідаційними, Раніше ми їх будували вручну, але в sklearn для них їх побудови є спеціальні методи, які ми теж зараз будемо використовувати.

4. Де логістична регресія хороша і де не дуже

Аналіз відгуків IMDB до фільмів

Вирішуватимемо завдання бінарної класифікації відгуків IMDB до фільмів. Є навчальна вибірка з розміченими відгуками, по 12500 відгуків відомо, що вони хороші, ще про 12500 – що вони погані. Тут уже не так просто відразу приступити до машинного навчання, тому що готової матриці немає – її треба приготувати. Будемо використовувати найпростіший підхід - мішок слів ("Bag of words"). При такому підході ознаками відкликання будуть індикатори наявності в ньому кожного слова з усього корпусу, де корпус – це багато відгуків. Ідея ілюструється картинкою

від __future__ import division, print_function # відключимо будь-які попередження Anaconda import warnings warnings.filterwarnings("ignore") import numpy as np import matplotlib.pyplot as plt %matplotlib inline import seaborn as sns import n. від sklearn .feature_extraction.text import CountVectorizer, TfidfTransformer, TfidfVectorizer від sklearn.linear_model import LogisticRegression from sklearn.svm import LinearSVC

Завантажимо дані звідси ( короткий опис-). У навчальній та тестовій вибірках по 12500 тисяч хороших та поганих відгуків до фільмів.

Приклад поганого відгуку:

"Words can"t describe how bad this movie is. I can\"t explain it by writing only. You have too see it for yourself to get at grip of how horrible a movie really can be. No that I recomend you to do that. mistakes (і всі інші negative things you can imagine) here that will just make you cry. To start with the technical first, there are a LOT of mistakes regarding the airplane. of the plane. Вони несуть цю позицію, щоб показати лінію в кольорах fictional airline, але вона була використана в 747 виконана в оригіналу Boeing livery. Very bad. Better.There are so many ridiculous moments here that i lost count of it really early. Also, I was on the bad guys\" side all the time in the movie, because the good guys were so stupid. "Executive Decision" повинен без будь-якого "виконати цей один, навіть "Турбуленство"-перетворюється на better. У дійсності, будь-яке інше зображення в світі є тим, що це."

Приклад хорошого відгуку:

"Якщо грати свою частину приємно добре в цьому "мінімально хорошому світі". Belushi збирається жити в реальній частині його життя різносторонньо, але закінчується реалізовуючи те, що він хотів, щоб йти до того, як приємно або може бути ще більше. Якщо ви не можете розраховувати на можливості, вони не мають, не буде або не може бути.Як можу отримати це відео на відео за $10, it\xc2\xb4d be an investment!"

Простий підрахунок слів

Складемо словник усіх слів за допомогою CountVectorizer. Всього у вибірці 74 849 унікальних слів. Якщо подивитися на приклади отриманих "слів" (краще їх називати токенами), то можна побачити, що багато важливих етапів обробки тексту ми тут пропустили (автоматична обробка текстів - це могло бути темою окремої серії статей).

Код

cv = CountVectorizer() cv.fit(text_train) print(len(cv.vocabulary_)) #74849
print(cv.get_feature_names()[:50]) print(cv.get_feature_names())

["00", "000", "0000000000001", "00001", "00015", "000s", "001", "003830", "006", "007", "0079", "0080", " 0083", "0093638", "00am", "00pm", "00s", "01", "01pm", "02", "020410", "029", "03", "04", "041" , "05", "050", "06", "06th", "07", "08", "087", "089", "08th", "09", "0f", "0ne", " 0r", "0s", "10", "100", "1000", "1000000", "10000000000000", "1000lb", "1000s", "1001", "100b", "100k", "100m ]
["pincher", "pinchers", "pinches", "pinching", "pinchot", "pinciotti", "pine", "pineal", "pineapple", "pineapples", "pines", "pinet", " pinetrees", "pineyro", "pinfall", "pinfold", "ping", "pingo", "pinheads", "pinheads", "pinho", "pining", "pinjar", "pink", "pinkerton" , "pinkett", "pinkie", "pinkins", "pinkish", "pinko", "pinks", "pinku", "pinkus", "pinky", "pinnacle", "pinnacles", "pinned", " pinning", "pinnings", "pinnochio", "pinnocioesque", "pino", "pinocchio", "pinochet", "pinochets", "pinoy", "pinpoint", "pinpoints", "pins", "pinsent" ]

Закодуємо речення з текстів навчальної вибірки індексами вхідних слів. Використовуємо розріджений формат. Перетворимо також тестову вибірку.

Навчимо логістичну регресію та подивимося на частки правильних відповідей на навчальній та тестовій вибірках. Виходить, на тестовій вибірці ми правильно вгадуємо тональність приблизно 86.7% відгуків.

Код

%%time logit = LogisticRegression(n_jobs=-1, random_state=7) logit.fit(X_train, y_train) print(round(logit.score(X_train, y_train), 3), round(logit.score(X_test, y_test)) , 3))

Коефіцієнти моделі можна красиво відобразити.

Код візуалізації коефіцієнтів моделі

def visualize_coefficients(classifier, feature_names, n_top_features=25): # get coefficients with large absolute values ​​coef = classifier.coef_.ravel() positive_coefficients = np.argsort(coef)[-n_top_features: :n_top_features] interesting_coefficients = np.hstack() # plot them plt.figure(figsize=(15, 5)) colors = ["red" if c< 0 else "blue" for c in coef] plt.bar(np.arange(2 * n_top_features), coef, color=colors) feature_names = np.array(feature_names) plt.xticks(np.arange(1, 1 + 2 * n_top_features), feature_names, rotation=60, ha="right");
def plot_grid_scores(grid, param_name): plt.plot(grid.param_grid, grid.cv_results_["mean_train_score"], color="green", label="train") plt.plot(grid.param_grid, grid.cv_results_[ mean_test_score"], color="red", label="test") plt.legend();
visualize_coefficients(logit, cv.get_feature_names())

Підберемо коефіцієнт регуляризації для логістичної регресії. Використовуємо sklearn.pipeline, оскільки CountVectorizer правильно застосовувати тільки на тих даних, на яких зараз навчається модель (щоб не "підглядати" в тестову вибірку і не рахувати за нею частоти входження слів). У даному випадку pipeline задає послідовність дій: застосувати CountVectorizer, потім навчити логістичну регресію. Так ми піднімаємо частку правильних відповідей до 88.5% на крос-валідації та 87.9% – на відкладеній вибірці.

Код

з sklearn.pipeline import make_pipeline text_pipe_logit = make_pipeline(CountVectorizer(), LogisticRegression(n_jobs=-1, random_state=7)) _selection import GridSearchCV param_grid_logit = ("logisticregression__C": np.logspace(-5, 0, 6)) grid_logit = GridSearchCV(text_pipe_logit, param_grid_logit, cv=3, n_jobs=-1) grid_logit.fit(text_train, y .best_score_ plot_grid_scores(grid_logit, "logisticregression__C") grid_logit.score(text_test, y_test)

Тепер те саме, але з випадковим лісом. Бачимо, що з логістичною регресією ми досягаємо більшої частки правильних відповідей меншими зусиллями. Ліс працює довше, на відкладеній вибірці 85.5% правильних відповідей.

Код для навчання випадкового лісу

від sklearn.ensemble import RandomForestClassifier forest = RandomForestClassifier(n_estimators=200, n_jobs=-1, random_state=17) forest.fit(X_train, y_train) print(round(forest.score(X_test, y_tes))

XOR-проблема

Тепер розглянемо приклад, де лінійні моделі справляються гірше.

Лінійні методи класифікації будують все ж таки дуже просту розділяючу поверхню - гіперплощину. Найвідоміший іграшковий приклад, у якому класи не можна без помилок поділити гіперплощиною (тобто прямий, якщо це 2D), отримав ім'я "XOR problem".

XOR - це "що виключає АБО", булева функція з наступною таблицею істинності:

XOR дав ім'я простому завданню бінарної класифікації, в якій класи представлені витягнутими по діагоналях і хмарами точок, що перетинаються.

Код, що малює наступні 3 картинки

# породжуємо дані rng = np.random.RandomState(0) X = rng.randn(200, 2) y = np.logical_xor(X[:, 0] > 0, X[:, 1] > 0)
plt.scatter(X[:, 0], X[:, 1], s=30, c=y, cmap=plt.cm.Paired);
def plot_boundary(clf, X, y, plot_title): xx, yy = np.meshgrid(np.linspace(-3, 3, 50), np.linspace(-3, 3, 50)) clf.fit(X, y) # plot вирішення функції для кожного datapoint на шнур Z = clf.predict_proba(np.vstack((xx.ravel(), yy.ravel())).T)[:, 1] Z = Z.reshape (xx.shape) image = plt.imshow(Z, interpolation="nearest", extent=(xx.min(), xx.max(), yy.min(), yy.max()), aspect=" auto", origin="lower", cmap=plt.cm.PuOr_r) contours = plt.contour(xx, yy, Z, levels=, linewidths=2, linetypes="--") plt.scatter(X[: , 0], X[:, 1], s=30, c=y, cmap=plt.cm.Paired) plt.xticks(()) plt.yticks(()) plt.xlabel(r"$$") plt.ylabel(r"$$") plt.axis([-3, 3, -3, 3]) plt.colorbar(image) plt.title(plot_title, fontsize=12);
plot_boundary(LogisticRegression(), X, y, "Logistic Regression, XOR problem")
з sklearn.preprocessing import PolynomialFeatures from sklearn.pipeline import Pipeline
logit_pipe = Pipeline([("poly", PolynomialFeatures(degree=2)), ("logit", LogisticRegression())])
plot_boundary(logit_pipe, X, y, "Logistic Regression + quadratic features. XOR problem")

Очевидно, не можна провести пряму так, щоб без помилок відокремити один клас від іншого. Тому логістична регресія погано справляється із таким завданням.

А от якщо на вхід подати поліноміальні ознаки, в даному випадку до 2-го ступеня, то проблема вирішується.

Тут логістична регресія все одно будувала гіперплощину, але в 6-мірному просторі ознак і . У проекції на вихідний простір ознак кордон вийшов нелінійним.

Насправді поліноміальні ознаки справді допомагають, але будувати їх явно – обчислювально неефективно. Набагато швидше працює SVM із ядровим трюком. При такому підході у просторі високої розмірності вважається лише відстань між об'єктами (що задається функцією-ядром), а явно плодити комбінаторно велику кількість ознак не доводиться. Про це можна детально почитати в курсі Євгена Соколова (математика вже серйозна).

5. Криві валідації та навчання

Ми вже отримали уявлення про перевірку моделі, крос-валідацію та регуляризацію.
Тепер розглянемо головне питання:

Якщо якість моделі нас не влаштовує, що робити?

• Зробити модель складніше чи спростити?
• Додати більше ознак?
• Чи нам потрібно більше даних для навчання?

Відповіді на ці питання не завжди лежать на поверхні. Зокрема, іноді використання складнішої моделі призведе до погіршення показників. Або додавання спостережень не призведе до суттєвих змін. Здатність прийняти правильне рішеннята вибрати правильний спосібПоліпшення моделі, власне кажучи, і відрізняє хорошого фахівця від поганого.

Працюватимемо зі знайомими даними щодо відтоку клієнтів телеком-оператора.

Імпорт бібліотек та читання даних

від __future__ import division, print_function # відключимо будь-які попередження Anaconda import warnings warnings.filterwarnings("ignore") Features from sklearn .pipeline import Pipeline з sklearn.preprocessing import StandardScaler з sklearn.linear_model import LogisticRegression, LogisticRegressionCV, SGDClassifier з sklearn.model_selection import validation_curve data = pd.read_csv(". State", axis=1) data["International plan"] = data["International plan"].map(("Yes": 1, "No": 0)) data["Voice mail plan"] = data[ "Voice mail plan"].map(("Yes": 1, "No": 0)) y = data["Churn"].astype("int").values ​​X = data.drop("Churn", axis=1).values

Логістичну регресію навчатимемо стохастичним градієнтним спуском. Поки що пояснимо це тим, що так швидше, але далі у програмі у нас окрема стаття про цю справу. Побудуємо валідаційні криві, що показують, як якість (ROC AUC) на навчальній та перевірочній вибірці змінюється зі зміною параметра регуляризації.

Код

alphas = np.logspace(-2, 0, 20) sgd_logit = SGDClassifier(loss="log", n_jobs=-1, random_state=17) logit_pipe = Pipeline([("scaler", StandardScaler()), ("poly ", PolynomialFeatures(degree=2)), ("sgd_logit", sgd_logit)]) val_train, val_test = validation_curve(logit_pipe, X, y, "sgd_logit__alpha", alphas, cv=5, scoring="roc_auc" x, data, **kwargs): mu, std = data.mean(1), data.std(1) lines = plt.plot(x, mu, "-", **kwargs) plt.fill_between(x, mu - std, mu + std, edgecolor = "none", facecolor = lines.get_color (), alpha = 0.2) ") plt.xlabel(r"$\alpha$"); plt.ylabel("ROC AUC") plt.legend();

Тенденція видно відразу, і дуже часто зустрічається.

Для простих моделей тренувальна та валідаційна помилка знаходяться десь поряд, і вони великі. Це говорить про те, що модель недонавчилась: тобто вона не має достатньої кількості параметрів.

Для сильно ускладнених моделей тренувальна та валідаційна помилки значно відрізняються. Це можна пояснити перенавчанням: коли параметрів занадто багато або не вистачає регуляризації, алгоритм може "відволікатися" на шум даних і упускати основний тренд.

Скільки потрібно даних?

Відомо, що чим більше даних використовує модель, то краще. Але як нам зрозуміти у конкретній ситуації, чи допоможуть нові дані? Скажімо, чи доцільно нам витратити N$ на працю асессорів, щоб збільшити вибірку вдвічі?

Оскільки нових даних поки може і не бути, розумно поваріювати розмір наявної навчальної вибірки та подивитися, як якість розв'язання задачі залежить від обсягу даних, на якому ми навчали модель. Так виходять криві навчання (learning curves).

Ідея проста: ми відображаємо помилку як функцію кількості прикладів, що використовуються для навчання. При цьому параметри моделі заздалегідь фіксуються.

Погляньмо, що ми отримаємо для лінійної моделі. Коефіцієнт регуляризації виставимо більшим.

Код

з sklearn.model_selection import learning_curve def plot_learning_curve(degree=2, alpha=0.01): train_sizes = np.linspace(0.05, 1, 20) PolynomialFeatures(degree=degree)), ("sgd_logit", SGDClassifier(n_jobs=-1, random_state=17, alpha=alpha))]) N_train, val_train, val_test = learning_curve(logit_pipe, X, =5; plt.ylabel("AUC") plt.legend() plot_learning_curve(degree=2, alpha=10)

Типова ситуація: для невеликого обсягу даних помилки на навчальній вибірці та у процесі крос-валідації досить сильно відрізняються, що вказує на перенавчання. Для тієї ж моделі, але з великим обсягом даних помилки "сходяться", що вказується на недонавчання.

Якщо додати ще дані, помилка на навчальній вибірці не зростатиме, але з іншого боку, помилка на тестових даних не зменшуватиметься.

Виходить, помилки "зійшлися" і додавання нових даних не допоможе. Власне, це випадок – найцікавіший для бізнесу. Можлива ситуація, коли ми збільшуємо вибірку вдесятеро. Але якщо не змінювати складність моделі, це може не допомогти. Тобто стратегія "налаштувала один раз – далі використовую 10 разів" може і не працювати.

Що буде, якщо змінити коефіцієнт регулювання (зменшити до 0.05)?

Бачимо хорошу тенденцію – криві поступово сходяться, і якщо далі рухатись праворуч (додавати в модель дані), можна ще підвищити якість на валідації.

А якщо ускладнити модель ще більше?

Проявляється перенавчання – AUC падає як у навчанні, і на валідації.

Будуючи такі криві, можна зрозуміти, в який бік рухатися, і як правильно налаштувати складність моделі на нових даних.

Висновки з кривих валідації та навчання

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

6. Плюси та мінуси лінійних моделей у завданнях машинного навчання

• Погано працюють у завданнях, у яких залежність відповідей від ознак складна, нелінійна
• На практиці припущення теореми Маркова-Гаусса майже ніколи не виконуються, тому частіше лінійні методи працюють гірше, ніж, наприклад, SVM та ансамблі (за якістю вирішення задачі класифікації/регресії)

7. Домашнє завдання №4

Актуальні домашні завдання оголошуються під час чергової сесії курсу, стежити можна у

Врахуємо тепер обмеження (2.2.2) управління. Якщо в процесі оптимального управління функції не досягають меж множини (2.2.2) (що означає), то для них виконуються співвідношення (2.2.13), (2.2.14). Однак часто оптимальне управління приймає граничні значення або, більше того, оптимальне управління може стрибком переходити з одного кордону на інший. Такі управління вже є шматково-безперервними функціями часу.

При попаданні оптимального управління на межу множини U співвідношення (2.2.13), (2.2.14) порушуються. Оптимальні управління задовольняють у разі принципу максимуму Л. З. Понтрягіна, встановленого і доведеного у вигляді наведеної нижче - теореми.

Переходячи до цієї теореми, зробимо деякі пояснення. Візьмемо довільне допустиме управління і за початкових умовахЗнайдемо рішення системи (2.2.1): .

Підставляючи це рішення та управління (2.2.8), визначимо, поки за деяких довільних початкових умовах , рішення (2.2.8): . При фіксованих (постійних) значення векторів функція Н стає функцією вектора . Максимум цієї функції по і позначимо через:

Максимум (найбільше значення) безперервної функції може досягатися як у точках локального максимумуцієї функції, в яких

так і на межах множини.

Теорема 2.2.1 (принцип максимуму Л. С. Понтрягіна). Нехай , - таке допустиме управління, що відповідні рішення рівняння (2.2.11), що виходять у момент зі стану (2.2.3), (2.2.7), проходять в момент часу через точку .

Для оптимальності управління (при якому) приймає найменше значення) необхідно існування таких ненульових безперервних функцій, що задовольняють рівнянням (2.2.12), що при будь-якому функція змінного досягає при максимумі

при цьому в кінцевий момент часу виконуються співвідношення

Якщо задовольняють (2.2.11), (2.2.12) і (2.2.17), функції змінного t є постійними і тому перевірку співвідношень (2.2.18) можна проводити не обов'язково в момент часу а в будь-який момент .

Доказ теореми досить складним, і у додатку 2 наведено лише висновок основного співвідношення (2.2.17) теореми для випадку вільного правого кінця ( не заданий) і фіксованого .

Співвідношення (2.2.17) і (2.2.18) можна записати у простішій формі:

Таким чином, центральною в теоремі 2.2.1 є умова максимуму (2.2.19). Воно означає, що якщо - оптимальні управління, а -оптимальні траєкторії, то неодмінно знайдуться така постійна і такі рішення), системи (2.2.12), що їх функція, змінних при всіх досягатиме максимуму на U саме при оптимальних управліннях. Тому теорему 2.2.1, що дає необхідна умоваоптимальності у завдання оптимального управління, прийнято називати принципом максимуму. Зазначимо, що в внутрішніх точкахмножини U для оптимального управління виконуються умови (2.2.13), (2.2.14), які є необхідними для (2.2.19).

Практичне застосування принципу максимуму.

Тут надходять так: розглядаючи функцію ) як функцію змінних і вважаючи змінні параметрами, вирішують завдання максимізації функції та знаходять функцію

на якій досягається найбільше значення функції.

У ряді випадків функція (2.2.20) може бути записана у явному вигляді. Наприклад, якщо праві частини (2.2.1) мають структуру

а підінтегральний вираз функціоналу (2.2.5)

безліч описується U нерівностями (2.2.2), то

і ця функція досягає найбільшого значення на U у точці з координатами

Формула (2.2.22) дає великий обсяг інформації про структуру оптимального управління: координата оптимального управління є ступінчастою (кусково-постійною) функцією зі значеннями, при цьому моменти перемикання визначаються умовою

Отже, скажімо, що функція (2.2.20) відома. Розглянемо систему диференціальних рівнянь

Функції та , що входять до правих частин цих рівнянь, відомі. Загальне рішення системи (2.2.24), (2.2.25) залежить від довільних постійних, які визначаються з крайових умов (2.2.3), (2.2.4). Завдання інтегрування рівнянь (2.2.24), (2.2.25) за крайових умов (2.2.3), (2.2.4) називається крайовим завданням (двоточковим крайовим завданням).

Таким чином, принцип максимуму дозволяє звести розв'язання задачі про оптимальне програмне управління до вирішення крайової задачі.

Складність її вирішення полягає в тому, що інтегрування рівнянь (2.2.24), (2.2.25) у «прямому часі» не є можливим, оскільки невідомі початкові умови. Один із можливих підходів до вирішення крайового завдання полягає в наступному. Задаючись довільним вектором та інтегруючи (2.2.24), (2.2.25) за відомих початкових умов, знайдемо функції та перевіримо виконання рівності (2.2.4). Якщо воно порушується, задаємося іншим вектором і, інтегруючи (2.2.24), (2.2.25) за початкових умов, отримаємо при векторі.

Якщо він не збігається із заданим, продовжуємо процес доти, доки не знайдеться такий вектор, що умови (2.2.4) будуть виконуватися з прийнятною точністю. При цьому підході використовуються градієнтні методи, коли визначається з умови мінімуму відстані від заданого вектора .

У обчислювальної математики розроблено низку методів наближеного чисельного розв'язання крайових завдань: метод стрільби, метод прогонки, низку ітераційних методів. У багатьох випадках неможливо знайти з умови (2.2.19) явний вид (2.2.22) оптимального управління. Тоді рівняння (2.2.1), (2.2.6), пов'язана система (2.2.12) та умови максимуму (2.2.19) утворюють крайове завдання принципу максимуму. Це завдання має ряд специфічних особливостей, що ускладнюють застосування стандартних чисельних методіввирішення крайових завдань. До таких особливостей ставляться розриви функцій які задовольняють умові максимуму (2.2.14), їх неєдиність, нелінійний характер залежності (2.2.20) навіть у лінійних системах. Крім того, особливістю крайових завдань, пов'язаних із принципом максимуму навіть у випадках, коли вдається знайти явний вид управлінь (2.2.20), є їхня погана збіжність, викликана нестійкістю системи (2.2.24), (2.2.25). Ряд прийомів розв'язання крайових завдань принципу максимуму викладено, наприклад, .

Зазначимо на закінчення, що, незважаючи на різні методичисельного вирішення крайового завдання принципу максимуму, процес вирішення кожної оптимізації на основі цього принципу є самостійним творчим завданням, Розв'язувана в рамках тієї приватної галузі динаміки, до якої належить об'єкт управління, з урахуванням його специфічних особливостей, що використовуються для поліпшення збіжності чисельного рішення крайового завдання.

Приклад 2.2.1. Побудова оптимального витрати палива управління .

Розглянемо об'єкт управління, що описується рівняннями

Нехай на управління накладено обмеження

Функціонал оптимізації, що виражає витрату палива, має вигляд

Задано початковий стан

та умова в момент часу

Потрібно знайти , при якому об'єкт (2.2.26) переходить зі стану (2.2.29) у стан (2.2.30), при цьому виконуються обмеження (2.2.27), а функціонал (2.2.28) набуває найменшого значення.

Переходячи до визначення оптимального керування на основі принципу максимуму, сформуємо функцію

рівняння для допоміжних змінних

Управління, що доставляє максимум функції (2.2.31), визначається як

Рівняння (2.2.26), (2.2.32), (2.2.33) складають крайове завдання. Переходячи до її дослідження, запишемо рішення системи (2.2.32):

де – невідомі числа, які необхідно визначити так, щоб управління (2.2.33) привело об'єкт (2.2.26) у стан (2.2.30).

Знайдемо рішення системи (2.2.26) при і. У першому випадку рішення цієї системи має вигляд. Воно залежить від постійних R і р, причому . Фазові траєкторії цієї системи є колами з центром на початку координат (рис. 2.2.1, а). Фазові траєкторії системи (2.2.26) при і є колами, центри яких розташовані в точках відповідно (рис. 2.2.1, б, в).