Aprendizaje de múltiples instancias

En el aprendizaje automático , el aprendizaje de múltiples instancias (MIL) es un tipo de aprendizaje supervisado . En lugar de recibir un conjunto de instancias etiquetadas individualmente , el alumno recibe un conjunto de bolsas etiquetadas , cada una de las cuales contiene muchas instancias. En el caso simple de la clasificación binaria de múltiples instancias , una bolsa puede etiquetarse como negativa si todas las instancias que contiene son negativas. Por otro lado, una bolsa se etiqueta como positiva si hay al menos una instancia en ella que es positiva. A partir de una colección de bolsas etiquetadas, el alumno intenta (i) inducir un concepto que etiquetará las instancias individuales correctamente o (ii) aprender a etiquetar bolsas sin inducir el concepto.

Babenko (2008) ^[1] ofrece un ejemplo sencillo de MIL. Imaginemos que varias personas tienen un llavero que contiene varias llaves. Algunas de estas personas pueden entrar en una habitación determinada y otras no. La tarea consiste entonces en predecir si una determinada llave o un determinado llavero puede permitirnos entrar en esa habitación. Para resolver este problema, necesitamos encontrar la llave exacta que sea común a todos los llaveros "positivos". Si podemos identificar correctamente esta llave, también podemos clasificar correctamente un llavero completo: positivo si contiene la llave requerida o negativo si no la contiene.

Aprendizaje automático

Según el tipo y la variación de los datos de entrenamiento, el aprendizaje automático se puede clasificar en tres marcos: aprendizaje supervisado, aprendizaje no supervisado y aprendizaje de refuerzo. El aprendizaje de instancias múltiples (MIL) se incluye en el marco del aprendizaje supervisado, donde cada instancia de entrenamiento tiene una etiqueta, ya sea discreta o con valor real. MIL se ocupa de los problemas con el conocimiento incompleto de las etiquetas en los conjuntos de entrenamiento. Más precisamente, en el aprendizaje de instancias múltiples, el conjunto de entrenamiento consta de "bolsas" etiquetadas, cada una de las cuales es una colección de instancias sin etiquetar. Una bolsa está etiquetada positivamente si al menos una instancia en ella es positiva, y está etiquetada negativamente si todas las instancias en ella son negativas. El objetivo del MIL es predecir las etiquetas de bolsas nuevas, no vistas.

Historia

Keeler et al., ^[2] en su trabajo a principios de la década de 1990 fue el primero en explorar el área de MIL. El término actual de aprendizaje de múltiples instancias fue introducido a mediados de la década de 1990, por Dietterich et al. mientras investigaban el problema de la predicción de la actividad de los fármacos. ^[3] Intentaron crear un sistema de aprendizaje que pudiera predecir si una nueva molécula estaba calificada para producir algún fármaco, o no, mediante el análisis de una colección de moléculas conocidas. Las moléculas pueden tener muchos estados alternativos de baja energía, pero solo uno, o algunos de ellos, están calificados para producir un fármaco. El problema surgió porque los científicos solo podían determinar si la molécula estaba calificada, o no, pero no podían decir exactamente cuáles de sus formas de baja energía son responsables de eso.

Una de las formas propuestas para resolver este problema fue utilizar el aprendizaje supervisado y considerar todas las formas de baja energía de la molécula calificada como instancias de entrenamiento positivas, mientras que todas las formas de baja energía de las moléculas no calificadas como instancias negativas. Dietterich et al. demostraron que dicho método tendría un alto ruido de falsos positivos, debido a todas las formas de baja energía que están mal etiquetadas como positivas, y por lo tanto no era realmente útil. ^[3] Su enfoque fue considerar cada molécula como una bolsa etiquetada, y todas las formas alternativas de baja energía de esa molécula como instancias en la bolsa, sin etiquetas individuales. De este modo, se formuló el aprendizaje de múltiples instancias.

La solución al problema de aprendizaje de instancias múltiples que Dietterich et al. propusieron es el algoritmo de rectángulos paralelos a ejes (APR). ^[3] Intenta buscar rectángulos paralelos a ejes apropiados construidos por la conjunción de las características. Probaron el algoritmo en el conjunto de datos de Musk, ^{[4] [5] [ dudoso – discutir ]} que es un dato de prueba concreto de predicción de la actividad de fármacos y el punto de referencia más utilizado en el aprendizaje de instancias múltiples. El algoritmo APR logró el mejor resultado, pero APR fue diseñado teniendo en cuenta los datos de Musk.

El problema del aprendizaje de múltiples instancias no es exclusivo de la búsqueda de fármacos. En 1998, Maron y Ratan encontraron otra aplicación del aprendizaje de múltiples instancias para la clasificación de escenas en visión artificial y diseñaron el marco de trabajo Diverse Density ^[6] . Dada una imagen, una instancia se considera una o más subimágenes de tamaño fijo, y el conjunto de instancias se considera la imagen completa. Una imagen se etiqueta como positiva si contiene la escena objetivo (una cascada, por ejemplo) y negativa en caso contrario. El aprendizaje de múltiples instancias se puede utilizar para aprender las propiedades de las subimágenes que caracterizan la escena objetivo. A partir de ahí, estos marcos se han aplicado a un amplio espectro de aplicaciones, que van desde el aprendizaje de conceptos de imágenes y la categorización de textos hasta la predicción del mercado de valores.

Ejemplos

Tomemos como ejemplo la clasificación de imágenes de Amores (2013). Dada una imagen, queremos saber su clase de destino en función de su contenido visual. Por ejemplo, la clase de destino podría ser "playa", donde la imagen contiene tanto "arena" como "agua". En términos MIL , la imagen se describe como una bolsa , donde cada una es el vector de características (llamado instancia ) extraído de la región -ésima correspondiente en la imagen y es el total de regiones (instancias) que dividen la imagen. La bolsa se etiqueta como positiva ("playa") si contiene instancias de la región "arena" e instancias de la región "agua". ${\displaystyle X=\{X_{1},..,X_{N}\}}$ ${\displaystyle X_{i}}$ ${\displaystyle i}$ ${\displaystyle N}$

Algunos ejemplos de aplicaciones de MIL son:

• Actividad de la molécula
• Predicción de los sitios de unión de las proteínas de unión a la calmodulina ^[7]
• Función de predicción para isoformas empalmadas alternativamente Li, Menon y et al. (2014) , Eksi et al. (2013) harvtxt error: no target: CITEREFLiMenonet_al.2014 (help) harvtxt error: no target: CITEREFEksiLiMenonet_al.2013 (help)
• Clasificación de imágenes Maron & Ratan (1998)
• Categorización de textos o documentos Kotzias et al. (2015) harvtxt error: no target: CITEREFKotzias_et_al.2015 (help)
• Predicción de sitios de unión funcionales de dianas de microARN Bandyopadhyay, Ghosh y otros (2015) harvtxt error: no target: CITEREFBandyopadhyayGhoshet_al.2015 (help)
• Clasificación de imágenes médicas Zhu et al. (2016) , PJSudharshan et al. (2019) harvtxt error: no target: CITEREFZhu_et_al.2016 (help) harvtxt error: no target: CITEREFP.J.Sudharshan_et_al.2019 (help)

Numerosos investigadores han trabajado en la adaptación de técnicas de clasificación clásicas, como máquinas de vectores de soporte o boosting , para que funcionen en el contexto del aprendizaje de múltiples instancias.

Definiciones

Si el espacio de instancias es , entonces el conjunto de bolsas es el conjunto de funciones , que es isomorfo al conjunto de subconjuntos múltiples de . Para cada bolsa y cada instancia , se considera como el número de veces que ocurre en . ^[8] Sea el espacio de etiquetas, entonces un "concepto de instancia múltiple" es un mapa . El objetivo de MIL es aprender dicho concepto. El resto del artículo se centrará en la clasificación binaria , donde . ${\displaystyle {\mathcal {X}}}$ ${\displaystyle \mathbb {N} ^{\mathcal {X}}=\{B:{\mathcal {X}}\rightarrow \mathbb {N} \}}$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle B\in \mathbb {N} ^{\mathcal {X}}}$ ${\displaystyle x\in {\mathcal {X}}}$ ${\displaystyle B(x)}$ ${\displaystyle x}$ ${\displaystyle B}$ ${\displaystyle {\mathcal {Y}}}$ ${\displaystyle c:\mathbb {N} ^{\mathcal {X}}\rightarrow {\mathcal {Y}}}$ ${\displaystyle {\mathcal {Y}}=\{0,1\}}$

Supuestos

La mayor parte de los trabajos sobre aprendizaje de instancias múltiples, incluidos los primeros artículos de Dietterich et al. (1997) y Maron & Lozano-Pérez (1997), ^{[3] [9],} parten de la suposición sobre la relación entre las instancias dentro de una bolsa y la etiqueta de clase de la bolsa. Debido a su importancia, esa suposición a menudo se denomina suposición de MI estándar.

Supuesto estándar

La suposición estándar supone que cada instancia tiene una etiqueta asociada que está oculta para el alumno. El par se denomina "concepto a nivel de instancia". Ahora, una bolsa se considera un conjunto múltiple de conceptos a nivel de instancia y se etiqueta como positiva si al menos una de sus instancias tiene una etiqueta positiva, y negativa si todas sus instancias tienen etiquetas negativas. Formalmente, sea una bolsa. La etiqueta de es entonces . La suposición estándar de MI es asimétrica, lo que significa que si las etiquetas positiva y negativa se invierten, la suposición tiene un significado diferente. Por eso, cuando utilizamos esta suposición, debemos tener claro qué etiqueta debe ser la positiva. ${\displaystyle x\in {\mathcal {X}}}$ ${\displaystyle y\in \{0,1\}}$ ${\displaystyle (x,y)}$ ${\displaystyle B=\{(x_{1},y_{1}),\ldots ,(x_{n},y_{n})\}}$ ${\displaystyle B}$ ${\displaystyle c(B)=1-\prod _{i=1}^{n}(1-y_{i})}$

El supuesto estándar puede ser visto como demasiado estricto y, por lo tanto, en los últimos años, los investigadores intentaron relajar esa posición, lo que dio lugar a otros supuestos más laxos. ^[10] La razón de esto es la creencia de que el supuesto estándar de MI es apropiado para el conjunto de datos de Musk, pero como MIL se puede aplicar a muchos otros problemas, probablemente podrían ser más apropiados algunos supuestos diferentes. Guiado por esa idea, Weidmann ^[11] formuló una jerarquía de supuestos generalizados basados ​​en instancias para MIL. Consiste en el supuesto estándar de MI y tres tipos de supuestos generalizados de MI, cada uno más general que el último, en el sentido de que el primero se puede obtener como una elección específica de parámetros del último, estándar basado en presencia basado en umbral basado en conteo, siendo el supuesto basado en conteo el más general y el supuesto estándar el menos general. (Sin embargo, cabe señalar que cualquier bolsa que cumpla con el supuesto basado en el recuento cumple con el supuesto basado en el umbral, que a su vez cumple con el supuesto basado en la presencia, que, a su vez, cumple con el supuesto estándar. En ese sentido, también es correcto afirmar que el supuesto estándar es el más débil, por lo tanto, el más general, y el supuesto basado en el recuento es el más fuerte, por lo tanto, el menos general). Uno esperaría que un algoritmo que funciona bien bajo uno de estos supuestos funcione al menos igual de bien bajo los supuestos menos generales. ${\displaystyle \subset }$ ${\displaystyle \subset }$ ${\displaystyle \subset }$

Supuestos basados ​​en presencia, umbral y recuento

El supuesto basado en la presencia es una generalización del supuesto estándar, en el que una bolsa debe contener todas las instancias que pertenecen a un conjunto de conceptos requeridos a nivel de instancia para ser etiquetada como positiva. Formalmente, sea el conjunto de conceptos requeridos a nivel de instancia y sea denotar la cantidad de veces que el concepto a nivel de instancia aparece en la bolsa . Entonces , para todos los . Nótese que, al tomar que contiene solo un concepto a nivel de instancia, el supuesto basado en la presencia se reduce al supuesto estándar. ${\displaystyle C_{R}\subseteq {\mathcal {X}}\times {\mathcal {Y}}}$ ${\displaystyle \#(B,c_{i})}$ ${\displaystyle c_{i}}$ ${\displaystyle B}$ ${\displaystyle c(B)=1\Leftrightarrow \#(B,c_{i})\geq 1}$ ${\displaystyle c_{i}\in C_{R}}$ ${\displaystyle C_{R}}$

Una generalización adicional viene con el supuesto basado en umbrales, donde cada concepto requerido a nivel de instancia debe ocurrir no solo una vez en una bolsa, sino un número mínimo (umbral) de veces para que la bolsa sea etiquetada como positiva. Con la notación anterior, a cada concepto requerido a nivel de instancia se le asocia un umbral . Para una bolsa , para todos los . ${\displaystyle c_{i}\in C_{R}}$ ${\displaystyle l_{i}\in \mathbb {N} }$ ${\displaystyle B}$ ${\displaystyle c(B)=1\Leftrightarrow \#(B,c_{i})\geq l_{i}}$ ${\displaystyle c_{i}\in C_{R}}$

La suposición basada en el recuento es una generalización final que impone límites inferiores y superiores para la cantidad de veces que un concepto requerido puede aparecer en una bolsa etiquetada positivamente. Cada concepto requerido a nivel de instancia tiene un umbral inferior y un umbral superior con . Una bolsa se etiqueta según para todos los . ${\displaystyle c_{i}\in C_{R}}$ ${\displaystyle l_{i}\in \mathbb {N} }$ ${\displaystyle u_{i}\in \mathbb {N} }$ ${\displaystyle l_{i}\leq u_{i}}$ ${\displaystyle B}$ ${\displaystyle c(B)=1\Leftrightarrow l_{i}\leq \#(B,c_{i})\leq u_{i}}$ ${\displaystyle c_{i}\in C_{R}}$

Supuesto GMIL

Scott, Zhang y Brown (2005) ^[12] describen otra generalización del modelo estándar, que denominan "aprendizaje generalizado de múltiples instancias" (GMIL). El supuesto GMIL especifica un conjunto de instancias requeridas . Una bolsa se etiqueta como positiva si contiene instancias que están suficientemente cerca de al menos de las instancias requeridas . ^[12] Solo bajo esta condición, el supuesto GMIL es equivalente al supuesto basado en presencia. ^[8] Sin embargo, Scott et al. describen una generalización adicional en la que hay un conjunto de puntos de atracción y un conjunto de puntos de repulsión . Una bolsa se etiqueta como positiva si y solo si contiene instancias que están suficientemente cerca de al menos de los puntos de atracción y están suficientemente cerca de la mayoría de los puntos de repulsión. ^[12] Esta condición es estrictamente más general que la basada en presencia, aunque no cae dentro de la jerarquía anterior. ${\displaystyle Q\subseteq {\mathcal {X}}}$ ${\displaystyle X}$ ${\displaystyle r}$ ${\displaystyle Q}$ ${\displaystyle Q\subseteq {\mathcal {X}}}$ ${\displaystyle {\overline {Q}}\subseteq {\mathcal {X}}}$ ${\displaystyle r}$ ${\displaystyle s}$

Suposición colectiva

A diferencia de los supuestos anteriores, en los que las bolsas se consideraban fijas, el supuesto colectivo considera que una bolsa es una distribución entre instancias y, de manera similar, considera que las etiquetas son una distribución entre instancias. El objetivo de un algoritmo que opera bajo el supuesto colectivo es, entonces, modelar la distribución . ${\displaystyle B}$ ${\displaystyle p(x|B)}$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle p(y|x)}$ ${\displaystyle p(y|B)=\int _{\mathcal {X}}p(y|x)p(x|B)dx}$

Dado que normalmente se considera fijo pero desconocido, los algoritmos se centran en calcular la versión empírica: , donde es el número de instancias en bag . Dado que también se suele considerar fijo pero desconocido, la mayoría de los métodos basados ​​en suposiciones colectivas se centran en aprender esta distribución, como en la versión de instancia única. ^{[8] [10]} ${\displaystyle p(x|B)}$ ${\displaystyle {\widehat {p}}(y|B)={\frac {1}{n_{B}}}\sum _{i=1}^{n_{B}}p(y|x_{i})}$ ${\displaystyle n_{B}}$ ${\displaystyle B}$ ${\displaystyle p(y|x)}$

Mientras que el supuesto colectivo pondera cada instancia con la misma importancia, Foulds extendió el supuesto colectivo para incorporar ponderaciones de instancias. El supuesto colectivo ponderado es entonces que , donde es una función de ponderación sobre instancias y . ^[8] ${\displaystyle {\widehat {p}}(y|B)={\frac {1}{w_{B}}}\sum _{i=1}^{n_{B}}w(x_{i})p(y|x_{i})}$ ${\displaystyle w:{\mathcal {X}}\rightarrow \mathbb {R} ^{+}}$ ${\displaystyle w_{B}=\sum _{x\in B}w(x)}$

Algoritmos

Marco MIL

Existen dos tipos principales de algoritmos para el aprendizaje de múltiples instancias: algoritmos basados ​​en instancias y algoritmos basados ​​en metadatos o algoritmos basados ​​en incrustaciones. El término "basado en instancias" denota que el algoritmo intenta encontrar un conjunto de instancias representativas basándose en una suposición de MI y clasificar las futuras bolsas a partir de estos representantes. Por el contrario, los algoritmos basados ​​en metadatos no hacen suposiciones sobre la relación entre las instancias y las etiquetas de las bolsas, y en su lugar intentan extraer información independiente de las instancias (o metadatos) sobre las bolsas para aprender el concepto. ^[10] Para un estudio de algunos de los algoritmos de MI modernos, consulte Foulds y Frank. ^[8]

Algoritmos basados ​​en instancias

Los primeros algoritmos MI propuestos fueron un conjunto de algoritmos de "discriminación iterada" desarrollados por Dietterich et al., y Diverse Density desarrollado por Maron y Lozano-Pérez. ^{[3] [9]} Ambos algoritmos operaron bajo el supuesto estándar.

Discriminación iterada

En términos generales, todos los algoritmos de discriminación iterada constan de dos fases. La primera fase consiste en hacer crecer un rectángulo paralelo a los ejes (APR) que contenga al menos una instancia de cada bolsa positiva y ninguna instancia de ninguna bolsa negativa. Esto se hace de forma iterativa: a partir de una instancia aleatoria en una bolsa positiva, el APR se expande hasta el APR más pequeño que cubra cualquier instancia en una nueva bolsa positiva . Este proceso se repite hasta que el APR cubra al menos una instancia de cada bolsa positiva. Luego, a cada instancia contenida en el APR se le asigna una "relevancia", que corresponde a la cantidad de puntos negativos que excluye del APR si se elimina. Luego, el algoritmo selecciona instancias representativas candidatas en orden de relevancia decreciente, hasta que ninguna instancia contenida en una bolsa negativa también esté contenida en el APR. El algoritmo repite estos pasos de crecimiento y selección de representantes hasta la convergencia, donde el tamaño del APR en cada iteración se considera solo a lo largo de los representantes candidatos. ${\displaystyle x_{1}\in B_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle B_{2}}$ ${\displaystyle x_{i}}$

Después de la primera fase, se piensa que la APR contiene estrictamente solo los atributos representativos. La segunda fase expande esta APR estricta de la siguiente manera: se centra una distribución gaussiana en cada atributo y se dibuja una APR más flexible de modo que los casos positivos queden fuera de la APR estricta con una probabilidad fija. ^[4] Aunque las técnicas de discriminación iterada funcionan bien con el supuesto estándar, no se generalizan bien a otros supuestos de MI. ^[8]

Densidad diversa

En su forma más simple, la densidad diversa (DD) supone una única instancia representativa como concepto. Esta instancia representativa debe ser "densa" en el sentido de que está mucho más cerca de las instancias de los grupos positivos que de los grupos negativos, así como "diversa" en el sentido de que está cerca de al menos una instancia de cada grupo positivo. ${\displaystyle t^{*}}$

Sea el conjunto de bolsas etiquetadas positivamente y sea el conjunto de bolsas etiquetadas negativamente, entonces el mejor candidato para la instancia representativa está dado por , donde la densidad diversa bajo el supuesto de que las bolsas se distribuyen independientemente dado el concepto . Si denotamos la instancia j de la bolsa i, el modelo ruidoso-or da: ${\displaystyle {\mathcal {B}}^{+}=\{B_{i}^{+}\}_{1}^{m}}$ ${\displaystyle {\mathcal {B}}^{-}=\{B_{i}^{-}\}_{1}^{n}}$ ${\displaystyle {\hat {t}}=\arg \max _{t}DD(t)}$ ${\displaystyle DD(t)=Pr\left(t|{\mathcal {B}}^{+},{\mathcal {B}}^{-}\right)=\arg \max _{t}\prod _{i=1}^{m}Pr\left(t|B_{i}^{+}\right)\prod _{i=1}^{n}Pr\left(t|B_{i}^{-}\right)}$ ${\displaystyle t^{*}}$ ${\displaystyle B_{ij}}$

${\displaystyle Pr(t|B_{i}^{+})=1-\prod _{j}\left(1-Pr\left(t|B_{ij}^{+}\right)\right)}$

${\displaystyle Pr(t|B_{i}^{-})=\prod _{j}\left(1-Pr\left(t|B_{ij}^{-}\right)\right)}$

${\displaystyle P(t|B_{ij})}$se toma como la distancia escalada donde es el vector de escala. De esta manera, si cada bolsa positiva tiene una instancia cercana a , entonces será alta para cada , pero si cualquier bolsa negativa tiene una instancia cercana a , será baja. Por lo tanto, es alta solo si cada bolsa positiva tiene una instancia cercana a y ninguna bolsa negativa tiene una instancia cercana a . El concepto candidato se puede obtener a través de métodos de gradiente. La clasificación de nuevas bolsas se puede realizar evaluando la proximidad a . ^[9] Aunque la densidad diversa fue propuesta originalmente por Maron et al. en 1998, los algoritmos MIL más recientes utilizan el marco DD, como EM-DD en 2001 ^[13] y DD-SVM en 2004, ^[14] y MILES en 2006 ^[8] ${\displaystyle P(t|B_{ij})\propto \exp \left(-\sum _{k}s_{k}^{2}\left(x_{k}-(B_{ij})_{k}\right)^{2}\right)}$ ${\displaystyle s=(s_{k})}$ ${\displaystyle t}$ ${\displaystyle Pr(t|B_{i}^{+})}$ ${\displaystyle i}$ ${\displaystyle B_{i}^{-}}$ ${\displaystyle t}$ ${\displaystyle Pr(t|B_{i}^{-})}$ ${\displaystyle DD(t)}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle {\hat {t}}}$ ${\displaystyle {\hat {t}}}$

También se han adaptado varios algoritmos de instancia única a un contexto de instancias múltiples bajo el supuesto estándar, incluidos

• Máquinas de vectores de soporte ^[15]
• Redes neuronales artificiales ^[16]
• Árboles de decisión ^[17]
• Impulso ^[18]

Después del año 2000, se produjo un alejamiento del supuesto estándar y el desarrollo de algoritmos diseñados para abordar los supuestos más generales enumerados anteriormente. ^[10]

• Weidmann ^[11] propone un algoritmo de clasificación de dos niveles (TLC) para aprender conceptos bajo el supuesto basado en recuentos. El primer paso intenta aprender conceptos a nivel de instancia mediante la construcción de un árbol de decisiones a partir de cada instancia en cada bolsa del conjunto de entrenamiento. Luego, cada bolsa se asigna a un vector de características basado en los recuentos en el árbol de decisiones. En el segundo paso, se ejecuta un algoritmo de instancia única en los vectores de características para aprender el concepto.
• Scott et al. ^[12] propusieron un algoritmo, GMIL-1, para aprender conceptos bajo el supuesto GMIL en 2005. GMIL-1 enumera todos los rectángulos paralelos al eje en el espacio original de instancias y define un nuevo espacio de características de vectores booleanos. Una bolsa se asigna a un vector en este nuevo espacio de características, donde si APR cubre , y en caso contrario. Luego se puede aplicar un algoritmo de instancia única para aprender el concepto en este nuevo espacio de características. ${\displaystyle \{R_{i}\}_{i\in I}}$ ${\displaystyle B}$ ${\displaystyle \mathbf {b} =(b_{i})_{i\in I}}$ ${\displaystyle b_{i}=1}$ ${\displaystyle R_{i}}$ ${\displaystyle B}$ ${\displaystyle b_{i}=0}$

Debido a la alta dimensionalidad del nuevo espacio de características y al costo de enumerar explícitamente todos los APR del espacio de instancias original, GMIL-1 es ineficiente tanto en términos de computación como de memoria. GMIL-2 se desarrolló como un refinamiento de GMIL-1 en un esfuerzo por mejorar la eficiencia. GMIL-2 preprocesa las instancias para encontrar un conjunto de instancias representativas candidatas. Luego, GMIL-2 asigna cada bolsa a un vector booleano, como en GMIL-1, pero solo considera los APR correspondientes a subconjuntos únicos de las instancias representativas candidatas. Esto reduce significativamente los requisitos de memoria y computación. ^[8]

• Xu (2003) ^[10] propuso varios algoritmos basados ​​en regresión logística y métodos de refuerzo para aprender conceptos bajo el supuesto colectivo.

Algoritmos basados ​​en metadatos (o incrustaciones)

Al asignar cada bolsa a un vector de características de metadatos, los algoritmos basados ​​en metadatos permiten la flexibilidad de usar un algoritmo arbitrario de instancia única para realizar la tarea de clasificación real. Las bolsas futuras simplemente se asignan (incrustan) en el espacio de características de los metadatos y se etiquetan mediante el clasificador elegido. Por lo tanto, gran parte del enfoque de los algoritmos basados ​​en metadatos se centra en qué características o qué tipo de incrustación conducen a una clasificación efectiva. Tenga en cuenta que algunos de los algoritmos mencionados anteriormente, como TLC y GMIL, podrían considerarse basados ​​en metadatos.

• Un enfoque consiste en dejar que los metadatos de cada bolsa sean un conjunto de estadísticas sobre las instancias de la bolsa. El algoritmo SimpleMI adopta este enfoque, en el que los metadatos de una bolsa se toman como una estadística de resumen simple, como el promedio o el mínimo y el máximo de cada variable de instancia tomada sobre todas las instancias de la bolsa. Hay otros algoritmos que utilizan estadísticas más complejas, pero SimpleMI demostró ser sorprendentemente competitivo para varios conjuntos de datos, a pesar de su aparente falta de complejidad. ^[8]
• Otro enfoque común es considerar la geometría de las propias bolsas como metadatos. Este es el enfoque adoptado por los algoritmos MIGraph y miGraph, que representan cada bolsa como un gráfico cuyos nodos son las instancias en la bolsa. Hay un borde entre dos nodos si la distancia (hasta alguna métrica en el espacio de instancias) entre las instancias correspondientes es menor que algún umbral. La clasificación se realiza a través de un SVM con un núcleo de gráfico (MIGraph y miGraph solo difieren en su elección de núcleo). ^{[8] MILES [19]} y MInD adoptan enfoques similares . ^[20] MILES representa una bolsa por sus similitudes con las instancias en el conjunto de entrenamiento, mientras que MInD representa una bolsa por sus distancias a otras bolsas.
• Una modificación de los vecinos más cercanos (kNN) también puede considerarse un algoritmo basado en metadatos con metadatos geométricos, aunque el mapeo entre las bolsas y las características de los metadatos no es explícito. Sin embargo, es necesario especificar la métrica utilizada para calcular la distancia entre las bolsas. Wang y Zucker (2000) ^[21] sugieren las métricas de Hausdorff (máximo y mínimo, respectivamente) para las bolsas y : ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle H(A,B)=\max \left\{\max _{A}\min _{B}\|a-b\|,\max _{B}\min _{A}\|a-b\|\right\}}$

${\displaystyle h_{1}(A,B)=\min _{A}\min _{B}\|a-b\|}$

Definen dos variaciones de kNN, Bayesian-kNN y citation-kNN, como adaptaciones del tradicional problema del vecino más cercano al entorno de múltiples instancias.

Generalizaciones

Hasta ahora, este artículo ha considerado el aprendizaje de múltiples instancias exclusivamente en el contexto de clasificadores binarios. Sin embargo, las generalizaciones de los clasificadores binarios de una sola instancia pueden trasladarse al caso de múltiples instancias.

• Una de esas generalizaciones es el problema de múltiples instancias y múltiples etiquetas (MIML), en el que cada bolsa puede asociarse ahora con cualquier subconjunto del espacio de etiquetas. Formalmente, si es el espacio de características y es el espacio de etiquetas, un concepto MIML es un mapa . Zhou y Zhang (2006) ^[22] proponen una solución al problema MIML mediante una reducción a un problema de múltiples instancias o de múltiples conceptos. ${\displaystyle {\mathcal {X}}}$ ${\displaystyle {\mathcal {Y}}}$ ${\displaystyle c:\mathbb {N} ^{\mathcal {X}}\rightarrow 2^{\mathcal {Y}}}$
• Otra generalización obvia es la regresión de instancias múltiples. Aquí, cada bolsa está asociada con un único número real como en la regresión estándar. De manera muy similar a la suposición estándar, la regresión MI supone que hay una instancia en cada bolsa, llamada la "instancia principal", que determina la etiqueta para la bolsa (hasta el ruido). El objetivo ideal de la regresión MI sería encontrar un hiperplano que minimice la pérdida cuadrada de las instancias principales en cada bolsa, pero las instancias principales están ocultas. De hecho, Ray y Page (2001) ^[23] muestran que encontrar un hiperplano de mejor ajuste que se ajuste a una instancia de cada bolsa es intratable si hay menos de tres instancias por bolsa, y en su lugar desarrollan un algoritmo para la aproximación. Muchos de los algoritmos desarrollados para la clasificación MI también pueden proporcionar buenas aproximaciones al problema de regresión MI. ^[8]

Véase también

• Aprendizaje supervisado
• Clasificación de múltiples etiquetas

Referencias

1. Babenko, Boris. "Aprendizaje de instancias múltiples: algoritmos y aplicaciones". Ver artículo PubMed/NCBI Google Scholar (2008).
2. Keeler, James D., David E. Rumelhart y Wee-Kheng Leow. Segmentación integrada y reconocimiento de números impresos a mano. Microelectronics and Computer Technology Corporation, 1991.
3. Dietterich, Thomas G., Richard H. Lathrop y Tomás Lozano-Pérez. "Resolución del problema de instancias múltiples con rectángulos de ejes paralelos". Inteligencia artificial 89.1 (1997): 31-71.
4. C. Blake, E. Keogh y CJ Merz. Repositorio UCI de bases de datos de aprendizaje automático [1], Departamento de Información y Ciencias de la Computación, Universidad de California, Irvine, CA, 1998.
5. Wang, Wei-Hong; Du, Yan-ye; Li, Qu; Colmillo, Zhao-lin (2011). "Evaluación de créditos basada en programación de expresión genética y selección clonal". Ingeniería de Procedia . 15 : 3759–3763. doi : 10.1016/j.proeng.2011.08.704 .
6. O. Maron y AL Ratan. Aprendizaje de múltiples instancias para la clasificación de escenas naturales. En Actas de la 15.ª Conferencia Internacional sobre Aprendizaje Automático, Madison, WI, págs. 341-349, 1998.
7. Minhas, F. u. A. A; Ben-Hur, A (2012). "Aprendizaje de múltiples instancias de sitios de unión de calmodulina". Bioinformática . 28 (18): i416–i422. doi :10.1093/bioinformatics/bts416. PMC 3436843 . PMID  22962461. 
8. Foulds, James y Eibe Frank. "Una revisión de los supuestos de aprendizaje de múltiples instancias". The Knowledge Engineering Review 25.01 (2010): 1-25.
9. Maron, Oded y Tomás Lozano-Pérez. "Un marco para el aprendizaje de múltiples instancias". Avances en sistemas de procesamiento de información neuronal (1998): 570-576
10. Xu, X. Aprendizaje estadístico en problemas de instancias múltiples. Tesis de maestría, Universidad de Waikato (2003).
11. Weidmann, Nils B. "Clasificación de dos niveles para datos generalizados de instancias múltiples". Disentimiento. Universidad Albert-Ludwigs, 2003.
12. Scott, Stephen, Jun Zhang y Joshua Brown. "Sobre el aprendizaje generalizado de múltiples instancias". Revista internacional de inteligencia computacional y aplicaciones 5.01 (2005): 21-35.
13. Zhang, Qi y Sally A. Goldman . "EM-DD: una técnica de aprendizaje de múltiples instancias mejorada". Avances en sistemas de procesamiento de información neuronal. (2001): 1073-80
14. Chen, Yixin y James Z. Wang. "Categorización de imágenes mediante aprendizaje y razonamiento con regiones". The Journal of Machine Learning Research 5 (2004): 913-939
15. Andrews, Stuart, Ioannis Tsochantaridis y Thomas Hofmann. "Máquinas de vectores de soporte para el aprendizaje de múltiples instancias". Avances en sistemas de procesamiento de información neuronal (2003). pp. 561-658
16. Zhou, Zhi-Hua y Min-Ling Zhang. "Redes neuronales para el aprendizaje en múltiples instancias". Actas de la Conferencia Internacional sobre Tecnología de la Información Inteligente, Beijing, China. (2002). pp 455 - 459
17. Blockeel, Hendrik, David Page y Ashwin Srinivasan. "Aprendizaje de árboles de múltiples instancias". Actas de la 22.ª conferencia internacional sobre aprendizaje automático. ACM, 2005. pp. 57-64
18. Auer, Peter y Ronald Ortner. "Un enfoque de impulso al aprendizaje de instancias múltiples". Aprendizaje automático: ECML 2004. Springer Berlin Heidelberg, 2004. 63-74.
19. Chen, Yixin; Bi, Jinbo; Wang, JZ (1 de diciembre de 2006). "MILES: aprendizaje de múltiples instancias mediante selección de instancias integradas". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 28 (12): 1931–1947. doi :10.1109/TPAMI.2006.248. ISSN  0162-8828. PMID  17108368. S2CID  18137821.
20. Cheplygina, Veronika; Tax, David MJ; Loog, Marco (1 de enero de 2015). "Aprendizaje de instancias múltiples con diferencias de bolsa". Reconocimiento de patrones . 48 (1): 264–275. arXiv : 1309.5643 . Código Bibliográfico :2015PatRe..48..264C. doi :10.1016/j.patcog.2014.07.022. S2CID  17606924.
21. Wang, Jun y Jean-Daniel Zucker. "Resolución de problemas de instancias múltiples: un enfoque de aprendizaje perezoso". ICML (2000): 1119-25
22. Zhou, Zhi-Hua y Min-Ling Zhang. "Aprendizaje multi-instancia y multi-etiqueta con aplicación a la clasificación de escenas". Avances en sistemas de procesamiento de información neuronal. 2006. pp. 1609-16.
23. Ray, Soumya y David Page. "Regresión de instancias múltiples". ICML. Vol. 1. 2001. págs. 425-32.

Lectura adicional

Las revisiones recientes de la literatura MIL incluyen:

• Amores (2013), que ofrece una extensa revisión y estudio comparativo de los diferentes paradigmas,
• Foulds & Frank (2010), que proporciona una revisión exhaustiva de los diferentes supuestos utilizados por diferentes paradigmas en la literatura.
• Dietterich, Thomas G; Lathrop, Richard H; Lozano-Pérez, Tomás (1997). "Resolución del problema de instancias múltiples con rectángulos paralelos a los ejes". Inteligencia Artificial . 89 (1–2): 31–71. doi :10.1016/S0004-3702(96)00034-3.
• Herrera, Francisco; Ventura, Sebastián; Bello, Rafael; Cornelis, Chris; Zafra, Amelia; Sánchez-Tarragó, Danel; Vluymans, Sarah (2016). Aprendizaje de instancias múltiples. doi :10.1007/978-3-319-47759-6. ISBN 978-3-319-47758-9. Número de identificación del sujeto  24047205.
• Amores, Jaume (2013). "Clasificación de instancias múltiples: Revisión, taxonomía y estudio comparativo". Inteligencia Artificial . 201 : 81–105. doi : 10.1016/j.artint.2013.06.003 .
• Foulds, James; Frank, Eibe (2010). "Una revisión de los supuestos de aprendizaje de múltiples instancias". The Knowledge Engineering Review . 25 : 1–25. CiteSeerX  10.1.1.148.2333 . doi :10.1017/S026988890999035X. S2CID  8601873.
• Keeler, James D.; Rumelhart, David E.; Leow, Wee-Kheng (1990). "Segmentación integrada y reconocimiento de números escritos a mano". Actas de la Conferencia de 1990 sobre avances en sistemas de procesamiento de información neuronal (NIPS 3) . Morgan Kaufmann Publishers. págs. 557–563. ISBN 978-1-55860-184-0.
• Li, Hong-Dong; Menon, Rajasree; Omenn, Gilbert S; Guan, Yuanfang (2014). "La era emergente de la integración de datos genómicos para analizar la función de las isoformas de empalme". Tendencias en genética . 30 (8): 340–7. doi :10.1016/j.tig.2014.05.005. PMC  4112133 . PMID  24951248.
• Eksi, Ridvan; Li, Hong-Dong; Menon, Rajasree; Wen, Yuchen; Omenn, Gilbert S; Kretzler, Matthias; Guan, Yuanfang (2013). "Diferenciación sistemática de funciones para isoformas con empalme alternativo mediante la integración de datos de secuenciación de ARN". PLOS Computational Biology . 9 (11): e1003314. Bibcode :2013PLSCB...9E3314E. doi : 10.1371/journal.pcbi.1003314 . PMC  3820534 . PMID  24244129.
• Maron, O.; Ratan, AL (1998). "Aprendizaje de múltiples instancias para la clasificación de escenas naturales". Actas de la Decimoquinta Conferencia Internacional sobre Aprendizaje Automático . Morgan Kaufmann Publishers. págs. 341–349. ISBN 978-1-55860-556-5.
• Kotzias, Dimitrios; Denil, Misha; De Freitas, Nando; Smyth, Padhraic (2015). "De etiquetas grupales a individuales usando características profundas". Actas de la 21.ª Conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos - KDD '15 . págs. 597–606. doi :10.1145/2783258.2783380. ISBN 9781450336642.S2CID 7729996  .
• Ray, Soumya; Page, David (2001). Regresión de instancias múltiples (PDF) . ICML.
• Bandyopadhyay, Sanghamitra; Ghosh, Dip; Mitra, Ramkrishna; Zhao, Zhongming (2015). "MBSTAR: aprendizaje de instancias múltiples para predecir sitios de unión funcionales específicos en dianas de microARN". Scientific Reports . 5 : 8004. Bibcode :2015NatSR...5E8004B. doi :10.1038/srep08004. PMC  4648438 . PMID  25614300.
• Zhu, Wentao; Lou, Qi; Vang, Yeeleng Scott; Xie, Xiaohui (2017). "Redes multiinstancia profundas con asignación de etiquetas dispersas para la clasificación de mamografías completas". Computación de imágenes médicas e intervención asistida por computadora − MICCAI 2017. Apuntes de clase en informática. Vol. 10435. págs. 603–11. arXiv : 1612.05968 . doi :10.1007/978-3-319-66179-7_69. ISBN 978-3-319-66178-0.S2CID 9623929  .