Навчання з підкріпленням для самих маленьких

В даній статті розібраний принцип роботи методу машинного навчання«Навчання з підкріпленням» на прикладі фізичної системи. Алгоритм пошуку оптимальної стратегії реалізований у коді на Python з допомогою методу «Q-Learning».

Навчання з підкріпленням — це метод машинного навчання, при якому відбувається навчання моделі, яка не має відомостей про систему, але має можливість здійснювати будь-які дії в ній. Дії переводять систему в новий стан і модель отримує від системи певну винагороду. Розглянемо роботу методу на приклад, показаному відео. В описі до відео знаходиться код Arduino, який реалізуємо на Python.

Завдання
З допомогою методу «навчання з підкріпленням» необхідно навчити візок від'їжджати від стіни на максимальну відстань. Нагорода представлена у вигляді значення зміни відстані від стіни до візка при русі. Вимірювання відстані D від стіни проводиться далекоміром. Рух у даному прикладі можливо тільки при певному усунення «приводу», що складається з двох стріл S1 і S2. Стріли являють собою два сервоприводу з напрямними, сполученими у вигляді «коліна». Кожен сервопривід в даному прикладі може повертатися на 6 однакових кутів. Модель має можливість здійснити 4 дії, які являють собою управління двома сервоприводами, дія 0 і 1 повертають перший сервопривід на певний кут за годинниковою і проти годинникової стрілки, дія 2 і 3 повертають другий сервопривід на певний кут за годинниковою і проти годинникової стрілки. На малюнку 1 показаний робочий прототип візки.


Рис. 1. Прототип візки для експериментів з машинним навчанням

На малюнку 2 червоним кольором виділено стріла S2, синім кольором – стріла S1, чорним кольором – 2 сервоприводу.


Рис. 2. Двигун системи

Схема системи наведена на рисунку 3. Відстань до стіни позначено D, жовтим показаний далекомір, червоним і чорним виділено привід системи.


Рис. 3. Схема системи

Діапазон можливих положень для S1 та S2 показано на малюнку 4:


Рис. 4.а. Діапазон положень стріли S1


Рис. 4.б. Діапазон положень стріли S2

Прикордонні положення приводу показано на малюнку 5:

При S1 = S2 = 5 максимальна дальність від землі.
При S1 = S2 = 0 мінімальна дальність до землі.


Рис. 5. Прикордонні положення стріл S1 і S2

У «приводу» 4 ступеня свободи. Дія (action) змінює положення стріл S1 і S2 у просторі за певним принципом. Види дій показано на малюнку 6.


Рис. 6. Види дій (Action) у системі

Дія 0 збільшує значення S1. Дія 1 зменшує значення S1.
Дія 2 збільшує значення S2. Дія 3 зменшує значення S2.

Рух
У нашій задачі візок приводиться в рух всього у 2х випадках:
У положенні S1 =0, S2 = 1 дію 3 приводить в рух візок від стіни, система отримує позитивну винагороду, що дорівнює зміні відстані до стіни. У нашому прикладі винагорода дорівнює 1.


Рис. 7. Рух системи з позитивним винагородою

У положенні S1 = 0, S2 = 0 дію 2 приводить в рух візок до стіни, система отримує негативне винагороду, що дорівнює зміні відстані до стіни. У нашому прикладі винагороду одно -1.


Рис. 8. Рух системи з негативним винагородою

При інших станах і будь-яких діях «приводу» система буде стояти на місці і винагорода буде дорівнює 0.
Хочеться відзначити, що стабільним динамічним станом системи буде послідовність дій 0-2-1-3 зі стану S1=S2=0, в якому візок буде рухатися в позитивному напрямку при мінімальній кількості витрачених дій. Підняли коліно – разогнули коліно – опустили коліно – зігнули коліна = візок зрушила вперед, повтор. Таким чином, за допомогою методу машинного навчання необхідно знайти такий стан системи, таку певну послідовність дій, нагорода за які буде отримана не відразу (дії 0-2-1 – нагорода за що дорівнює 0, але які необхідні для отримання 1 за наступна дія 3).

Метод Q-Learning
Основою методу Q-Learning є матриця ваг стану системи. Матриця Q являє собою сукупність можливих станів системи і ваг реакції системи на різні дії.
В даній задачі можливих комбінацій параметрів системи 36 = 6^2. У кожному з 36 станів системи можливо зробити 4 різних дії (Action = 0,1,2,3).
На рисунку 9 показано початкове стан матриці Q. Нульова колонка містить індекс рядка, перший рядок – значення S1, друга – значення S2, останні 4 колонки рівні ваг при діях рівних 0, 1, 2 і 3. Кожен рядок являє собою унікальне стан системи.
При ініціалізації таблиці всі значення ваг приравняем 10.


Рис. 9. Ініціалізація матриці Q

Після навчання моделі (~15000 ітерацій) матриця Q має вигляд, показаний на малюнку 10.


Рис. 10. Матриця Q після 15000 ітерацій навчання

Зверніть увагу, дії з вагами, рівними 10, неможливі в системі, тому значення ваг не змінилося. Наприклад, у крайньому положенні при S1=S2=0 можна виконати дію 1 і 3, так як це обмеження фізичного середовища. Ці прикордонні дії заборонені в нашій моделі, тому 10тки алгоритм не використовує.

Розглянемо результат роботи алгоритму:

Iteration: 14991, was: S1=0, S2=0, action= 0, now: S1=1, S2=0, prize: 0
Iteration: 14992, was: S1=1, S2=0, action= 2, now: S1=1, S2=1, prize: 0
Iteration: 14993, was: S1=1, S2=1, action= 1, now: S1=0, S2=1, prize: 0
Iteration: 14994, was: S1=0, S2=1, action= 3, now: S1=0, S2=0, prize: 1
Iteration: 14995, was: S1=0, S2=0, action= 0, now: S1=1, S2=0, prize: 0
Iteration: 14996, was: S1=1, S2=0, action= 2, now: S1=1, S2=1, prize: 0
Iteration: 14997, was: S1=1, S2=1, action= 1, now: S1=0, S2=1, prize: 0
Iteration: 14998, was: S1=0, S2=1, action= 3, now: S1=0, S2=0, prize: 1
Iteration: 14999, was: S1=0, S2=0, action= 0, now: S1=1, S2=0, prize: 0

