Quel algorithme de classification statistique peut prédire vrai / faux pour une séquence d'entrées?

15

Étant donné une séquence d'entrées, je dois déterminer si cette séquence a une certaine propriété souhaitée. La propriété ne peut être vraie ou fausse, c'est-à-dire qu'il n'y a que deux classes possibles auxquelles une séquence peut appartenir.

La relation exacte entre la séquence et la propriété n'est pas claire, mais je pense qu'elle est très cohérente et devrait se prêter à une classification statistique. J'ai un grand nombre de cas sur lesquels former le classificateur, bien que cela puisse être légèrement bruyant, dans le sens où il y a une légère probabilité qu'une séquence soit affectée à la mauvaise classe dans cet ensemble de formation.

Exemples de données d'entraînement:

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
...

En gros, la propriété est déterminée par l'ensemble des valeurs de la séquence (par exemple, la présence d'un "11" signifie que la propriété sera presque certainement fausse), ainsi que par l' ordre des valeurs (par exemple "21 7 5 "augmente considérablement les chances que la propriété soit vraie).

Après l'entraînement, je devrais être en mesure de donner au classificateur une séquence précédemment invisible, comme (1 21 7 5 3), et il devrait produire sa confiance que la propriété est vraie. Existe-t-il un algorithme bien connu pour former un classificateur avec ce type d'entrées / sorties?

J'ai considéré le classificateur bayésien naïf (qui n'est pas vraiment adaptable au fait que l'ordre compte, du moins pas sans briser gravement l'hypothèse que les entrées sont indépendantes). J'ai également étudié l'approche du modèle de Markov caché, qui semble être inapplicable car une seule sortie est disponible, au lieu d'une sortie par entrée. Qu'est-ce que j'ai raté?

machine-learning classification modeling Roman Starkov
la source

Avez-vous un moyen de mesurer la distance entre une paire de séquences? La longueur de séquence min et / ou max est-elle connue?

Craig Wright

@CraigWright Il n'y a aucune mesure de distance applicable à laquelle je puisse penser. On peut supposer une longueur maximale de l'ordre de 12 et un minimum d'environ 4. En outre, il existe environ 30 valeurs distinctes (ce ne sont pas des valeurs naturelles illimitées; juste un ensemble assez restreint de possibilités)

Roman Starkov,

Quelles sont vos variables de réponse multiples que vous mentionnez? Je lisais votre problème car il s'agit d'une sortie binaire et peut-être pourriez-vous simplement créer des variables factices Var1.1, Var1.12, ..., Var12.12

B_Miner

@B_Miner Je peux mal comprendre le fonctionnement de HMM, mais il semble que cela fonctionne comme suit: je lui donne ma séquence d'entrée (abcde) et il produit une séquence cachée qui correspond le mieux à cela, à savoir (a 'b' c 'd' e ' ). Je ne pense pas que les variables muettes résoudraient cela; J'ai besoin d'une classification vrai / faux pour toute la séquence.

Roman Starkov

@romkyns, ce n'est pas tout à fait le fonctionnement d'un HMM. Un HMM est un processus probabiliste. Étant donné une séquence

et un HMM

, vous pouvez calculer la probabilité que

produise

(en utilisant la programmation dynamique; l'algorithme direct). En outre, étant donné un ensemble de séquences d'apprentissage, vous pouvez trouver le HMM

qui a la probabilité maximale de produire ces séquences d'apprentissage (en utilisant l'algorithme Baum-Welch). Les HMM pourraient donc être quelque chose à essayer ici. Il y aura cependant quelques détails à remplir.

s

$s$

M

$M$

M

$M$

s

$s$

M

$M$

DW

10

Vous pouvez essayer des approches probabilistes similaires au classificateur naïf de Bayes mais avec des hypothèses plus faibles. Par exemple, au lieu de faire l'hypothèse d'indépendance forte, faites une hypothèse 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)$

est votre étiquette de classe, est votre séquence. Vous devez estimer deux distributions conditionnelles, une pour et une pour . $c$ $x$ $c = 1$ $c = 0$

Selon la règle 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)}.$

Les distributions à choisir pour dépendent des autres hypothèses que vous pouvez faire sur les séquences et de la quantité de données dont vous disposez. $p(x_t \mid x_{t - 1}, c)$

Par exemple, vous pouvez utiliser:

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)}$

Avec des distributions comme celle-ci, s'il y a 21 nombres différents dans vos séquences, vous devez estimer paramètres plus paramètres pour plus paramètres pour . $21 \cdot 21 \cdot 2 = 882$ $\pi(x_t, x_t, c)$ $21 \cdot 2 = 42$ $p(x_0 \mid c)$ $2$ $p(c)$

Si les hypothèses de votre modèle ne sont pas remplies, cela peut aider à affiner les paramètres directement par rapport aux performances de classification, par exemple en minimisant la perte de log moyenne

- \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)$

en utilisant la descente de gradient.

Lucas
la source

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

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

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

Je vous suggère de définir certaines fonctionnalités, puis de choisir un algorithme d'apprentissage automatique à appliquer à ces fonctionnalités.

Fonctionnalités: Fondamentalement, chaque fonctionnalité doit être quelque chose qui peut être calculée à partir d'une séquence particulière et qui, selon vous, peut être pertinente pour déterminer si la séquence a la propriété ou non. En fonction de votre description, vous pourriez envisager des fonctionnalités telles que les suivantes:

$i$ $i$ (7 5 21 3 3)
(7 5 21 3 3)7 55 2121 33 3 $30^2$ $30^2$
"Sac de trigrammes." Vous pouvez également envisager des trigrammes, qui sont une sous-séquence de trois nombres consécutifs de la séquence d'origine. Vous pouvez faire la même chose que ci-dessus.

$d=30+30^2+30^3$ $d$

$i$ $i$

$d$

DW
la source

La première tentative que j'ai réellement implémentée a été un "sac de trigrammes" avec une classification bayésienne naïve. Les résultats sont encourageants mais pas excellents. Je pensais que cela pourrait être lié au fait que les trigrammes ne sont pas du tout indépendants: si j'ai "1 2 3", je suis aussi très susceptible d'avoir un trigramme "2 3 *". Peut-être devrais-je essayer davantage les caractéristiques exactes.

Roman Starkov,

Expérimenter davantage, à la fois avec différents ensembles de fonctionnalités et avec différents algorithmes d'apprentissage, est une bonne idée. En outre, en fonction de la description de votre problème, vous souhaiterez peut-être ajouter des fonctionnalités pour l'apparence de chaque numéro individuel (sac de mots, pas seulement sac de trigrammes): si vous utilisez uniquement des trigrammes, vous compliquez l'apprentissage de l'algorithme d'apprentissage automatique des faits comme "les séquences qui contiennent 11 n'ont presque certainement pas la propriété".

DW

2

Ce que vous faites effectivement, c'est des tests d'hypothèses sur des séries chronologiques. Les HMM fonctionneraient pour vous, bien que vous deviez les adapter à votre cas particulier.

Honnêtement, si vous ne pouvez pas écrire une sorte de description mathématique de ce que vous essayez de détecter, vous n'irez pas très loin. Peut-être pouvez-vous nous dire quel type de fonctionnalité vous attendez?

user873
la source

1

L'apprentissage automatique nous a montré que nous pouvons aller très loin sans avoir la moindre idée de ce qu'il faut rechercher.

bayerj

1

Étant donné une longueur maximale de 12 sur la séquence, un réseau de neurones avec 12 entrées et une sortie peut fonctionner, mais vous devrez remplir la fin de chaque séquence avec des zéros ou une valeur inerte.

Craig Wright
la source

1

Avez-vous essayé d'utiliser des réseaux bayésiens? C'est la première chose à laquelle je pense lorsque j'ai besoin de fusionner plusieurs éléments de données (entrant un à la fois) pour arriver aux probabilités d'une variable aléatoire.

Les réseaux bayésiens ne reposent pas sur l'hypothèse d'indépendance que les Bayes naïfs font.

BTW, les modèles de Markov cachés sont un cas particulier des réseaux bayésiens.

DojoGojira
la source

Quel algorithme de classification statistique peut prédire vrai / faux pour une séquence d'entrées?

Réponses: