I den övervakade inlärningsmiljö som kallas Multiple-Instance Learning (MIL), exemplen är påsar av fall, och påsetiketten är en funktion av etiketterna av dess fall. Vanligtvis är denna funktion den Booleska OR. Inläraren observerar ett prov av påsar och påsetiketter, men inte instansetiketter som bestämmer påsetiketterna. Inläraren är då skyldig att utfärda en klassificeringsregel för påsar baserat på provet. MIL har många tillämpningar, och många heuristiska algoritmer har använts framgångsrikt på detta problem, var och en anpassat till specifika inställningar eller applikationer. I detta arbete ger vi en enhetlig teoretisk analys för MIL, som innehar för någon underliggande hypotes klass, oavsett en specifik applikation eller problemdomän. Vi visar att provet komplexitet av MIL är endast poly-logaritmiskt beroende av storleken på väskan, för någon underliggande hypotes klass. Dessutom introducerar vi en ny PAC-lärande algoritm för MIL, som använder en regelbunden övervakad läralgoritm som ett orakel. Vi visar att effektiv PAC-learning för MIL kan genereras från någon effektiv icke-MIL övervakad inlärningsalgoritm som hanterar ensidiga fel. Den beräkningsmässiga komplexiteten hos den resulterande algoritmen är endast polynomiskt beroende av säckstorleken.
En grundläggande version av lärande i flera instanser kan reduceras till klassificering med ensidig märkning av buller (se REF.
Multi-Instance Learning with Any Hypothesis Class
{'venue': 'Journal of Machine Learning Research 13(Oct):1999-3039, 2012', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}