Multiple Instance Learning: Algorithms and Applications (2008)

Cold Ui·2023년 2월 15일

Abstract

기존 지도 학습에는 입력과 해당 레이블로 구성된 훈련 데이터 세트가 필요합니다. 그러나 많은
애플리케이션에서 레이블을 입력에 정확하고 일관되게 할당하는 것이 어렵거나 심지어 불가능합니다. Multiple Instance Learning이라는 비교적 새로운 학습 패러다임을 사용하면 모호하게 레이블이 지정된 데이터에서 분류기를 교육할 수 있습니다. 이 패러다임은 지난 몇 년 동안 많은 관심을 받아 왔으며 여러 도메인(예: 컴퓨터 비전, 컴퓨터 오디션, 생물 정보학, 텍스트 처리)에서 많은 유용한 응용 프로그램을 가지고 있습니다. 이 보고서에서는 이 문제를 해결하기 위해 제안된 몇 가지 대표적인 알고리즘을 검토합니다. 또한 여러 기존 및 잠재적 응용 프로그램과 현재 사용 가능한 알고리즘이 이러한 응용 프로그램에서 제시하는 문제를 얼마나 잘 해결하는지에 대해 논의합니다.

1. Introduce

전통적인 감독 학습에서 입력 및 출력/레이블 쌍으로 구성된 훈련 데이터 세트는 새로운 입력에 대한 출력/레이블을 예측할 수 있는 분류기를 구성하는 데 사용됩니다[1, 2]. 이 문제에 대한 강력한 알고리즘을 개발하기 위해 엄청난 양의 이론 및 실제 작업이 진행되었습니다.
그러나 교육 데이터의 입력/레이블 쌍 요구 사항은 특정 응용 프로그램에서 놀라울 정도로 금지되어 있으며 최근 연구에서는 학습을 위한 보다 유연한 패러다임 개발에 중점을 두었습니다. 이 백서에서는 여러 애플리케이션 도메인에서 유용한 도구로 부상하고 있는 다중 인스턴스 학습(MIL) 패러다임에 중점을 둡니다. 이 패러다임에서 데이터는 레이블이 할당되는 방식에 약간의 모호성이 있다고 가정합니다. 특히 학습 알고리즘에 입력/레이블 쌍을 제공하는 대신 레이블이 입력 세트 또는 백에 할당됩니다.
레이블을 바이너리로 제한하는 MIL 가정은 모든 포지티브 백에 적어도 하나의 포지티브 입력이 포함된다는 것입니다. 실제 입력 레이블은 훈련 중에 알 수 없기 때문에 잠재 변수로 생각할 수 있습니다.

그림 1에 설명된 MIL 문제의 다음 간단한 예([3]에서 채택)를 고려하십시오. 여러 명의 교수진이 있으며 각각 몇 개의 키가 포함된 키 체인을 소유합니다.
이 교수진 중 일부는 특정 방에 들어갈 수 있고 일부는 그렇지 않다는 것을 알고 있습니다.
그런 다음 작업은 특정 키 또는 특정 키 체인이 당신을 이 방으로 데려갈 수 있는지 예측하는 것입니다. 이를 해결하기 위해 우리는 모든 "긍정적" 키 체인이 공통적으로 가지고 있는 키를 찾아야 합니다. 이 키를 올바르게 식별할 수 있으면 필요한 키를 포함하거나 포함하지 않는 전체 키 체인을 올바르게 분류할 수도 있습니다.

