Qual algoritmo de classificação estatística pode prever verdadeiro / falso para uma sequência de entradas?

14

Dada uma sequência de entradas, preciso determinar se essa sequência tem uma certa propriedade desejada. A propriedade só pode ser verdadeira ou falsa, ou seja, existem apenas duas classes possíveis às quais uma sequência pode pertencer.

A relação exata entre a sequência e a propriedade não é clara, mas acredito que é muito consistente e deve se prestar à classificação estatística. Eu tenho um grande número de casos para treinar o classificador, embora possa ser um pouco barulhento, no sentido de que há uma pequena probabilidade de que uma sequência seja atribuída à classe errada neste conjunto de treinamento.

Dados de treinamento de exemplo:

Sequence 1: (7 5 21 3 3) -> true
Sequence 2: (21 7 5 1) -> true
Sequence 3: (12 21 7 5 11 1) -> false
Sequence 4: (21 5 7 1) -> false
...

Em termos gerais, a propriedade é determinada pelo conjunto de valores na sequência (por exemplo, a presença de um "11" significa que a propriedade quase certamente será falsa), bem como a ordem dos valores (por exemplo "21 7 5 "aumenta significativamente a chance de a propriedade ser verdadeira).

Após o treinamento, devo ser capaz de fornecer ao classificador uma sequência nunca vista anteriormente, como (1 21 7 5 3), e deve gerar sua confiança de que a propriedade é verdadeira. Existe um algoritmo conhecido para treinar um classificador com esse tipo de entradas / saídas?

Eu considerei o classificador bayesiano ingênuo (que não é realmente adaptável ao fato de que a ordem é importante, pelo menos não sem quebrar severamente a suposição de que as entradas são independentes). Também investiguei a abordagem oculta do modelo de Markov, que parece inaplicável porque apenas uma única saída está disponível, em vez de uma saída por entrada. Do que eu senti falta?

machine-learning classification modeling Roman Starkov
fonte

Você tem como medir a distância entre um par de sequências? O comprimento mínimo e / ou máximo da sequência é conhecido?

Craig Wright

@ CraigWright Não há nenhuma medida de distância aplicável em que eu possa pensar. Pode ser assumido um comprimento máximo da ordem de 12 e um mínimo em torno de 4. Além disso, existem cerca de 30 valores distintos (eles são naturais não ilimitados, apenas um relativamente pequeno conjunto de possibilidades)

Roman Starkov

Quais são as suas variáveis de resposta múltipla que você mencionou? Eu estava lendo o seu problema, pois esta é uma saída binária e talvez você possa simplesmente criar variáveis fictícias Var1.1, Var1.12, ..., Var12.12

B_Miner

