memória da máquina

• o hello world do raciocínio probabilístico
• a regressão logística
• reforço
  • do mdp à equação de bellman
    • função $v_{\pi}(s)$
    • função $q_{\pi}(s,a)$
    • comentários
  • temporal-difference learning
    • sarsa (on-policy)
    • q-learning (off-policy)
    • double q-learning
• rascunhos
  • construção axiomática de kolmogorov
    • probabilidade condicional
    • fórmula de bayes

Anotações desordenadas sobre as periferias da aprendizagem estatística.

o hello world do raciocínio probabilístico

estatística

Do ponto de vista estatístico ambas, regressão e classificação, podem ser pensadas como a busca pela aproximação de uma certa $f(y | x, w)$ que relaciona o conjunto de propriedades $x$ de uma observação à chance $p$ de certa informação de interesse $y$ dessa observação possuir determinado valor.

Em uma regressão $y$ é uma variável contínua. No problema de classificação $y$ é discreta. Em particular $y \in \{0, 1\}$ dá origem a problemas de classificação binária.
Fundamentalmente essa função $f$ tal que $f(y | x,w) \mapsto p$ nunca é completamente conhecida então há alguma liberdade na sua escolha. Desde um ponto de vista probabilístico as funções que compõem a chamada família exponencial recebem atenção especial na tarefa de estimar $p$. Duas escolhas clássicas são

a regressão logística

classificação

Nos primórdios nada havia. Então surgiu a regressão linear. Muita gente boa debruçou sobre esse problema, dando origem a métodos como o dos mínimos quadrados. A princípio os métodos de regressão só funcionam quando a variável de interesse $y$ – ou “target”, ou “variável resposta”, ou “variável dependente” – é contínua.

A ideia na regressão logística é usar técnicas/algoritmos de regressão para resolver problemas de classificação. Daí a esquizofrenia da regressão logística – um método de classificação com “regressão” no nome.

O truque é limitar o resultado da regressão no intervalo $\left[0, 1\right]$, para ter cara de probabilidade, e eventualmente definir um valor de probabilidade que separa as classes $0$ e $1$.

Há algumas funções que satisfazem essa necessidade, mas no lugar de sacar uma delas é interessante pensar no problema inverso: como levar algo de $[0,1]$ em $\mathbb{R}$?

Algo com a cara $\mathcal{F}(x) = \frac{1}{x}$ serve para levar para o infinito. Nesse caso:

Um detalhe da $\mathcal{F}$ é que probabilidades altas levam a valores pequenos e vice-versa. Uma forma de acalmar os corações mais desesperados dos apostadores do mundo é construí-la como $\mathcal{F}(x) = \frac{1}{\frac{1}{x}-1}$, assim:

Para atingir o outro infinito a $\mathcal{G}(x) = log(x)$ resolve:

Essas duas funções $\mathcal{F}(p)$ e $\mathcal{G}(\mathcal{F}(p))$ são chamadas por aí respectivamente de odds, ou “chance”, e logit, que já vi chamarem de “logíto” também.
$\mathcal{G}(\mathcal{F}(p))$ leva pseudo-probabilidades nos reais, então para para resolver um problema de classificação usando os métodos de regressão, basta aplicar $\mathcal{F}^{-1}(\mathcal{G}^{-1}(\cdot)) \equiv \sigma(\cdot)$ no resultado.
Essa inversa também tem nome: função sigmoide

Com respeito ao modelo é interessante observar que os parâmetros de ajuste $w$ não são as probabilidades, senão os logitos. Como $p \sim \sigma(w^T x)$, então

\begin{equation} \boxed{ w^Tx = log \left( \frac{p}{1-p} \right) } \label{reglog} \end{equation}

Uma das hipóteses da regressão logística é que as observações são distribuídas de forma que $p(y=c) \sim Bern$, com $c \in \{0, 1\}$, ou seja

À luz disso é interessante olhar pra $\mathcal{F}$ uma última vez:

reforço

aprendizagem estatística

De forma completamente rasteira e sem compromisso com qualquer espécie de rigor:

do mdp à equação de bellman

Alguns sistemas – sobretudo os de tomadas de decisões sequenciais – podem ser estruturados de acordo com o framework Markov Decision Process (MDP). Nele é suposta que a propriedade de Markov é satisfeita para o sistema, ou seja, que as probabilidades de transição entre estados não depende de toda a história dos eventos e ações nesse sistema, senão apenas do estado anterior – ou seja, nesses sistemas o que impera é a memória curta; nesse sentido, nosso sistema eleitoral pode ser estruturado de acordo com um MDP. Essa propriedade pode ser resumida por

em que $S_{i}$ é o estado do sistema no i-ésimo instante – esse estado é elemento do conjunto $\mathcal{S} = \left[ s_1, s_2, \dots, s_n \right]$ de todos estados possíveis de serem acessados no sistema. Analogamente, $A_i$ é a ação executada no i-ésimo instante, podendo assumir os valores contidos no conjunto $\mathcal{A} = \left[ a_1, a_2, \dots, a_n \right]$ que contém todas as ações possíveis.

Além disso, é suposto que há uma recompensa final $G$ que é resultado de retornos parciais $R$ devidas à sequência de ações

Em que $R_T$ é a recompensa do estado terminal. Então, em um MDP, a probabilidade $p$ de receber a recompensa $r$ transitando do estado $s$ para o estado $s’$ após a ação $a$ satisfaz

Contudo, no contexto de tomada de decisão sequencial o tempo tem papel central, de modo que é natural interpretar que a melhor sequência de tomada de decisão é a que chega a bons estados terminais mais rapidamente – ou seja, quanto maior o tempo gasto para ganho de recompensas futuras, menos elas valem. Essa urgência pode ser expressada através do decremento temporal proporcional a um fator de desconto $\gamma \in \left[0, 1\right]$ tal que

Disso, surgem provavelmente as duas funções em torno das quais orbitam todos os métodos de aprendizagem por reforço: $v_{\pi}(s)$ e $q_{\pi}(s,a)$.

É interessante sintetizar que, conceitualmente, o objetivo da aprendizagem por reforço é aprender políticas $\pi$ que otimizem a função objetivo

função $v_{\pi}(s)$

A (mal traduzindo) função estado-valor $v_{\pi}(s)$ é definida como uma medida da recompensa esperada por seguir a política $\pi$ partindo do estado $s$ – também pode ser interpretada como uma função que atribui um valor a um estado $s$ quando a política $\pi$ é usada na tomada de decisão. Ou seja

Desenvolvendo:

O primeiro termo é a recompensa esperada dado um estado $s$. Por definição de média para variáveis discretas combinada às propriedades das funções densidade probabilidade

O segundo tem desenvolvimento análogo

Então

Eu tenho sérias dúvidas se essa já é a equação de Bellman para sistemas descritos como MDP, ou se as equações de Bellman são as que definem as condições de otimalidade para a solução da equação acima.

função $q_{\pi}(s,a)$

A (mal traduzindo) função estado-ação-valor $q_{\pi}(s,a)$ é definida como uma medida da recompensa esperada por seguir a política $\pi$ partindo do estado $s$ executando a ação $a$ – ou seja, é uma função que atribui um valor à ação $a$ executada no estado $s$. Ou seja

É possível desenvolver essa equação usando as mesmas ideias da seção anterior. Nesse caso a conclusão seria que

É curioso notar que

comentários

operador de bellman

No caso de políticas determinísticas $a = \pi(s)$, então

Nesse cenário determinístico é possível construir operadores com propriedades muito importantes – exploradas nesse texto. Os operadores são

Com $T_{1}^{\pi} : (S \rightarrow \mathbb{R}) \rightarrow (S \rightarrow \mathbb{R})$ e $T_{2}^{\pi} : (S \times A \rightarrow \mathbb{R}) \rightarrow (S \times A \rightarrow \mathbb{R})$. Então as equações de Bellman assumem a forma

otimalidade

Uma política ótima é alguma que, dentre todas as políticas possíveis, dá os maiores retornos esperados possíveis para todos os estados. Como

então

É possível existir mais de uma política ótima, porém todas compartilham as mesmas funções estado-valor e ação-estado-valor

Conceitualmente – e por construção – o valor de um estado de acordo com a política ótima deve coincidir com o retorno esperado associado a esse estado ao se executar a melhor ação do estado – certo? Então

de onde é possível escrever

e

temporal-difference learning

a partir daqui os parágrafos são rascunhos e esboços

• $\text{policy evaluation} \quad (v^{*}:v\mid\pi) \rightarrow \text{prediction problem}$
• $\text{optimal policy search} \quad (\pi^{*}) \rightarrow \text{control problem}$

Em contraste aos métodos Monte Carlo, em que o problema da predição é resolvido levando-se em conta a recompensa $G_t$

nos métodos Temporal-Difference o problema é resolvido levando em conta os retornos parciais $R_t$, de acordo com

de onde surge a forma mais primitiva do algoritmo TD para estimativa de $v_{\pi}$

\begin{algorithm}
\caption{TD}
\begin{algorithmic}
\Procedure{TD}{$\pi,\alpha \in [0,1)$} 
    \State inicializa $V(s)$ aleatoriamente
    \State define $V(terminal)=0$
    \For{episódio}
    \State inicializa $S$
    \Repeat
        \State $A \leftarrow a$ de acordo com $\pi(a \mid s)$
        \State observa $R$ e $S'$
        \State $V(S) \leftarrow V(S) + \alpha\left[ R - \gamma V(S') - V(S))\right]$
        \State $S \leftarrow S'$
    \Until{$S$ é estado terminal}
    \EndFor
\EndProcedure
\end{algorithmic}
\end{algorithm}

Dessa estrutura derivam dois importantes métodos

sarsa (on-policy)

Nessa abordagem a função aprendida é a $q_{\pi}(s,a)$, com passo de atualização

\begin{algorithm}
\caption{SARSA}
\begin{algorithmic}
\Procedure{SARSA}{$\pi,\alpha \in [0,1), \epsilon \to 0^{+}$} 
    \State inicializa $Q(s,a)$ aleatoriamente
    \State define $Q(terminal, \cdot)=0$
    \For{episódio}
    \State inicializa $S$
    \State escolhe $A$ em $S$ de acordo com $\pi(a \mid s)$ de $Q$
    \Repeat
        \State observa $R$ e $S'$
        \State escolhe $A'$ em $S'$ de acordo com $\pi(a \mid s)$ de $Q$
        \State $Q(S,A) \leftarrow Q(S,A) + \alpha\left[R - \gamma Q(S',A') - Q(S,S))\right]$
        \State $S \leftarrow S'$
        \State $A \leftarrow A'$
    \Until{$S$ é estado terminal}
    \EndFor
\EndProcedure
\end{algorithmic}
\end{algorithm}

# ...

q-learning (off-policy)

Nessa abordagem há uma mudança sutil: a função aprendida é a ação-valor ótima $q_{*}(s,a)$, com passo de atualização

\begin{algorithm}
\caption{Q-Learning}
\begin{algorithmic}
\Procedure{QL}{$\alpha \in [0,1), \epsilon \to 0^{+}$} 
    \State inicializa $Q(s,a)$ aleatoriamente
    \State define $Q(terminal, \cdot)=0$
    \For{episódio}
    \State inicializa $S$
    \Repeat
        \State escolhe $A$ em $S$ de acordo com $Q$
        \State observa $R$ e $S'$
        \State $Q(S,A) \leftarrow Q(S,A) + \alpha\left[R - \gamma \underset{a}{max} Q(S',a) - Q(S,A))\right]$
        \State $S \leftarrow S'$
    \Until{$S$ é estado terminal}
    \EndFor
\EndProcedure
\end{algorithmic}
\end{algorithm}

# ...

double q-learning

Para evitar o “viés da maximização” no Q-Learning, causado pelo uso dos mesmos valores usados para ambos, obter a ação que maximiza a função ação-valor e estimar seu valor, é introduzida uma segunda função ação-valor, de modo a desacoplar esses dois passos, fazendo o passo de atualização passar a ser

\begin{algorithm}
\caption{Double Q-Learning}
\begin{algorithmic}
\Procedure{DQL}{$\alpha \in [0,1), \epsilon \to 0^{+}$} 
    \State inicializa $Q_{1}(s,a)$ aleatoriamente
    \State inicializa $Q_{2}(s,a)$ aleatoriamente
    \State define $Q_{1}(terminal, \cdot)=0$
    \State define $Q_{2}(terminal, \cdot)=0$
    \For{episódio}
    \State inicializa $S$
    \Repeat
        \State escolhe $A$ em $S$ de acordo com $Q_{1}+Q_{2}$
        \State observa $R$ e $S'$
        \State $p \leftarrow \mathcal{U}_{[0,1]}$
        \If{$p > 0.5$}
            \State $Q_{1}(S,A) \leftarrow Q_{1}(S,A) + \alpha\left[R - \gamma Q_{2}\left(S', \underset{a}{max} Q_{1}(S',a)\right) - Q_{1}(S, A))\right]$
        \Else
            \State $Q_{2}(S,A) \leftarrow Q_{2}(S,A) + \alpha\left[R - \gamma Q_{1}\left(S', \underset{a}{max} Q_{2}(S',a)\right) - Q_{2}(S, A))\right]$
        \EndIf
        \State $S \leftarrow S'$
    \Until{$S$ é estado terminal}
    \EndFor
