F1 기대치 최대화

다중 선택 가능 예측 문제 (Multi Label Classification 1)에서, 어느 것을 선택하는 것이 가장 F1의 기대치가 높은 것인가라는 이야기입니다.


그림 : 유카타를 입은 동물 캐릭터 2

"이 이미지에 무엇이 찍혀 있습니까?"라고 물을 때


이누
고양이
토끼
쥐
곰
타누키


○
○
○
-
○
-


이와 같은 상황에 복수의 라벨을 출력하고 싶은 경우가 있다. 그 경우에 라벨로서 올리는 항목이 너무 적어도 너무 많아도 안 되므로, 딱 좋은 라벨의 출력수를 어떻게든 수학적으로 구할 수 없는가 하는 요구가 있거나 합니다.

문제

$ n $ 개의 상품이 있다고 가정합니다. 사용자는 여러 상품을 선택할 수있는 경우 (선택하지 않아도 됨) 사용자가 상품을 선택할 확률 $ p $가 알려져 있다고 가정합니다.
유저가 어느 상품을 선택한다고 예측하면 F1의 기대치를 극대화할 수 있을까?

예

A, B, C라는 상품이 있고 사용자가 선택할 확률이 $p = (0.45, 0.40, 0.35)^\mathrm{T}$
1개 1개는 5할 미만이지만 전부 가리지 않는 것보다는 어느 쪽인지 선택하는 편이 확률이 높다고 하는 이야기가 됩니다.

사고방식

$ 2 ^ n $의 모든 패턴을 시도하면 F1의 예상 값이 높은 조합을 알 수 있습니다.
단지 Probability Ranking Principle 3
동적 계획 방법을 사용하면 $ O (n ^ 2) $로 풀 수있는 것으로 알려져 있습니다. 4

구현

그 논문 4 의 실장을 Faron씨 5 가 해 주고 있고, 한층 더 CPMP씨 6 가 numba 7 로 고속화해 줍니다.

References

Jain, Solving Multi-Label Classification problems (Case studies included) , 2017.  ↩

미후네타카시, 이라 스토야   ↩

Suhara, Notes on Probabilistic Information Retrieval—Probability Ranking Principle에서 BM25까지—, 2012. (Probability Ranking Principal 설명)

Nan et al., ↩ , 2012.  Optimizing F-measure: A Tale of Two Approaches

Faron, ↩, (Faron의 구현) Get Expected F1-Score in O(n²)

CPMP, ↩, (CPMP의 구현, numba로 가속화)

ANACONDA, F1-Score Expectation Maximization in O(n²) ,   ↩