Проблема машинного навчання

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

Тобто вважається, що у нас є велика множина прикладів \(E\). Кожний приклад \(e \in E\) складається з пари \(e = \{ a, b\}\), де \(a \in A\) представляє вхід, який отримує агент і \(b \in B\) це вихід який агент має зв’язати з входом. Агент має знайти функцію \(f\), яка відображує \(A \rightarrow B\) для найбільш можливої кількості прикладів.

Кожен алгоритм навчання від навчання з підкріпленням до СВМ призводить до одної функції, але вибір може бути випадковим. Два алгоритма можуть навчитись на однаковому прикладі і дати дві різні функції. Це називається індукційне зміщення (induction bias). Саме тому деякі алгоритми працюють краще в певних областях. Їх індукційне зміщення “узгоджується” з внтурішніми особливостями проблем у цій області. Цей факт, що жоден навчальний алгоритм не може переважати всі інші в усіх можливих областях застосування був формалізований у No free lunch theorem (Wolpert and Macready, 1995).

Мультиагентна постановка

Якщо агент навчається за умов мультиагентної постановки фундаментальні припущення машинного навчання порушуються.
Тепер агент не намагається навчитись не на фіксованій множині прикладів \(E\). Замість цього мета змінюється у часі, тобто точки на попередньому рисунку рухаються. Це призводить до проблеми змінної функції (Vidal and Durfee, 1998b). Взагалі кажучи, точки зміщуються не випадково. Їх зміни обумовлені навчальною динамікою інших агентів у системі. Оскільки ці інші агенти також навчаються, множини входів-виходів змінюються.

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

Координаційна гра

globals [
colors
actions
]


patches-own[
  strategy
  payoff
  history
  played?
]

to setup
  ca
  reset-ticks
  set colors [red blue]
  set actions [0 1]
  ask patches[
    ifelse random-float 100 < percentage [
      set strategy 0
      set pcolor item 0 colors]
    [
      set strategy 1
      set pcolor item 1 colors]
    set played? false
  ]
end

to go
  
   ask patches [
    set played? false
    ]
  
  ask patches [
    let temp neighbors with [played? = false]
    if count temp > 0 [
     
    let p 0
    let s strategy   
    ask one-of temp [
        set p play-game strategy s
        set played? true
        set payoff p
    ]
    set payoff p  
    set played? true
  ]
  ]
 
  tick  
end

to-report play-game [act1 act2]
  ifelse act1 != act2 [report 0]
  [
    if act1 = 0 [report a11]
    if act1 = 1 [report a22]
   ]
end

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

Теоретичне обгрутнування? Як обчислити рівновагу Неша?

Завдання. зробити випадковий метчінг з усіма патчами які ще не грали.

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

Ідея зміни стратегії

globals [
colors
actions
]


patches-own[
  strategy
  payoff
  history
  played?
]

to setup
  ca
  reset-ticks
  set colors [red blue]
  set actions [0 1]
  ask patches[
    ifelse random-float 100 < percentage [
      set strategy 0
      set pcolor item 0 colors]
    [
      set strategy 1
      set pcolor item 1 colors]
    set played? false
  ]
end

to go

   ask patches [
    set played? false
    ]

  ask patches [
    let temp patches with [played? = false]
    if count temp > 0 [

    let p 0
    let s strategy
    ask one-of temp [
        set p play-game strategy s
        set played? true
        set payoff p
    ]
    set payoff p
    set played? true
  ]
  ]
  if change-strategy? [
    ask patches [
      if played? = true [
      switch-stategy
      ]
    ]
  ]
  tick
end

to-report play-game [act1 act2]
  ifelse act1 != act2 [report 0]
  [
    if act1 = 0 [report a11]
    if act1 = 1 [report a22]
   ]
end

to switch-stategy
  let n max-one-of neighbors4 [payoff]
  if [payoff] of n > payoff [
    set strategy [strategy] of n
    set pcolor [pcolor] of n
  ]
end

Інший спосіб

to switch-stategy-random
  let n one-of patches with [played? = true]
  if [payoff] of n > payoff [
    set strategy [strategy] of n
    set pcolor [pcolor] of n
  ]
end

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

Метод уявної гри

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

Метод уявної гри. Програма 1.

globals [
  colors
]

patches-own [
  history
  past-colors
]

to setup
  ca
  set colors [red white]
  ask patches [
    set pcolor one-of colors
    set history []
  ]
  
  reset-ticks
end

to go
  ask patches [
    take-action
  ]
  tick
  
end

to take-action 
  
  set history fput ([pcolor] of neighbors) history
  set past-colors reduce [[f s] -> sentence f s] history
  set pcolor one-of past-colors
end

Програма два. Вибір найбільш популярного кольору.

globals [
  colors
]

patches-own [
  history
  past-colors
]

to setup
  ca
  set colors [red white blue]
  ask patches [
    set pcolor one-of colors
    set history []
  ]
  
  reset-ticks
end

to go
  ask patches [
    take-action
  ]
  tick
  
end

to take-action 
  if (length history > memory-size)[
    set history but-last history
  ]
  set history fput ([pcolor] of neighbors) history
  set past-colors reduce [[f s] -> sentence f s] history
  set pcolor one-of modes past-colors
end

Програма три. Вибір найменш популярного кольору.

to-report count-matches [i the-list]
  report length filter [a -> a = i] the-list 
end

to take-action 
  if (length history > memory-size)[
    set history but-last history
  ]
  set history fput ([pcolor] of neighbors) history
  set past-colors reduce [[f s] -> sentence f s] history
  let color-frequency map [a -> count-matches a past-colors] colors
  let min-color-count min color-frequency
  set pcolor item (position min-color-count color-frequency) colors   
  ;set past-colors reduce [[f s] -> sentence f s] history
  ;set pcolor one-of modes past-colors
end