MIL의 정신은 Keeler et al. 훈련 중에 손으로 쓴 숫자의 최상의 분할을 찾는 신경망 알고리즘을 설계했습니다[4]. 즉, 숫자 레이블은 잘린 이미지가 아니라 숫자 이미지의 가능한 모든 (블록) 분할에 할당되었습니다. 아이디어는 더욱 발전되었고 실제 용어는 [3]에서 Dietterich et al에 의해 만들어졌습니다. 이 작업에 영감을 준 문제는 분자의 일부 속성이 모양 통계에서 예측되어야 하는 약물 발견 문제였습니다. 모호성은 각 분자가 여러 가지 다른 모양으로 뒤틀리고 구부러질 수 있고 어떤 모양이 특정 속성을 담당하는지 알 수 없기 때문에 작용합니다(그림 4 참조). 섹션 3에서 우리는 MIL 패러다임에 맞는 더 많은 흥미로운 응용 프로그램을 보게 될 것입니다.

MIL은 최근 몇 년 동안 점점 더 많은 관심을 받고 있지만 문제는 여전히 상당히 미개발 상태이며 많은 흥미로운 공개 질문이 있습니다. 이 보고서의 목표는 몇 가지 흥미로운 응용 프로그램뿐만 아니라 MIL을 위한 몇 가지 대표적인 알고리즘에 대한 검토를 제공하는 것입니다.
마지막으로 기존 알고리즘이 응용 프로그램에서 제시한 문제를 얼마나 잘 해결하는지 논의하고 향후 연구를 위한 잠재적인 방법을 지적합니다.

2. Algorithms

이 섹션의 목적은 MIL 문제를 공식적으로 정의하고 MIL을 해결하기 위해 널리 사용되는 알고리즘을 검토하는 것입니다. 명확성을 위해 기존의 모든 메소드를 계층으로 나누는 것이 유용하지만, 일반적으로 그렇듯이 다양한 메소드가 여러 방식으로 중첩되므로 불가능합니다. 감독 학습과 마찬가지로 MIL 교육 절차에는 두 가지 기본 요소가 필요합니다: 비용 함수(예: 0/1 손실, 우도) 및 해당 비용 함수를 최적화하는 분류기를 찾는 방법(예: 경사 하강법, 휴리스틱 검색). 우리는 이전 기준에 따라 방법을 분할하여 이 검토를 구조화하기로 선택했지만 최적화 절차 측면에서 실제로 매우 유사한 비용 함수가 다른 방법이 있다는 점에 유의해야 합니다. 다음으로 MIL 문제를 공식적으로 정의하고 MIL을 해결하는 가장 기본적인 방법과 일부 PAC 알고리즘 및 이론적 결과를 검토합니다. 마지막으로 최대 우도 및 최대 마진 MIL 알고리즘을 검토하면서 결론을 내립니다.

2.1 Problem Statement

문제를 공식적으로 설명하고 이 섹션의 나머지 부분에서 사용할 표기법을 설정하는 것으로 시작합니다. MIL을 표준 지도 학습과 비교하는 것이 유용하고 대부분의 MIL 알고리즘이 잘 알려진 지도 학습 알고리즘에서 파생되기 때문에 먼저 지도 학습에 대한 표기법을 설정합니다. 학습 데이터는 인스턴스 예 {x1, x2, ...,xn} 및 레이블 {y1, y2, ...,yn}로 구성되며 여기서 x_i ∈ X 및 y_i ∈ Y입니다.

