Campo aleatório condicional - Conditional random field

Parte de uma série sobre
Aprendizado de máquina e mineração de dados
Problemas Classificação Clustering Regressão Detecção de anomalia Limpeza de Dados AutoML Regras de associação Aprendizagem por reforço Previsão estruturada Engenharia de recursos Aprendizagem de recursos Aprendizagem online Aprendizagem semissupervisionada Aprendizagem não supervisionada Aprendendo a classificar Indução gramatical
Aprendizagem supervisionada ( classificação  • regressão ) Árvores de decisão Conjuntos Ensacamento Boosting Floresta aleatória k -NN Regressão linear Baías ingénuas Redes neurais artificiais Regressão logística Perceptron Máquina de vetor de relevância (RVM) Máquina de vetores de suporte (SVM)
Clustering BÉTULA CURA Hierárquico k- significa Expectativa-maximização (EM) DBSCAN ÓPTICA Mudança média
Redução de dimensionalidade Análise Fatorial CCA ICA LDA NMF PCA PGD t-SNE
Previsão estruturada Modelos gráficos Rede Bayes Campo aleatório condicional Markov Oculto
Detecção de anomalia k -NN Fator de outlier local
Rede neural artificial Autoencoder Computação cognitiva Aprendizagem profunda DeepDream Perceptron multicamadas RNN LSTM GRU ESN Máquina de Boltzmann restrita GAN SOM Rede neural convolucional U-Net Transformador Spiking rede neural Memtransistor RAM eletroquímica (ECRAM)
Aprendizagem por reforço Q-learning SARSA Diferença temporal (TD)
Teoria Compensação de polarização-variância Teoria de aprendizagem computacional Minimização de risco empírico Aprendizagem Occam Aprendizagem PAC Aprendizagem estatística Teoria VC
Locais de aprendizado de máquina NeurIPS ICML ML JMLR ArXiv: cs.LG
Artigos relacionados Glossário de inteligência artificial Lista de conjuntos de dados para pesquisa de aprendizado de máquina Esboço do aprendizado de máquina
v t e

Os campos aleatórios condicionais ( CRFs ) são uma classe de métodos de modelagem estatística frequentemente aplicados no reconhecimento de padrões e aprendizado de máquina e usados ​​para predição estruturada . Enquanto um classificador prevê um rótulo para uma única amostra sem considerar as amostras "vizinhas", um CRF pode levar o contexto em consideração. Para fazer isso, a previsão é modelada como um modelo gráfico , que implementa dependências entre as previsões. O tipo de gráfico usado depende do aplicativo. Por exemplo, no processamento de linguagem natural , os CRFs de cadeia linear são populares, os quais implementam dependências sequenciais nas previsões. No processamento de imagem, o gráfico normalmente conecta locais a locais próximos e / ou semelhantes para garantir que eles recebam previsões semelhantes.

Outros exemplos em que os CRFs são usados ​​são: marcação ou análise de dados sequenciais para processamento de linguagem natural ou sequências biológicas , marcação de POS , análise superficial , reconhecimento de entidade nomeada , descoberta de gene , descoberta de região funcional crítica de peptídeo e reconhecimento de objeto e segmentação de imagem em visão computacional .

Descrição

Os CRFs são um tipo de modelo gráfico probabilístico não direcionado discriminativo .

Lafferty , McCallum e Pereira definem um CRF nas observações e variáveis ​​aleatórias da seguinte forma: ${\ displaystyle {\ boldsymbol {X}}}$ ${\ displaystyle {\ boldsymbol {Y}}}$

Deixe ser um gráfico tal que ${\ displaystyle G = (V, E)}$

${\ displaystyle {\ boldsymbol {Y}} = ({\ boldsymbol {Y}} _ {v}) _ {v \ in V}}$, de modo que é indexado pelos vértices de . Então é um campo aleatório condicional quando as variáveis ​​aleatórias , condicionadas em , obedecem à propriedade de Markov com relação ao gráfico:, onde significa que e são vizinhas em . ${\ displaystyle {\ boldsymbol {Y}}}$${\ displaystyle G}$${\ displaystyle ({\ boldsymbol {X}}, {\ boldsymbol {Y}})}$${\ displaystyle {\ boldsymbol {Y}} _ {v}}$${\ displaystyle {\ boldsymbol {X}}}$${\ displaystyle p ({\ boldsymbol {Y}} _ {v} | {\ boldsymbol {X}}, {\ boldsymbol {Y}} _ {w}, w \ neq v) = p ({\ boldsymbol {Y }} _ {v} | {\ boldsymbol {X}}, {\ boldsymbol {Y}} _ {w}, w \ sim v)}$${\ displaystyle {\ mathit {w}} \ sim v}$${\ displaystyle w}$${\ displaystyle v}$${\ displaystyle G}$

O que isso significa é que um CRF é um modelo gráfico não direcionado cujos nós podem ser divididos em exatamente dois conjuntos disjuntos e , as variáveis ​​observadas e de saída, respectivamente; a distribuição condicional é então modelada. ${\ displaystyle {\ boldsymbol {X}}}$${\ displaystyle {\ boldsymbol {Y}}}$${\ displaystyle p ({\ boldsymbol {Y}} | {\ boldsymbol {X}})}$

Inferência

Para gráficos gerais, o problema de inferência exata em CRFs é intratável. O problema de inferência para um CRF é basicamente o mesmo que para um MRF e os mesmos argumentos são válidos. No entanto, existem casos especiais para os quais a inferência exata é viável:

• Se o gráfico for uma cadeia ou uma árvore, os algoritmos de passagem de mensagens geram soluções exatas. Os algoritmos usados ​​nesses casos são análogos ao algoritmo forward-backward e de Viterbi para o caso de HMMs.
• Se o CRF contém apenas potenciais de pares e a energia é submodular , os algoritmos combinatórios de corte mínimo / fluxo máximo fornecem soluções exatas.

Se a inferência exata for impossível, vários algoritmos podem ser usados ​​para obter soluções aproximadas. Esses incluem:

• Propagação de crença maluca
• Expansão alfa
• Inferência de campo médio
• Relaxamentos de programação linear

Aprendizagem de Parâmetros

Aprender os parâmetros geralmente é feito por aprendizado de máxima verossimilhança para . Se todos os nós têm distribuições exponenciais de família e todos os nós são observados durante o treinamento, essa otimização é convexa. Pode ser resolvido, por exemplo, usando algoritmos de descida gradiente ou métodos Quasi-Newton , como o algoritmo L-BFGS . Por outro lado, se algumas variáveis ​​não são observadas, o problema de inferência deve ser resolvido para essas variáveis. A inferência exata é intratável em gráficos gerais, então aproximações devem ser usadas. ${\ displaystyle \ theta}$${\ displaystyle p (Y_ {i} | X_ {i}; \ theta)}$

Exemplos

Na modelagem de sequência, o gráfico de interesse geralmente é um gráfico de cadeia. Uma sequência de entrada de variáveis ​​observadas representa uma sequência de observações e representa uma variável de estado oculta (ou desconhecida) que precisa ser inferida de acordo com as observações. Eles são estruturados para formar uma cadeia, com uma borda entre cada um e . Além de ter uma interpretação simples das "etiquetas" para cada elemento na sequência de entrada, este layout admite algoritmos eficientes para: ${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle Y_ {i}}$${\ displaystyle Y_ {i-1}}$${\ displaystyle Y_ {i}}$${\ displaystyle Y_ {i}}$

• treinamento de modelo , aprendendo as distribuições condicionais entre as funções de recurso e de algum corpus de dados de treinamento.${\ displaystyle Y_ {i}}$
• decodificação , determinando a probabilidade de uma dada sequência de rótulo dada .${\ displaystyle Y}$${\ displaystyle X}$
• inferência , determinando a sequência de rótulo mais provável fornecida .${\ displaystyle Y}$${\ displaystyle X}$

A dependência condicional de cada um em é definida através de um conjunto fixo de funcionamento do recurso da forma , o que pode ser pensado como medições sobre a sequência de entrada que parcialmente determinam a probabilidade de cada valor possível para . O modelo atribui a cada recurso um peso numérico e os combina para determinar a probabilidade de um determinado valor para . ${\ displaystyle Y_ {i}}$${\ displaystyle X}$${\ displaystyle f (i, Y_ {i-1}, Y_ {i}, X)}$${\ displaystyle Y_ {i}}$${\ displaystyle Y_ {i}}$

Os CRFs de cadeia linear têm muitas das mesmas aplicações dos modelos ocultos de Markov (HMMs) conceitualmente mais simples, mas relaxam certas suposições sobre as distribuições de sequência de entrada e saída. Um HMM pode ser entendido vagamente como um CRF com funções de recursos muito específicas que usam probabilidades constantes para modelar transições de estado e emissões. Por outro lado, um CRF pode ser vagamente entendido como uma generalização de um HMM que torna as probabilidades de transição constantes em funções arbitrárias que variam entre as posições na sequência de estados ocultos, dependendo da sequência de entrada.

Notavelmente, em contraste com os HMMs, os CRFs podem conter qualquer número de funções de recurso, as funções de recurso podem inspecionar toda a sequência de entrada em qualquer ponto durante a inferência e o intervalo das funções de recurso não precisa ter uma interpretação probabilística. ${\ displaystyle X}$

Variantes

CRFs de ordem superior e CRFs semi-Markov

Os CRFs podem ser estendidos para modelos de ordem superior, tornando cada um dependente de um número fixo de variáveis ​​anteriores . Em formulações convencionais de CRFs de ordem superior, o treinamento e a inferência são práticos apenas para pequenos valores de (como k ≤ 5), uma vez que seu custo computacional aumenta exponencialmente com . ${\ displaystyle Y_ {i}}$${\ displaystyle k}$${\ displaystyle Y_ {ik}, ..., Y_ {i-1}}$${\ displaystyle k}$${\ displaystyle k}$

No entanto, outro avanço recente conseguiu amenizar esses problemas, alavancando conceitos e ferramentas do campo da não parametrização bayesiana. Especificamente, a abordagem CRF-infinito constitui um modelo do tipo CRF que é capaz de aprender dinâmicas temporais infinitamente longas de uma forma escalável. Isso é realizado pela introdução de uma nova função potencial para CRFs que é baseada no Sequence Memoizer (SM), um modelo bayesiano não paramétrico para aprender dinâmicas infinitamente longas em observações sequenciais. Para tornar tal modelo computacionalmente tratável, o CRF-infinito emprega uma aproximação de campo médio das novas funções potenciais postuladas (que são conduzidas por um SM). Isso permite o desenvolvimento de algoritmos de inferência e treinamento aproximado eficientes para o modelo, sem prejudicar sua capacidade de capturar e modelar dependências temporais de comprimento arbitrário.

Existe outra generalização dos CRFs, o campo aleatório condicional semi-Markov (semi-CRF) , que modela segmentações de comprimento variável da sequência do rótulo . Isso fornece muito do poder dos CRFs de ordem superior para modelar dependências de longo alcance do , a um custo computacional razoável. ${\ displaystyle Y}$${\ displaystyle Y_ {i}}$

Finalmente, modelos de grande margem para predição estruturada , como a Máquina de Vetores de Suporte estruturada, podem ser vistos como um procedimento de treinamento alternativo para CRFs.

Campo aleatório condicional latente-dinâmico

Campos aleatórios condicionais dinâmicos latentes ( LDCRF ) ou modelos de variáveis ​​latentes probabilísticas discriminativas ( DPLVM ) são um tipo de CRFs para tarefas de marcação de sequência. Eles são modelos de variáveis ​​latentes que são treinados discriminativamente.

Numa LDCRF, como em qualquer tarefa sequência de codificação, dada uma sequência de observações x = , o principal problema o modelo deve resolver é a forma de atribuir uma sequcia de etiquetas y = a partir de um conjunto finito de etiquetas Y . Em vez de modelar directamente P ( Y | x ) como um CRF de cadeia linear normal faria, um conjunto de variáveis latentes h é "inseridas" entre X e Y utilizando o regra cadeia de probabilidade : ${\ displaystyle x_ {1}, \ dots, x_ {n}}$${\ displaystyle y_ {1}, \ dots, y_ {n}}$

${\ displaystyle P (\ mathbf {y} | \ mathbf {x}) = \ sum _ {\ mathbf {h}} P (\ mathbf {y} | \ mathbf {h}, \ mathbf {x}) P ( \ mathbf {h} | \ mathbf {x})}$

Isso permite capturar a estrutura latente entre as observações e rótulos. Embora os LDCRFs possam ser treinados usando métodos quase-Newton, uma versão especializada do algoritmo perceptron chamada perceptron de variável latente foi desenvolvida para eles também, com base no algoritmo perceptron estruturado de Collins . Esses modelos encontram aplicações em visão computacional , especificamente reconhecimento de gestos de fluxos de vídeo e análise superficial .

Programas

Esta é uma lista parcial de softwares que implementam ferramentas CRF genéricas.

• CRFs RNNSharp baseados em redes neurais recorrentes ( C # , .NET )
• CRF-ADF CRFs de cadeia linear com treinamento ADF online rápido ( C # , .NET )
• CRFSharp CRFs de cadeia linear ( C # , .NET )
• GCO CRFs com funções de energia submodular ( C ++ , Matlab )
• DGM General CRFs ( C ++ )
• GRMM General CRFs ( Java )
• CRFs gerais da fábrica ( Scala )
• CRFall CRFs Gerais ( Matlab )
• CRFs de cadeia linear de CRF de Sarawagi ( Java )
• CRFs de estado oculto da biblioteca HCRF ( C ++ , Matlab )
• Accord.NET CRF de cadeia linear, e HCRF HMMs ( C # , .NET )
• CRFs Wapiti Fast de cadeia linear ( C )
• CRFSuite CRFs de cadeia linear restrita rápida ( C )
• CRF ++ CRFs de cadeia linear ( C ++ )
• FlexCRFs Markov CRFs de primeira e segunda ordem ( C ++ )
• crf-chain1 CRFs de cadeia linear de primeira ordem ( Haskell )
• imageCRF CRF para segmentar imagens e volumes de imagens ( C ++ )
• Cadeia linear MALLET para marcação de sequência ( Java )
• PyStruct Structured Learning in Python ( Python )
• Pycrfsuite Uma ligação python para crfsuite ( Python )
• Linguagem de programação probabilística Figaro capaz de definir CRFs e outros modelos gráficos ( Scala )
• Modelagem de CRF e ferramentas computacionais para CRFs e outros modelos gráficos não direcionados ( R )
• Biblioteca OpenGM para modelos de gráfico de fator discreto e operações distributivas nesses modelos ( C ++ )
• Biblioteca UPGMpp para construir, treinar e realizar inferência com modelos gráficos não direcionados ( C ++ )
• KEG_CRF Fast Linear CRFs ( C ++ )

Esta é uma lista parcial de softwares que implementam ferramentas relacionadas ao CRF.

• MedaCy Medical Named Entity Recognizer ( Python )
• Preditor de genes baseado em Conrad CRF ( Java )
• Stanford NER Named Entity Recognizer ( Java )
• BANNER Named Entity Recognizer ( Java )
• SparkNLP SparkNLP NerCrfApproach ( Java , Scala , Python )

Veja também

• Teorema de Hammersley-Clifford
• Modelo gráfico
• Campo aleatório de Markov
• Modelo de Markov de entropia máxima (MEMM)

Referências

Leitura adicional

• McCallum, A .: Características de indução eficiente de campos aleatórios condicionais . In: Proc. 19ª Conferência sobre Incerteza em Inteligência Artificial . (2003)
• Wallach, HM : Campos aleatórios condicionais: Uma introdução . Relatório técnico MS-CIS-04-21, Universidade da Pensilvânia (2004)
• Sutton, C., McCallum, A .: Uma introdução aos campos aleatórios condicionais para a aprendizagem relacional. Em "Introdução à Aprendizagem Relacional Estatística". Editado por Lise Getoor e Ben Taskar. MIT Press. (2006) PDF Online
• Klinger, R., Tomanek, K .: Classical Probabilistic Models and Conditional Random Fields. Relatório de Engenharia de Algoritmo TR07-2-013, Departamento de Ciência da Computação, Universidade de Tecnologia de Dortmund, dezembro de 2007. ISSN 1864-4503. PDF online