Публикувано на: 15 юни, 2018Съдържание:
- Обзор от предишния път.
- Смятане на Q стойности вместо V стойности
- Обучение с утвърждение с и без модел на света
- Очаквана стойност, семплиране и Монте Карло
- TD-обучение и връзката с динамично програмиране
- ε-алчна стратегия
- OpenAI Gym
- Имплементиране на агент с TD-обучение
- Заключение
Обзор
В част 1 от поредицата се запознахме с част от основните идеи и техники, които стоят зад процеса на обучение чрез утвърждение, а именно какво е Процес на Марков, как можем да измерим и научим полезността на различните възможни състояния на агента в света, какво са уравнения на Белман, как да ги програмираме и използваме, за да научим агента да използва оптимална стратегия спрямо определена задача в дадена среда. Методите, които разгледахме обаче, не са общо приложими за проблеми в реалния свят решавани от истински роботи.
Роботът PR2 се учи да реди кубчета използвайки обучение с утвърждение.
Photograph by Spencer Lowell
Q-обучене
Чрез уравненията на Белман, можем да научим функция на полезност V, от която да изведем “алчна” стратегия – стратегия, при която агентът би получил максимална очаквана награда от средата на всяка стъпка.
При итеративното изчисляване на функцията V, използвайки динамично програмиране, ние смятаме и избираме максималната от няколко междинни стойности, които от своя страна съставят друга фунцкия на полезност Q (quality). Q(st,at), за разлика от V(st), се използва за обозначаване на полезността на действие at извършено в състояние st.
При алчни стратегии, връзката между V(st) и Q(st,at) е следната
тоест полезността на дадено състояние е равна на полезността на най-доброто действие, което можем да предприемем от това състояние.
Чрез тази зависимост можем да дефинираме рекурсивните уравнения на Белман и за Q функциията:
Обучение с утвърждение с и без модел на света
В задачата от предишната статия допуснахме два основни факта, които направиха уравненията на Белман приложими:
- Aгентът имаше достъп до функцията на преходите P(st+1 | st, at) на света – т.е моделирането на средата бе предварително извършено и роботът просто трябваше да използва този модел наготово. Доста често това е невъзможно в реалния свят. За конкретния проблем, това би означавало някой да напише правилата за това как би се държал робота при всевъзможни условия – различни подови настилки, наклон, заряд на батериите, температура и т.н.
- Въпросният модел на средата бе статичен и не се променяше с времето – това изключва възможността, например, някой да смени килима с теракот и роботът да продължи да се учи и работи правилно. Най-вероятно функцията на преходите за стая с килим е различна от тази на стая с теракот – килимът дава повече сцепление на колелата на робота и следователно средата е по-предвидима.
За друг пример нека вземем Seaquest – една от ATARI игрите, които са широко използвани за разработване на нови алгоритми и методи достигащи свръх човешки резултати. Задачата на агента е да се научи да спасява водолази, докато избягва вражески подводници, акули и от време на време изплува на повърхността за въздух.
Ако искаме да научим агента как успешно да играе Seaquest, използвайки техниките от предишната статия, то той трябва да има достъп до програмния код на играта – еквивалент на модел на света, който в случая е самата игра. Ако агентът е робот, който се учи в реалния свят, то той трябва да има достъп до всички физични закони управляващи околната среда (не просто тези, които ние знаем). Както виждате, агентите обикновено нямат директен достъп до модела на света, в който се намират, но могат да комуникират със света под формата на “черна кутия”. Агентът може да прочете от кутията състоянието st, в което се намира, след което да подаде на кутията действието, което решава да извърши at, а кутията връща следващото състояние st+1, в което агентът попада, заедно със съответна моментална награда rt+1.
Очаквана стойност, семплиране и Монте Карло
Алгоритми, използващи в себе си произволност, се делят грубо на 2 класа – Лас Вегас и Монте Карло. Лас Вегас са тип алгоритми, които при задедено количество изчислителни ресурси, намират винаги верен отговор или сигнализират за неуспеха си да намерят такъв. Лас Вегас методи се използват за проблеми, при които може бързо да се провери коректността на даден отговор (например проблеми с графи).
От друга страна, при зададени изчислителни ресурси, Монте Карло алгоритмите намират отговор с неизвестно количество грешка. Обикновено тази грешка може да се намали, ако се отделят повече ресурси. Така добиването на допълнителни извадки от данните, което ще наричаме семплиране (sample) на нови точки, ни позволява да намерим по-точен отговор.
Семплирането ни позволява с малко ресурси да придобием представа за стойността на различни суми или интеграли. При решими суми, можем много бързо да намерим приблизителната им стойност като използваме статистиката на малки партиди (mini batches).
Например може да намерим приблизително сумата на един милион числа като намерим средната стойност на произволни 100 от тях и предположим, че тя е характерна за останалите числа.
import numpy as np
# Let's generate the data
N = int(1e6)
a = np.random.randint(0, 101, size=N)
# Here we take 100 samples
c = np.random.choice(a, size=100)
# Now compare the approximated sum to the real one!
print('Approximate: {} Exact: {}'.format(c.mean()*N, a.sum()))
# Output: Approximate with 100 samples: 55520000.0. Exact: 49963052
Използвайки само 100 семпъла от всичките 1 милион числа получаваме отговор само с +11% грешка.
В други случаи, когато имаме нерешима сума или интеграл, можем да разглеждаме сумата или интеграла като очаквана стойност спрямо вероятностно разпределение и моделираме крайната стойност чрез средната стойност. Нека s бъде сумата или интеграла, който искаме да приближим, като p е вероятностно разпределение на произволната променлива x:
Може да приближим стойността на s като вземем n на брой семпъли x1, x2, …, xn от p(x) и намерим емпирично средното аритметично
От тук може да видим, че с увеличението на броя на семпъли, приближението ще става все по-точно.
Нека си представим, че се намираме в казиното Монте Карло. Искаме да се убедим в това, че заровете са наистина безпристрастни и вероятността да се падне всяко едно от числата е punbiased = ⅙. За съжаление нямаме възможността да ги огледаме внимателно и единствено може да наблюдаваме резултата от мятанията на различни хора.
Нека моделираме проблема по следния начин:
import numpy as np class Dice(): def __init__(self): is_biased = np.random.random_sample(1) > 0.5 if is_biased: # Generate probabilities around an unbiased dice p = np.random.normal(1./6, scale=0.05, size=6) self.p = p/p.sum() # Normalize to 1 else: # Generate uniform probabilities self.p = np.ones(6)/6. def roll(self, n=1): return np.random.choice(range(1,7), size=n, p=self.p) dice = Dice() # We don't know if the dice is biased or not # We can only observe samples from rolling it print(dice.roll()) # Output: print(dice.roll(n=5)) # Output:
В ляво може да видим хистограма на пристрастно зарче , с по-голяма вероятност да се падне ‘6’ (p = ). А от дясно – на балансирано зарче.
Може да намерите и експериментирате с кода на разгледаните Монте Карло примери тук.
TD-обучение
Методът, обединяващ идеите от динамично програмиране (т.е. рекурсивните уравненяе на Белман) със семплиране на модела на света за изчисляване на емпирично приближение на функцията на преходите, се нарича TD-обучение (temporal differencing learning). Използвайки нотацията за очавкана стойност, можем да представим полезността на дадено състояние като:
За всяко състояние трябва да анализираме всички следващи възможни състояние, обхождайки дървото на състояния в ширина.
Както споменахме, обаче, обикновено нямаме достъп до функцията на преходите, затова трябва да изчислим нейното приближение чрез семплиране:
където rit+1 и sit+1са семпли, които сме получили подавайки на “черната кутия” действие at< докато сме се намирали в състояние st. Ако следваме това уравнение, трябва първо да генерираме всичките си N семпли и след това да обновим полезността на състояние st. Ще бъде много по-ефективно, ако агентът може да използва информацията за всяко едно състояние веднага щом наблюдава резултата от решението си. Можем да го постигнем, ако заместим сумата с пълзяща средна стойност (moving average), получавайки следното уравнение:
Параметърът α задава скоростта на обучение (learning rate) на агента. Теоритично, α = 1 / N, но за да избегнем числова нестабилност в алгоритъма с нарастване броя на семплите, обикновено задаваме малка фиксирана стойност за α. Уравнението казва, че когато получим нов семпъл обновяваме текущата полезност на състоянието st с грешката в нашата оценка на полезността умножена по коефициент, който контролира колко бързо учим.
По аналогичен начин можем да изчислим полезността на всяко действие в дадено състояние:
След като заместим V(st+1) получаваме следното уравнение:
Това е основното уравнение, което се използва за TD-обучение, защото позволява на агента да учи, докато получава нови семпли, обхождайки дървото на състояния само по двойки:
Изследване на Непознатото и Използване на Познатото
Един от основните проблеми пред обучението с утвърждение е балансирането между изследването на нови региони от пространството на възможни състояния и използването на вече познатите такива. Ако даден агент е “алчен” и постоянно предприема действия водещи до състояния, които познава и е сигурен, че ще получи награда, то той може да пропусне още по-голяма награда в някое от състоянията, които не е посетил. Балансът между изследване и използване (exploration vs. exploitation) e ключов за постигане на добри резултати. Съществуват множество методи за модифициране на стратегията, която даден агент ползва, така че да се спрява по-добре с поставената задача. Една от най-широко използваните стратегии, която ще изплозваме и ние в следващата част, е ε-алчна стратегия. При нея агентът предприема произволно действие с малка вероятност ε, а в останалата част от времето следва напълно алчна стратегия.
OpenAI Gym
След толкова много теория, вече е време да преминем и към програмиране. В предишната статия сами си написахме света на нашия робот, защото знаехме всичко за него. Сега обаче ще разгледаме OpenAI Gym – един от най-широко използваните Python модули за тестване на агенти. Образно казано, OpenAI Gym предлага голям набор от “черни кутии” със стандартизиран интерфейс, които можем да ползваме като среда за нашия агент. Ние ще си изберем средата FrozenLake, която е много сходна със задачата за робота и котката. Тук целта е да минем по замръзнало езеро, като ходим само по замръзнала повърхност, избягвайки опасни дупки. Можем да се придвижваме хоризонтално и вертикално в четирите посоки с по една позиция. Така изглежда картата на света, представена като матрица от символи:
SFFF S (start): начална позиция, безопасна
Loading …
Fully Remote
HybridFHFH F (frozen): замръзнала повърхност, безопасна
FFFH H (hole): дупка, опасна
HFFG G (goal): крайна цел
Ако разгледате документацията на OpenAI Gym, ще видите, че така можем да пуснем напълно произволен агент в средата:
import gym
env = gym.make('FrozenLake-v0')
# Get the initial state s0
state = env.reset()
for _ in range(1000):
# Choose randomly one of the 4 possible actions
action = env.action_space.sample()
# Take the action
next_state, reward, done, info = env.step(acton)
# Visualise
env.render()
Първо създаваме средата, след това използваме reset(), за да я инициализираме и да получим s0. Състоянието във FrozenLake е индексът на клетката, в която се намира агента, като 0 е горен ляв ъгъл, а 15 долен десен. След това можем да си изберем напълно произволно действие и да го подадем на step() функцията, която ни връща следващото състояние, получената награда, дали агентът е стигнал терминално състояние и допълнителна информация за средата, ако ни трябва. За видим какво прави нашият агент можем да използваме функцията render().
Програмиране на агент с ε-алчна стратегия
За да имплементираме нашия агент, ще започнем с импортиране на модули и задаване на няколко константи.
import gym import numpy as np from matplotlib import pyplot as plt # Learning rate alpha = 0.05 # Discounting factor gamma = 0.999 # Exploration rate epsilon = 0.1
Сега ще напишем функция, която изиграва един епизод от началото до момента, в който агентът ни стигне целта или не падне в дупка. Функцията ще използва зададени Q стойности и ε-алчна стратегия.
def rollout(env, Q): episode_reward = 0 # Get initial state state = env.reset() for t in range(env.unwrapped.spec.max_episode_steps): # Choose action if np.random.uniform(0., 1.) < epsilon: # Select a random action action = np.random.choice(env.action_space.n) else: # Select the greedy action action = np.argmax(Q) next_state, reward, done, _ = env.step(action) episode_reward += reward state = next_state if done: break return episode_reward
Както виждате, имплементирането на ε-алчна стратегия е доста лесно. Първо избираме дали да предприемем напълно произволно или алчно действие като семплираме произволно число между 0 и 1 и проверим дали е по-малко от ε. Ако е, то тогава избираме произволно действие, иначе намираме най-доброто възможно действие в текущото състояние използвайки Q. Тук Q e двумерен NumPy масив, в който съхраняваме пресметнатата полезност на всяко едно действие за всяко едно състояние. Изразът Q връща полезността на всяко едно възможно действие в даденото състояние.
ТD-обучение
След като агентът вече може да си взаимодейства със средата, нека имплементираме и самото TD-обучение. Ще добавим аргумент train към нашата функция rollout, който ще включва или изключва тренирането по време на епизода. Ето вече как изглежда функцията:
def rollout(env, Q, train=False): episode_reward = 0 # Get initial state state = env.reset() for t in range(env.unwrapped.spec.max_episode_steps): # Choose action if train and np.random.uniform(0., 1.) < epsilon: # Select a random action action = np.random.choice(env.action_space.n) else: # Select the greedy action action = np.argmax(Q) next_state, reward, done, _ = env.step(action) episode_reward += reward if train: # Read the current state-action value Q_sa = Q # Find the value of the next state next_Q_s = np.max(Q) # Calculate the updated state action value new_Q_sa = Q_sa + alpha * (reward + gamma * next_Q_s - Q_sa) # Write the updated value Q = new_Q_sa state = next_state if done: break return episode_reward
Ако агентът трябва да се обучава по време на епизода, то тогава просто пресмятаме времевата грешка и обновяваме стойностите в Q според уравнението за TD-обучение. Също така, вече използваме ε-алчна стратегия само, ако агентът се обучава, иначе използваме алчна стратегия.
Сега ще го пуснем агента да се обучава за 10000 епизода и ще следим средната награда, която получава, за да разберем дали е научил задачата.
env = gym.make('FrozenLake-v0')
# Q is of size (# possible states, # possible actions) and
# initialised to small values around 0
Q = np.random.normal(
scale=1e-2,
size=(env.observation_space.n, env.action_space.n))
episodes = int(1e4)
average_reward = 0.
for e in range(episodes):
# Train with e-greedy policy
rollout(env, Q, train=True)
# Test with greedy policy
episode_reward = rollout(env, Q, train=False)
# Keep an estimate of the average reward for the past 100 episodes
average_reward = 0.99 * average_reward + 0.01 * episode_reward
# Reward threshold is 0.78 (theoretical optimum is 0.81)
if average_reward >= env.spec.reward_threshold:
print('Solved!')
break
print("{}: {}".format(e, average_reward))
Важно е да тренираме агентa с ε-алчна стратегия, а да тестваме с напълно алчна стратегия, за да балансираме използването на познати състояния срещу изследването на нови.
Сега ще визуализираме научената стратегия:
# Calculate state values
V = np.max(Q, 1).reshape(4, 4)
# Handle terminal states
for hole in [(1, 1), (1, 3), (2, 3), (3, 0)]:
V = 0.
V = 1.
# Visualise resulting values
plt.imshow(V, interpolation='none', aspect='auto', cmap='RdYlGn')
plt.xticks()
plt.yticks()
plt.colorbar()
arrows = ['\u25c0', '\u25bc', '\u25b6', '\u25b2'] # left, down, right, up
for (i, j), v in np.ndenumerate(np.around(V, 2)):
idx = i * 4 + j
a = np.argmax(Q)
# Handle terminal states
if idx in {5, 7, 11, 12, 15}:
label = str(v)
else:
label = arrows + '\n' + str(v)
plt.gca().text(j, i, label, ha='center', va='center')
plt.show()
Ето го и крайния резултат:
Преди знаехме каква е динамиката на света и можехме да проверим дали стратегията, която агентът е научил, е правилна. Сега действията, които водят до най-добър резултат, понякога изглеждат неинтуитивни, но все пак решават задачата. Ако разгледате внимателно сорс кода на FrozenLake сигурно ще разберете защо това е оптималната стратегия.
Можете да свалите целия код за TD-обучение от тук. Ако имате коментари или въпроси можете да ги зададете в репозиторито. При желание да експериментирате онлайн с различни параметри на ε или други константи, може да го направите тук.
Задачи с големи пространства на състоянията
FrozenLake има 16 възможни дискретни състояния, както и 4 възможни действия за всяко състояние. В резултат на това, Q таблицата е с малки размери (16х4=64). Пространството на състоянията на повечето проблеми обикновено е с доста по-голяма размерност и включва измерения с реални координати. Например, нека разгледаме още една среда от OpenAI Gym – LunarLander. Тук целта ни е да приземим летателен апарат на лунната повърхност като можем да контролираме тягата на основния и страничните двигатели. Състоянието е 8-мерен вектор, който съдържа 2D позиция, ориентация, линейна скорост, ъглова скорост на апарата, както и информация дали краката за кацане докосват повърхността.
8-мерно състояние не звучи чак толкова голямо, а пък и с реалните числа можем да се справим като ги дискретизираме. Kъм кода за тази статия ще намерите и файл q_learning_lunar_lander.py , където сме адаптирали решението ни на FrozenLake, за LunarLander. Експериментирайте, за да видите какви резултати ще получите*.
* GIF визуализацията на LunarLander не сме я генерирали с TD-обучение 😉
Заключение
В тази статия разгледахме какво е Q-обучение и какви предимства има пред стандартно динамично програмиране. Изведохме и програмирахме един от най-популярните алгоритми за обучение с утвърждение – TD-обучение. Агентът, използващ TD-обучение, може да се учи докато третира света като “черна кутия”, с която взаимодейства, като подава действия и наблюдава резултати. Използвахме OpenAI Gym и разрешихме FrozenLake проблема, който може да бъде сведен до навигиране в квадратна решетка. Повечето интересни задачи, обаче, имат доста по-сложно пространство на състоянията, където не можем да учим Q стойности под формата на голяма таблица. Затова в следващата статия ще разгледаме как можем да решим този тип проблеми чрез линеаризиране на Q функцията.
Допълнителни материали:
Searching for optimal policies I
Monte Carlo Methods – Deep Learning Book
Автори:
Йордан Христов
>>> Втора година докторант по „Роботика и Изкуствен Интелект“ в Единбургския Университет. Основният фокус на работата му е приложението на естествени, свободно-говорими езици в сферата на роботиката. Изследва и създавам алгоритми, които могат да се учат да изпълняват определени задачи и да извличат познания за съответната среда чрез интеракция с хора, които играят ролята на учители.
>>> С компютърни науки и софтуерно инженерство се занимава още от гинмазиалните си години – завършил е профил с Информатика и Математика в Математическата гимназия „Баба Тонка“, Русе. След това завършва Бакалавър по „Компютърни Науки“ в Единбургския университет. Там се запознава с идеята за изкуствен интелект под формата на автономни роботи и учещи се системи, което го вдъхновява да запиша докторска си степен.
>>> През годините е правил технически стажове във фирми от световно ниво – Amazon, Merrill Lynch, Skyscanner – които му показват индустриалната гледна точка върху изкуствения интелект – практични приложения, потенциални плюсове и лимитации.
Даниел Ангелов
>>> Завършил е стаж в PARC (Palo Alto Research Centre) в Калифорния, работейки по проект на DARPA за обясним изкуствен интелект (XAI). Целта е разработка на интелигентни агенти, които имат възможността не само да разрешават сложни проблеми, но и да обяснят своите действия.
>>> Докторант в сферата на „Роботика и Автономни Системи“ в Единбургския Университет. Основна тема на работата му е свързана с алгоритми базирани на изследване на причинно-следствени връзки. Това би помогнало за създаването на системи разбиращи света на по-фундаментално ниво, учещи се по-бързо, правейки аналогии от опит, докато предоставят възможността да се аргументират за всяко свое действие.
>>> Стремежът му да се занимавам с технологии/роботика тръгва още от времето му в СМГ, което го кара да завърши степен „Роботика“ в Университета в Рединг и го насочва по пътя му до момента. Това му дава възможността да се занимава паралелно по разнообразни индустриални проекти и да консултира различни фирми в България, Великобритания, САЩ.
Светлин Пенков
>>> Роботиката вдъхновява съзнанието на Светлин още от детските му години.
>>> В стремежа си да създава интелигентни роботи завършва “Роботика” в университета в Рединг, Великобритания, както и “Невроинфроматика и Изчислителни Невронауки” в Единбургския университет, където сега е във финалната фаза от докторантурата си по “Роботика и Изкуствен Интелект”.
>>> Голямата част от времето си прекарва като научен изследовател в стартъпа FiveAI, където имат за цел да създадът автономни автомобили с безпрецедентна сигурност.
>>> В изследователската си дейност разработва методи от сферата на изкуствения интелект, чрез които роботите разбират човешкото поведение, доближавайки ги до мечтаният асистент в нашето ежедневие.
>>> Носител на множество награди и стипендии за академичните си постижения.
>>> Проектите, по които Светлин е работил, варират от автономна система за наблюдение, през операционна система за роботи, до дизайн на бордови компютър за сателит.
>>> Светлин вярва, че е важно човек да споделя знанията и опита си, затова организира и води курсове свързани с машинно самообучение, изкуствен интелект, компютърно зрение, конструиране на цифрови компютри и вероятностно програмиране.
Стани част от потребителските групи на DEV.BG. Абонирай се и ще ти изпращаме информация за всичко, което предстои в групата.
Прочети още:
Обучение с Утвърждение (Част 1)
Изграждане на MVP блокчейн