일반적으로 X = R^d는 d-차원 유클리드 공간이고 Y = {0, 1}입니다. 감독 학습의 목표는 새로운 인스턴스 x에 대한 레이블 y를 정확하게 예측하는 분류기 함수 h(X) : X → Y를 훈련하는 것입니다. 반면에 다중 인스턴스 학습에서 훈련 세트는 가방 {X1, X2, ... , Xn}과 가방 라벨 {y1, y2, ... , yn}로 구성되며 여기서 X_i = {x_i1, x_i2, x_im}, x_ij ∈ X 및 y_i∈ {0, 1}입니다.(편의상 y' = (2y −1) ∈ {−1, +1}로도 정의합니다.)

MIL 문제는 이진 사례에 대해서만 정의됩니다(확장도 탐색되었지만 [5, 6]). 단순화를 위해 X = R^d라고 가정합니다. 또한 대부분의 알고리즘에서는 필요하지 않지만 모든 가방의 크기가 고정되어 있다고 가정합니다.

앞에서 언급한 바와 같이 MIL의 기본 가정은 해당 백의 인스턴스 중 적어도 하나가 양성이면 백이 양성이라는 것입니다(양성 백 내부의 참 양성 인스턴스는 때때로 "증인" 또는 "키"라고 합니다. ”). 즉, 인스턴스 레이블 y_ij ∈ {0, 1}이 각 인스턴스에 대해 존재하지만 학습 중에는 알 수 없다고 가정합니다. 우리는 이것들을 잠재 변수라고 생각할 수 있습니다.
MIL 가정은 다음과 같이 요약될 수 있습니다.:

이것을 작성하는 또 다른 방법은 다음과 같습니다.:

이것은 약간 덜 직관적이지만 나중에 유용할 것입니다.
MIL의 목표는 인스턴스 분류기 h(X) : X → Y 또는 백 분류기 H(X) : X^m → Y를 훈련시키는 것입니다. 그러나 백 분류자는 올바른 인스턴스 분류자로 쉽게 구성할 수 있습니다: H(X_i) = max_j h(x_ij ). 따라서 몇 가지 예외[7, 8]를 제외하고 대부분의 MIL 알고리즘은 인스턴스 분류기를 학습하는 것을 목표로 합니다.

2.2 Naive MIL

아마도 MIL 문제를 해결하는 가장 간단한 방법은 가방 레이블 y_i와 동일한 인스턴스 레이블 y_ij를 생성하는 것입니다. 네거티브 백의 경우 네거티브 백의 모든 인스턴스가 네거티브이기 때문에 생성된 인스턴스 레이블이 올바릅니다. 그러나 포지티브 백에는 포지티브 인스턴스와 네거티브 인스턴스가 모두 포함될 수 있으며 이러한 접근 방식은 필연적으로 네거티브 인스턴스에 포지티브 레이블을 지정하게 됩니다.

여전히 질문은 남아 있습니다. 표준 감독 학습 알고리즘이 MIL 알고리즘과 비교할 수 있게 수행할 수 있습니까? 많은 논문에서 이 문제를 조사했으며 MIL 프레임워크를 사용하면 성능이 향상된다는 다양한 데이터 세트 및 알고리즘(지도 및 MIL 모두)에 대해 나타났습니다[3, 9, 10, 11]. MIL 알고리즘은 실제로 이 "Naive MIL" 접근 방식을 훨씬 능가하는 경향이 있습니다. 그럼에도 불구하고 이것은 고려해야 할 중요한 시나리오이며 이와 유사한 접근 방식이 흥미로운 이론적 결과로 이어지는 것을 보게 될 것입니다.

2.3 PAC Algorithms and Bounds

2.3 PAC 알고리즘 및 범위
MIL에 대한 초기 작업은 이론적 결과를 보다 쉽게 도출할 수 있는 축 정렬 사각형과 같은 간단한 알고리즘에 중점을 두었습니다[12, 13]. 특히 몇몇 연구자들은 PAC(Probably Approximately Correct) [14] 학습 알고리즘을 개발하고 샘플 복잡도 범위를 보여주는 데 집중했습니다. PAC의 기본 아이디어는 일부 training 데이터가 주어지면 특정 학습 알고리즘이 높은 확률로 정확한 분류자를 생성한다는 것을 증명하는 것입니다. 공식적으로 small 입실론과 δ에 대해 P[err(h) > 입실론] < δ이며 여기서 err(h)는 보이지 않는 데이터에 대한 분류기 h의 오류입니다. 이 프레임워크를 사용하면 확률이 높은 오류를 달성하는 데 필요한 데이터의 양을 대략적으로 보여줄 수 있습니다. 이를 종종 샘플 복잡성이라고 합니다. 이러한 결과에 도달하기 위해 이러한 알고리즘은 일반적으로 데이터에 대해 몇 가지 가정을 해야 합니다. 감독 학습의 경우 가장 일반적인 가정은 인스턴스가 일부 분포에서 i.i.d.(독립 항등 분포)로 그려진다는 것입니다.
MIL의 경우 유사한 가정이 있습니다. 모든 인스턴스가 일부 분포에서 i.i.d.로 추출된 다음 무작위로 가방에 배치된다고 가정합니다. 이는 하나의 백에 있는 인스턴스가 특별한 관계가 없음을 의미합니다. 이것은 매우 중요한 가정이며 그것이 적용되는 경우와 적용되지 않는 경우에 대해 섹션 4에서 논의할 것입니다.

Blum [15]은 감독 학습과 MIL 간의 흥미로운 관계를 보여주는 놀랍도록 간단한 알고리즘을 제안했습니다. 그의 알고리즘의 기본 아이디어는 다음과 같습니다. 네거티브 백의 경우 모든 인스턴스에 네거티브 인스턴스 레이블을 할당합니다. 포지티브 백의 경우 백당 임의로 하나의 인스턴스를 선택하고 포지티브 인스턴스 레이블을 할당합니다. 마지막으로 이러한 인스턴스/레이블 쌍을 노이즈 허용 학습 알고리즘에 연결합니다[16]. 이는 이전 섹션에서 논의한 Naive MIL 접근 방식과 유사합니다. 이 알고리즘의 핵심은 양성 인스턴스가 항상 올바른 레이블을 갖는다는 것입니다. 그러나 부정적인 인스턴스는 긍정적인 레이블이 지정될 수 있습니다(긍정적인 백에서 나온 경우). 따라서 우리가 생성하는 데이터 세트에는 비대칭 레이블 노이즈가 있습니다. 이러한 감소를 통해 Blum은 노이즈로 학습 가능한 PAC 개념 클래스가 MIL에서도 PAC 학습 가능함을 보여줍니다. 최고의 샘플 복잡성 범위는 Blum 때문이기도 합니다. 이 알고리즘은 위의 것보다 더 정교한 확장이며 통계 쿼리 프레임워크[16](Kearns 등의 noise-tolerant(허용) 학습을 위한 PAC 범위를 증명하는 데 사용됨)를 사용합니다. 이 MIL 알고리즘의 샘플 복잡도 범위는 빅오 O(d^2m / 입실론^2)입니다.
이것은 E(앱실론)가 감소하고 차원 d가 증가하고 가방 크기 m이 증가함에 따라 학습이 더 어려워진다는 것을 의미합니다.

Blum의 알고리즘이 MIL에 대해 가장 잘 알려진 PAC 범위를 달성했지만 분명히 실용적인 알고리즘은 아닙니다. 큰 가방 크기 m의 경우 본질적으로 방대한 양의 데이터를 버릴 것입니다. 그러나 이 알고리즘은 지도 학습과 MIL 간의 관계를 강조하기 때문에 연구하기에 흥미롭습니다. 아래 섹션에서 검토하는 알고리즘은 일반적으로 알려진 이론적 속성이 적지만 더 실용적이며 어려운 데이터에서 잘 수행되는 것으로 나타났습니다.

2.4 Maximum Likelihood

우리가 논의할 실용적인 MIL 알고리즘의 첫 번째 범주는 데이터의 우도를 최대화하는 분류기를 훈련하는 것을 목표로 합니다. 최대 우도 방법은 감독 학습에서 널리 사용되며 간단한 검토로 시작합니다. 각 인스턴스 x_i와 분류기 h에 대해 p_i ≡ P(y_i = 1|x_i, h)를 해당 인스턴스의 사후 확률로 둡니다. 이 엔터티의 정확한 정의는 분류기에 따라 달라집니다. 로그 우도는 다음과 같이 정의됩니다.

MIL에 대해 이 손실 함수를 적용하려면 인스턴스 레이블에 대한 의존성을 제거해야 합니다. 이는 훈련 중에 알려지지 않았기 때문입니다. 대신, 우리는 p_i ≡ P(y_i = 1|X_i, h)를 백의 사후 확률로 하고 p_ij ≡ P(y_ij = 1|x_ij , h)를 인스턴스의 사후 확률로 둡니다. 로그 가능성에 대한 방정식은 동일하게 유지되지만 p_i는 이제 가방 확률입니다. 이전과 마찬가지로 p_ij의 정확한 정의는 분류기에 따라 달라집니다.

마지막으로 가방 확률 p_i를 인스턴스 p_ij의 확률에 연결해야 합니다. 이 관계를 정의하는 자연스러운 방법은 다음과 같습니다.

위의 내용은 Eqn 2의 확률적 등가물로 간주할 수 있습니다. 중요한 관찰은 최대 연산자가 미분 가능하지 않다는 것입니다. 이는 MIL에 대한 로그 우도가 미분 가능하지 않음을 의미합니다. 이것은 지도 학습에서 대부분의 최대 우도 방법이 손실 함수의 평활성을 이용하여 어떤 형태의 경사 하강법을 수행하기 때문에 상당한 문제를 제시합니다. 다행스럽게도 최대 연산자에 대한 몇 가지 미분 가능한 근사치가 문헌에 존재합니다. 이러한 근사치에 대한 검토를 계속합니다.

2.4.1 Differentiable Max Approximations

미분 가능한 최대 근사치
이제 소프트맥스라고 하는 최대값의 미분 가능한 근사치에 대한 개요를 제시합니다. 일반적인 아이디어는 다음과 같이 미분 가능 함수 g_l(vl)에 의해 {v1, v2,...,vm}에 대한 최대값을 근사하는 것입니다.

직관적으로 v_i가 고유한 최대값인 경우 v_i를 변경하면 동일한 양만큼 최대값이 변경되고, 그렇지 않으면 vi를 변경해도 최대값에 영향을 주지 않습니다.

g에 대한 많은 근사치가 제안되었습니다. 여기에서 사용된 선택 사항을 표 2에 요약했습니다: LSE(log-sum-exponential), GM(generalized mean), NOR(noise-or) 및 ISR 모델의 변형. MIL 내에서 이러한 다양한 선택의 실험적 비교를 위해 우리는 독자를 참조합니다.
그림 2에서 v ∈ [0, 1]에 대해 (v, 1 - v)에 적용된 다양한 모델을 보여줍니다.

LSE와 GM은 각각 선명도와 정확도를 제어하는 매개변수 r을 가지고 있습니다. g_l(v_l) → v∗ 같이 r → ∞ (큰 r은 수치적 불안정성을 초래할 수 있음에 유의하십시오). LSE의 경우 v∗ − log(m)/r ≤ g_l(v_l) ≤ v∗[17]임을 표시할 수 있고 GM의 경우 (1/m)^(1/r)v∗ ≤ g_l(v_l) ≤ v∗임을 표시할 수 있습니다. ∗, 여기서 m = |v_l|.
NOR 및 ISR은 [0, 1]에 대해서만 정의됩니다. 둘 다 확률적 해석을 가지고 있으며 실제로 잘 작동합니다. 그러나 이러한 모델은 작은 m(g_l(v_l) → 1 as m → ∞에 가장 적합합니다. 마지막으로 모든 모델은 m = 1에 대해 정확하고 ∀l v_l ∈ [0, 1]이면 모든 모델에 대해 0 ≤ g_l(v_l) ≤ 1입니다.

이제 우리는 MIL에 대한 몇 가지 특정 최대 우도 알고리즘을 검토할 준비가 되었습니다. 각각에 대해 분류기 h와 인스턴스 확률 p_ij를 h로 정의합니다.