\EndProcedure
\end{algorithmic}
\end{algorithm}

# ...

a partir daqui os parágrafos são rascunhos e esboços

rascunhos

construção axiomática de kolmogorov

probabilidade

Dados eventos $A_1, A_2, \dots ,A_n \in \mathcal{A}$, disjuntos, em que $\mathcal{A}$ é uma $\sigma$-álgebra do conjunto $\Omega$, denotando $P(A_i)$ a probabilidade de $A_i$, segue uma função $P$ definida em $\mathcal{A}$ satisfazendo

A1. $P(A) \geq 0$

A2. $P(\Omega) = 1$

A3. $P \left( \bigcup_{n=1}^{\infty} A_n \right) = \sum_{n=1}^{\infty} P(A_n)$

é chamada medida de probabilidade em $\mathcal{A}$ e satisfaz as seguintes propriedades

P1. $P(A^c) = 1 - P(A)$

P2. $0 \leq P(a) \leq 1$

P3. $A_1 \subset A_2 \Rightarrow P(A_1) \leq P(A_2)$

P4. $P \left( \bigcup_{i=1}^{\infty} A_i \right) \leq \sum_{i=1}^{\infty} P(A_i)$

P5. $A_n \uparrow A \Rightarrow P(A_n) \uparrow P(A) \qquad e \qquad A_n \downarrow A \Rightarrow P(A_n) \downarrow P(A)$

probabilidade condicional

A probabilidade condicional do evento $A$ dada observação de $B$ pode ser definida como

expresando um resultado intuitivo: dados $n$ ensaios independentes de $A$ e $B$, no limite de $n \to \infty$ é razoável que

Disso segue que

• $P(A \cap B) = P(B)P(A \mid B)$
• $P(A \cap B \cap C) = P(A)P(B \mid A)P(C \mid A \cap B)$

esse segundo resultando podendo ser generalizado para o teorema da probabilidade composta, onde vale que

Dada a disjuntividade dos $A_i$, um evento $B \in \mathcal{A}$ pode ser representado como

consequentemente

fórmula de bayes

Combinando os resultados anteriores segue a fórmula de Bayes

from math import factorial as fac
import matplotlib.pyplot as plt
%matplotlib inline

def comb(a,b):
    return  fac(a) / (fac(b)*fac(a-b))

def P(u, nb, N):
    marg = (1/11) * sum( [ comb(N, nb)*((U/10)**nb)*(1-(U/10))**(N-nb) for U in range(11) ] )
    return (1/11)*(1/marg)*comb(N, nb)*((u/10)**nb)*(1-(u/10))**(N-nb)

def g(sorteios, bolas_p):
    plt.bar( [i for i in range(11)], [P(j, bolas_p, sorteios) for j in range(11)], width=0.0005)
    plt.xlim([-0.5, 10.5])
    plt.title('Probabilidade de ser a urna u')
    plt.xticks([i for i in range(11)]);
    
def l(sorteios, bolas_p):
    L = []
    for i,v in enumerate([j for j in range(11)]):
        L.append(float('{:.7f}'.format(P(v, bolas_p, sorteios))))
    return L

g(10,6)

plt.figure(figsize=(12,9))
plt.imshow([l(10, i) for i in range(11)], interpolation='nearest')
plt.colorbar()
plt.title('Probabilidade')
plt.ylabel('u')
plt.xlabel('nb')
plt.yticks([i for i in range(11)]);
plt.xticks([i for i in range(11)]);