Algoritmo de encaminhamento - Forward algorithm

O algoritmo direto , no contexto de um modelo oculto de Markov (HMM), é usado para calcular um 'estado de crença': a probabilidade de um estado em um determinado momento, dado o histórico de evidências. O processo também é conhecido como filtragem . O algoritmo de encaminhamento está intimamente relacionado, mas distinto do algoritmo de Viterbi .

Os algoritmos para frente e para trás devem ser colocados dentro do contexto de probabilidade, pois parecem simplesmente ser nomes dados a um conjunto de procedimentos matemáticos padrão dentro de alguns campos. Por exemplo, nem "algoritmo progressivo" nem "Viterbi" aparecem na enciclopédia de matemática de Cambridge. A principal observação a tirar desses algoritmos é como organizar atualizações e inferências bayesianas para serem eficientes no contexto de gráficos direcionados de variáveis ​​(ver redes soma-produto ).

Para um HMM como este:

essa probabilidade é escrita como . Aqui está o estado oculto que é abreviado como e são as observações para . Um estado de crença pode ser calculado em cada etapa de tempo, mas fazer isso não produz, em sentido estrito, a sequência de estados mais provável , mas sim o estado mais provável em cada etapa de tempo, dada a história anterior. ${\ displaystyle P (x_ {t} | y_ {1: t})}$${\ displaystyle x (t)}$${\ displaystyle x_ {t}}$${\ displaystyle y_ {1: t}}$${\ displaystyle 1}$${\ displaystyle t}$

História

O algoritmo de encaminhamento é um dos algoritmos usados ​​para resolver o problema de decodificação. Desde o desenvolvimento do reconhecimento de voz e reconhecimento de padrões e campos relacionados, como biologia computacional que usa HMMs, o algoritmo de encaminhamento ganhou popularidade.

Algoritmo

O objetivo do algoritmo direto é calcular a probabilidade conjunta , onde por conveniência de notação abreviamos como e como . A computação direta exigiria a marginalização de todas as sequências de estados possíveis , cujo número cresce exponencialmente com . Em vez disso, o algoritmo de encaminhamento aproveita as regras de independência condicional do modelo oculto de Markov (HMM) para realizar o cálculo recursivamente. ${\ displaystyle p (x_ {t}, y_ {1: t})}$${\ displaystyle x (t)}$${\ displaystyle x_ {t}}$${\ displaystyle (y (1), y (2), ..., y (t))}$${\ displaystyle y_ {1: t}}$${\ displaystyle p (x_ {t}, y_ {1: t})}$${\ displaystyle \ {x_ {1: t-1} \}}$${\ displaystyle t}$

Para demonstrar a recursão, vamos

${\ displaystyle \ alpha _ {t} (x_ {t}) = p (x_ {t}, y_ {1: t}) = \ sum _ {x_ {t-1}} p (x_ {t}, x_ {t-1}, y_ {1: t})}$.

Usando a regra da cadeia para expandir , podemos escrever ${\ displaystyle p (x_ {t}, x_ {t-1}, y_ {1: t})}$

${\ displaystyle \ alpha _ {t} (x_ {t}) = \ sum _ {x_ {t-1}} p (y_ {t} | x_ {t}, x_ {t-1}, y_ {1: t-1}) p (x_ {t} | x_ {t-1}, y_ {1: t-1}) p (x_ {t-1}, y_ {1: t-1})}$.

Porque é condicionalmente independente de tudo , exceto , e é condicionalmente independente de tudo , mas , isso simplifica para ${\ displaystyle y_ {t}}$${\ displaystyle x_ {t}}$${\ displaystyle x_ {t}}$${\ displaystyle x_ {t-1}}$

${\ displaystyle \ alpha _ {t} (x_ {t}) = p (y_ {t} | x_ {t}) \ sum _ {x_ {t-1}} p (x_ {t} | x_ {t- 1}) \ alpha _ {t-1} (x_ {t-1})}$.

Assim, uma vez e são dadas por do modelo distribuições de emissão e probabilidades de transição , pode-se calcular rapidamente a partir e evitar incorrer em tempo de computação exponencial. ${\ displaystyle p (y_ {t} | x_ {t})}$${\ displaystyle p (x_ {t} | x_ {t-1})}$${\ displaystyle \ alpha _ {t} (x_ {t})}$${\ displaystyle \ alpha _ {t-1} (x_ {t-1})}$

O algoritmo direto é facilmente modificado para levar em conta as observações de variantes do modelo oculto de Markov também, como o sistema linear de salto de Markov .

Alisamento

Para levar em consideração o histórico futuro (ou seja, se alguém quiser melhorar a estimativa para tempos passados), você pode executar o algoritmo de retrocesso, que complementa o algoritmo de avanço. Isso é chamado de suavização . O algoritmo para frente / para trás calcula para . Portanto, o algoritmo completo para frente / para trás leva em consideração todas as evidências. ${\ displaystyle P (x_ {k} | y_ {1: t})}$${\ displaystyle 1 <k <t}$

Decodificação

Para atingir a sequência mais provável, o algoritmo de Viterbi é necessário. Ele calcula a sequência de estados mais provável, dado o histórico de observações, ou seja, a sequência de estados que maximiza . ${\ displaystyle P (x_ {0: t} | y_ {0: t})}$

Pseudo-código

       for ${\displaystyle t=t+1}$
           ${\displaystyle \alpha _{t}(x_{t})=p(y_{t}|x_{t})\sum _{x_{t-1}}p(x_{t}|x_{t-1})\alpha _{t-1}(x_{t-1})}$.
       until t=T

Exemplo

Este exemplo do tutorial HMM de Roger Boyle sobre a observação de possíveis estados do tempo a partir da condição observada das algas marinhas. Temos observações de algas marinhas por três dias consecutivos como secas, úmidas e encharcadas em ordem. Os possíveis estados de tempo podem ser ensolarado, nublado ou chuvoso. No total, pode haver essas sequências meteorológicas. Explorar todas essas possíveis sequências de estado é computacionalmente muito caro. Para reduzir essa complexidade, o algoritmo Forward é útil, onde o truque está em usar a independência condicional das etapas da sequência para calcular as probabilidades parciais, conforme mostrado na derivação acima. Portanto, podemos calcular as probabilidades como o produto da probabilidade de observação / emissão apropriada (probabilidade de estado vista no tempo t da observação anterior) com a soma das probabilidades de atingir esse estado no tempo t, calculada usando probabilidades de transição. Isso reduz a complexidade do problema de pesquisar todo o espaço de pesquisa para apenas usar probabilidades de transição e computadas anteriormente . ${\ displaystyle 3 ^ {3} = 27}$${\ displaystyle \ alpha _ {t} (x_ {t}) = p (x_ {t}, y_ {1: t}) = p (y_ {t} | x_ {t}) \ sum _ {x_ {t -1}} p (x_ {t} | x_ {t-1}) \ alpha _ {t-1} (x_ {t-1})}$${\ displaystyle p (y_ {t} | x_ {t})}$${\ displaystyle y_ {t}}$${\ displaystyle \ alpha}$

Aplicações do algoritmo

O algoritmo direto é usado principalmente em aplicativos que precisam de nós para determinar a probabilidade de estar em um estado específico quando sabemos sobre a sequência de observações. Primeiro calculamos as probabilidades sobre os estados calculados para a observação anterior e os usamos para as observações atuais e, em seguida, estendemos para a próxima etapa usando a tabela de probabilidade de transição. A abordagem basicamente armazena em cache todas as probabilidades de estado intermediário para que sejam calculadas apenas uma vez. Isso nos ajuda a calcular um caminho de estado fixo. O processo também é chamado de decodificação posterior. O algoritmo calcula a probabilidade com muito mais eficiência do que a abordagem ingênua, que rapidamente termina em uma explosão combinatória. Juntos, eles podem fornecer a probabilidade de uma dada emissão / observação em cada posição na sequência de observações. É a partir dessas informações que uma versão do caminho de estado mais provável é calculada ("decodificação posterior"). O algoritmo pode ser aplicado onde quer que possamos treinar um modelo à medida que recebemos dados usando Baum-Welch ou qualquer algoritmo EM geral. O algoritmo Forward irá então nos informar sobre a probabilidade dos dados em relação ao que é esperado de nosso modelo. Uma das aplicações pode estar no domínio das finanças, onde pode ajudar a decidir quando comprar ou vender ativos tangíveis. Ele pode ter aplicações em todos os campos onde aplicamos modelos ocultos de Markov. Os mais populares incluem domínios de processamento de linguagem natural, como marcação de classes gramaticais e reconhecimento de fala. Recentemente, também está sendo usado no domínio da Bioinformática. O algoritmo de avanço também pode ser aplicado para realizar especulações sobre o clima. Podemos ter um HMM descrevendo o tempo e sua relação com o estado de observações por alguns dias consecutivos (alguns exemplos podem ser seco, úmido, encharcado, ensolarado, nublado, chuvoso etc.). Podemos considerar o cálculo da probabilidade de observar qualquer sequência de observações recursivamente dado o HMM. Podemos então calcular a probabilidade de atingir um estado intermediário como a soma de todos os caminhos possíveis para esse estado. Assim, as probabilidades parciais para a observação final conterão a probabilidade de alcançar esses estados percorrendo todos os caminhos possíveis.

Variantes do algoritmo

Algoritmo Hybrid Forward: Uma variante do Algoritmo Forward chamado Hybrid Forward Algorithm (HFA) pode ser usado para a construção de redes neurais de função de base radial (RBF) com nós sintonizáveis. A rede neural RBF é construída pelos algoritmos convencionais de seleção de subconjunto. A estrutura da rede é determinada pela combinação da configuração da rede progressiva e da otimização contínua do parâmetro RBF. É usado para produzir de forma eficiente e eficaz uma rede neural RBF parcimoniosa que generaliza bem. Isso é obtido por meio da determinação simultânea da estrutura da rede e da otimização de parâmetros no espaço de parâmetros contínuo. O HFA aborda o problema difícil de inteiro misto usando uma estrutura analítica integrada, levando a um desempenho de rede aprimorado e uso de memória reduzido para a construção da rede.

Algoritmo Forward para Controle Ótimo em Sistemas Híbridos: Esta variante do algoritmo Forward é motivada pela estrutura dos ambientes de manufatura que integram o controle de processos e operações. Derivamos uma nova propriedade da estrutura de trajetória de estado ótima que se mantém sob uma condição modificada na função de custo. Isso nos permite desenvolver um algoritmo escalonável de baixa complexidade para determinar explicitamente os controles ideais, que podem ser mais eficientes do que o algoritmo direto.

Algoritmo de encaminhamento contínuo: Um algoritmo de encaminhamento contínuo (CFA) pode ser usado para modelagem não linear e identificação usando redes neurais de função de base radial (RBF). O algoritmo proposto realiza as duas tarefas de construção de rede e otimização de parâmetros em uma estrutura analítica integrada e oferece duas vantagens importantes. Primeiro, o desempenho do modelo pode ser significativamente melhorado por meio da otimização contínua de parâmetros. Em segundo lugar, a representação neural pode ser construída sem gerar e armazenar todos os regressores candidatos, levando a uma redução significativa do uso de memória e da complexidade computacional.

Complexidade

Complexity of Forward Algorithm é , onde é o número de variáveis ​​ocultas ou latentes, como o clima no exemplo acima, e é o comprimento da sequência da variável observada. Esta é uma redução clara do método ad hoc de explorar todos os estados possíveis com uma complexidade de . ${\ displaystyle \ Theta (nm ^ {2})}$${\ displaystyle m}$${\ displaystyle n}$${\ displaystyle \ Theta (nm ^ {n})}$

Veja também

• Algoritmo de Viterbi
• Algoritmo para frente e para trás

Leitura adicional

• Artificial Intelligence, a Modern Approach , de Russell e Norvig , que começa na página 570 da edição de 2010, fornece uma exposição sucinta deste e de tópicos relacionados
• Smyth, Padhraic, David Heckerman e Michael I. Jordan. "Redes de independência probabilística para modelos de probabilidade de Markov ocultos." Neural computation 9.2 (1997): 227-269. [1]
• Leia, Jonathon. "Modelos ocultos de Markov e programação dinâmica." Universidade de Oslo (2011). [2]
• Kohlschein, Christian, Uma introdução aos modelos ocultos de Markov [3]
• Manganiello, Fabio, Mirco Marchetti e Michele Colajanni. Detecção de ataque em várias etapas e correlação de alerta em sistemas de detecção de intrusão. Segurança e garantia da informação. Springer Berlin Heidelberg, 2011. 101-110. [4]

Referências

• Stratonovich, RL "Processos de markov condicionais". Teoria da Probabilidade e suas Aplicações 5, no. 2 (1960): 156178.
• Lawrence R. Rabiner, BH Juang (janeiro de 1986). "Uma introdução aos modelos ocultos de Markov". Revista IEEE ASSP : 4–15.

• Roger Boyle, A Tutorial on Hidden Markov Models. 24 de abril de 2016. [5]
• Zhang, Ping e Christos G. Cassandras. "Um algoritmo avançado aprimorado para o controle ideal de uma classe de sistemas híbridos." Automatic Control, IEEE Transactions on 47.10 (2002): 1735-1739.

links externos

Programas

• O pacote R oculto de Markov contém funcionalidades para calcular e recuperar o procedimento de encaminhamento
• Biblioteca GHMM para Python
• A biblioteca Haskell do pacote hmm para HMMS implementa o algoritmo Forward.
• Biblioteca para Java contém implementações de algoritmos de Aprendizado de Máquina e Inteligência Artificial.