¿Qué algoritmo de clasificación estadística puede predecir verdadero / falso para una secuencia de entradas?

14

Dada una secuencia de entradas, necesito determinar si esta secuencia tiene cierta propiedad deseada. La propiedad solo puede ser verdadera o falsa, es decir, solo hay dos clases posibles a las que puede pertenecer una secuencia.

La relación exacta entre la secuencia y la propiedad no está clara, pero creo que es muy consistente y debería prestarse a una clasificación estadística. Tengo una gran cantidad de casos para entrenar al clasificador, aunque puede ser un poco ruidoso, en el sentido de que hay una ligera probabilidad de que a una secuencia se le asigne la clase incorrecta en este conjunto de entrenamiento.

Ejemplo de datos de entrenamiento:

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 términos generales, la propiedad está determinada por el conjunto de valores en la secuencia (por ejemplo, la presencia de un "11" significa que la propiedad seguramente será falsa), así como el orden de los valores (por ejemplo, "21 7 5 "aumenta significativamente la posibilidad de que la propiedad sea verdadera).

Después del entrenamiento, debería poder darle al clasificador una secuencia que no se había visto anteriormente, como (1 21 7 5 3), y debería generar su confianza de que la propiedad es verdadera. ¿Existe un algoritmo bien conocido para entrenar a un clasificador con este tipo de entradas / salidas?

He considerado el ingenuo clasificador bayesiano (que no es realmente adaptable al hecho de que el orden importa, al menos no sin romper severamente la suposición de que las entradas son independientes). También he investigado el enfoque oculto del modelo de Markov, que parece ser inaplicable porque solo hay una salida disponible, en lugar de una salida por entrada. ¿Qué me perdí?

machine-learning classification modeling Roman Starkov
fuente

¿Tienes forma de medir la distancia entre un par de secuencias? ¿Se conoce la longitud de secuencia mínima y / o máxima?

Craig Wright, el

@CraigWright No hay una medida de distancia aplicable que se me ocurra. Se puede suponer una longitud máxima del orden de 12 y un mínimo de alrededor de 4. Además, hay alrededor de 30 valores distintos (no son naturales ilimitados; solo un conjunto bastante pequeño de posibilidades)

Roman Starkov

¿Cuáles son tus variables de respuesta múltiple que mencionas? Estaba leyendo su problema, ya que esta es una salida binaria y tal vez podría simplemente crear variables ficticias Var1.1, Var1.12, ..., Var12.12

B_Miner

@B_Miner Podría estar malinterpretando cómo funciona HMM, pero parece que funciona de la siguiente manera: le doy mi secuencia de entrada (abcde) y genera una secuencia oculta que coincide mejor, a saber (a 'b' c 'd' e ' ) No creo que las variables ficticias resuelvan esto; Necesito una clasificación de verdadero / falso para toda la secuencia.

Roman Starkov

@romkyns, no es así como funciona un HMM. Un HMM es un proceso probabilístico. Dada una secuencia

un

HMM , puede calcular la probabilidad de que

produzca

(usando programación dinámica; el algoritmo directo). Además, dado un conjunto de secuencias de entrenamiento, puede encontrar el HMM

que tiene la máxima probabilidad de producir esas secuencias de entrenamiento (utilizando el algoritmo Baum-Welch). Entonces, los HMM podrían ser algo para probar aquí. Sin embargo, habrá algunos detalles que completar.

s

$s$

M

$M$

M

$M$

s

$s$

M

$M$

DW

9

Podría probar enfoques probabilísticos similares al ingenuo clasificador de Bayes pero con suposiciones más débiles. Por ejemplo, en lugar de hacer una fuerte suposición de independencia, haga una suposición 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)$

es la etiqueta de tu clase, es tu secuencia. Necesita estimar dos distribuciones condicionales, una para y otra para . $c$ $x$ $c = 1$ $c = 0$

Por la regla 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)}.$

Qué distribuciones elegir para depende de qué otras suposiciones puede hacer sobre las secuencias y cuántos datos tiene disponibles. $p(x_t \mid x_{t - 1}, c)$

Por ejemplo, podría 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)}$

Con distribuciones como esta, si hay 21 números diferentes en sus secuencias, tendría que estimar parámetros más parámetros para más 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)$

Si no se cumplen los supuestos de su modelo, puede ayudar a ajustar los parámetros directamente con respecto al rendimiento de clasificación, por ejemplo, minimizando la pérdida de registro promedio

- \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 de descenso.

Lucas
fuente

(+1) Me gusta este. Sin embargo, uno podría necesitar cantidades terribles de datos para obtener estimaciones confiables para todos los

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

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

steffen

Si puede hacer más suposiciones sobre las distribuciones involucradas, puede salirse con muchos menos parámetros. Si, por ejemplo, supiera que

era binomial y