@B_Miner Eu posso estar entendendo mal como o HMM funciona, mas parece que funciona da seguinte forma: eu alimento minha sequência de entrada (abcde) e ela gera uma sequência oculta que melhor corresponde àquela, a saber (a 'b' c 'd' e ' ) Eu não acho que as variáveis fictícias resolveriam isso; Eu preciso de uma classificação verdadeira / falsa para toda a sequência.

Roman Starkov

@romkyns, não é bem assim que um HMM funciona. Um HMM é um processo probabilístico. Dada uma sequência e um HMM , você pode calcular a probabilidade de produzir (usando programação dinâmica; o algoritmo forward). Além disso, dado um conjunto de sequências de treinamento, você pode encontrar o HMM que tem a probabilidade máxima de produzir essas sequências de treinamento (usando o algoritmo Baum-Welch). Portanto, os HMMs podem muito bem ser algo para tentar aqui. Porém, haverá alguns detalhes a serem preenchidos.

s

$s$

M

$M$

M

$M$

s

$s$

M

$M$

DW

9

Você pode tentar abordagens probabilísticas semelhantes ao classificador ingênuo de Bayes, mas com suposições mais fracas. Por exemplo, em vez de fazer uma forte suposição de independência, faça uma suposição de Markov:

p (x ∣ c) = p (x_{0} ∣ c) \prod_{t} p (x_{t} ∣ x_{t - 1}, c)

$p(x \mid c) = p(x_0 \mid c)\prod_t p(x_t \mid x_{t - 1}, c)$

$c$ é o rótulo da sua classe, é a sua sequência. Você precisa estimar duas distribuições condicionais, uma para e outra para . $x$ $c = 1$ $c = 0$

Pela regra de Bayes:

p (c = 1 ∣ x) = \frac{p (x ∣ c = 1) p (c = 1)}{p (x ∣ c = 1) p (c = 1) + p (x ∣ c = 0) p (c = 0)} .

$p(c = 1 \mid x) = \frac{p(x \mid c = 1) p(c = 1)}{p(x \mid c = 1) p(c = 1) + p(x \mid c = 0) p(c = 0)}.$

Quais distribuições escolher para dependem de quais outras suposições você pode fazer sobre as seqüências e a quantidade de dados disponíveis. $p(x_t \mid x_{t - 1}, c)$

Por exemplo, você pode usar:

p (x_{t} ∣ x_{t - 1}, c) = \frac{π (x_{t}, x_{t - 1}, c)}{\sum_{i} π (x_{i}, x_{t - 1}, c)}

$p(x_t \mid x_{t - 1}, c) = \frac{\pi(x_t, x_{t - 1}, c)}{\sum_i \pi(x_i, x_{t - 1}, c)}$

Com distribuições como essa, se houver 21 números diferentes ocorrendo em suas seqüências, você teria que estimar parâmetros mais parâmetros para mais parâmetros para . $21 \cdot 21 \cdot 2 = 882$ $\pi(x_t, x_t, c)$ $21 \cdot 2 = 42$ $p(x_0 \mid c)$ $2$ $p(c)$

Se as suposições do seu modelo não forem atendidas, pode ajudar a ajustar os parâmetros diretamente em relação ao desempenho da classificação, por exemplo, minimizando a perda média de log

- \frac{1}{# D} \sum_{(x, c) \in D} \log p (c ∣ x)

$-\frac{1}{\#\mathcal{D}} \sum_{(x, c) \in \mathcal{D}} \log p(c \mid x)$

usando gradiente-descida.

Lucas
fonte

(+1) Eu gosto deste. No entanto, um pode precisar terríveis quantidades de dados para obter estimativas confiáveis para todos

p (x_{t} | x_{t - 1}, c)

$p(x_t|x_{t-1},c)$

Steffen

Se você pode fazer mais suposições sobre as distribuições envolvidas, pode se dar bem com muito menos parâmetros. Se, por exemplo, você soubesse que era binomial e , você teria estimar apenas dois parâmetros, um para cada valor de . Obviamente, se você não pode fazer suposições e não possui dados suficientes, não há muito o que fazer. Não há almoço grátis.

p (x_{t} ∣ x_{t - 1}, c)

$p(x_t \mid x_{t - 1}, c)$

E [x_{t} ∣ x_{t - 1}, c] = x_{t - 1}

$E[x_t \mid x_{t - 1}, c] = x_{t - 1}$

c

$c$

Lucas

6

Sugiro que você defina alguns recursos e escolha um algoritmo de aprendizado de máquina para aplicar a esses recursos.

Recursos: Basicamente, cada recurso deve ser algo que possa ser calculado a partir de uma sequência específica e que você julgue relevante se a sequência tem a propriedade ou não. Com base na sua descrição, você pode considerar recursos como os seguintes:

"Bolsa de números". Você pode contar quantas vezes cada número possível aparece na sequência. Por exemplo, suponha que cada sequência seja composta apenas dos números de 1 a 30. Então você pode gerar 30 recursos; o ésimo recurso conta quantas vezes o número aparece na sequência. Por exemplo, a sequência gera o vetor de característica (0,0,2,0,1,0,1,0, ..., 0,1,0, ..., 0). $i$ $i$ (7 5 21 3 3)
"Saco de digramas." Um digram é um par de números consecutivos. Dada uma sequência, você pode extrair todos os seus digramas. Depois, você pode contar quantas vezes cada digrama possível aparece. Por exemplo, a sequência (7 5 21 3 3)tem o seguinte como seus digrams: 7 5, 5 21, 21 3, e 3 3. Supondo que a sequência seja composta dos números de 1 a 30, existem digramas possíveis, portanto, você obtém recursos. Dada uma sequência, você pode gerar esse vetor de recurso. $30^2$ $30^2$
"Saco de trigramas." Você também pode considerar trigramas, que são uma subsequência de três números consecutivos da sequência original. Você pode fazer o mesmo que acima.

Se você usar os recursos acima, poderá extrair de cada sequência. Em outras palavras, para cada sequência, você associa um vetor de recurso dimensional, que é a coleção de recursos. Depois de ter isso, você pode jogar fora as seqüências originais. Por exemplo, seu conjunto de treinamento se torna um conjunto de pares de entrada / saída, em que a entrada é o vetor de recurso (correspondente a alguma sequência do seu conjunto de treinamento) e a saída é um booleano (indicando se essa sequência tinha a propriedade ou não) . $d=30+30^2+30^3$ $d$

Outra variação da idéia acima é usar "conjunto de X" em vez de "saco de X". Por exemplo, em vez de contar quantas vezes cada número aparece, você poderia simplesmente gerar um booleano que indica se o número apareceu pelo menos uma vez ou não. Isso pode ou não dar melhores resultados. Em geral, você pode experimentar o conjunto de recursos que usa, para descobrir quais fornecem os melhores resultados (por exemplo, talvez você largue o "saco de trigramas"; ou talvez você possa ter outras idéias para tentar) . $i$ $i$

Algoritmo de aprendizado de máquina: não estou qualificado para fornecer conselhos sobre como selecionar um algoritmo de aprendizado de máquina; existem muitas possibilidades. Mas, em geral, você aplicará o algoritmo de aprendizado ao seu conjunto de treinamento (os pares de recursos / booleanos de entrada / saída) e tentará usá-lo para prever quais dos valores no conjunto de testes têm a propriedade. Sua seleção do algoritmo de aprendizado de máquina pode depender de vários fatores, incluindo como o tamanho do conjunto de treinamento se compara em relação a (o número de recursos). Sua melhor aposta pode ser tentar vários algoritmos de aprendizado de máquina e ver qual funciona melhor. Convém incluir SVMs (Support Vector Machines) como um dos algoritmos que você tenta. $d$

DW
fonte

A primeira tentativa que efetuei foi um "saco de trigramas" com classificação bayesiana ingênua. Os resultados são animadores, mas não excelentes. Eu pensei que isso poderia estar relacionado ao fato de que os trigramas não são de todo independentes: se eu tiver "1 2 3", também tenho muita probabilidade de ter um trigrama "2 3 *". Talvez eu deva experimentar um pouco mais as características exatas.

Roman Starkov

Experimentar mais, com diferentes conjuntos de recursos e com diferentes algoritmos de aprendizado, é uma boa idéia. Além disso, com base na descrição do seu problema, você pode adicionar recursos para a aparência de cada número individual (conjunto de palavras, não apenas conjunto de trigramas): se você usar apenas trigramas, estará dificultando o aprendizado do algoritmo de aprendizado de máquina fatos como "seqüências que contêm 11 quase certamente não têm a propriedade".

DW

2

O que você está efetivamente fazendo é testar hipóteses em séries temporais. Os HMMs funcionariam para você, embora você tivesse que adaptá-los ao seu caso particular.

Honestamente, se você não pode escrever algum tipo de descrição matemática do que está tentando detectar, não vai muito longe. Talvez você possa nos contar sobre que tipo de recurso você espera ver?

user873
fonte

1

O aprendizado de máquina nos mostrou que podemos ir muito longe sem ter idéia do que procurar.

precisa saber é o seguinte

1

Dado um comprimento máximo de 12 na sequência, uma rede neural com 12 entradas e uma saída pode funcionar, mas você teria que preencher o final de cada sequência com zeros ou algum valor inerte.

Craig Wright
fonte

1

Você já tentou usar redes bayesianas? Essa é a primeira coisa em que penso quando preciso mesclar vários dados (chegando um de cada vez) para chegar às probabilidades de uma variável aleatória.

As redes bayesianas não confiam na suposição de independência que Bayes ingênuo faz.

Aliás, os modelos Markov ocultos são um caso especial das redes bayesianas.

DojoGojira
fonte

Qual algoritmo de classificação estatística pode prever verdadeiro / falso para uma sequência de entradas?

Respostas: