Hispanopedia Wiki
Articulo de referencia

aprendizaje de instancias múltiples

En el aprendizaje automático , el aprendizaje de instancias múltiples (MIL) es un tipo de aprendizaje supervisado . En lugar de recibir un conjunto de instancias etiquetadas ind...

Hispanopedia WikiContenido en espanolLectura gratuita

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

Babenko (2008) [ 1 ] ofrece un ejemplo sencillo de MIL. Imaginemos a varias personas, cada una con un llavero que contiene varias llaves. Algunas de ellas pueden entrar en una habitación determinada, mientras que otras no. La tarea consiste en predecir si una llave o un llavero específico permite acceder a esa habitación. Para resolver este problema, necesitamos encontrar la llave exacta que comparten todos los llaveros "positivos". Si logramos identificar correctamente esta llave, también podremos clasificar correctamente todo el llavero: 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 principales: aprendizaje supervisado, aprendizaje no supervisado y aprendizaje por refuerzo. El aprendizaje de instancias múltiples (MIL) se enmarca dentro del aprendizaje supervisado, donde cada instancia de entrenamiento tiene una etiqueta, ya sea discreta o real. El MIL aborda problemas de 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 se etiqueta positivamente si al menos una instancia es positiva, y negativamente si todas son negativas. El objetivo del MIL es predecir las etiquetas de bolsas nuevas y desconocidas.

Historia

Keeler et al., [ 2 ] en su trabajo de principios de la década de 1990 fue el primero en explorar el área de MIL. El término real aprendizaje de instancias múltiples 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 era apta para fabricar 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, son aptos para fabricar un fármaco. El problema surgió porque los científicos solo podían determinar si una molécula era apta o no, pero no podían decir exactamente cuál de sus formas de baja energía era responsable de ello.

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 fueron 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 se etiquetan erróneamente 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 esta manera formularon el aprendizaje de instancias múltiples.

La solución al problema de aprendizaje de instancias múltiples que propusieron Dietterich et al. es el algoritmo de rectángulo paralelo a los ejes (APR). [ 3 ] Este intenta buscar rectángulos paralelos a los ejes apropiados construidos mediante la conjunción de las características. Probaron el algoritmo en el conjunto de datos de Musk, [ 4 ] [ 5 ] que es un conjunto de datos de prueba concreto para la 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 obtuvo el mejor resultado, pero fue diseñado teniendo en cuenta los datos de Musk.

El problema del aprendizaje de instancias múltiples no es exclusivo del descubrimiento de fármacos. En 1998, Maron y Ratan encontraron otra aplicación del aprendizaje de instancias múltiples a la clasificación de escenas en visión artificial y diseñaron el marco de Densidad Diversa. [ 6 ] Dada una imagen, una instancia se considera una o más subimágenes de tamaño fijo, y la bolsa 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 instancias múltiples 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 texto, hasta la predicción del mercado de valores.

Ejemplos

Tomemos como ejemplo la clasificación de imágenes (Amores, 2013) . Dada una imagen, queremos conocer su clase objetivo basándonos en su contenido visual. Por ejemplo, la clase objetivo podría ser "playa", donde la imagen contiene tanto "arena" como "agua". En términos de MIL , la imagen se describe como una bolsa.incógnita={incógnita1,..,incógnitanorte}{\displaystyle X=\{X_{1},..,X_{N}\}}, donde cadaincógnitai{\displaystyle X_{i}}es el vector de características (llamado instancia ) extraído del correspondientei{\displaystyle i}-ésima región en la imagen ynorte{\displaystyle N}es el número 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".

Ejemplos de casos en los que se aplica MIL son:

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

Definiciones

Si el espacio de instancias esincógnita{\displaystyle {\mathcal {X}}}, entonces el conjunto de bolsas es el conjunto de funcionesnorteincógnita={B:incógnita→norte}{\displaystyle \mathbb {N} ^{\mathcal {X}}=\{B:{\mathcal {X}}\rightarrow \mathbb {N} \}}, que es isomorfo al conjunto de subconjuntos múltiples deincógnita{\displaystyle {\mathcal {X}}}. Por cada bolsaB∈norteincógnita{\displaystyle B\in \mathbb {N} ^{\mathcal {X}}}y cada instanciaincógnita∈incógnita{\displaystyle x\in {\mathcal {X}}},B(incógnita){\displaystyle B(x)}se considera como el número de vecesincógnita{\displaystyle x}ocurre enB{\displaystyle B}. [ 8 ] DejeY{\displaystyle {\mathcal {Y}}}Si el espacio de etiquetas es un "concepto de instancia múltiple", entonces un "concepto de instancia múltiple" es un mapa.do:norteincógnita→Y{\displaystyle c:\mathbb {N} ^{\mathcal {X}}\rightarrow {\mathcal {Y}}}El objetivo de MIL es aprender dicho concepto. El resto del artículo se centrará en la clasificación binaria , dondeY={0,1}{\displaystyle {\mathcal {Y}}=\{0,1\}}.

Supuestos

La mayor parte del trabajo 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, esta suposición se suele denominar suposición estándar de MI.

Suposición estándar

La suposición estándar toma cada instanciaincógnita∈incógnita{\displaystyle x\in {\mathcal {X}}}tener una etiqueta asociaday∈{0,1}{\displaystyle y\in \{0,1\}}que está oculto para el alumno. El par(incógnita,y){\displaystyle (x,y)}se denomina "concepto a nivel de instancia". Una bolsa se considera ahora como un multiconjunto 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, seaB={(incógnita1,y1),…,(incógnitanorte,ynorte)}{\displaystyle B=\{(x_{1},y_{1}),\ldots ,(x_{n},y_{n})\}}ser una bolsa. La etiqueta deB{\displaystyle B}es entoncesdo(B)=1−∏i=1norte(1−yi){\displaystyle c(B)=1-\prod _{i=1}^{n}(1-y_{i})}El supuesto estándar de MI es asimétrico, lo que significa que si se invierten las etiquetas positivas y negativas, el supuesto tiene un significado diferente. Por lo tanto, al utilizar este supuesto, debemos tener claro cuál de las etiquetas debe considerarse positiva.

La suposición estándar podría considerarse demasiado estricta y, por lo tanto, en los últimos años, los investigadores intentaron flexibilizar esa postura, lo que dio lugar a otras suposiciones más flexibles. [ 10 ] La razón de esto es la creencia de que la suposición MIL estándar es apropiada para el conjunto de datos de Musk, pero dado que MIL se puede aplicar a muchos otros problemas, probablemente otras suposiciones diferentes serían más apropiadas. Guiado por esa idea, Weidmann [ 11 ] formuló una jerarquía de suposiciones generalizadas basadas en instancias para MIL. Consiste en la suposición MI estándar y tres tipos de suposiciones MI generalizadas, cada una más general que la anterior, en el sentido de que la primera se puede obtener como una elección específica de parámetros de la segunda, estándar.⊂{\displaystyle \subset }basado en la presencia⊂{\displaystyle \subset }basado en umbrales⊂{\displaystyle \subset }Basado en el conteo, siendo la suposición basada en el conteo la más general y la suposición estándar la menos general. (Cabe señalar, sin embargo, que cualquier bolsa que cumpla con la suposición basada en el conteo cumple con la suposición basada en el umbral, que a su vez cumple con la suposición basada en la presencia, que nuevamente cumple con la suposición estándar. En ese sentido, también es correcto afirmar que la suposición estándar es la más débil, por lo tanto la más general, y la suposición basada en el conteo es la más fuerte, por lo tanto la menos general). Cabría esperar que un algoritmo que funcione bien bajo una de estas suposiciones funcione al menos igual de bien bajo las suposiciones menos generales.

Supuestos basados ​​en la presencia, el umbral y el recuento

La suposición basada en la presencia es una generalización de la suposición estándar, en la que una bolsa debe contener todas las instancias que pertenecen a un conjunto de conceptos requeridos a nivel de instancia para poder ser etiquetada como positiva. Formalmente, seadoR⊆incógnita×Y${\displaystyle C_{R}\subseteq {\mathcal {X}}\times {\mathcal {Y}}}$sea ​​el conjunto de conceptos requeridos a nivel de instancia, y deje que#(B,doi){\displaystyle \#(B,c_{i})}denota el número de veces que el concepto de nivel de instanciadoi{\displaystyle c_{i}}ocurre en la bolsaB{\displaystyle B}. Entoncesdo(B)=1⇔#(B,doi)≥1{\displaystyle c(B)=1\Leftrightarrow \#(B,c_{i})\geq 1}a pesar dedoi∈doR{\displaystyle c_{i}\in C_{R}}. Tenga en cuenta que, al tomardoR{\displaystyle C_{R}}Para contener un único concepto a nivel de instancia, la suposición basada en la presencia se reduce a la suposición estándar.

Una generalización adicional viene con la suposición basada 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 instanciadoi∈doR{\displaystyle c_{i}\in C_{R}}está asociado a un umbralli∈norte{\displaystyle l_{i}\in \mathbb {N} }Para una bolsaB{\displaystyle B},do(B)=1⇔#(B,doi)≥li{\displaystyle c(B)=1\Leftrightarrow \#(B,c_{i})\geq l_{i}}a pesar dedoi∈doR{\displaystyle c_{i}\in C_{R}}.

La suposición basada en el conteo es una generalización final que impone límites inferiores y superiores para la cantidad de veces que un concepto requerido puede ocurrir en una bolsa etiquetada positivamente. Cada concepto requerido a nivel de instanciadoi∈doR{\displaystyle c_{i}\in C_{R}}tiene un umbral más bajoli∈norte{\displaystyle l_{i}\in \mathbb {N} }y umbral superiortúi∈norte{\displaystyle u_{i}\in \mathbb {N} }conli≤túi{\displaystyle l_{i}\leq u_{i}}Una bolsaB{\displaystyle B}está etiquetado segúndo(B)=1⇔li≤#(B,doi)≤túi{\displaystyle c(B)=1\Leftrightarrow l_{i}\leq \#(B,c_{i})\leq u_{i}}a pesar dedoi∈doR{\displaystyle c_{i}\in C_{R}}.

Suposición de GMIL

Scott, Zhang y Brown (2005) [ 12 ] describen otra generalización del modelo estándar, que denominan "aprendizaje generalizado de instancias múltiples" (GMIL). La suposición GMIL especifica un conjunto de instancias requeridas.Q⊆incógnita{\displaystyle Q\subseteq {\mathcal {X}}}Una bolsaincógnita{\displaystyle X}se etiqueta como positivo si contiene instancias que están suficientemente cerca de al menosr{\displaystyle r}de las instancias requeridasQ{\displaystyle Q}[ 12 ] Bajo esta condición, la suposición GMIL es equivalente a la suposición basada en la presencia. [ 8 ] Sin embargo, Scott et al. describen una generalización adicional en la que hay un conjunto de puntos de atracción .Q⊆incógnita{\displaystyle Q\subseteq {\mathcal {X}}}y un conjunto de puntos de repulsiónQ¯⊆incógnita{\displaystyle {\overline {Q}}\subseteq {\mathcal {X}}}. Una bolsa se etiqueta como positiva si y solo si contiene instancias que están suficientemente cerca de al menosr{\displaystyle r}de los puntos de atracción y están suficientemente cerca de como máximos{\displaystyle s}de los puntos de repulsión. [ 12 ] Esta condición es estrictamente más general que la basada en la presencia, aunque no se encuentra dentro de la jerarquía anterior.

Suposición colectiva

A diferencia de las suposiciones anteriores donde las bolsas se consideraban fijas, la suposición colectiva considera una bolsaB{\displaystyle B}como una distribuciónpag(incógnita|B){\displaystyle p(x|B)}en instanciasincógnita{\displaystyle {\mathcal {X}}}y de manera similar, consideran las etiquetas como una distribución.pag(y|incógnita){\displaystyle p(y|x)}sobre instancias. El objetivo de un algoritmo que opera bajo el supuesto colectivo es entonces modelar la distribuciónpag(y|B)=∫incógnitapag(y|incógnita)pag(incógnita|B)dincógnita{\displaystyle p(y|B)=\int _{\mathcal {X}}p(y|x)p(x|B)dx}.

Desdepag(incógnita|B){\displaystyle p(x|B)}Por lo general, se considera que es fijo pero desconocido; los algoritmos, en cambio, se centran en calcular la versión empírica:pag^(y|B)=1norteB∑i=1norteBpag(y|incógnitai){\displaystyle {\widehat {p}}(y|B)={\frac {1}{n_{B}}}\sum _{i=1}^{n_{B}}p(y|x_{i})}, dóndenorteB{\displaystyle n_{B}}es el número de instancias en la bolsaB{\displaystyle B}. Desdepag(y|incógnita){\displaystyle p(y|x)}También se suele considerar fijo pero desconocido; la mayoría de los métodos basados ​​en supuestos colectivos se centran en aprender esta distribución, como en la versión de instancia única. [ 8 ] [ 10 ]

Si bien la suposición colectiva otorga a cada instancia la misma importancia, Foulds extendió la suposición colectiva para incorporar ponderaciones de instancia. La suposición colectiva ponderada es entonces quepag^(y|B)=1wB∑i=1norteBw(incógnitai)pag(y|incógnitai){\displaystyle {\widehat {p}}(y|B)={\frac {1}{w_{B}}}\sum _{i=1}^{n_{B}}w(x_{i})p(y|x_{i})}, dóndew:incógnita→R+{\displaystyle w:{\mathcal {X}}\rightarrow \mathbb {R} ^{+}}es una función de peso sobre instancias ywB=∑incógnita∈Bw(incógnita){\displaystyle w_{B}=\sum _{x\in B}w(x)}. [ 8 ]

Algoritmos

Marco MIL

Existen dos tipos principales de algoritmos para el aprendizaje de instancias múltiples: algoritmos basados ​​en instancias y algoritmos basados ​​en metadatos o incrustaciones. El término "basado en instancias" indica que el algoritmo intenta encontrar un conjunto de instancias representativas basándose en una suposición de MI y clasificar futuras bolsas a partir de estos representantes. Por el contrario, los algoritmos basados ​​en metadatos no hacen suposiciones sobre la relación entre instancias y etiquetas de bolsas, sino que intentan extraer información independiente de la instancia (o metadatos) sobre las bolsas para aprender el concepto. [ 10 ] Para una revisión de algunos de los algoritmos modernos de MI, véase 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 operaban bajo el supuesto estándar.

discriminación iterada

En términos generales, todos los algoritmos de discriminación iterativa constan de dos fases. La primera fase consiste en construir 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 realiza de forma iterativa: comenzando desde una instancia aleatoria.incógnita1∈B1{\displaystyle x_{1}\in B_{1}}En una bolsa positiva, la TAE se amplía a la TAE más pequeña que cubre cualquier instancia.incógnita2{\displaystyle x_{2}}en una nueva bolsa positivaB2{\displaystyle B_{2}}. Este proceso se repite hasta que el APR cubra al menos una instancia de cada bolsa positiva. Luego, cada instanciaincógnitai{\displaystyle x_{i}}A cada elemento contenido en el APR se le asigna una "relevancia", que corresponde a la cantidad de puntos negativos que excluye del APR si se elimina. A continuación, el algoritmo selecciona instancias representativas candidatas en orden de relevancia decreciente, hasta que ninguna instancia contenida en un conjunto negativo se encuentre también 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 define únicamente a lo largo de los representantes candidatos.

Tras la primera fase, se considera que la APR contiene estrictamente solo los atributos representativos. La segunda fase amplía 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 las instancias positivas queden fuera de la APR estricta con una probabilidad fija. [ 4 ] Si bien las técnicas de discriminación iterativa 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) asume una única instancia representativa.t∗{\displaystyle t^{*}}como concepto. Esta instancia representativa debe ser "densa" en el sentido de que está mucho más cerca de instancias de bolsas positivas que de bolsas negativas, así como "diversa" en el sentido de que está cerca de al menos una instancia de cada bolsa positiva.

DejarB+={Bi+}1metro{\displaystyle {\mathcal {B}}^{+}=\{B_{i}^{+}\}_{1}^{m}}ser el conjunto de bolsas etiquetadas positivamente y dejarB−={Bi−}1norte{\displaystyle {\mathcal {B}}^{-}=\{B_{i}^{-}\}_{1}^{n}}Sea el conjunto de bolsas con etiquetas negativas, entonces el mejor candidato para la instancia representativa viene dado port^=arg⁡máximotDD(t){\displaystyle {\hat {t}}=\arg \max _{t}DD(t)}donde la densidad diversaDD(t)=PAGr(t|B+,B−)=arg⁡máximot∏i=1metroPAGr(t|Bi+)∏i=1nortePAGr(t|Bi−){\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)}bajo el supuesto de que las bolsas se distribuyen independientemente dado el conceptot∗{\displaystyle t^{*}}AlquilerBij{\displaystyle B_{ij}}Sea j la j-ésima instancia de la bolsa i, el modelo noisy-or da como resultado:

PAGr(t|Bi+)=1−∏j(1−PAGr(t|Bij+)){\displaystyle Pr(t|B_{i}^{+})=1-\prod _{j}\left(1-Pr\left(t|B_{ij}^{+}\right)\right)}
PAGr(t|Bi−)=∏j(1−PAGr(t|Bij−)){\displaystyle Pr(t|B_{i}^{-})=\prod _{j}\left(1-Pr\left(t|B_{ij}^{-}\right)\right)}

PAG(t|Bij){\displaystyle P(t|B_{ij})}se toma como la distancia escaladaPAG(t|Bij)∝exp⁡(−∑ksk2(incógnitak−(Bij)k)2){\displaystyle P(t|B_{ij})\propto \exp \left(-\sum _{k}s_{k}^{2}\left(x_{k}-(B_{ij})_{k}\right)^{2}\right)}dóndes=(sk){\displaystyle s=(s_{k})}es el vector de escala. De esta manera, si cada bolsa positiva tiene una instancia cercana at{\displaystyle t}, entoncesPAGr(t|Bi+){\displaystyle Pr(t|B_{i}^{+})}será alto para cada unoi{\displaystyle i}pero si alguna bolsa negativaBi−{\displaystyle B_{i}^{-}}tiene una instancia cercana at{\displaystyle t},PAGr(t|Bi−){\displaystyle Pr(t|B_{i}^{-})}será bajo. Por lo tanto,DD(t){\displaystyle DD(t)}es alto solo si cada bolsa positiva tiene una instancia cercana at{\displaystyle t}y ninguna bolsa negativa tiene una instancia cercana at{\displaystyle t}El concepto candidatot^{\displaystyle {\hat {t}}}se pueden obtener a través de métodos de gradiente. La clasificación de nuevas bolsas se puede realizar evaluando la proximidad at^{\displaystyle {\hat {t}}}. [ 9 ] Aunque la Densidad Diversa fue propuesta originalmente por Maron et al. en 1998, 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 ]

Varios algoritmos de instancia única también se han adaptado a un contexto de instancias múltiples bajo el supuesto estándar, incluyendo:

Después del año 2000, se produjo un alejamiento de la suposición estándar y el desarrollo de algoritmos diseñados para abordar las suposiciones más generales enumeradas anteriormente. [ 10 ]

  • Weidmann [ 11 ] propone un algoritmo de clasificación de dos niveles (TLC) para aprender conceptos bajo el supuesto basado en conteos. El primer paso intenta aprender conceptos a nivel de instancia construyendo un árbol de decisión a partir de cada instancia en cada bolsa del conjunto de entrenamiento. Cada bolsa se asigna luego a un vector de características basado en los conteos en el árbol de decisión. 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 la suposición GMIL en 2005. GMIL-1 enumera todos los rectángulos paralelos a los ejes.{Ri}i∈I{\displaystyle \{R_{i}\}_{i\in I}}en el espacio original de instancias, y define un nuevo espacio de características de vectores booleanos. Una bolsaB{\displaystyle B}se asigna a un vectorb=(bi)i∈I{\displaystyle \mathbf {b} =(b_{i})_{i\in I}}en este nuevo espacio de funciones, dondebi=1{\displaystyle b_{i}=1}si la TAERi{\displaystyle R_{i}}cubiertasB{\displaystyle B}, ybi=0{\displaystyle b_{i}=0}De lo contrario, se puede aplicar un algoritmo de instancia única para aprender el concepto en este nuevo espacio de características.

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 con el fin de 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 que corresponden 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 boosting para aprender conceptos bajo el supuesto colectivo.

Algoritmos basados ​​en metadatos (o basados ​​en 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. 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 conduce a una clasificación efectiva. Cabe señalar que algunos de los algoritmos mencionados anteriormente, como TLC y GMIL, podrían considerarse basados ​​en metadatos.

  • Un enfoque consiste en utilizar como metadatos para cada bolsa un conjunto de estadísticas sobre las instancias que la componen. El algoritmo SimpleMI adopta este enfoque, donde los metadatos de una bolsa se consideran una estadística descriptiva simple, como el promedio o el mínimo y el máximo de cada variable de instancia calculada para todas las instancias de la bolsa. Existen otros algoritmos que utilizan estadísticas más complejas, pero SimpleMI ha demostrado 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 bolsas mismas como metadatos. Este es el enfoque adoptado por los algoritmos MIGraph y miGraph, que representan cada bolsa como un grafo cuyos nodos son las instancias en la bolsa. Hay una arista 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 mediante una SVM con un núcleo de grafo (MIGraph y miGraph solo difieren en su elección de núcleo). [ 8 ] Enfoques similares son adoptados por MILES [ 19 ] y MInD. [ 20 ] MILES representa una bolsa por sus similitudes con instancias en el conjunto de entrenamiento, mientras que MInD representa una bolsa por sus distancias a otras bolsas.
  • Una modificación del algoritmo de k vecinos más cercanos (kNN) también puede considerarse un algoritmo basado en metadatos con metadatos geométricos, aunque el mapeo entre bolsas y características de metadatos no es explícito. Sin embargo, es necesario especificar la métrica utilizada para calcular la distancia entre bolsas. Wang y Zucker (2000) [ 21 ] sugieren las métricas de Hausdorff (máxima y mínima, respectivamente) para bolsas.A{\displaystyle A}yB{\displaystyle B}:
H(A,B)=máximo{máximoAminB‖a−b‖,máximoBminA‖a−b‖}{\displaystyle H(A,B)=\max \left\{\max _{A}\min _{B}\|a-b\|,\max _{B}\min _{A}\|a-b\|\right\}}
h1(A,B)=minAminB‖a−b‖{\displaystyle h_{1}(A,B)=\min _{A}\min _{B}\|a-b\|}

Definen dos variantes de kNN, kNN bayesiano y kNN de citación, como adaptaciones del problema tradicional del vecino más cercano al entorno de instancias múltiples.

Generalizaciones

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

  • Una de esas generalizaciones es el problema de instancias múltiples y etiquetas múltiples (MIML), donde cada bolsa ahora puede asociarse con cualquier subconjunto del espacio de etiquetas. Formalmente, siincógnita{\displaystyle {\mathcal {X}}}es el espacio de características yY{\displaystyle {\mathcal {Y}}}es el espacio de etiquetas, un concepto MIML es un mapado:norteincógnita→2Y{\displaystyle c:\mathbb {N} ^{\mathcal {X}}\rightarrow 2^{\mathcal {Y}}}. Zhou y Zhang (2006) [ 22 ] proponen una solución al problema MIML mediante una reducción a un problema de instancias múltiples o de conceptos múltiples.
  • Otra generalización obvia es la regresión de instancias múltiples. Aquí, cada bolsa se asocia con un único número real, como en la regresión estándar. Al igual que en la suposición estándar, la regresión de instancias múltiples asume que hay una instancia en cada bolsa, llamada "instancia prima", que determina la etiqueta de la bolsa (salvo ruido). El objetivo ideal de la regresión de instancias múltiples sería encontrar un hiperplano que minimice la pérdida cuadrática de las instancias prima en cada bolsa, pero las instancias prima 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 de aproximación. Muchos de los algoritmos desarrollados para la clasificación de instancias múltiples también pueden proporcionar buenas aproximaciones al problema de regresión de instancias múltiples. [ 8 ]

Véase también

Referencias

  1. ↑ Babenko, Boris. "Aprendizaje de instancias múltiples: algoritmos y aplicaciones." Ver artículo PubMed/NCBI Google Académico (2008).
  2. ↑ Keeler, James D., David E. Rumelhart y Wee-Kheng Leow. Segmentación y reconocimiento integrados de números escritos a mano. Microelectronics and Computer Technology Corporation, 1991.
  3. 1 2 3 4 5 Dietterich, Thomas G., Richard H. Lathrop y Tomás Lozano-Pérez. "Resolución del problema de instancias múltiples con rectángulos paralelos a los ejes". Inteligencia artificial 89.1 (1997): 31-71.
  4. 1 2 C. Blake, E. Keogh y CJ Merz. Repositorio de bases de datos de aprendizaje automático de la UCIDepartamento 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 instancias múltiples 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 instancias múltiples de sitios de unión de calmodulina" . Bioinformatics . 28 ( 18): i416– i422. doi : 10.1093/bioinformatics/bts416 . PMC 3436843. PMID 22962461 .  
  8. 1 2 3 4 5 6 7 8 9 10 11 Foulds, James y Eibe Frank. "Una revisión de los supuestos del aprendizaje de instancias múltiples". The Knowledge Engineering Review 25.01 (2010): 1-25.
  9. 1 2 3 Maron, Oded y Tomás Lozano-Pérez. «Un marco para el aprendizaje de instancias múltiples». Avances en sistemas de procesamiento de información neuronal (1998): 570-576
  10. 1 2 3 4 5 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 múltiples instancias". Disentimiento. Universidad Albert-Ludwigs, 2003.
  12. 1 2 3 4 Scott, Stephen, Jun Zhang y Joshua Brown. "Sobre el aprendizaje generalizado de instancias múltiples." Revista Internacional de Inteligencia Computacional y Aplicaciones 5.01 (2005): 21-35.
  13. ↑ Zhang, Qi y Sally A. Goldman . «EM-DD: Una técnica mejorada de aprendizaje de instancias múltiples». 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 instancias múltiples». Avances en sistemas de procesamiento de información neuronal (2003). págs. 561-658
  16. ↑ Zhou, Zhi-Hua y Min-Ling Zhang. «Redes neuronales para el aprendizaje multiinstancia». Actas de la Conferencia Internacional sobre Tecnología de la Información Inteligente, Pekín, China. (2002). págs. 455-459
  17. ↑ Blockeel, Hendrik, David Page y Ashwin Srinivasan. «Aprendizaje de árboles multi-instancia». Actas de la 22.ª conferencia internacional sobre aprendizaje automático. ACM, 2005. págs. 57-64.
  18. ↑ Auer, Peter y Ronald Ortner. "Un enfoque de boosting para el aprendizaje de instancias múltiples". Machine Learning: ECML 2004. Springer Berlin Heidelberg, 2004. 63-74.
  19. ↑ Chen, Yixin; Bi, Jinbo; Wang, JZ (2006-12-01). "MILES: Aprendizaje de instancias múltiples mediante selección de instancias integrada". IEEE Transactions on Pattern Analysis and Machine Intelligence . 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 (2015-01-01). "Aprendizaje de instancias múltiples con disimilitudes de bolsas". Pattern Recognition . 48 (1): 264– 275. arXiv : 1309.5643 . Bibcode : 2015PatRe..48..264C . doi : 10.1016/j.patcog.2014.07.022 . S2CID 17606924 . 
  21. ↑ Wang, Jun y Jean-Daniel Zucker. «Resolución del problema de instancias múltiples: un enfoque de aprendizaje perezoso». ICML (2000): 1119-25
  22. ↑ Zhou, Zhi-Hua y Min-Ling Zhang. "Aprendizaje multi-instancia-multietiqueta con aplicación a la clasificación de escenas". Avances en sistemas de procesamiento de información neuronal. 2006. págs. 1609-1616
  23. ↑ Ray, Soumya y David Page. "Regresión de instancias múltiples". ICML. Vol. 1. 2001. págs. 425-432

Lecturas adicionales

Las revisiones recientes de la literatura sobre alfabetización infantil incluyen:

  • Amores (2013) , que proporciona una revisión exhaustiva y un estudio comparativo de los diferentes paradigmas,
  • Foulds y Frank (2010) , que proporciona una revisión exhaustiva de los diferentes supuestos utilizados por los distintos 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. S2CID 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 del aprendizaje multiinstancia". 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 y reconocimiento integrados 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 el análisis de la función de las isoformas de empalme" . Trends in Genetics . 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 de 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 instancias múltiples 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 mediante 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  978-1-4503-3664-2. 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 objetivos de microARN" . Scientific Reports . 5 : 8004. Bibcode : 2015NatSR...5.8004B . doi : 10.1038/srep08004 . PMC 4648438. PMID 25614300 .  
  • Zhu, Wentao; Lou, Qi; Vang, Yeeleng Scott; Xie, Xiaohui (2017). "Redes profundas multiinstancia con asignación de etiquetas dispersas para la clasificación de mamografías completas". Medical Image Computing and Computer-Assisted Intervention − MICCAI 2017. Lecture Notes in Computer Science. Vol.  10435. pp. 603–11 . arXiv : 1612.05968 . doi : 10.1007/978-3-319-66179-7_69 . ISBN  978-3-319-66178-0. S2CID 9623929 .