Обучение с Утвърждение (Част 1)

Съдържание:

Какво е обучение с утвърждение?
Описание на проблема
Какво е процес на Марков?
Полезност на състояния на агента в света; Уравнения на Белман.
Намиране на оптимални стойности на полезност и резултатни стратегии; Програмиране на уравненията на Белман.
Какво научихме за обучението с утвърждение?
Какво да очакваме от следващата статия?

Обучение с Утвърждение

Несъмнено сте чули за скорошните успехи на AlphaGo и AlphaZero – компютърни агенти, създадени от компанията Deepmind, които са способни да окажат сериозна конкуренция на световните шампиони по Го и Шах. Това са игри, които са изключително сложни и времеемки за усъвършенстване. В основата на тези алгоритми стои метод познат като обучение с утвърждение (reinforcement learning (en/bg)). Целта на тази и следващата статии е да надникнем под капака на обучението с утвърждение, чрез серия от теоретични формулировки и практични упражнения, и да покажем, че нещата всъщност не са въобще сложни и мистични.
Всеки, който е бил собственик на домашен любимец и се е занимавал с неговата дресировка, най-вероятно е използвал форма на обучение с утвърждение. Какъв е стандартният начин да накараме един домашен любимец – например куче – да изпълнява определени команди? Задаваме командата на кучето и ако то отговори по начина, по който очакваме, му даваме награда. Ако не отговори/реагира правилно – не му даваме награда. След определен брой опити и възнаграждения от наша страна, кучето би трябвало да започне да отговаря на командите ни само с правилни реакции, очаквайки награда всеки път – когато чуе “седни” – да сяда. Можем да кажем, че се е научило да асоциира определени гласови команди и съответните негови действия с резултатно възнаграждение.

Какво е процес на Марков?

В съвременната литература основният механизъм/модел, върху който се гради обучението с утвърждение, е процесът на Марков (Markov decision process (en/bg)). За да мотивираме следващите теоретични и практични примери, ще използваме следния пример: нека си представим че сме си купили робот прахосмукачка. Апартаментът е разделен на 12 квадранта, които роботът може да обитава във всеки един момент, с изключение на (1,1), където има колона. На всеки няколко часа роботът трябва да се зарежда, за да продължи да функционира – трябва да достигне до квадрант (3,2). Проблемът е, че освен робота имаме и котка, която спи в квадрант (3,1) и не обича да и пречат. Нека кажем, че ако роботът навлезе в пространството на котката ни, то ще ни трябва нов робот. Приемаме, че роботът може да се блъска в стени, оставайки в квадранта в който е, без трайни последици.
Задачата на робота е да се научи да стига до станцията си за зареждане максимално бързо от всяка една точка на апартамента, без да закача котката.

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

Множество от възможни състояния на агента S, (S for states) – 11-те квадранта, в които роботът може да бъде
Множество от възможни решения А, (A for actions), който агента може да взема – 4-те посоки, в които може да се движи
Транзиционна функция P(s’|s,a), (P for probability), която определя вероятността агента да попадне в състояние s’ ϵ S, ако преди това е бил в състояние s ϵ S и е взел решение а ϵ A. Транзиционната функция може да бъде предвидима – очакваният резултат от всяко решение в дадено състояние е напълно сигурен (ляво) – или стохастична (непредвидима) – очакваният резултат от дадено решение в дадено състояние не е напълно сигурен (дясно) – ако агентът реши да мине нагоре, има шанс да се окаже в различен от очаквания резултатен квадрант.

Функция R(s, a, s’), (R for reward), която определя каква моментална награда би получил агента ако е бил в състояние s ϵ S, взел е решение а ϵ A и е попаднал в състояние s’ ϵ S – в нашия случай само квадрант (4, 3) има положителна моментална награда, и само квадрант (4, 2) има отрицателна моментална награда. Бидейки във всички останали квадранти не носи никаква моментална награда на робота ни.
Начално състояние s₀ ϵ S – за нас това е квадрант (0, 0) – квадранта, в който се намираме, когато батерията ни се е изтощила достатъчно и трябва вече да бъде презаредена.
Преоценителен коефициент 𝜸 ϵ (гама), който определя колко нашия агент предпочита скорошни пред далечни-във-времето награди. По този начин може да накараме роботът ни да не губи време, когато се стреми да стигне до станцията – ако е пред станцията и се включи веднага, ще получи повече награда, отколкото ако изчака определено време и тогава започне да се зарежда.
Краен хоризонт H (H for horizon) – максималния брой стъпки, които агентът има, за да реши даден проблем – в нашия случай това могат да са максималния брой стъпки, които роботът ни може да направи, преди напълно да се изключи.

Ключов елемент при процеса на Марков е идеята за линейно време Т. Времето е дискретизирано на времеви стъпки – 0, 1, …., t, t+1, t+2, …., като всяка стъпка е пряко зависима само от предходната – това къде е робота в апартамента сега зависи само и единствено от това, къде е бил една стъпка назад във времето и не зависи от това къде е бил преди това.
Във всяка времева стъпка t агентът се намира в състояния s_t , взема решение a_t , преминава в състояние s_t+1 с вероятност P(s_t+1 | s_t, a_t) и получава награда r_t. Времето започва в 0 и свършва в H. Целта на агента ни е да максимизира сумарната награда, която може да получи от всяка една стъпка:

Обикновено, награди, които могат да бъдат получени по-скоро във времето са по-високо ценени от награди, които могат да бъдат получени в по-далечното бъдеще. Тази идея се демонстрира чрез регулация на преоценителния коефициент 𝛄:

Поведението на агента в средата се определя от стратегия 𝛑 (pi for policy), която той следва. Интуитивно, можем да приемем, че стратегията е определен тип предписание, което нашият почистващ робот следва:
“Ако си в квадрант (0, 0) -> мини нагоре”
“Ако си в квадрант (0, 1) -> мини нагоре”
…
“Ако си в квадрант (2, 2) -> мини наляво”
Формално, 𝛑 може да се разглежда като функция, която взема стойности от множеството на състоянията на агента s ϵ S и връща решение а ϵ A, което агента взема.
Въпросът е как, ако ни е даден процесът на Марков, описващ агента и динамиката на средата, да намерим такава оптимална стратегия 𝝿*, че сумарната R награда да е максимална.

Полезност на състояния на агента в света; Уравнения на Белман.

На теория, броя възможни стратегии, които съществуват, е A^s – във всяко едно свое състояние, агента може да вземе А на брой възможни решения. Само една от тези стратегии, обаче, задоволява условието да е оптимална – да носи на агента максимална възможна награда. Например, и трите стратегии, илюстрирани на фигурата по-долу са валидни, но само третата е оптимална.

Оптимална стратегия 𝝿* може да се извлече, ако знаем полезността на всеки един квадрант в света – по този начин бихме се стремили да попадаме само в квадранти, които са ни по-полезни от други. Какво означава, обаче, за един квадрант да бъде по-полезен от друг. В идеалния случай, с колкото по-малко стъпки можем да достигнем целта си, и колкото по-малък е шанса да попаднем на котката докато достигаме целта си, толкова по-добре. Например, квадрант (2,2) би ни бил по-полезен от квадрант (0,0), тъй като броя стъпки, които са ни нужни да стигнем до станцията за зареждане са съответно 1 и 5.
Прието е полезността да се обозначава с V(s) (V for value), за всеки s ϵ S. V*(s) (* често обозначава оптималност) определя колко награда максимално може да добие агента ни, ако започне в квадрант s и следва възможно най-добрата от всички стратегии 𝛑 до края на хоризонта или докато не стигне в терминално състояние.

Следвайки формулата, сумарната бъдеща награда, с преоценителен коефициент 𝜸 = 0.9, която можем да получим в предвидима среда (действията ни са еднозначни), започвайки от двата квадранта – (0,0) и (2,2) – и действайки оптимално (придържаме се към възможно най-добрата от всички възможни стратегии – max 𝝿) е:
V*(2,2) = 𝜸 * r₁ = 0.9
V*(0,0) = 𝜸⁵ * r₅ = 0.59
Въпросът е как можем да намерим тези интуитивни стойности на полезност за всеки един квадрант, от които след това да си изведем оптимална стратегия.
Струва си да отбележим връзката между R(s, a, s’) и V*(s). R(s, a, s’) е функция, която определя моменталната награда, която агента получава ако се окаже в състояние s’ от s, при взето решение a – полезността на тези състояние s е същата като съответната моменталната награда. Полезността на всички останали квадранти, които нямат моментални награди асоциирани с тях е пропорционална на разстоянието от тях до най-близкия квадрант с моментална награда. На практика V*(s) определя евентуалната очаквана награда, която агента би получил, ако във времева стъпка К той вземе възможно най-доброто решение (насочи се към възможно най-полезния следващ квадрант) и след това продължи да се държи оптимално през останалите К-1 времеви стъпки, стремейки се в крайна сметка да стигне до квадрант с положителна моментална награда. Именно придържането към оптимално държание в оставащите К-1 времеви стъпки води до рекурсивна връзка между стойностите на полезност на квадрантите/състоянията на агента:

Рекурсивни уравнения на Белман

където K, обозначава К оставащи времеви стъпки до края на хоризонта. Стойностите на полезност биха могли да бъдат намерени чрез решаването на система от S линейни уравнения – по едно уравнение за всяко състояние s. В случая обаче това не е възможно поради максимизиращата операция върху решенията a.
Това, което търсим ние са стойностите на полезност при H оставащи на брой възможни стъпки на агента. Използвайки рекурсивната зависимост можем да започнем с К=0 и да извършваме обновение на стойностите, докато К=H. На помощ ни идва динамичното програмиране и уравненията на Белман, които гарантират, че колкото по-голямо е К, толкова по малко ще се променя V_K+1 спрямо V_K , или иначе казано, след определена стойност на К ще открием оптималните стойности на полезност, от които ще можем да си изведем оптимална стратегия – колкото повече К расте, толкова по малка относителна промяна наблюдаваме в V_K-1 , V_K, V_K+1 , които клонят към V*.

Днес те питаме…

Loading …

Виж всички обяви Laptop graphic

Pwrteams

Project Management Office (PMO) Consultant

Fully Remote

dormakaba business services

Cloud Operations Engineer

Hybrid

A1 Bulgaria

DevOps Specialist

София

Виж всички обяви

Намиране на оптимални стойности на полезност и резултани стратегии; Програмиране на уравненията на Белман.

Тук следва практичната част, в която ще използваме динамично програмиране, за да намерим съответните оптимални стойности за полезност на всеки един от квадрантите, от които ще може да изведем и оптимална стратегия. Избрали сме Python като програмен език.
Първоначално започваме с К=0 оставащи времеви стъпки, което позволява само на квадрантите с моментална награда да имат полезност, която не е 0.
Продължаваме с К=1 оставащи времеви стъпки – оптималните стойности на полезност можем да сметнем, като за всеки квадрант вземем възможно най-доброто решение, и след това използваме стойностите на полезност при 0 оставащи стъпки. Така бихме добили стойностите на полезност за квадранти, от които ни е нужно поне едно движение, за да се окажем в квадрант с моментална награда.
…
При К=H оставащи времеви стъпки – оптималните стойности на полезност можем да сметнем, като за всеки квадрант вземем възможно най-доброто решение, и след това използваме стойностите на полезност при N-1 оставащи стъпки. Така бихме добили стойностите на полезност за квадранти, от които са ни нужни поне N движения, за да се окажем в квадрант с моментална награда.
Стига със обясненията, нека напишем програмата за нашия робот, която ще му позволява да намери пътя до зареждащата си станция, независимо къде се намира. Ще използваме следните модули и функции:

from copy import deepcopy
from matplotlib import pyplot as plt
from numpy import ndenumerate, around, argmax

Нека започнем със задаването на света (картата на помещението) в нашата програма, както и действията които са възможни. Също така да зададем преоценителния коефициент и вероятността, с която действията на нашия робот не успяват.

# Terminal states have nonzero reward
world = [
    ,
    ,
    ,
]
# Actions: Up, Down, Left, Right
actions = 
# Actions succeed with probability (1. - noise)
noise = 0.2
# Discount factor
gamma = 0.9

Тъй като знаем изцяло динамиката на света, можем да напишем функция, която за дадена текуща позиция в света и действие, пресмята всички възможни следващи позиции, както и техните вероятности. При зададената стойност на шума (noise=0.2), роботът ни ще успява да изпълни командата си 80% от времето, а 10% ще отива наляво и 10% надясно от зададената посока.

def step(state, action):
    # Up
    if action == 0:
        next_states = 
    # Down
    if action == 1:
        next_states = 
    # Left
    if action == 2:
        next_states = 
    # Right
    if action == 3:
        next_states = 
    # Probability of every possible next state
    probs = 
    return probs, next_states

Също така, трябва да вземем предвид, че ако нашият робот се опита да се придвижи в дадена посока, а там има препятствие (стена или колона), то той остава на мястото си – затова използваме следващите 4 помощни функции.

def move_up(state):
   i, j = state
   if i > 0 and world is not None:
       return (i - 1, j)
   else:
       return state
def move_down(state):
   i, j = state
   if i < len(world) - 1 and world is not None:
       return (i + 1, j)
   else:
       return state
def move_left(state):
   i, j = state
   if j > 0 and world is not None:
       return (i, j - 1)
   else:
       return state
def move_right(state):
   i, j = state
   if j < len(world) - 1 and world is not None:
       return (i, j + 1)
   else:
       return state

Сега, след като имаме цялата динамика на света, можем да се фокусираме върху смятането на стойността на полезност на дадена позиция използвайки рекурсивните уравнения на Белман (РУБ).

def stateValue(state, V):
    i, j = state
    state_values =  * len(actions)
    for a in actions:
        # Determine all possible next states and their probabilities
        probs, next_states = step(state, a)
        for p, (next_i, next_j) in zip(probs, next_states):
            # Accumulate current reward
            state_values += p * world
            # Accumulate future reward if state not terminal
            if world == 0.:
                state_values += p * gamma * V
    return max(state_values), argmax(state_values)

Вътрешният цикъл изброяващ всички възможни следващи позиции отговаря на сумата в РУБ, а външният цикъл върху всички възможни действия пресмята стойностите за max / argmax операторите в РУБ. С други думи, в дадено състояние, първият цикъл взима предвид всички възможни действия, а вторя всички възможни резултати от избраното действие. Сега единствено остава да пресметнем стойността на полезност на всяка позиция в нашия свят, като пропускаме позициите, на които има препятствия.

def valueIteration(V):
    next_V = deepcopy(V)
    policy = deepcopy(world)
    for i in range(len(V)):
        for j in range(len(V)):
            # Skip obstacles
            if world is None:
                continue
            # Calculate value of the state and find the best action
            next_V, policy = stateValue((i, j), V)
    return next_V, policy

Последната стъпка е да напишем и основната функция на нашата програма, която инициализира стойността на полезност за всяка позиция с 0, задава колко стъпки напред да вземем предвид (в случая сме избрали 100) и пресмята V*(s). Последната част от функцията визуализира намереното решение.

if __name__ == "__main__":
    # Initialise the value for each state to 0.
    h = len(world)
    w = len(world)
    V = [ * w for _ in range(h)]
    # Set horizon
    H = 100
    # Run value iteration
    for t in range(H):
        V, policy = valueIteration(V)
    # Visualise resulting values
    plt.imshow(V, interpolation='none', aspect='auto', cmap='RdYlGn')
    plt.xticks()
    plt.yticks(, ['2', '1', '0'])
    plt.colorbar()
    arrows = ['\u25b2', '\u25bc', '\u25c0', '\u25b6']
    for (i, j), v in ndenumerate(around(V, 2)):
        a = policy
        label = ""
        if a is not None:
            label += "\n" + str(v)
            if world == 0.:
                label = arrows + label
        plt.gca().text(j, i, label, ha='center', va='center')
       plt.show()

И така след като пуснем нашата програма трябва да получим следните стойности на полезност и стратегия:

Интересен е резултатът за квадрант (1, 0) където по-краткият път е надясно, но рискът в квадрант (2, 1) е прекалено голям, тъй като 10% от случаите роботът ни може да се окаже изправен лице в лице с котката, а както знаем това би било фатално. Експериментирайте с различни стойности на шума, преоценителния коефициент, както и дължината на хоризонта, за да разберете по-добре ролята на всеки параметър.
Можете да си свалите целият код от тук. Ако имате коментари или въпроси можете да ги зададете в репозиторито.
Важно е да отбележим, че имплемнтацията, която написахме е походяща за разбиране на метода, но далеч не е оптимална. За да напишем, оптимална имплементация е добра идея да използваме модулът за многомерни масиви Numpy и да сведем до минимум броят цикли, които пишем, използвайки функциите в Numpy.

Какво научихме за обучението с утвърждение?

Представеният пример далеч не се приближава по сложност до първоначално споменатите компютърни програми, които са се “научили” умело да играят Го и Шах. Същевременно е достатъчно прост, за да може да илюстрира крайъгълните камъни на всеки един агент, който се учи чрез утвърждение – а именно идеите за оптималност:

максимизиране на евентуална награда,
оптимални функции за полезност и
съответно оптимално стратегии.

Второстепенната цел на примера е да демонстрира с какво обучението чрез утвърждаване е различно от останалите подходи за машинно обучение, които са широкоизползвани в днешно време:

Сигналите от средата, които позволяват на агента да се учи, могат да са изключително редки и бедни на информация – често награда се получава само след като редица от действия са извършени, което прави трудно разграничаването на полезни от неполезни действия, при малък брой опити, което в реалния свят не винаги е възможно. За контраст, при проблемите за класифициране, информация се получава след всяко направено от агента решение – предсказание на дадена карегория – което прави процеса на трениране по-стабилен и осъществим.
Пресмятането на функции на полезност на решения и състояние и резултатни оптимални стратегии е лесно постижимо чрез демонстрираните алгоритми и методи, при положение, че имаме достъп до динамиката на средата – знаем транзиционната функция и функцията на моментална награда. В реалния свят, това доста честно е информация, до която агентът няма достъп, докато се учи.

Какво да очакваме от следващата статия?

В следващата статия, ще погледнем върху алтернативен подход за провеждане на обучение чрез утвърждение – подход, при който агента има по-малко информация за средата, което прави процесът на обучение по-труден. Ще се фокусираме върху алгоритъма Q Learning, който цели да пресметне оптималните стойности на полезност – Q*(s,a), за дадено решение в дадено състояние на света – без да има достъп до динамиката на света, както беше досега. За практичната част ще използваме подобна на сегашната двуизмерна среда, в която ще имаме марсоход, който се учи да навигира.

Допълнителни материали:
Berkeley Bootcamp: https://sites.google.com/view/deep-rl-bootcamp/lectures
Peter Abeel’s lecture: https://drive.google.com/file/d/0BxXI_RttTZAhVXBlMUVkQ1BVVDQ/view
Sutton’s book: http://www.incompleteideas.net/book/bookdraft2018mar16.pdf
CS 188: Artificial Intelligence Markov Decision Processes: https://s3-us-west-2.amazonaws.com/cs188websitecontent/lectures/SP17/SP17-CS188-Lecture-8-MDPs-I.pdf
CS 188: Artificial Intelligence Markov Decision Processes II: https://s3-us-west-2.amazonaws.com/cs188websitecontent/lectures/SP17/SP17-CS188-Lecture-9-MDPs-II.pdf
CS 188 Introduction to Artificial Intelligence, Fall 2017: https://drive.google.com/file/d/1nWKsik–Ht6PamiVLduCnwm35EMbIh7C/view

Автори:
Йордан Христов
>> Втора година докторант по „Роботика и Изкуствен Интелект“ в Единбургския Университет. Основният фокус на работата му е приложението на естествени, свободно-говорими езици в сферата на роботиката. Изследва и създавам алгоритми, които могат да се учат да изпълняват определени задачи и да извличат познания за съответната среда чрез интеракция с хора, които играят ролята на учители.
>>> С компютърни науки и софтуерно инженерство се занимава още от гинмазиалните си години – завършил е профил с Информатика и Математика в Математическата гимназия „Баба Тонка“, Русе. След това завършва Бакалавър по „Компютърни Науки“ в Единбургския университет. Там се запознава с идеята за изкуствен интелект под формата на автономни роботи и учещи се системи, което го вдъхновява да запиша докторска си степен.
>>> През годините е правил технически стажове във фирми от световно ниво – Amazon, Merrill Lynch, Skyscanner – които му показват индустриалната гледна точка върху изкуствения интелект – практични приложения, потенциални плюсове и лимитации.
Даниел Ангелов
>>> Завършил е стаж в PARC (Palo Alto Research Centre) в Калифорния, работейки по проект на DARPA за обясним изкуствен интелект (XAI). Целта е разработка на интелигентни агенти, които имат възможността не само да разрешават сложни проблеми, но и да обяснят своите действия.
>>> Докторант в сферата на „Роботика и Автономни Системи“ в Единбургския Университет. Основна тема на работата му е свързана с алгоритми базирани на изследване на причинно-следствени връзки. Това би помогнало за създаването на системи разбиращи света на по-фундаментално ниво, учещи се по-бързо, правейки аналогии от опит, докато предоставят възможността да се аргументират за всяко свое действие.
>>> Стремежът му да се занимавам с технологии/роботика тръгва още от времето му в СМГ, което го кара да завърши степен „Роботика“ в Университета в Рединг и го насочва по пътя му до момента. Това му дава възможността да се занимава паралелно по разнообразни индустриални проекти и да консултира различни фирми в България, Великобритания, САЩ.
Светлин Пенков
>>> Роботиката вдъхновява съзнанието на Светлин още от детските му години.
>>> В стремежа си да създава интелигентни роботи завършва “Роботика” в университета в Рединг, Великобритания, както и “Невроинфроматика и Изчислителни Невронауки” в Единбургския университет, където сега е във финалната фаза от докторантурата си по “Роботика и Изкуствен Интелект”.
>>> Голямата част от времето си прекарва като научен изследовател в стартъпа FiveAI, където имат за цел да създадът автономни автомобили с безпрецедентна сигурност.
>>> В изследователската си дейност разработва методи от сферата на изкуствения интелект, чрез които роботите разбират човешкото поведение, доближавайки ги до мечтаният асистент в нашето ежедневие.
>>> Носител на множество награди и стипендии за академичните си постижения.
>>> Проектите, по които Светлин е работил, варират от автономна система за наблюдение, през операционна система за роботи, до дизайн на бордови компютър за сателит.
>>> Светлин вярва, че е важно човек да споделя знанията и опита си, затова организира и води курсове свързани с машинно самообучение, изкуствен интелект, компютърно зрение, конструиране на цифрови компютри и вероятностно програмиране.