, tendría que estimar solo dos parámetros, uno por cada valor de

. Por supuesto, si no puede hacer suposiciones y no tiene suficientes datos, no hay mucho que pueda hacer. No hay almuerzo gratis.

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

Sugeriría que defina algunas características y luego elija un algoritmo de aprendizaje automático para aplicarlas.

Características: Básicamente, cada característica debe ser algo que se pueda calcular a partir de una secuencia particular, y que usted piense que puede ser relevante para saber si la secuencia tiene la propiedad o no. Según su descripción, puede considerar características como las siguientes:

$i$ $i$ (7 5 21 3 3)
(7 5 21 3 3)7 55 2121 33 3 $30^2$ $30^2$
"Bolsa de trigramas". También podría considerar trigramas, que es una subsecuencia de tres números consecutivos de la secuencia original. Puedes hacer lo mismo que arriba.

$d=30+30^2+30^3$ $d$ -dimensional vector de características, que es la colección de características. Una vez que tenga esto, puede tirar las secuencias originales. Por ejemplo, su conjunto de entrenamiento se convierte en un grupo de pares de entrada / salida, donde la entrada es el vector de características (correspondiente a alguna secuencia de su conjunto de entrenamiento) y la salida es un booleano (que indica si esa secuencia tenía la propiedad o no) .

Otra variación de la idea anterior es usar "conjunto de X" en lugar de "bolsa de X". Por ejemplo, en lugar de contar cuántas veces cada número $i$ aparece, simplemente podría generar un booleano que indica si el número $i$ ha aparecido al menos una vez o no. Esto puede o no dar mejores resultados. En general, puede experimentar con el conjunto de características que utiliza, para descubrir cuáles dan los mejores resultados (por ejemplo, tal vez deje caer la "bolsa de trigramas"; o tal vez pueda proponer otras ideas para probar) .

Algoritmo de aprendizaje automático: no estoy calificado para darle consejos sobre cómo seleccionar un algoritmo de aprendizaje automático; Hay muchas posibilidades. Pero, en general, va a aplicar el algoritmo de aprendizaje a su conjunto de entrenamiento (los pares de características de entrada / salida / booleanos) e intentará usarlo para predecir cuáles de los valores en el conjunto de prueba tienen la propiedad. Su selección del algoritmo de aprendizaje automático puede depender de varios factores, incluida la forma en que el tamaño del conjunto de entrenamiento se compara con $d$ (la cantidad de funciones). Su mejor opción puede ser probar varios algoritmos de aprendizaje automático y ver cuál funciona mejor. Es posible que desee incluir Máquinas de vectores de soporte (SVM) como uno de los algoritmos que intente.

DW
fuente

El primer intento que realmente implementé fue una "bolsa de trigramas" con ingenua clasificación bayesiana. Los resultados son alentadores pero no excelentes. Pensé que esto podría estar relacionado con el hecho de que los trigramas no son del todo independientes: si tengo "1 2 3", entonces también es muy probable que tenga un trigrama "2 3 *". Quizás debería experimentar con las características exactas un poco más.

Roman Starkov

Experimentar más, tanto con diferentes conjuntos de características como con diferentes algoritmos de aprendizaje, es una buena idea. Además, según la descripción de su problema, es posible que desee agregar características para la apariencia de cada número individual (bolsa de palabras, no solo bolsa de trigramas): si usa solo trigramas, está dificultando que el algoritmo de aprendizaje automático aprenda hechos como "las secuencias que contienen 11 casi seguramente no tienen la propiedad".

DW

2

Lo que efectivamente está haciendo es la prueba de hipótesis en series de tiempo. Los HMM funcionarían para usted, aunque tendría que adaptarlos a su caso particular.

Honestamente, si no puede escribir algún tipo de descripción matemática de lo que está tratando de detectar, no llegará muy lejos. ¿Quizás pueda decirnos qué tipo de característica espera ver?

usuario873
fuente

1

El aprendizaje automático nos ha demostrado que podemos llegar muy lejos sin tener idea de qué buscar.

bayerj

1

Dada una longitud máxima de 12 en la secuencia, una red neuronal con 12 entradas y una salida puede funcionar, pero tendría que rellenar el final de cada secuencia con ceros o algún valor inerte.

Craig Wright
fuente

1

¿Has intentado usar redes bayesianas? Eso es lo primero en lo que pienso cuando necesito fusionar múltiples datos (que vienen de uno en uno) para llegar a las probabilidades de una variable aleatoria.

Las redes bayesianas no se basan en el supuesto de independencia que los ingenuos Bayes hacen.

Por cierto, los modelos ocultos de Markov son un caso especial de redes bayesianas.

DojoGojira
fuente

¿Qué algoritmo de clasificación estadística puede predecir verdadero / falso para una secuencia de entradas?

Respuestas: