Previsão de sequência pseudo-aleatória

9

Disclaimer: Eu sou um biólogo, desculpe-me pela (talvez) pergunta básica formulada em termos tão grosseiros.

Não tenho certeza se devo fazer essa pergunta aqui ou no DS / SC, mas o CS é o maior de três, então aqui vai. (Depois que postei, ocorreu-me que o Validado Cruzado pode ser o melhor lugar para isso, mas, infelizmente).

Imagine que existe um agente que toma decisões binárias. E um ambiente que, para cada uma das decisões do agente ("julgamentos"), recompensa o agente ou não. Os critérios para recompensar as decisões do agente não são simples. Em geral, os critérios são aleatórios, mas têm limitação, por exemplo, o ambiente nunca recompensa mais de 3 vezes pela mesma decisão e nunca alterna a decisão recompensada mais de 4 vezes seguidas.

Seqüência de critérios pode ser algo assim, então

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

mas nunca

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

porque o critério de recompensa não pode repetir mais de 3 vezes.

Nessas condições, é bastante fácil formular a estratégia que o observador ideal deve empreender para maximizar a recompensa. Algo ao longo das linhas de

  1. decidir aleatoriamente
  2. se você detectar esse critério repetido três vezes - decida o contrário do último critério
  3. se você detectar esse critério alternadamente 4 vezes, decida de acordo com o último critério

Agora, a parte difícil. Agora, o critério de cada tentativa depende não apenas do histórico dos critérios anteriores, mas também do histórico das decisões do agente, por exemplo, se o agente alternar em mais de 8 dos últimos 10 testes, recompensar a mesma decisão do agente da última vez (como se desencorajar o agente de alternar) e se o agente repetiu a mesma decisão em mais de 8 dos últimos 10 ensaios, ou seja, ele é tendencioso, faça o critério oposto ao viés. A prioridade do histórico de critérios sobre o histórico de decisões é especificada antecipadamente, para que nunca haja ambiguidade.

As seqüências de decisões (d) e critérios (c) agora podem ter esta aparência

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  

Não vejo uma maneira simples de inventar uma estratégia maximizadora para o agente. Mas tenho certeza de que deve haver um e algum tipo de algoritmo inteligente de aprendizado de máquina deve ser capaz de identificá-lo.

Minha pergunta não é tanto sobre como resolver esse problema (embora eu ficaria feliz se você sugerir uma solução), mas mais como esses tipos de problemas são chamados? Onde posso ler sobre isso? Existe uma solução abstrata ou apenas a simulação pode ajudar? Em geral, como posso, como biólogo, abordar esse tipo de problema?

Sergey Antopolskiy
fonte
2
veja, por exemplo , análise de séries temporais autoregressiva . ajudaria se você fosse mais detalhado sobre os dados de entrada. é da biologia? Existem técnicas STD para problemas STD. RNAs recorrentes (redes neurais artificiais) também lidam com isso. também talvez caia pelo Computer Science Chat
vzn 13/12/2015
2
Modelos ocultos de Markov podem ser uma ferramenta útil.
Raphael
11
Você pode querer ler sobre Follow-The-Leader e outras variantes - onlineprediction.net/?n=Main.FollowTheLeader
MotiN
2
Acho que você está se referindo ao que as pessoas no ML chamam de Aprendizagem por Reforço .
Kaveh
11
ps: convém tentar postar no Cross Validated se você não receber uma resposta aqui depois de algum tempo.
Kaveh

Respostas:

1

Você pode abordar esse problema usando o Aprendizado por reforço.

Um livro clássico para isso é Sutton e Barto:

O rascunho da segunda edição está disponível gratuitamente: https://webdocs.cs.ualberta.ca/~sutton/book/the-book.html

Para tornar seu problema markoviano, defina cada estado como um vetor das últimas dez decisões. Suas ações serão 1 ou 0.

Juan Leni
fonte