다중 인스턴스 학습

시리즈의 일부
기계 학습 및 데이터 마이닝
문제 분류 클러스터링 회귀 이상 검출 데이터 클리닝 자동 ML 어소시에이션 규칙 강화 학습 구조화된 예측 기능 엔지니어링 기능 학습 온라인 학습 준지도 학습 비지도 학습 순위 매기기 학습 문법 유도
지도 학습 (분류 • 회귀) 의사결정 트리 앙상블 배깅 부스팅 랜덤 포레스트 k-NN 선형 회귀 네이비 베이즈 인공신경망 로지스틱 회귀 분석 퍼셉트론 관련 벡터 머신(RVM) 서포트 벡터 머신(SVM)
클러스터링 버치 치유하다 계층적 k자형 기대 최대화(EM) DBSCAN 광학 평균 이동
치수 축소 인자 분석 CCA ICA LDA NMF PCA PGD t-SNE
구조화된 예측 그래픽 모델 베이즈 네트 조건부 랜덤 필드 히든 마르코프
이상 검출 k-NN 국소 특이치 계수
인공신경망 자동 인코더 인지 컴퓨팅 딥 러닝 딥 드림 다층 퍼셉트론 RNN LSTM GRU ESN 저장고 계산 제한 볼츠만 기계 GAN somerset. 컨볼루션 뉴럴 네트워크 유넷 트랜스포머 비전. 스파이킹 뉴럴 네트워크 메모리 트랜지스터 전기화학 RAM(ECRAM)
강화 학습 Q-러닝 사사 시간차(TD) 멀티 에이전트 셀프 플레이
인간과의 학습 액티브 러닝 크라우드 소싱 휴먼 인 더 루프
모델 진단 학습 곡선
이론. 커널 머신 바이어스-분산 트레이드오프 컴퓨터 학습 이론 경험적 리스크 최소화 오컴 러닝 PAC 학습 통계학 학습 VC 이론
기계학습장 NeurolIPS ICML ML JMLR ArXiv:cs.LG
관련 기사 인공지능 용어집 기계 학습 연구를 위한 데이터 세트 목록 기계학습의 개요
v t

기계학습에서 MIL(Multiple-Instance Learning)은 지도학습의 일종입니다.학습자는 개별적으로 라벨이 지정된 일련의 인스턴스를 받는 대신 라벨이 지정된 가방 세트를 받게 되며, 각 가방에는 여러 인스턴스가 들어 있습니다.단순한 다중 인스턴스 바이너리 분류의 경우 가방 내의 모든 인스턴스가 음수이면 가방이 음수라고 라벨이 붙을 수 있습니다.한편, 봉투에 적어도 1개의 포지티브 인스턴스가 있는 경우에는 포지티브라고 표기한다.학습자는 라벨이 붙은 가방의 컬렉션에서 (i)개별 인스턴스에 라벨을 올바르게 붙이는 개념을 유도하거나 (ii)개념을 유도하지 않고 가방에 라벨을 붙이는 방법을 배우려고 한다.

Babenko(2008)^[1]는 MIL의 간단한 예를 제시합니다.여러 사람을 상상해 보세요.각자는 키가 거의 없는 키 체인을 가지고 있습니다.이 사람들 중 일부는 특정 방에 들어갈 수 있고 일부는 들어갈 수 없습니다.그런 다음 특정 키 또는 특정 키 체인이 해당 룸에 들어갈 수 있는지 예측하는 작업을 수행합니다.이 문제를 해결하려면 모든 "긍정적" 키 체인에 공통되는 정확한 키를 찾아야 합니다.이 키를 올바르게 식별할 수 있으면 키 체인 전체를 올바르게 분류할 수 있습니다.필요한 키가 포함되어 있는 경우는 긍정, 존재하지 않는 경우는 부정입니다.

기계 학습

훈련 데이터의 유형과 변동에 따라 기계 학습은 대략 지도 학습, 비지도 학습, 강화 학습의 세 가지 프레임워크로 분류될 수 있습니다.MIL(Multiple Instance Learning)은 지도 학습 프레임워크에 속하며, 모든 교육 인스턴스에는 개별 또는 실제 가치의 라벨이 있습니다.MIL은 트레이닝 세트의 라벨에 대한 불완전한 지식에 관한 문제를 다룬다.보다 정확하게는 다중 인스턴스 학습에서 훈련 세트는 라벨이 부착된 "백"으로 구성되며, 각 백은 라벨이 부착되지 않은 인스턴스의 집합이다.가방 내의 적어도 하나의 인스턴스가 양의 경우 봉투에 긍정 라벨이 부착되고, 모든 인스턴스가 음의 경우 봉투에 부정 라벨이 부착됩니다.MIL의 목표는 보이지 않는 새 가방의 라벨을 예측하는 것입니다.

역사

킬러 ^[2]등은 1990년대 초 그의 연구에서 MIL 영역을 최초로 탐구한 사람이다.실제 다중 인스턴스 학습이라는 용어는 1990년대 중반에 Dietterich 등에 의해 약물 활동 ^[3]예측의 문제를 조사하던 중 도입되었다.그들은 알려진 분자의 집합을 분석함으로써 새로운 분자가 어떤 약을 만들기에 적합한지 여부를 예측할 수 있는 학습 시스템을 만들려고 했다.분자는 많은 대체적인 저에너지 상태를 가질 수 있지만, 오직 한 가지 또는 그들 중 일부는 약물을 만들 자격이 있다.이 문제는 과학자들이 분자가 적격인지 아닌지만 판단할 수 있었지만, 어떤 저에너지 형태에 원인이 있는지 정확하게 말할 수 없었기 때문에 발생했다.

이 문제를 해결하기 위해 제안된 방법 중 하나는 감독 학습을 사용하고, 적격 분자의 모든 저에너지 형태를 양성 훈련 사례로 간주하는 반면, 부적격 분자의 저에너지 모양은 모두 음성 사례로 간주하는 것이었다.Dietterich 등은 그러한 방법이 양으로 잘못 표시된 모든 저에너지 형태에서 높은 거짓 양의 노이즈를 가질 것이며, 따라서 실제로 ^[3]유용하지 않다는 것을 보여주었다.그들의 접근법은 각각의 분자를 라벨이 붙은 봉투로 간주하고, 그 분자의 모든 대체적인 저에너지 형태를 개별 라벨이 없는 봉투의 인스턴스로 간주하는 것이었습니다.따라서 다중 인스턴스 학습을 공식화합니다.

Dietterich 등이 제안한 다중 인스턴스 학습 문제에 대한 해결책은 축-병렬 직사각형(^[3]APR) 알고리즘이다.피쳐의 결합에 의해 생성된 적절한 축-평행 직사각형을 검색하려고 합니다.그들은 Musk ^[4]데이터셋에 대해 이 알고리즘을 테스트했는데, 이것은 약물 활동 예측의 구체적인 테스트 데이터이며 다중 인스턴스 학습에서 가장 일반적으로 사용되는 벤치마크입니다.APR 알고리즘은 최고의 결과를 얻었지만 APR은 머스크 데이터를 염두에 두고 설계되었습니다.

다인스턴스 학습의 문제는 약물 발견에만 국한된 것이 아니다.1998년, Maron과 Ratan은 기계 시각에서의 장면 분류를 위한 다중 인스턴스 학습의 다른 응용 프로그램을 발견했고, 다양한 ^[5]밀도 프레임워크를 고안했다.이미지가 주어지면 인스턴스는 하나 이상의 고정 크기 하위 이미지로 간주되고 인스턴스의 가방은 이미지 전체로 간주됩니다.대상 장면(예: 폭포)이 포함된 경우 이미지에 양(+)의 레이블이 지정되고 그렇지 않은 경우 음(-)의 레이블이 지정됩니다.여러 인스턴스 학습을 사용하여 대상 장면을 특징짓는 하위 영상의 속성을 학습할 수 있습니다.그 후, 이러한 프레임워크는 이미지 컨셉 학습이나 텍스트 분류로부터 주식 시장 예측에 이르기까지, 폭넓은 분야에 적용되고 있다.

예

Amores(2013)와 같은 이미지 분류를 예로 들 수 있습니다.이미지가 주어지면 시각 콘텐츠를 기반으로 대상 클래스를 알고 싶습니다.예를 들어 대상 클래스는 "beach"일 수 있으며, 이미지에는 "모래"와 "물"이 모두 포함되어 있습니다.MIL 용어로 이미지는 $봉투{\displaystyle }$ X ${\displaystyle =}$ { ${\displaystyle {}_{}{1\mathrm{}}_{}}$,${\displaystyle }$. , X ${\displaystyle N_{}}$ $}$ { $displaystyle$ X = \ { $X _$ { { { X _ {1} , , ,$X$_ { N $}$} 。$여기$서 각 ${\displaystyle X_{}}$i { $displaystyle X_{$i$$}는 대응하는$$i 및$n번째$$이미지$에서 추출된 특징 벡터(인스턴스)입니다.(partitioning) 이미지를 분할합니다.백에 "모래" 영역 인스턴스와 "물" 영역 인스턴스가 모두 포함된 경우 백에 양('비치') 레이블이 지정됩니다.

MIL이 적용되는 예는 다음과 같습니다.

• 분자 활성
• 칼모듈린 결합단백질^[6] 결합부위 예측
• 대체 결합 Isoforms Li, Menon & al. (2014) harvhtx 오류에 대한 예측 함수: 대상 없음: CITREFLiMenonet_al. 2014(도움말), Eksi 등(2013) harvtx 오류: 대상 없음: CITREFeksiLiMenonet_al.
• 이미지 분류 Maron & Ratan (1998)
• 텍스트 또는 문서 분류 Kotzias et al. (2015) harvhts 오류: 대상 없음: CITREFKotzias_et_al.2015(도움말)
• MicroRNA의 기능 결합 부위 예측 대상 Bandyopadhyay, Ghosh & al. (2015) harvhts 오류: 대상 없음: CITREFBandyopadhyayGhoshet_al. 2015 (도움말)
• 의료 이미지 분류 Zhu 외 (2016) harvts 오류: 대상 없음: CITREFZhu_et_al.2016(도움말), P.J.Sudharshan et al. (2019) harvts 오류: 대상 없음: CITEREFP.J.Sudharshan_et_al.2019(도움말)

수많은 연구자들이 다중 인스턴스 학습의 맥락에서 작동하도록 지원 벡터 머신이나 부스팅과 같은 고전 분류 기술을 적응시키는 데 힘써왔다.

정의들

인스턴스 공간이 ${\style$ {$X$인 경우 가방 세트는 함수 $집합{\displaystyle {\mathbb{}}^{}}$ N ${\displaystyle {\mathcal{}}^{}}$ ${\displaystyle =}$ {${\displaystyle B}$ : ${\displaystyle X\mathcal{}}$ ${\displaystyle \to }$ ${\displaystyle N\mathbb{}}$ $}$ { $displaystyle \mathbb {N} ^{\mathcal {X}}=$\{$B:$${\mathcal$$${$X}\rightarrow$\$mathbb$$${$N$$}$ $\backslash \}.$$$X의 $멀티$ 서브셋 집합과 동형입니다.각 $가방{\displaystyle }$ B${\displaystyle {\mathbb{}}^{}}$ N ${\displaystyle {\mathcal{}}^{}}$\ $display style$B \ $in$\ $mathbb${$N$} ^ \ $mathcal { X$$$}$${ $x$ x x x x x x X$x$ x x x x x x x x x x x x x x x 。횟수){\displaystyle)}B{B\displaystyle}에서 발생한다 표지를 가능한 다음"여러 인스턴스를 개념"지도가 있어 c:NX→ Y{\displaystyle c:\mathbb{N}^{{X\mathcal}}\rightarrow{{Y\mathcal}}}Y{\displaystyle{{Y\mathcal}}}가 되는 공간. 음악은 내 인생의 목표는 그러한 속임수를 배우는 것이다자 .[7].cept. 이 문서의 나머지 부분에서는 이진 분류에 초점을 맞춥니다. $여기$서 Y${\displaystyle =}${ ${\displaystyle 0}$ , 1$$ { $displaystyle${ \$mathcal$ { Y } = \ { 0 ,$1$ \$$} 。

전제 조건

Dietterich 외 연구진(1997년)과 Maron & Lozano-Pérez(1997년) 초기 논문을 ^[3][8]포함한 다중 사례 학습에 대한 대부분의 연구는 가방 내의 사례와 가방의 클래스 라벨 사이의 관계에 관한 가정을 한다.그 중요성 때문에 그 가정을 흔히 표준 MI 가정이라고 한다.

표준 가정

표준 가정에서는 각 $인스턴스{\displaystyle }$ $(\$ x$\in\mathcal${${\displaystyle \mathrm{X}}$$})$에 관련된 $라벨{\displaystyle }$ y$display$ y$\in\{0,1\})$가$$ 있어야 합니다.이러한 라벨은 학습자에게 숨겨집니다.쌍$({\displaystyle x,}$ $)$ {$displaystyle(x, y)}$을 "인스턴스 수준 개념"이라고 합니다.이제 가방은 인스턴스 수준의 개념의 멀티셋으로 간주되며 적어도1개의 인스턴스가 양의 라벨을 가진 경우 양의 라벨을 붙이고 모든 인스턴스가 음의 라벨을 가진 경우 음의 라벨을 붙입니다.$정식적$으로는 B${\displaystyle =}$ { (${\displaystyle {}_{}{}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$y 1${\displaystyle ),}$ ${\displaystyle \dots ,}$( ${\displaystyle x_{}}$n , ${\displaystyle y_{}}$n ) $}$ { $display style$ B = \ { ( x$_$ {1} , $y$_ {1$}$ } , $\ldots$ , ( x _ $n$, y _ { n$$} ) 。$B{\displaystyle }$$({displaystyle$ B$})$의 라벨은 c${\displaystyle (\mathrm{B})}$ ${\displaystyle =\underset{}{\overset{}{1}}}$ - ${\displaystyle \underset{}{\overset{}{}}}$ i ${\displaystyle \underset{}{\overset{}{=}}}$ ${\displaystyle 1\underset{}{\overset{}{}}}$ (${\displaystyle }$1 - ${\displaystyle y_{}}$i$$) { $displaystyle$c(B)= $1$- \ $prod$_ { i$= 1$} ( 1 - y _ { $i$}$$} 。표준 MI 가정은 양과 음의 라벨이 서로 다른 가정임을 의미합니다.그렇기 때문에 이 가정을 사용할 때 어떤 라벨이 긍정적인 라벨이어야 하는지 명확히 해야 합니다.

표준적인 가정은 너무 엄격하다고 여겨질 수 있고, 따라서 최근 몇 년 동안 연구자들은 그 입장을 완화하려고 노력했고, 이것은 다른 느슨한 ^[9]가정을 낳았다.그 이유는 Musk 데이터 세트에 표준 MI 가정이 적합하지만 MIL은 다른 수많은 문제에 적용될 수 있기 때문에 다른 가정들이 더 적합할 수 있기 때문입니다.이 아이디어에 따라, Weidmann은 MIL에 대한 일반화 사례 기반 가정의 계층을 공식화했다.It consists of the standard MI assumption and three types of generalized MI assumptions, each more general than the last, standard ${\displaystyle \subset }$ presence-based ${\displaystyle \subset }$ threshold-based ${\displaystyle \subset }$ count-based, with the count-based assumption being the most general and the standa가장 일반적이지 않은 가정입니다.이러한 전제 조건 중 하나에서 잘 작동하는 알고리즘이 적어도 덜 일반적인 전제 조건에서도 잘 수행될 것으로 예상할 수 있습니다.

존재 기반, 임계값 기반 및 카운트 기반 전제 조건

존재 기반 가정은 표준 가정의 일반화입니다.여기서 가방에는 positive라는 라벨이 붙기 위해서는 필요한 인스턴스 수준의 개념 세트에 속하는1개 이상의 인스턴스가 포함되어 있어야 합니다.형식적으로는 C ${\displaystyle R_{}x}$X ×$$ \ $subsete$ \ mathcal { $X }$ \$times$ \ $mathcal${$Y }$${\displaystyle \mathrm{display<img\; alt="C\_\{R\}\backslash subseteq\; \{\backslash mathcal\; \{X\}\}\backslash times\; \{\backslash mathcal\; \{Y\}\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/35b24defde595f49205d0917a0c257230dd25e01"\; style="vertical-align:\; -0.671ex;\; width:12.615ex;\; height:2.509ex;">}}$ ${\displaystyle 、}$ #${\displaystyle }$(${\displaystyle {}_{}{B}_{}}$, ${\displaystyle {}_{}}$ ) \ $display style \$ # ( $B$, c _ { i $}$ )${\displaystyle \mathrm{}}$displaydisplaydisplaydisplay$$ c$_ stylevel$ c ${\displaystyle {개념}_{}}$의 수를 나타냅니다$.$$ystyle$ B$\}.$ $다음$으로 c${\displaystyle }$(${\displaystyle B}$ ) $=$ ${\displaystyle 1}$ ${\displaystyle \mathrm{\#}}$# (${\displaystyle B}$ , ${\displaystyle c_{}}$i )$1$ 1$$\ $display style$c ( $B$, $c$_ { $i$} \$geq$ 1$$note$$ ${\displaystyle {}_{}}$ 모든 ${\displaystyle c_{}}$ ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$ C _ $R$note C$$$_$ { $display style$ c$_$ { i$}$。${\displaystyle C_{}}$에 $주의$해 주십시오.n.

한층 더 일반화하면, 임계값 베이스의 가정이 됩니다.이 가정에서는, 필요한 인스턴스 레벨의 각 개념은, 백에 1회 뿐만이 아니라, 최소(임계치) 회수로 행해지지 않으면, 백에 의해 백에 플러스 라벨이 붙여지지 않습니다.위의 표기법에서는 필요한 인스턴스 레벨의 각 $개념{\displaystyle {}_{}}$ c ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle C_{}}$ R$${\$displaystyle c_{i}\in$ C_${R}$에 $임계값{\displaystyle {}_{}}$ ${\displaystyle l_{}}$ n ${\$이 관련지어집니다.$백{\displaystyle }$B(\$displaystyle$ B$\},$ $C{\displaystyle )}$의 ${\displaystyle {경우}_{}}$ (${\displaystyle B)=}$ 1${\displaystyle 、}$ [ ]$l_{i}:$ $모든$ ${\displaystyle {ci}_{}}$ ${\displaystyle {}_{}}$ $(\$ C_${R$

카운트 베이스 가정은 라벨이 붙은 가방에서 필요한 개념이 발생할 수 있는 횟수에 대해 하한과 상한을 모두 적용하는 최종 일반화이다.필요한 인스턴스 레벨의 $개념{\displaystyle {}_{}}$ ${\displaystyle c_{}}$ i ${\displaystyle {}_{}{}_{}{C}_{}}$R \ $displaystyle c$$_$ { $i$$$ \ $in$ C _ { $R$$$} \ $in$ \ $mathbb$ { N$$ $}$ upper upper $upper{\displaystyle {}_{}}$ i$$$$N \ $displaystyle$ ${\displaystyle u_{}}$$$_ { $i$}\ $in$\ $mathbbb${ N $}$ $upperstylestylestyle$ upper upper upper upper upper upper upper upper $upper$ upper upper upper upper upper upper upper upper upper upper upper upper upper upper upper upper i upper upper upper upper upper upper upperstyle upper upper upper upper a a a each each each each each each each each each each each each each each each each each each$B}$의 라벨은${\displaystyle }$c$($${\displaystyle )}$ ${\displaystyle =}$ ${\displaystyle 1{}_{}}$ ${\displaystyle l_{}}$ i${\displaystyle \mathrm{\#}}$ # (${\displaystyle B}$ , ${\displaystyle {}_{}{i}_{}}$ ) ${\displaystyle 、}$ ${\displaystyle u_{}}$i { $displaystyle c$( B , $c$_ i )$=$1 \$leq$ \ # ($B$ , c _ { $i$} \ $leq$ \ # ( B , c _ { i } \ $leq$ $u$$$_ {$$$i$} } $b{\displaystyle }$${\displaystyle {}_{}}$b ${\displaystyle c_{}}$ c c b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b 。

GMIL의 가정

Scott, Zhang 및 Brown(2005)은 표준 모델의 또 다른 일반화를 설명합니다.이것을 「Generalized Multiple Instance Learning」(GMIL)이라고 부릅니다.그 GMIL 가정}. 가방 X{X\displaystyle}표시된다 필요한 인스턴스의 집합 Q⊆ X{\displaystyle Q\subseteq{{X\mathcal}}를 지정하는 긍정적인 만약 치약이 인스턴스는 충분히 가까이 최소한 r{r\displaystyle}의 필요한 인스턴스 Q{Q\displaystyle}.[11]에 따라만 이 conditio.n,GMIL 가정은 존재 기반 ^[7]가정과 동일합니다.그러나 Scott 등에서는 Q ${\displaystyle x\mathcal{}}$X \ $display style$Q \ $subseteq$\ $mathcal${ $X$} ${\displaystyle a}$ X \ $display$style { $Q$ \ subseteq \ display style { Q } \ $subseteq$ \ $mathcal {X}$is bag is is is is is is is is is which which which which which which which which which which which $which{\displaystyle }$ which which which which which which which which which which which which which which which which which which which which which which which which which which which which which which which which which which which which which which which which which which which $which{\displaystyle \stackrel{}{}}$최소$r개$ $이상$의$$흡인 $지점$과 근접하고 최소$$대부분의$$ $반발$^[11]지점과 충분히 근접합니다.이 상태는 존재 기반보다 엄격히 일반적이지만 위의 계층에 속하지는 않습니다.

집합적 가정

가방이 고정된 것으로 간주되는 이전의 가정과는 달리 집합적인 가정에서는 $B$를 $X$에 대한 $분포{\displaystyle }$ p$x$ B$)$로 간주하고 라벨을 $분포{\displaystyle }$ p$($x)로 간주합니다.$x)}$을(를) 사용합니다.집합적 가정 하에서 작동하는 알고리즘의 목적은 분포 $p{\displaystyle (y}$ ${\displaystyle B)}$ $=$ ${\displaystyle {\delta \mathcal{}}_{}}$X ${\displaystyle p_{}(y}$x ) ${\displaystyle p(x}$ B${\displaystyle )}$ ${\displaystyle d}$ ${\displaystyle x}$ ${\displaystyle$ p$(y$ B)=\$int$ _${\mathcal {X}p(y$ x$)p(x)dx$를 모형화하는 것입니다.

p${\displaystyle }$( ${\displaystyle x}$B ) ${display style$ p$($x ${\displaystyle B\frac{\mathrm{}}{}}$)}는$$ 일반적으로 고정되어 있지만 알 수 없는 것으로 $간주$되므로 알고리즘은 대신 경험적 버전을 계산하는 데 초점을 맞춥니다. $p{\displaystyle \stackrel{}{}^}$ ( ${\displaystyle yB}$ ) ${\displaystyle \underset{}{\overset{}{=}}}$ ${\displaystyle \underset{}{\overset{}{{}_{}}}}$ ${\displaystyle \underset{}{\overset{}{n_{}}}}$ ${\displaystyle \underset{}{\overset{}{{}_{}}}\underset{}{\overset{}{p}}}$ ( ${\displaystyle y}$ x${\displaystyle {}_{}{i}_{}}$) style ( \ $display$style \$wide hat$ {${\displaystyle p{}_{}}$ } ( y B ) =$$1 n B { n p$}$ { n _$sum$}$displaystyle n_{B}$는 $(\displaystyle$ B$)$의 인스턴스 수입니다${\displaystyle .}$p( ${\displaystyle yx}$ $)(\displaystyle$ p$(y$ x$)}$도 일반적으로 고정으로 간주되지만 알 수 없는 것으로 간주되기 $때문$에 대부분의 집합적 가정 기반 메서드는 단일 인스턴스 ^[7][9]버전과 같이 이 분포를 학습하는 데 중점을 둡니다.

집합적 가정은 모든 인스턴스에 동일한 중요성을 부여하지만 Foulds는 집합적 가정을 인스턴스 가중치를 포함하도록 확장했다.가중 집단 가정은 p${\displaystyle \stackrel{}{}^}$ ( ${\displaystyle yB}$ ) ${\displaystyle =}$ ${\displaystyle 1\frac{\mathrm{}}{}}$ ${\displaystyle \frac{{}_{}}{}}$ ${\displaystyle \frac{B_{}}{}\underset{i}{\overset{}{}}}$ i ${\displaystyle \underset{}{\overset{}{=}}}$ ${\displaystyle \underset{}{\overset{}{{}_{}}}}$ n ${\displaystyle \underset{}{\overset{}{B_{}}}\underset{}{\overset{}{{}_{}}}}$ ( ${\displaystyle x_{}}$i ) ${\displaystyle p}$ ( ${\displaystyle y}$ ${\displaystyle x{}_{}{i}_{}}$ )$（$ \ $display$style { $widehat${$p$} ( y$$B ) =$displayfrac {$1} {$w_{B}$} \ $sum _$ { i = 1$^{n_n_n_b$}($x_i)$입니다.ht는 인스턴스 상에서 ${\displaystyle {기능}_{}}$하며 w B $=$ ${\displaystyle \underset{}{xx}B}$ $w$(${\displaystyle }$x ) { displaystyle$w_{B$}=\$sum$_{$x\in$B}$w($x$)\}$^[7] 입니다.

알고리즘

Multiple Instance Learning에는 인스턴스 기반 및 메타데이터 기반 또는 임베디드 기반 알고리즘의 두 가지 주요 알고리즘이 있습니다."인스턴스 기반"이라는 용어는 알고리즘이 MI 가정에 기반하여 일련의 대표 사례를 찾고 이러한 대표로부터 미래 가방을 분류하려고 시도한다는 것을 나타낸다.반면 메타데이터 기반 알고리즘은 인스턴스와 가방라벨의 관계에 대한 가정을 하지 않고 ^[9]그 개념을 학습하기 위해 가방의 인스턴스에 의존하지 않는 정보(또는 메타데이터)를 추출하려고 합니다.일부 최신 MI 알고리즘에 대한 조사는 Foulds와 Frank를 참조하십시오.^[7]

인스턴스 기반 알고리즘

가장 먼저 제안된 MI 알고리즘은 Dietterich 등이 개발한 "반복-차별" 알고리즘과 Maron과 Lozano-Pérez가 ^[3][8]개발한 Diversity Density 알고리즘 세트였다.이 두 알고리즘 모두 표준 가정 하에서 작동했다.

반복 차별

일반적으로 모든 반복 식별 알고리즘은 2단계로 구성됩니다.첫 번째 단계는 각 양의 가방에서 최소 1개의 인스턴스가 포함되고 음의 가방에서 인스턴스가 없는 축 평행 직사각형(APR)을 키우는 것입니다.이것은 반복됩니다.긍정적인 백에 $랜덤인스턴스{\displaystyle {}_{}}$ x ${\displaystyle {1\mathrm{}}_{}{}_{}}$ B$$(\$displaystyle x_{1$}\$in$ B_${1$})에서$$ APR은 새로운 $포지티브백{\displaystyle {}_{}}$ $(\$의 $인스턴스{\displaystyle {}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$2(\$displaystyle x_{$2}})를 커버하는 최소 APR로 확장됩니다.각 포지티브 백에서 한 가지 예를 들 수 있습니다.그런 다음 APR에 포함된 각 $인스턴스{\displaystyle {}_{}}$ $($\displaystyle x_$$${i$})에는 APR에서 제외되는 마이너스 포인트의 수에 해당하는 "관련성"이 부여됩니다.다음으로 알고리즘은 APR에 네거티브백에 포함된 인스턴스가 포함되지 않을 때까지 관련성이 감소하는 순서대로 후보 대표 인스턴스를 선택합니다.알고리즘은 컨버전스가 이루어질 때까지 이러한 성장과 대표 선택 단계를 반복합니다.컨버전스에서는 각 반복에서의 APR 사이즈는 후보 대표만을 따릅니다.

첫 번째 단계 이후 APR에는 대표 속성만 촘촘히 포함되어 있다고 생각됩니다.두 번째 단계에서는 이 엄격한 APR이 다음과 같이 확장됩니다.가우스 분포는 각 Atribut을 중심으로 이루어지며 양의 인스턴스가 고정된 ^[4]확률로 엄격한 APR을 벗어나도록 느슨한 APR이 그려집니다.반복 식별 기법은 표준 가정에서는 잘 작동하지만 다른 MI ^[7]가정에서는 잘 일반화되지 않는다.

다양한 밀도

가장 단순한 형태로 Diversity Density(DD; 다양성 밀도)는 단일 $대표{\displaystyle {}^{}}$ 인스턴스 t ${\$ {\$displaystyle$ t$^{*}$를 개념으로 가정합니다.이 대표적인 인스턴스는 음의 가방보다 양의 가방의 인스턴스에 훨씬 가깝다는 점에서 "밀도"여야 하며, 각 양의 가방에서 적어도 하나의 인스턴스에 가깝다는 점에서 "다양"해야 한다.

$B{\displaystyle {\mathcal{}}^{}}$+ ${\displaystyle =}$ { ${\displaystyle {}_i^{}}$ + ${\displaystyle {}_{}^{}{}_{}^{}}$ ${\displaystyle {1\mathrm{}}_{}^{}}$ { $displaystyle${$mathcal${$$B } $=$ \ {$B_{i}^{+}\}_{1}^{m}$은(는) 양의 라벨이 붙은 봉투 세트이며${\displaystyle {,}^{}}$ B - ${\displaystyle =}$ { ${\displaystyle {}_i^{}}$ - ${\displaystyle {}_{}^{}{}_{}^{}}$ ${\displaystyle {1\mathrm{}}_{}^{}}$ { $style$ { $B$ } { - } = \ { $B$_ { $i$}^{ - } \ { $n$} = { B _ { i }$_$ { n } { n ${\displaystyle \stackrel{}{\}}}$ { n } $ly$ {\$lylylylylylylylylylylylylylylylyly$ bags bags bags bags bags bags bags bags bags bags bags bags bags bags bags bags bags bags bags bags bags bags bags bags bags bags bags bags bags bags bags bags$=\colon$ \$max _{t}DD($t$)$ 。$다양$한 밀도 ${\displaystyle D(}$t${\displaystyle )}$ =${\displaystyle P}$ ${\displaystyle r}$ ( ${\displaystyle t{\mathcal{}}^{}{\mathcal{}}^{}}$ + ,${\displaystyle {}^{}}$B -${\displaystyle }$) =${\displaystyle \arg }$ ${\displaystyle \underset{}{max}}$ max t${\displaystyle \underset{}{}\underset{\mathrm{i}}{\overset{}{}}}$ i${\displaystyle \underset{}{\overset{}{}}}$= ${\displaystyle \underset{}{\overset{}{}}}$ m${\displaystyle }$P ${\displaystyle r}$ ( ${\displaystyle t{}_{}^{}}$ ${\displaystyle B_{}^{}}$i +${\displaystyle \underset{}{\overset{}{}}}$) ${\displaystyle \underset{}{\overset{}{}}}$ i${\displaystyle \underset{}{\overset{}{}}}$= 1 ${\displaystyle \underset{}{\overset{}{}}P}$ ${\displaystyle r}$ ( $t$-$$) $styleft$（$t ）$ （ t ） =$ight)\param$ _${i=1}^{n}Pr\left(t$ B_${i}^{-}\right)$는 개념 t ${\$ {{$displaystyle$ t$^\{*\}\}\}\}$에 따라 가방이 독립적으로 분산된다고 가정합니다.${\displaystyle {\mathrm{Bi}}_{}}$j {$displaystyle B_{ij}$는 noise-or 모델의 j번째 인스턴스를 나타냅니다.

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

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

${\displaystyle P}$( ${\displaystyle t}$ ${\displaystyle B{}_{}}$ ${\displaystyle i_{}}$j$$) { $display$ P${\displaystyle }$( t ${\displaystyle B_{}}$$$_ { ${\displaystyle {\mathrm{ij}}_{}}$} ${\displaystyle \mathrm{exp<img\; alt="\{\backslash displaystyle\; P(t|B\_\{ij\})\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/37c2b3026d853e9ba3f40abae09e76ddef22678a"\; style="vertical-align:\; -1.005ex;\; width:8.282ex;\; height:3.009ex;">}}$ $exp{\displaystyle (}$ ( -${\displaystyle \underset{}{}{}_{}^{}}$ k${\displaystyle {{}_{}}^{}{\mathrm{}}_{}^{}}$ ${\displaystyle {k{}_{}}^{}{}_{}^{}{}^{}}$-${\displaystyle {}^{}}$( ${\displaystyle {B_{}}^{}}$ i${\displaystyle {{}_{}{}_{}{j}_{}}^{}}$ )${\displaystyle {{}_{}}^{\mathrm{}}}$ ) 2$$) \ $display P$( t$B$_ { $ij$} \ $proto \$ ${ sum }$$_{k}\right)^{2}\right}$ $여기$서 s $=$ ( ${\displaystyle {}_{}{k}_{}}$) {$displaystyle$ s=($s_{k})$는 스케일링 벡터입니다.이렇게 하면 모든 포지티브백에 인스턴스가 t${displaystyle$ t$\}$에 가까운 $경우{\displaystyle }$ ${\displaystyle \mathrm{Pr}}$( ${\displaystyle t_{}^{}}$Bi ${\displaystyle {}_{}^{}}$ $)($${\displaystyle t}$ $B_{i$$\}^+)$는 각$i$에 대해 높아지지만, $네거티브백{\displaystyle {}_{}^{Bi}}$- \$displaystyle B_{$i}^{-}}에$$ $가까운{\displaystyle }$ 인스턴스가 $있는{\displaystyle }$ 경우(\$displaystyle$ tyle$$${\displaystyle t)<img\; alt="t"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/65658b7b223af9e1acc877d848888ecdb4466560"\; style="vertical-align:\; -0.338ex;\; width:0.84ex;\; height:2.009ex;">}$${\displaystyle B_{}^{}}$i -$)({displaystyle$ Pr$(t$ B_${i}^{-})$가 낮습니다.${\displaystyle \mathrm{따라서}}$ D${\displaystyle }$D${\displaystyle (}$ $)$ {$displaystyle$ DD$(t)}$는 모든 포지티브백의 인스턴스가 t${displaystyle$ t$}$에 가깝고 네거티브백의 인스턴스가 t${displaystyle$ t$\}$에 가깝지 않은 경우에만 하이입니다.후보 $콘셉트{\displaystyle \stackrel{}{}}$t$$^ $displaystyle$ {$t}$은$($는) 그라데이션 방법을 통해 얻을 수 있습니다.새 가방의 분류는 t$^(\$^[8]와의 근접성을 평가하여 수행할 수 있습니다. Diversity Density는 원래 1998년 Maron 등에 의해 제안되었지만, 보다 최근의 MIL 알고리즘은 2001년 EM-DD, ^[13]2004년 DD-SVM, 2006년 MIILES 등 DD 프레임워크를 사용합니다.

다수의 단일 인스턴스 알고리즘이 표준 가정 하에서 다중 인스턴스 컨텍스트에 적응되어 있습니다.

• 서포트 벡터 머신^[14]
• 인공신경망^[15]
• 의사결정 트리^[16]
• 부스팅^[17]

2000년 이후,^[9] 위에 열거된 보다 일반적인 가정을 다루기 위해 설계된 알고리즘의 개발과 표준 가정으로부터 벗어나는 움직임이 있었다.

• Weidmann은 카운트 기반 가정 하에서 개념을 학습하기 위해 TLC(Two-Level Classification) 알고리즘을 제안한다.첫 번째 단계에서는 트레이닝 세트의 각 백에 각 인스턴스의 Decision Tree를 구축함으로써 인스턴스 수준의 개념을 학습합니다.다음으로 각 가방은 결정 트리 내의 카운트에 근거해 특징 벡터에 매핑된다.두 번째 단계에서는 단일 인스턴스 알고리즘이 특징 벡터 상에서 실행되어 개념을 학습한다.
• Scott 등은 2005년에 GMIL 가정 하에서 개념을 학습하기 위한 알고리즘인 GMIL-1을 제안했다.GMIL-1은 모든 축-평행 ${\displaystyle {}_{}}{\displaystyle }${${\displaystyle R_{}{}_i}$ ${\displaystyle {\}}_{}}$ i$$ I {\$style \{R_{i}\}_${i\$in$I}를 인스턴스의 원래 공간에 열거하여 부울 벡터의 새로운 특징 공간을 정의합니다.$가방{\displaystyle }$ B$({displaystyle$ B$}$는 이 새로운 피쳐 공간에서 벡터 b${\displaystyle =}$($bi$ ${\displaystyle i_{}}$($b_{i}) _{i\in$I}에 매핑됩니다. $여기$서 ${\displaystyle {bi}_{}}$ ${\displaystyle {}_{}}$ $({displaystyle$ B_i} $=1}$ i$$(${\displaystyle {APR}_{}}$ I$${\$displaystyle R_{i$})가$B$를 덮는 벡터 $b{\displaystyle \mathbf{}}$b_i$)$에 매핑됩니다.그런 다음 단일 인스턴스 알고리즘을 적용하여 이 새로운 기능 공간에서 개념을 학습할 수 있습니다.

새로운 피쳐 공간의 높은 차원성과 원래 인스턴스 공간의 모든 APR을 명시적으로 열거하는 비용 때문에 GMIL-1은 계산과 메모리 측면에서 모두 비효율적입니다.GMIL-2는 효율을 개선하기 위해 GMIL-1의 정제법으로 개발되었습니다.GMIL-2는 후보 대표 인스턴스 세트를 찾기 위해 인스턴스를 사전 처리합니다.그런 다음 GMIL-2는 각 백을 GMIL-1과 같이 부울 벡터에 매핑하지만 후보 대표 인스턴스의 고유한 서브셋에 대응하는 APR만 고려합니다.이것에 의해, 메모리와 계산의 ^[7]요건이 큰폭으로 삭감됩니다.

• Xu(2003)는 집단 가정 하에서 개념을 배우기 위해 로지스틱 회귀 및 부스트 방법에 기초한 몇 가지 알고리즘을 제안했다.

메타데이터 기반(또는 임베디드 기반) 알고리즘

메타데이터 기반 알고리즘은 각 백을 메타데이터의 특징 벡터에 매핑함으로써 실제 분류 태스크를 수행하기 위해 임의의 단일 인스턴스 알고리즘을 사용하는 유연성을 가능하게 한다.미래의 가방은 단순히 메타데이터의 특징 공간에 매핑(삽입)되고 선택된 분류기로 라벨이 지정됩니다.따라서 메타데이터 기반 알고리즘의 대부분은 어떤 기능 또는 어떤 유형의 임베딩이 효과적인 분류로 이어지는지에 초점을 맞추고 있습니다.전술한 알고리즘의 일부(TLC나 GMIL 등)는 메타데이터 베이스로 간주될 가능성이 있습니다.

• 한 가지 방법은 각 가방의 메타데이터가 가방 내의 인스턴스에 대한 통계 집합이 되도록 하는 것입니다.심플한MI 알고리즘은 이 접근방식을 채택합니다.예를 들어 가방 내의 모든 인스턴스에 대해 취득되는 각 인스턴스 변수의 평균 또는 최소 및 최대값과 같은 가방의 메타데이터는 단순한 요약 통계량으로 간주됩니다.더 복잡한 통계를 사용하는 다른 알고리즘도 있지만,MI는 복잡성이 분명히 ^[7]낮음에도 불구하고 다수의 데이터셋에 대해 놀라울 정도로 경쟁력이 있는 것으로 나타났습니다.
• 또 다른 일반적인 접근법은 가방 자체의 기하학적 구조를 메타데이터로 간주하는 것입니다.이것은 MIGraph 알고리즘과 miGraph 알고리즘에 의해 채택된 접근법입니다.이 알고리즘은 각 백을 백 내의 노드가 인스턴스인 그래프로 나타냅니다.대응하는 인스턴스 간의 거리(인스턴스 공간의 일부 메트릭까지)가 임계값보다 작을 경우 두 노드 사이에 엣지가 있습니다.분류는 그래프 커널이 있는 SVM을 통해 이루어집니다(MIGraph와 miGraph는 ^[7]커널 선택이 다를 뿐입니다).MIILES와 ^[19]MInD에서도 비슷한 접근방식을 취하고 있습니다.MIRES는 교육 세트의 인스턴스와의 유사성으로 가방을 나타내며, MInD는 다른 가방과의 거리로 가방을 나타냅니다.
• 가방과 메타데이터 기능 간의 매핑은 명시적이지 않지만 k-nearest neighbors(kNN)의 수정은 기하학적 메타데이터를 사용하는 메타데이터 기반 알고리즘으로 간주할 수도 있습니다.그러나 가방 사이의 거리를 계산하는 데 사용되는 메트릭을 지정해야 합니다.Wang과 Zucker(2000)는$$ $A$와 $가방 B$의 하우스도르프 메트릭(각각 $최대값$과 최소값$)$을 제안합니다$.$

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

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

이들은 kNN의 두 가지 변형인 Basian-kNN과 quotation-kNN을 다중 인스턴스 설정에 대한 기존의 가장 가까운 네이버 문제의 적응으로 정의합니다.

일반화

지금까지 이 문서에서는 바이너리 분류자의 맥락에서만 다중 인스턴스 학습을 검토했습니다.단, 단일 인스턴스 바이너리 분류자의 일반화는 여러 인스턴스의 경우로 넘어갈 수 있습니다.

• 이러한 일반화 중 하나는 MIML(Multiple-Instance Multiple-Label Problem)입니다.각 가방은 라벨 공간의 서브셋과 관련지을 수 있습니다.라벨의 특성을 형식적으로, 만약 X{\displaystyle{{X\mathcal}}}은 공간과 Y{\displaystyle{{Y\mathcal}}}는 우주, MIML 개념 지도가 있어 c:NX2Y{\displaystyle c:\mathbb{N}^{{X\mathcal}→}\rightarrow 2^{{Y\mathcal}}}. 주, 장[21]은 MIML에 대한 해결책을 제안하(2006년). 프로blem은 멀티플렉스 또는 멀티컨셉트 문제 중 하나로 감소합니다.
• 또 하나의 분명한 일반화는 다중 인스턴스 회귀입니다.여기서 각 가방은 표준 회귀와 같이 단일 실수에 관련지어진다.표준 가정과 마찬가지로 MI 회귀 분석에서는 각 가방에 "프라임 인스턴스"라고 불리는 인스턴스가 하나 있다고 가정합니다. 이 인스턴스는 가방의 라벨을 결정합니다(노이즈까지).MI 회귀 분석의 이상적인 목표는 각 가방의 주요 인스턴스의 제곱 손실을 최소화하는 하이퍼플레인을 찾는 것이지만 주요 인스턴스는 숨겨져 있습니다.실제로 Ray와 Page(2001)는 가방당 인스턴스가 3개 미만일 경우 각 가방에서 하나의 인스턴스에 맞는 최적의 하이퍼플레인 찾기가 어렵고 대신 근사 알고리즘을 개발한다는 것을 보여준다.MI 분류를 위해 개발된 알고리즘의 대부분은 MI ^[7]회귀 문제에 대한 근사치를 제공할 수도 있다.

「 」를 참조해 주세요.

• 지도 학습
• 다중 라벨 분류

레퍼런스

추가 정보

MIL 문헌에 대한 최근 리뷰에는 다음이 포함됩니다.

• Amores(2013)는 다양한 패러다임의 광범위한 검토 및 비교 연구를 제공한다.
• Foulds & Frank (2010) - 문헌의 다양한 패러다임에 의해 사용되는 다양한 가정을 철저히 검토합니다.
• Dietterich, Thomas G; Lathrop, Richard H; Lozano-Pérez, Tomás (1997). "Solving the multiple instance problem with axis-parallel rectangles". Artificial Intelligence. 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ó, Dánel; Vluymans, Sarah (2016). Multiple Instance Learning. doi:10.1007/978-3-319-47759-6. ISBN 978-3-319-47758-9. S2CID 24047205.
• Amores, Jaume (2013). "Multiple instance classification: Review, taxonomy and comparative study". Artificial Intelligence. 201: 81–105. doi:10.1016/j.artint.2013.06.003.
• Foulds, James; Frank, Eibe (2010). "A review of multi-instance learning assumptions". 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). "Integrated segmentation and recognition of hand-printed numerals". Proceedings of the 1990 Conference on Advances in Neural Information Processing Systems (NIPS 3). pp. 557–563. ISBN 978-1-55860-184-0.
• Li, Hong-Dong; Menon, Rajasree; Omenn, Gilbert S; Guan, Yuanfang (2014). "The emerging era of genomic data integration for analyzing splice isoform function". 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). "Systematically Differentiating Functions for Alternatively Spliced Isoforms through Integrating RNA-seq Data". PLOS Computational Biology. 9 (11): e1003314. Bibcode:2013PLSCB...9E3314E. doi:10.1371/journal.pcbi.1003314. PMC 3820534. PMID 24244129.
• Maron, O.; Ratan, A.L. (1998). "Multiple-instance learning for natural scene classification". Proceedings of the Fifteenth International Conference on Machine Learning. pp. 341–349. ISBN 978-1-55860-556-5.
• Kotzias, Dimitrios; Denil, Misha; De Freitas, Nando; Smyth, Padhraic (2015). "From Group to Individual Labels Using Deep Features". Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD '15. pp. 597–606. doi:10.1145/2783258.2783380. ISBN 9781450336642. S2CID 7729996.
• Ray, Soumya; Page, David (2001). Multiple instance regression (PDF). ICML.
• Bandyopadhyay, Sanghamitra; Ghosh, Dip; Mitra, Ramkrishna; Zhao, Zhongming (2015). "MBSTAR: Multiple instance learning for predicting specific functional binding sites in microRNA targets". 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). "Deep Multi-instance Networks with Sparse Label Assignment for Whole Mammogram Classification". 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.