Многократное обучение

В машинном обучении обучение с несколькими экземплярами (MIL) является типом контролируемого обучения . Вместо получения набора экземпляров, которые помечены индивидуально , обучающийся получает набор помеченных мешков , каждый из которых содержит много экземпляров. В простом случае бинарной классификации с несколькими экземплярами мешок может быть помечен как отрицательный, если все экземпляры в нем отрицательные. С другой стороны, мешок помечен как положительный, если в нем есть хотя бы один экземпляр, который является положительным. Из коллекции помеченных мешков обучающийся пытается либо (i) вызвать концепцию, которая будет правильно маркировать отдельные экземпляры, либо (ii) научиться маркировать мешки, не вызывая концепцию.

Бабенко (2008) ^[1] приводит простой пример для MIL. Представьте себе нескольких человек, и у каждого из них есть брелок, содержащий несколько ключей. Некоторые из этих людей могут войти в определенную комнату, а некоторые нет. Затем задача состоит в том, чтобы предсказать, может ли определенный ключ или определенная брелок провести вас в эту комнату. Чтобы решить эту задачу, нам нужно найти точный ключ, который является общим для всех «положительных» цепочек ключей. Если мы можем правильно идентифицировать этот ключ, мы также можем правильно классифицировать всю цепочку ключей — положительную, если она содержит требуемый ключ, или отрицательную, если она его не содержит.

Машинное обучение

В зависимости от типа и вариации обучающих данных машинное обучение можно условно разделить на три фреймворка: контролируемое обучение, неконтролируемое обучение и обучение с подкреплением. Обучение с несколькими экземплярами (MIL) относится к фреймворку контролируемого обучения, где каждый обучающий экземпляр имеет метку, либо дискретную, либо вещественную. MIL решает проблемы с неполным знанием меток в обучающих наборах. Точнее, при обучении с несколькими экземплярами обучающий набор состоит из помеченных «мешков», каждый из которых представляет собой набор непомеченных экземпляров. Мешок помечен положительно, если хотя бы один экземпляр в нем положительный, и помечен отрицательно, если все экземпляры в нем отрицательные. Цель MIL — предсказать метки новых, невидимых мешков.

История

Килер и др. ^[2] в своей работе в начале 1990-х годов были первыми, кто исследовал область MIL. Фактический термин «многоэкземплярное обучение» был введен в середине 1990-х годов Дитерихом и др., когда они исследовали проблему прогнозирования активности лекарств. ^[3] Они пытались создать обучающую систему, которая могла бы предсказать, подходит ли новая молекула для создания какого-либо лекарства или нет, путем анализа набора известных молекул. Молекулы могут иметь много альтернативных низкоэнергетических состояний, но только одно или некоторые из них подходят для создания лекарства. Проблема возникла из-за того, что ученые могли только определить, подходит ли молекула или нет, но они не могли точно сказать, какие из ее низкоэнергетических форм отвечают за это.

Одним из предложенных способов решения этой проблемы было использование контролируемого обучения и рассмотрение всех низкоэнергетических форм квалифицированной молекулы как положительных обучающих примеров, в то время как все низкоэнергетические формы неквалифицированных молекул как отрицательных примеров. Диттерих и др. показали, что такой метод будет иметь высокий уровень ложноположительного шума из-за всех низкоэнергетических форм, которые неправильно помечены как положительные, и, таким образом, не был действительно полезен. ^[3] Их подход заключался в рассмотрении каждой молекулы как маркированного мешка, а все альтернативные низкоэнергетические формы этой молекулы как экземпляров в мешке, без индивидуальных меток. Таким образом, формулируя обучение с несколькими примерами.

Решение проблемы обучения с множественными экземплярами, предложенное Дитерихом и др., — это алгоритм прямоугольника, параллельного осям (APR). ^[3] Он пытается найти подходящие прямоугольники, параллельные осям, построенные путем соединения признаков. Они протестировали алгоритм на наборе данных Маска, ^{[4] [5] [ dubious – discussion ]} , который представляет собой конкретные тестовые данные для прогнозирования активности лекарств и наиболее популярный эталон в обучении с множественными экземплярами. Алгоритм APR достиг наилучшего результата, но APR был разработан с учетом данных Маска.

Проблема обучения на нескольких экземплярах не является уникальной для поиска лекарств. В 1998 году Марон и Ратан нашли другое применение обучения на нескольких экземплярах для классификации сцен в машинном зрении и разработали структуру Diverse Density. ^[6] При наличии изображения экземпляр считается одним или несколькими подизображениями фиксированного размера, а мешок экземпляров считается всем изображением. Изображение помечается как положительное, если оно содержит целевую сцену — например, водопад — и как отрицательное в противном случае. Обучение на нескольких экземплярах может использоваться для изучения свойств подизображений, которые характеризуют целевую сцену. С тех пор эти структуры применялись к широкому спектру приложений, начиная от изучения концепций изображений и категоризации текста и заканчивая прогнозированием фондового рынка.

Примеры

Возьмем, к примеру, классификацию изображений Amores (2013). Имея изображение, мы хотим узнать его целевой класс на основе его визуального содержания. Например, целевым классом может быть «пляж», где изображение содержит как «песок», так и «воду». В терминах MIL изображение описывается как мешок , где каждый из них является вектором признаков (называемым экземпляром ), извлеченным из соответствующей -й области изображения, и является общими областями (экземплярами), разделяющими изображение. Мешок помечается как положительный («пляж»), если он содержит как экземпляры областей «песок», так и экземпляры областей «вода». ${\displaystyle X=\{X_{1},..,X_{N}\}}$ ${\displaystyle X_{i}}$ ${\displaystyle i}$ ${\displaystyle N}$

Примеры применения MIL:

• Молекулярная активность
• Прогнозирование участков связывания белков, связывающих кальмодулин ^[7]
• Функция прогнозирования для альтернативно сплайсированных изоформ Ли, Менон и др. (2014) , Экси и др. (2013) harvtxt error: no target: CITEREFLiMenonet_al.2014 (help) harvtxt error: no target: CITEREFEksiLiMenonet_al.2013 (help)
• Классификация изображений Марон и Ратан (1998)
• Категоризация текста или документа Котзиас и др. (2015) harvtxt error: no target: CITEREFKotzias_et_al.2015 (help)
• Прогнозирование функциональных участков связывания микроРНК-мишеней Бандйопадхай, Гош и др. (2015) harvtxt error: no target: CITEREFBandyopadhyayGhoshet_al.2015 (help)
• Классификация медицинских изображений Чжу и др. (2016) , П. Дж. Судхаршан и др. (2019) harvtxt error: no target: CITEREFZhu_et_al.2016 (help) harvtxt error: no target: CITEREFP.J.Sudharshan_et_al.2019 (help)

Многочисленные исследователи работали над адаптацией классических методов классификации, таких как машины опорных векторов или бустинг , для работы в контексте обучения на множественных примерах.

Определения

Если пространство экземпляров равно , то набор сумок — это набор функций , который изоморфен набору мультиподмножеств . Для каждой сумки и каждого экземпляра , рассматривается как количество раз, которое встречается в . ^[8] Пусть будет пространством меток, тогда «концепцией множественного экземпляра» является карта . Целью MIL является изучение такой концепции. Оставшаяся часть статьи будет сосредоточена на бинарной классификации , где . ${\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\}}$

Предположения

Большинство работ по обучению множественным экземплярам, ​​включая ранние работы Dietterich et al. (1997) и Maron & Lozano-Pérez (1997), ^{[3] [9]} делают предположение относительно связи между экземплярами в пределах мешка и меткой класса мешка. Из-за своей важности это предположение часто называют стандартным предположением MI.

Стандартное предположение

Стандартное предположение предполагает, что каждый экземпляр имеет связанную метку , которая скрыта от обучающегося. Пара называется «концепцией уровня экземпляра». Мешок теперь рассматривается как мультимножество концепций уровня экземпляра и помечается как положительный, если хотя бы один из его экземпляров имеет положительную метку, и как отрицательный, если все его экземпляры имеют отрицательные метки. Формально, пусть будет мешком. Метка тогда равна . Стандартное предположение MI асимметрично, что означает, что если положительные и отрицательные метки поменять местами, предположение имеет другое значение. Из-за этого, когда мы используем это предположение, нам нужно четко понимать, какая метка должна быть положительной. ${\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})}$

Стандартное предположение может рассматриваться как слишком строгое, и поэтому в последние годы исследователи пытались смягчить эту позицию, что привело к другим более свободным предположениям. ^[10] Причиной этого является убеждение, что стандартное предположение MI подходит для набора данных Маска, но поскольку MIL можно применять к многочисленным другим проблемам, некоторые другие предположения, вероятно, могли бы быть более подходящими. Руководствуясь этой идеей, Вайдманн ^[11] сформулировал иерархию обобщенных предположений на основе экземпляров для MIL. Она состоит из стандартного предположения MI и трех типов обобщенных предположений MI, каждое из которых более общее, чем предыдущее, в том смысле, что первое может быть получено как определенный выбор параметров последнего, стандартного предположения на основе присутствия, основанного на пороге, основанного на подсчете, причем предположение на основе подсчета является наиболее общим, а стандартное предположение — наименее общим. (Однако следует отметить, что любой мешок, удовлетворяющий предположению, основанному на количестве, удовлетворяет предположению, основанному на пороге, которое, в свою очередь, удовлетворяет предположению, основанному на присутствии, которое, в свою очередь, удовлетворяет стандартному предположению. В этом смысле также правильно утверждать, что стандартное предположение является самым слабым, а значит, наиболее общим, а предположение, основанное на количестве, является самым сильным, а значит, наименее общим.) Можно было бы ожидать, что алгоритм, который хорошо работает при одном из этих предположений, будет работать по крайней мере так же хорошо при менее общих предположениях. ${\displaystyle \subset }$ ${\displaystyle \subset }$ ${\displaystyle \subset }$

Предположения, основанные на присутствии, пороговом значении и количестве

Предположение, основанное на присутствии, является обобщением стандартного предположения, в котором мешок должен содержать все экземпляры, которые принадлежат набору требуемых понятий уровня экземпляра, чтобы быть помеченным как положительный. Формально, пусть будет набором требуемых понятий уровня экземпляра, и пусть обозначает количество раз, когда понятие уровня экземпляра встречается в мешке . Тогда для всех . Обратите внимание, что, принимая, что содержит только одно понятие уровня экземпляра, предположение, основанное на присутствии, сводится к стандартному предположению. ${\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}}$

Дальнейшее обобщение приходит с пороговым предположением, где каждое требуемое понятие уровня экземпляра должно встречаться не только один раз в мешке, но и некоторое минимальное (пороговое) количество раз, чтобы мешок был помечен как положительный. С указанной выше нотацией каждому требуемому понятию уровня экземпляра соответствует порог . Для мешка , для всех . ${\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}}$

Предположение на основе подсчета является окончательным обобщением, которое обеспечивает как нижнюю, так и верхнюю границу для количества раз, которое требуемое понятие может встречаться в положительно помеченном мешке. Каждое требуемое понятие уровня экземпляра имеет нижний порог и верхний порог с . Мешок помечен в соответствии с для всех . ${\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}}$

Предположение GMIL

Скотт, Чжан и Браун (2005) ^[12] описывают другое обобщение стандартной модели, которое они называют «обобщенным обучением множественных экземпляров» (GMIL). Предположение GMIL определяет набор требуемых экземпляров . Мешок помечается как положительный, если он содержит экземпляры, которые достаточно близки по крайней мере к требуемым экземплярам . ^[12] Только при этом условии предположение GMIL эквивалентно предположению, основанному на присутствии. ^[8] Однако Скотт и др. описывают дальнейшее обобщение, в котором есть набор точек притяжения и набор точек отталкивания . Мешок помечается как положительный, если и только если он содержит экземпляры, которые достаточно близки по крайней мере к точкам притяжения и достаточно близки по большей части к точкам отталкивания. ^[12] Это условие является строго более общим, чем условие, основанное на присутствии, хотя оно и не попадает в указанную выше иерархию. ${\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}$

Коллективное предположение

В отличие от предыдущих предположений, где сумки рассматривались как фиксированные, коллективное предположение рассматривает сумку как распределение по экземплярам , ​​и аналогично рассматривает метки как распределение по экземплярам. Целью алгоритма, работающего в рамках коллективного предположения, является моделирование распределения . ${\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}$

Так как обычно считается фиксированным, но неизвестным, алгоритмы вместо этого фокусируются на вычислении эмпирической версии: , где — число экземпляров в мешке . Так как также обычно считается фиксированным, но неизвестным, большинство методов, основанных на коллективных предположениях, фокусируются на изучении этого распределения, как в версии с одним экземпляром. ^{[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)}$

В то время как коллективное предположение взвешивает каждый экземпляр с одинаковой важностью, Фулдс расширил коллективное предположение, включив веса экземпляров. Взвешенное коллективное предположение тогда таково, что , где — весовая функция над экземплярами и . ^[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)}$

Алгоритмы

Структура MIL

Существует два основных вида алгоритмов для обучения множественным экземплярам: основанные на экземплярах и основанные на метаданных, или алгоритмы на основе встраивания. Термин «основанный на экземплярах» означает, что алгоритм пытается найти набор репрезентативных экземпляров на основе предположения MI и классифицировать будущие сумки из этих репрезентативных. Напротив, основанные на метаданных алгоритмы не делают никаких предположений о связи между экземплярами и метками сумок, а вместо этого пытаются извлечь независимую от экземпляра информацию (или метаданные) о сумках, чтобы изучить концепцию. ^[10] Для обзора некоторых современных алгоритмов MI см. Foulds and Frank. ^[8]

Алгоритмы, основанные на экземплярах

Самыми ранними предложенными алгоритмами MI были набор алгоритмов «итеративной дискриминации», разработанный Диттерихом и др., и алгоритм Diverse Density, разработанный Мароном и Лосано-Пересом. ^{[3] [9]} Оба эти алгоритма работали в соответствии со стандартным предположением.

Повторяющаяся дискриминация

В целом, все алгоритмы итеративной дискриминации состоят из двух фаз. Первая фаза заключается в выращивании прямоугольника, параллельного осям (APR), который содержит по крайней мере один экземпляр из каждого положительного мешка и ни одного экземпляра из отрицательных мешков. Это делается итеративно: начиная со случайного экземпляра в положительном мешке, APR расширяется до наименьшего APR, охватывающего любой экземпляр в новом положительном мешке . Этот процесс повторяется до тех пор, пока APR не покроет по крайней мере один экземпляр из каждого положительного мешка. Затем каждому экземпляру, содержащемуся в APR, присваивается «релевантность», соответствующая количеству отрицательных точек, которые он исключает из APR при удалении. Затем алгоритм выбирает кандидатные репрезентативные экземпляры в порядке убывания релевантности, пока ни один экземпляр, содержащийся в отрицательном мешке, также не будет содержаться в APR. Алгоритм повторяет эти шаги роста и репрезентативного выбора до сходимости, где размер APR на каждой итерации принимается только вдоль кандидатов-представителей. ${\displaystyle x_{1}\in B_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle B_{2}}$ ${\displaystyle x_{i}}$

После первой фазы APR, как полагают, плотно содержит только репрезентативные атрибуты. Вторая фаза расширяет этот плотный APR следующим образом: распределение Гаусса центрируется на каждом атрибуте, а более свободный APR строится таким образом, что положительные примеры будут выпадать из плотного APR с фиксированной вероятностью. ^[4] Хотя методы итерационной дискриминации хорошо работают со стандартным предположением, они не очень хорошо обобщаются на другие предположения MI. ^[8]

Разнообразная плотность

В своей простейшей форме, Разнообразная плотность (DD) предполагает один представительный экземпляр в качестве концепции. Этот представительный экземпляр должен быть «плотным» в том смысле, что он гораздо ближе к экземплярам из положительных мешков, чем из отрицательных мешков, а также «разнообразным» в том смысле, что он близок по крайней мере к одному экземпляру из каждого положительного мешка. ${\displaystyle t^{*}}$

Пусть будет набором положительно помеченных сумок, а будет набором отрицательно помеченных сумок, тогда наилучшим кандидатом для представительного экземпляра будет , где разнообразная плотность при предположении, что сумки распределены независимо, учитывая концепцию . Обозначая j-й экземпляр сумки i, модель шумового ИЛИ дает: ${\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})}$принимается за масштабированное расстояние, где — масштабирующий вектор. Таким образом, если каждый положительный мешок имеет экземпляр, близкий к , то будет высоким для каждого , но если любой отрицательный мешок имеет экземпляр, близкий к , то будет низким. Следовательно, является высоким только если каждый положительный мешок имеет экземпляр, близкий к , и ни один отрицательный мешок не имеет экземпляра, близкого к . Понятие кандидата может быть получено с помощью градиентных методов. Классификация новых мешков затем может быть выполнена путем оценки близости к . ^[9] Хотя Diverse Density изначально был предложен Мароном и др. в 1998 году, более поздние алгоритмы MIL используют структуру DD, такую ​​как EM-DD в 2001 году ^[13] и DD-SVM в 2004 году ^[14] и MILES в 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}}}$

Ряд алгоритмов с одним экземпляром также были адаптированы к контексту с несколькими экземплярами в рамках стандартного предположения, включая

• Машины опорных векторов ^[15]
• Искусственные нейронные сети ^[16]
• Деревья решений ^[17]
• Повышение ^[18]

После 2000 года произошел отход от стандартных предположений и разработка алгоритмов, предназначенных для решения более общих предположений, перечисленных выше. ^[10]

• Вайдман ^[11] предлагает алгоритм двухуровневой классификации (TLC) для изучения концепций в предположении, основанном на подсчетах. На первом этапе пытаются изучить концепции уровня экземпляра, строя дерево решений из каждого экземпляра в каждом мешке обучающего набора. Затем каждый мешок сопоставляется с вектором признаков на основе подсчетов в дереве решений. На втором этапе алгоритм с одним экземпляром запускается на векторах признаков для изучения концепции
• Скотт и др. ^[12] предложили алгоритм GMIL-1 для изучения концепций в предположении GMIL в 2005 году. GMIL-1 перечисляет все прямоугольники, параллельные осям , в исходном пространстве экземпляров и определяет новое пространство признаков булевых векторов. Мешок сопоставляется с вектором в этом новом пространстве признаков, где если APR покрывает , и в противном случае. Затем можно применить алгоритм с одним экземпляром для изучения концепции в этом новом пространстве признаков. ${\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}$

Из-за высокой размерности нового пространства признаков и стоимости явного перечисления всех APR исходного пространства экземпляров GMIL-1 неэффективен как с точки зрения вычислений, так и памяти. GMIL-2 был разработан как усовершенствование GMIL-1 в попытке повысить эффективность. GMIL-2 предварительно обрабатывает экземпляры, чтобы найти набор кандидатов-представителей экземпляров. Затем GMIL-2 сопоставляет каждый мешок с булевым вектором, как в GMIL-1, но рассматривает только APR, соответствующие уникальным подмножествам кандидатов-представителей экземпляров. Это значительно снижает требования к памяти и вычислительным ресурсам. ^[8]

• Сюй (2003) ^[10] предложил несколько алгоритмов, основанных на логистической регрессии и методах усиления для изучения концепций в рамках коллективного предположения.

Алгоритмы на основе метаданных (или встраивания)

Сопоставляя каждый мешок с вектором признаков метаданных, алгоритмы на основе метаданных обеспечивают гибкость использования произвольного алгоритма с одним экземпляром для выполнения фактической задачи классификации. Будущие мешки просто сопоставляются (встраиваются) в пространство признаков метаданных и маркируются выбранным классификатором. Поэтому большая часть внимания алгоритмов на основе метаданных сосредоточена на том, какие признаки или какой тип встраивания приводит к эффективной классификации. Обратите внимание, что некоторые из ранее упомянутых алгоритмов, такие как TLC и GMIL, можно считать основанными на метаданных.

• Один из подходов заключается в том, чтобы позволить метаданным для каждого мешка быть некоторым набором статистики по экземплярам в мешке. Алгоритм SimpleMI использует этот подход, где метаданные мешка считаются простой сводной статистикой, такой как среднее или минимум и максимум каждой переменной экземпляра, взятой по всем экземплярам в мешке. Существуют другие алгоритмы, которые используют более сложную статистику, но SimpleMI показал себя на удивление конкурентоспособным для ряда наборов данных, несмотря на его кажущееся отсутствие сложности. ^[8]
• Другой распространенный подход заключается в рассмотрении геометрии самих мешков как метаданных. Этот подход используется алгоритмами MIGraph и miGraph, которые представляют каждый мешок как граф, узлами которого являются экземпляры в мешке. Между двумя узлами есть ребро, если расстояние (до некоторой метрики в пространстве экземпляров) между соответствующими экземплярами меньше некоторого порогового значения. Классификация выполняется с помощью SVM с ядром графа (MIGraph и miGraph отличаются только выбором ядра). ^[8] Аналогичные подходы используются MILES ^[19] и MInD. ^[20] MILES представляет мешок по его сходству с экземплярами в обучающем наборе, в то время как MInD представляет мешок по его расстоянию до других мешков.
• Модификацию k-ближайших соседей (kNN) также можно считать алгоритмом на основе метаданных с геометрическими метаданными, хотя отображение между сумками и особенностями метаданных не является явным. Однако необходимо указать метрику, используемую для вычисления расстояния между сумками. Ван и Цукер (2000) ^[21] предлагают (максимальную и минимальную, соответственно) метрики Хаусдорфа для сумок и : ${\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\|}$

Они определяют две разновидности kNN, байесовскую-kNN и цитируемую-kNN, как адаптации традиционной задачи ближайшего соседа к многоэкземплярной среде.

Обобщения

До сих пор в этой статье рассматривалось обучение множественных экземпляров исключительно в контексте бинарных классификаторов. Однако обобщения одноэкземплярных бинарных классификаторов могут быть перенесены на случай множественных экземпляров.

• Одним из таких обобщений является проблема множественных экземпляров и множественных меток (MIML), где каждый мешок теперь может быть связан с любым подмножеством пространства меток. Формально, если — пространство признаков, а — пространство меток, концепция MIML — это карта . Чжоу и Чжан (2006) ^[22] предлагают решение проблемы MIML посредством сведения либо к проблеме множественных экземпляров, либо к проблеме множественных концепций. ${\displaystyle {\mathcal {X}}}$ ${\displaystyle {\mathcal {Y}}}$ ${\displaystyle c:\mathbb {N} ^{\mathcal {X}}\rightarrow 2^{\mathcal {Y}}}$
• Другое очевидное обобщение — регрессия с несколькими экземплярами. Здесь каждый мешок связан с одним действительным числом, как в стандартной регрессии. Подобно стандартному предположению, регрессия MI предполагает, что в каждом мешке есть один экземпляр, называемый «первичным экземпляром», который определяет метку для мешка (с точностью до шума). Идеальной целью регрессии MI было бы найти гиперплоскость, которая минимизирует квадратную потерю первичных экземпляров в каждом мешке, но первичные экземпляры скрыты. Фактически, Рэй и Пейдж (2001) ^[23] показывают, что поиск наилучшей подходящей гиперплоскости, которая подходит одному экземпляру из каждого мешка, неразрешим, если в мешке меньше трех экземпляров, и вместо этого разрабатывают алгоритм для аппроксимации. Многие из алгоритмов, разработанных для классификации MI, также могут обеспечить хорошие аппроксимации для задачи регрессии MI. ^[8]

Смотрите также

• Контролируемое обучение
• Многоуровневая классификация

Ссылки

1. Бабенко, Борис. «Множественное обучение: алгоритмы и приложения». Просмотреть статью PubMed/NCBI Google Scholar (2008).
2. Килер, Джеймс Д., Дэвид Э. Румельхарт и Ви-Кхенг Леоу. Интегрированная сегментация и распознавание рукописных цифр. Корпорация по микроэлектронике и компьютерным технологиям, 1991.
3. Дитерих, Томас Г., Ричард Х. Латроп и Томас Лосано-Перес. «Решение проблемы множественных экземпляров с помощью прямоугольников, параллельных осям». Искусственный интеллект 89.1 (1997): 31-71.
4. C. Blake, E. Keogh и CJ Merz. Репозиторий баз данных машинного обучения UCI [1], Департамент информации и компьютерных наук, Калифорнийский университет, Ирвайн, Калифорния, 1998.
5. Ван, Вэй-Хонг; Ду, Ян-е; Ли, Цюй; Фан, Чжао-линь (2011). «Оценка кредита на основе программирования экспрессии генов и клональной селекции». Процедия Инжиниринг . 15 : 3759–3763. дои : 10.1016/j.proeng.2011.08.704 .
6. О. Марон и А. Л. Ратан. Многократное обучение для классификации естественных сцен. В трудах 15-й Международной конференции по машинному обучению, Мэдисон, Висконсин, стр. 341–349, 1998.
7. Минхас, Ф. у. А. А.; Бен-Хур, А (2012). «Множественное обучение сайтов связывания кальмодулина». Биоинформатика . 28 (18): i416–i422. doi :10.1093/bioinformatics/bts416. PMC 3436843. PMID  22962461 . 
8. Фулдс, Джеймс и Эйб Франк. «Обзор предположений о многоэкземплярном обучении». The Knowledge Engineering Review 25.01 (2010): 1-25.
9. Марон, Одед и Томас Лосано-Перес. "Структура для обучения на основе множественных экземпляров". Достижения в области нейронных систем обработки информации (1998): 570-576
10. Сюй, X. Статистическое обучение в задачах с несколькими экземплярами. Магистерская диссертация, Университет Вайкато (2003).
11. Вайдманн, Нильс Б. «Двухуровневая классификация для обобщенных данных из нескольких экземпляров». Дисс. Университет Альберта-Людвига, 2003 г.
12. Скотт, Стивен, Цзюнь Чжан и Джошуа Браун. «Об обобщенном многоэкземплярном обучении». Международный журнал вычислительного интеллекта и приложений 5.01 (2005): 21-35.
13. Чжан, Ци и Салли А. Голдман . "EM-DD: улучшенная техника обучения на основе множественных экземпляров". Достижения в области нейронных систем обработки информации. (2001): 1073 - 80
14. Чен, Исинь и Джеймс З. Ван. «Категоризация изображений путем обучения и рассуждения с областями». Журнал исследований машинного обучения 5 (2004): 913-939
15. Эндрюс, Стюарт, Иоаннис Цочантаридис и Томас Хофманн. «Машины опорных векторов для обучения на множественных экземплярах». Достижения в области нейронных систем обработки информации (2003). С. 561–658
16. Чжоу, Чжи-Хуа и Мин-Лин Чжан. «Нейронные сети для многоэкземплярного обучения». Труды Международной конференции по интеллектуальным информационным технологиям, Пекин, Китай. (2002). С. 455 - 459
17. Блокил, Хендрик, Дэвид Пейдж и Эшвин Шринивасан. «Многоэкземплярное обучение деревьев». Труды 22-й международной конференции по машинному обучению. ACM, 2005. С. 57-64
18. Ауэр, Питер и Рональд Ортнер. «Подход к многократному обучению». Машинное обучение: ECML 2004. Springer Berlin Heidelberg, 2004. 63-74.
19. Чэнь, Исинь; Би, Джинбо; Ван, Дж. З. (2006-12-01). «MILES: Обучение множественным экземплярам с помощью встроенного выбора экземпляров». Труды IEEE по анализу шаблонов и машинному интеллекту . 28 (12): 1931–1947. doi :10.1109/TPAMI.2006.248. ISSN  0162-8828. PMID  17108368. S2CID  18137821.
20. Чеплыгина, Вероника; Такс, Дэвид М.Дж.; Луг, Марко (2015-01-01). «Обучение на нескольких экземплярах с различиями в мешках». Распознавание образов . 48 (1): 264–275. arXiv : 1309.5643 . Bibcode : 2015PatRe..48..264C. doi : 10.1016/j.patcog.2014.07.022. S2CID  17606924.
21. Ван, Джун и Жан-Даниэль Цукер. «Решение многоэкземплярной проблемы: ленивый подход к обучению». ICML (2000): 1119-25
22. Чжоу, Чжи-Хуа и Мин-Лин Чжан. «Многократное обучение с множественными метками и его применение для классификации сцен». Достижения в области нейронных систем обработки информации. 2006. С. 1609–16
23. Рэй, Соумья и Дэвид Пейдж. «Множественная регрессия». ICML. Том 1. 2001. С. 425–32.

Дальнейшее чтение

Недавние обзоры литературы по МИЛ включают:

• Amores (2013), который представляет собой обширный обзор и сравнительное исследование различных парадигм,
• Фулдс и Фрэнк (2010), в которой представлен подробный обзор различных предположений, используемых в различных парадигмах в литературе.
• Дитерих, Томас Г.; Латроп, Ричард Х.; Лосано-Перес, Томас (1997). «Решение проблемы множественных экземпляров с помощью прямоугольников, параллельных осям». Искусственный интеллект . 89 (1–2): 31–71. doi :10.1016/S0004-3702(96)00034-3.
• Эррера, Франциско; Вентура, Себастьян; Белло, Рафаэль; Корнелис, Крис; Сафра, Амелия; Санчес-Тарраго, Данель; Влуйманс, Сара (2016). Многократное обучение. дои : 10.1007/978-3-319-47759-6. ISBN 978-3-319-47758-9. S2CID  24047205.
• Аморес, Жауме (2013). «Множественная классификация экземпляров: обзор, таксономия и сравнительное исследование». Искусственный интеллект . 201 : 81–105. doi : 10.1016/j.artint.2013.06.003 .
• Foulds, James; Frank, Eibe (2010). «Обзор предположений о многоэкземплярном обучении». The Knowledge Engineering Review . 25 : 1–25. CiteSeerX  10.1.1.148.2333 . doi :10.1017/S026988890999035X. S2CID  8601873.
• Килер, Джеймс Д.; Румельхарт, Дэвид Э.; Леоу, Ви-Кхенг (1990). «Интегрированная сегментация и распознавание рукописных цифр». Труды конференции 1990 года по достижениям в области нейронных систем обработки информации (NIPS 3) . Издательство Morgan Kaufmann. стр. 557–563. ISBN 978-1-55860-184-0.
• Ли, Хонг-Донг; Менон, Раджасри; Оменн, Гилберт С.; Гуан, Юаньфан (2014). «Начинающаяся эра интеграции геномных данных для анализа функции изоформ сплайсинга». Тенденции в генетике . 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). "Систематическое дифференцирование функций для альтернативно сплайсированных изоформ посредством интеграции данных РНК-секвенирования". PLOS Computational Biology . 9 (11): e1003314. Bibcode :2013PLSCB...9E3314E. doi : 10.1371/journal.pcbi.1003314 . PMC  3820534 . PMID  24244129.
• Марон, О.; Ратан, А. Л. (1998). «Множественное обучение для классификации естественных сцен». Труды пятнадцатой международной конференции по машинному обучению . Издательство Morgan Kaufmann. стр. 341–349. ISBN 978-1-55860-556-5.
• Kotzias, Dimitrios; Denil, Misha; De Freitas, Nando; Smyth, Padhraic (2015). «От групповых к индивидуальным меткам с использованием глубоких признаков». Труды 21-й Международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных — KDD '15 . стр. 597–606. doi :10.1145/2783258.2783380. ISBN 9781450336642. S2CID  7729996.
• Рэй, Соумья; Пейдж, Дэвид (2001). Множественная регрессия (PDF) . ICML.
• Bandyopadhyay, Sanghamitra; Ghosh, Dip; Mitra, Ramkrishna; Zhao, Zhongming (2015). "MBSTAR: Многократное обучение для прогнозирования специфических функциональных сайтов связывания в микроРНК-мишенях". Scientific Reports . 5 : 8004. Bibcode :2015NatSR...5E8004B. doi :10.1038/srep08004. PMC  4648438 . PMID  25614300.
• Чжу, Вентао; Лу, Ци; Ванг, Йелен Скотт; Се, Сяохуэй (2017). «Глубокие многоэкземплярные сети с разреженным назначением меток для классификации всей маммограммы». Медицинские вычисления изображений и компьютерное вмешательство − MICCAI 2017. Конспект лекций по информатике. Том 10435. С. 603–11. arXiv : 1612.05968 . doi :10.1007/978-3-319-66179-7_69. ISBN 978-3-319-66178-0. S2CID  9623929.