Przewidywanie sekwencji pseudolosowych

9

Zastrzeżenie: Jestem biologiem, więc przepraszam za (być może) podstawowe pytanie sformułowane w tak surowych terminach.

Nie jestem pewien, czy powinienem zadać to pytanie tutaj, czy na DS / SC, ale CS jest największym z trzech, więc proszę. (Po tym, jak opublikowałem, przyszło mi do głowy, że Cross-Validated może być lepszym miejscem na to, ale niestety).

Wyobraź sobie, że jest agent, który podejmuje decyzje binarne. Oraz środowisko, które za każdą decyzję agenta („próby”) nagradza agenta lub nie. Kryteria nagradzania decyzji agenta nie są proste. Ogólnie kryteria są losowe, ale mają ograniczenia, na przykład środowisko nigdy nie nagradza więcej niż 3 razy za tę samą decyzję i nigdy nie zmienia naprzemiennie decyzji nagradzanej więcej niż 4 razy z rzędu.

Sekwencja kryteriów może wtedy wyglądać mniej więcej tak

0 0 0 1 0 1 0 0 1 1 1 0 1 1 0 0 1 0 ...

ale nigdy

0 0 0 1 0 1 0 0 1 1 1 1 1 1 0 0 1 0 ...

ponieważ kryterium nagrody nie może się powtórzyć więcej niż 3 razy.

W tych warunkach dość łatwo jest sformułować strategię, którą powinien podjąć idealny obserwator, aby zmaksymalizować nagrodę. Coś w stylu

  1. decyduj losowo
  2. jeśli wykryjesz te kryteria powtórzone 3 razy - zdecyduj przeciwnie niż ostatnie kryterium
  3. jeśli wykryjesz te kryteria na przemian 4 razy, zdecyduj zgodnie z ostatnim kryterium

Teraz trudna część. Teraz kryterium dla każdej próby zależy nie tylko od historii poprzednich kryteriów, ale także od historii decyzji agenta, np. Jeśli agent naprzemiennie wykonuje więcej niż 8 z ostatnich 10 prób, nagradzaj tę samą decyzję, którą agent podjął ostatnim razem (ponieważ czy zniechęcić agenta do naprzemiennego zmieniania) i jeśli agent powtórzył tę samą decyzję w więcej niż 8 z ostatnich 10 prób, tj. jest stronniczy, należy zastosować kryterium przeciwne do uprzedzenia. Priorytet historii kryteriów nad historią decyzji jest z góry określony, więc nigdy nie ma dwuznaczności.

Sekwencje decyzji (d) i kryteriów (c) mogą teraz wyglądać następująco

d: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 0 1 0 ...
c: 1 0 1 0 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 0 ...
                       ↑ here criteria counteract bias in decisions  

Nie widzę żadnego prostego sposobu wymyślenia strategii maksymalizacji dla agenta. Ale jestem pewien, że musi być jeden i jakiś sprytny algorytm uczenia maszynowego powinien być w stanie go zidentyfikować.

Moje pytanie nie dotyczy raczej tego, jak rozwiązać ten problem (chociaż byłbym szczęśliwy, jeśli zaproponujesz rozwiązanie), ale bardziej, jak nazywane są tego rodzaju problemy? Gdzie mogę o tym przeczytać? Czy istnieje jakieś abstrakcyjne rozwiązanie, czy może pomóc tylko symulacja? Ogólnie, jak mogę, jako biolog, podejść do tego rodzaju problemu?

Siergiej Antopolskiy
źródło
2
patrz np. autoregresyjna analiza szeregów czasowych . pomogłoby to, gdybyś był bardziej szczegółowy na temat danych wejściowych. czy to z biologii? istnieją standardowe techniki dla problemów standardowych. radzą sobie z tym również powtarzające się ANN (sztuczne sieci neuronowe). również może upuść przez Computer Science Chat
vzn
2
Ukryte modele Markowa mogą być przydatnym narzędziem.
Raphael
1
Możesz przeczytać więcej na temat Follow-The-Leader i innych wariantów - onlineprediction.net/?n=Main.FollowTheLeader
MotiN
2
Myślę, że to, o czym mówisz, jest bliskie temu, co ludzie w ML nazywają Reinforcement Learning .
Kaveh
1
ps: Możesz spróbować opublikować post na Cross Validated, jeśli po pewnym czasie nie otrzymasz tutaj odpowiedzi.
Kaveh

Odpowiedzi:

1

Możesz podejść do tego problemu za pomocą Reinforcement Learning.

Klasyczna książka na ten temat to Sutton i Barto:

Szkic drugiej edycji jest dostępny za darmo: https://webdocs.cs.ualberta.ca/~sutton/book/the-book.html

Aby rozwiązać problem Markoviana, zdefiniuj każdy stan jako wektor dziesięciu ostatnich decyzji. Twoje działania będą wynosić 1 lub 0.

Juan Leni
źródło