Introduction
이 포스팅에서는 multi-label 문제에서 각 metric(precsion at k, 혹은 recall at k)에 따라 사용해야 하는 적합한 reduction 방법과 loss들을 알아보려고 한다. 이 글의 전개는
- Multi-label이 어떤 문제인지,
- 각 metric을 높이는 scorer가 어떤 것인지,
- multi-label에서 사용할 수 있는 reduction 방법과 loss들은 어떤 것이 있는지,
- 각 reduction과 loss의 조합에 따른 optimal scorer를 어떤 것인지 알아볼 것이다.
결과적으로, 특정 reduction 방법과 loss의 조합을 사용하면, scorer는 precision at k 혹은 recall at k를 높이는 방향으로 학습되게 된다는 것을 알 수 있다.
Multi-label classification
Multi-label classification은 multi classification 문제와 혼동될 수 있는데 다음 그림이 둘의 차이를 잘 설명해주고 있다.
Multi-class는 class가 세 개 이상이며, 각 샘플들이 하나의 class에만 속할 수 있는 상황을 말한다. 반면, multi-label은 각 샘플의 레이블이 1개 이상일 수 있는 상황을 말한다.
multi-label 문제로서 하나의 샘플 x에 대해 가능한 레이블이 y₀, y₁인 상황을 가정해보자. 이 상황에서의 샘플 하나에 대해 가능한 상황들은 다음과 같은 4가지 케이스가 있다. x는 해당 레이블에 속하지 않았다는 것을 의미하고, o는 해당 레이블에 속한다는 것을 의미한다.
표 안의 4가지 사건들은 샘플 하나에 대해서 일어날 수 모든 사건들(표본 공간)이다. 주어진 샘플에 대해서 위 각각의 케이스에 따라 모확률이 존재할 것이며, 딥러닝 모델은 그 확률을 추정하려 할 것이다.
추후 예시를 들 때의 편의를 위하여, 이 포스팅의 대표 예시로서 하나의 샘플 x에 대해 다음과 같은 모확률을 가정하자.
일반적으로 multi-label 문제는 레이블이 적어도 하나 존재하는 상황을 가정하므로 xx가 일어날 확률은 0으로 가정했다. 위의 예시대로 모확률이 존재한다면, 우리가 x에 대한 실험을 100번 한다면, xx는 0번 xo는 10번, ox는 60번, oo는 30번 정도 나올 것으로 예상할 수 있다. 또, x에 대해서 각 레이블이 등장할 확률을 구한다면, ℙ(y₀=1|x) = 0.9, ℙ(y₁=1|x)=0.4임을 알 수 있다.
How to train
위 예시에 맞는 모델의 아웃풋 레이어의 출력을 생각해보자. 가장 간단한 방법은 출력 벡터의 크기를 4로 하여 각각의 사건의 확률을 추정하는 것이다. 그 후 가장 높은 확률을 가진 사건을 결과로서 출력하면 될 것이다.
하지만 가능한 레이블의 개수(현재는 2개, y₀, y₁)가 늘어나게 된다면 아웃풋 레이어의 벡터의 크기는 2ˡ 으로 증가해야한다(여기서 l은 레이블의 개수). Multi-label 문제에서 레이블 개수가 100, 1000개 혹은 그 이상으로 증가할 수 있음을 생각하면, 이는 별로 좋은 선택은 아니다.
이 방법 외에 선택할 수 있는 방법은 아웃풋 레이어의 출력 벡터의 크기를 레이블의 개수로 축소하고 binary나 multi-class 문제처럼 만들어 해결하는 것이다(reduction). 출력 벡터의 크기 레이블 개수만큼으로 축소한 뒤 score가 높은 레이블들을 특정 기준에 따라 선택하여출력하면 멀티 레이블 문제를 어느 정도 해결할 수 있다.
여기서 특정 기준이란 상위 k개의 확률을 가진 레이블을 출력한다거나, 특정 확률값을 넘은 레이블들을 출력하는 방법이 있으며, 이 포스팅에서는 상위 k개의 확률을 가진 레이블을 출력하는 것 위주로 살펴볼 것이다.
Notation
뒤이어 나올 formula들을 표현하기 위해 먼저 몇 가지 notation들을 정의하자.
Metrics: Prec@k & Rec@k
상위 k개의 확률을 가진 레이블을 출력하는 것을 기준으로 삼을 때, 대표적인 metric은 precision at k, recall at k 두 가지가 있다.
precision at k의 의미는 예측된 상위 k 레이블 중 실제 레이블의 비율을 뜻하고, recall at k의 의미는 실제 레이블 중 예측된 상위 k에 속한 레이블의 비율을 뜻한다.
Prec@k & optimal scorer
논문에 따르면 주어진 scorer f가 있을 때, 우리는 모확률들을 이용하여 Prec@k(f)의 값을 다음과 같은 formula로 나타낼 수 있다.
위 formula를 받아들이고 나면, 다음과 같은 corollary를 추론할 수 있다.
이 corollary는 어찌보면 당연한데, 높은 Prec@k(f) 값을 얻기 위해서 scorer f의 top-k 결과가 실제 모확률 ℙ(yᵢ|x)의 top-k와 같은 값을 예측해야 한다는 말이다.
논문에서 제시하는 위의 수식이 합리적인지 확인하기 위해 하나의 예시를 생각해보자. 예시의 상황은 첫 번째 섹션의 예시를 가져오고, 추가로 하나의 샘플 x에 대해서, k=1, f(x)=(0.7, 0.5)를 가정한다면, 이 모델의 Prec@k의 값은 어떻게 될까?
Topₖ(f(x))는 {y₀}일 것이고, 이 scorer f의 Prec@k는
- (case xx) 0.0의 확률로 0/1
- (case xo) 0.1의 확률로 0/1
- (case ox) 0.6의 확률로 1/1
- (case oo) 0.3의 확률로 1/1
이다. 따라서, Prec@k값은 (0/1)*0.0 + (0/1)*0.1 + (1/1)*0.6 + (1/1)*0.3이다.
이 값은 (1/k) ℙ(y₀=1|x)처럼 쓸 수 있으며, 이는 위에 formula와 같은 의미를 갖는다.
Rec@k & optimal scorer
논문에 따르면 주어진 score f가 있을 때, 우리는 모확률들을 이용하여 Rec@k(f)의 값 또한 특별한 formula로 구할 수 있다. 이를 위해 먼저 새로운 notation을 정의하자.
위에 정의된 값을 이용하여 Rec@k(f) 또한 나타낼 수 있다.
위 formula에서 Prec@k와 같이 다음과 같은 corollary를 추론할 수 있다.
여기서 참고해야하는 점은 ℙ(yᵢ=1|x)의 순서와 ℙ(y’ᵢ=1|x)의 순서가 다를 수 있다는 것이다. 이 부분 때문에 Prec@k와 Rec@k를 높이는 scorer들이 각각 다른 성질을 갖게 된다. Prec@k를 높이는 scorer는 ℙ(yᵢ=1|x)의 순서를 잘 맞추는 모델이고, Rec@k를 높이는 scorer는 ℙ(y’ᵢ=1|x)의 순서를 잘 맞추는 모델이다.
이 경우에도 위 예시를 들어 위 formula가 합리적인지 판단해보자.
Rec@k는 다음과 같이 구할 수 있다.
- (case xx) 0.0의 확률로 (0/0)
- (case xo) 0.1의 확률로 (0/1)
- (case ox) 0.6의 확률로 (1/1)
- (case oo) 0.3의 확률로 (1/2) (true label이 2개)
따라서 Rec@k의 기댓값은 (0/0) * 0.0+ (0/1) * 0.1 + (1/1) * 0.6+ (1/2) * 0.3이다.
이는 (1/1) * 0.6 + (1/2) * 0.3 = 0.9 * ((1/1) * (0.6/0.9) + (1/2) * (0.3/0.9))처럼 표현할 수 있으며, 해당 수식은 또 다음과 같이 표현된다.
이는 위 formula와 같다.
Reductions: OVA, PAL, OVA-n & PAL-n
Reduction 방법은 크게 4가지가 있다.
- One-versus-all (OVA)
- Pick-all-labels (PAL)
- One-versus-all normalized (OVA-n)
- Pick-all-labels normalized (PAL-n)
OVA는 각 레이블을 독립적으로 예측하는 모델을 만드는 것이다. 이 경우 모델의 loss를 다음과 같이 표현할 수 있다.
OVA는 하나의 샘플에 대한 loss를 구할 때, 하나하나의 레이블에 대해 각각 binary classification loss를 적용하게 된다. Binary classification loss의 대표적인 방법은 logistic loss가 있으며 이를 수식으로 나타내면 다음과 같다.
PAL은 각 레이블에 독립적으로 binary classification을 적용하는 것이 아니라, multi-class로서 접근하는 방법이다. 해당 reduction의 loss는 다음과 같이 표현할 수 있다.
PAL의 대표적인 방법은 softmax + cross entropy가 있다.
OVA-n과 PAL-n은 각각의 레이블의 영향을 positive label의 개수로 나눠 정규화하는 방법이다.
OVA와 PAL의 대표 loss들로 표현하면 다음과 같다.
Risks
모확률을 이용해 reduction의 total loss의 값을 구할 수 있는데 이는 다음과 같다.
여기서
이다.
위 total loss 값이 합리적인지 예시를 통해 알아보자. 이 예시에서 loss는 logistic loss를 사용한다.
- R_OVA(f)
- (case xx) 0.0의 확률로
- (case xo) 0.1의 확률로
- (case ox) 0.6의 확률로
- (case oo) 0.3의 확률로
이다.
- 결과적으로,
- 위와 같은 결과가 나온다.
2. R_OVA-n(f)
- (case xx) 0.0의 확률로
- (case xo) 0.1의 확률로
- (case ox) 0.6의 확률로
- (case oo) 0.3의 확률로
이다.
- 결과적으로,
- 위와 같은 결과가 나온다.
3. 나머지 R_PAL과 R_PAL-n에 대해서도 formula와 같은 형태를 얻을 수 있다.
Bayes-optimal predictions
위와 같은 경우에서 각각의 Risk를 최소화하는 방법은 당연하게도 loss function 안에 있는 값이 같으면 된다. 수식으로 표현한다면, 다음과 같다.
Metrics & Reductions
우리는 2번 째 섹션에서 어떤 metric을 사용할 때, 어떤 scorer가 최적인지 알아봤고, 3번 째 섹션에서 어떤 reduction을 사용할 때, 어떤 scorer가 최적인지 알아보았다. Prec@k의 최적 scorer는 OVA와 PAL의 최적 scorer와 같고 (N(x)는 prediction order에 영향을 끼치지 않는다), Rec@k의 최적 scorer는 OVA-n과 PAL-n의 최적 scorer와 같다.
이와 같은 결론을 통해 우리는 풀고자 하는 multi-label 문제에 대해서 해당 문제가 Prec@k를 중요하게 봐야하는 문제인지 Rec@k를 중요하게 봐야하는 문제인지 고려하고, 적절한 reduction 방법과 loss를 구성하여 모델을 학습 시켜야 한다.