Розглянемо детальніше:
Візьмемо ітерацію 14991 в якості поточного стану.
1. Поточний стан системи S1=S2=0, цьому стану відповідає рядок з індексом 0. Найбільшим значенням є 0.617 (значення рівні 10 ігноруємо, описано вище, воно відповідає Action = 0. Отже, згідно матриці Q при стані системи S1=S2=0 ми виробляємо дію 0. Дія 0 збільшує значення кута повороту сервоприводу S1 (S1 = 1).
2. Наступного стану S1=1, S2=0 відповідає рядок з індексом 6. Максимальне значення ваги відповідає Action = 2. Виробляємо дію 2 – збільшення S2 (S2 = 1).
3. Наступного стану S1=1, S2=1 відповідає рядок з індексом 7. Максимальне значення ваги відповідає Action = 1. Виробляємо дію 1 – зменшення S1 (S1 = 0).
4. Наступного стану S1=0, S2=1 відповідає рядок з індексом 1. Максимальне значення ваги відповідає Action = 3. Виробляємо дію 3 – зменшення S2 (S2 = 0).
5. У підсумку повернулися в стан S1=S2=0 і заробили 1 очко винагороди.

На малюнку 11 показаний принцип вибір оптимальної дії.


Рис. 11.а. Матриця Q


Рис. 11.б. Матриця Q

Розглянемо детальніше процес навчання.

Алгоритм Q-learning
minus = 0;
plus = 0;
initializeQ();
for t in range(1,15000):
epsilon = math.exp(-float(t)/explorationConst); 
s01 = s1; s02 = s2
current_action = getAction(); 
setSPrime(current_action); 
setPhysicalState(current_action);
r = getDeltaDistanceRolled(); 
lookAheadValue = getLookAhead(); 
sample = r + gamma*lookAheadValue;
if t > 14900: 
print 'Time: %(0)d, was: %(1)d %(2)d, action: %(3)d, now: %(4)d %(5)d, prize: %(6)d' % \
{"0": t, "1": s01, "2": s02, "3": current_action, "4": s1, "5": s2, "6": r} 
Q. iloc[s, current_action] = Q. iloc[s, current_action] + alpha*(sample - Q. iloc[s, current_action] ) ;
s = sPrime;
if deltaDistance == 1: 
plus += 1;
if deltaDistance == -1: 
minus += 1;
print( minus, plus )



Повний код на GitHub.

Встановимо початкове положення коліна в крайнє верхнє положення:

s1=s2=5.

Ініціалізуємо матрицю Q, заповнивши початковим значенням:

initializeQ();

Обчислимо параметр epsilon. Це вага «випадковості» дії алгоритму в нашому розрахунку. Чим більше ітерацій навчання пройшло, тим менше випадкових значень дій будуть обрані:

epsilon = math.exp(-float(t)/explorationConst)

Для першої ітерації:

epsilon = 0.996672

Збережемо поточний стан:

s01 = s1; s02 = s2

Отримаємо «найкращі» значення дії:

current_action = getAction();

Розглянемо функцію детальніше.

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

У вихідному початковому положенні стріл можливі тільки два кроки 1 і 3. Алгоритм вибрав дія 1.
Далі визначимо номер рядка матриці Q для наступного стан системи, який система перейде після виконання дії, яку ми отримали в попередньому кроці.

setSPrime(current_action);

У реальному фізичному середовищі після виконання дії ми отримали б винагороду, якщо послідувало рух, але так як рух візка моделюється, необхідно ввести допоміжні функції емуляції фізичної реакції середовища на дії. (setPhysicalState і getDeltaDistanceRolled() )
Виконаємо функції:

setPhysicalState(current_action);
— моделюємо реакцію середовища на обраний нами дію. Змінюємо положення сервоприводів, зміщуємо візок.

r = getDeltaDistanceRolled();
— Обчислюємо винагороду – відстань, пройдена візком.

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

lookAheadValue = getLookAhead();

На самому початку воно дорівнює 10. І використовуємо значення ваги, ще не виконаного дії, для підрахунку поточного ваги.

sample = r + gamma*lookAheadValue;
sample = 7.5
Q. iloc[s, current_action] = Q. iloc[s, current_action] + alpha*(sample - Q. iloc[s, current_action] ) ;
Q. iloc[s, current_action] = 9.75

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

Масштабування алгоритму
Даний алгоритм можна розширити на більшу кількість ступенів свободи системи (s_features), і більша кількість значень, які приймає ступінь свободи (s_states), але в невеликих межах. Досить швидко матриця Q займе всю оперативну пам'ять. Нижче приклад коду побудови зведеної матриці станів і ваг моделі. При кількості «стріл» s_features = 5 і кількості різних положень стріли s_states = 10 матриця Q має розміри (100000, 9).

Збільшення ступенів свободи системи
import numpy as np

s_features = 5
s_states = 10
numActions = 4

data = np.empty(s_states**s_features, s_features + numActions), dtype='int')
for h in range(0, s_features):
k = 0
N = s_states**(s_features-1-1*h)
for q in range(0, s_states**h):
for i in range(0, s_states):
for j in range(0, N):
data[k, h] = i 
k += 1

for i in range(s_states**s_features):
for j in range(numActions):
data[i,j+s_features] = 10.0;

data.shape

# (100000L, 9L)


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

Спасибі за увагу!
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.