https://mlc.ijs.si/meta/files/IJIS_supplementary_methods_datasets.pdf
https://tonnykwon.github.io/blog/machine/2020-01-16-Multi-Label%20Classification/
https://arxiv.org/pdf/2102.07113

1 INTRODUCTION

Predictive Modeling은 기계 학습의 한 분야로, 목표 변수를 예측하기 위한 모델을 학습하는 방법을 개발하는 데 중점을 둠. 이때 목표 변수는 일반적으로 단일 연속형 변수나 이산형 변수를 의미하며, 이는 각각 회귀(Regression)와 분류(Classification)라는 두 가지 일반적인 작업에 해당함.

그러나 요즈음 예측해야 할 속성이 하나가 아니라 여러 개인 경우가 점점 더 많아지고 있음. 예를 들어, 다음과 같은 사례가 있다.

• 이미지 주석 작업: 하나의 이미지가 동시에 나무, 하늘, 풀과 같은 여러 레이블을 나타낼 수 있음.
• 유전자 기능 예측: 각 유전자는 일반적으로 여러 기능과 관련이 있음.
• 약물 효과 예측 하나의 약물이 여러 조건에 영향을 미칠 수 있음.

이처럼 목표 변수가 여러 이진 변수 인 문제는 다중 레이블 분류(Multi-Label Classification, MLC) 과제에 속함.

Binary Classification에서는 하나의 레이블 존재 여부(있음/없음)를 예측함. 반면, Multi-Label Classification(MLC)에서는 여러 레이블의 존재 여부를 예측하며, 하나의 샘플에 여러 레이블을 동시에 할당할 수 있음.

MLC는 Multi-Class Classification(MCC)와 종종 혼동됨. MCC에서도 여러 클래스(레이블)가 있지만, 한 샘플은 여러 클래스 중 단 하나에만 속할 수 있음. 이런 관점에서 MCC는 MLC의 특수한 경우로 볼 수 있음. 즉, MCC는 각 샘플에 대해 단 하나의 레이블만 관련 있는 경우를 말함.

또한, MLC는 Multi-Target Classification(MTC)와도 다름. MTC는 여러 목표를 예측하는 작업으로, 각 목표는 여러 가능한 클래스 중 하나의 값을 가질 수 있음. MLC는 여러 개의 Binary Classification 작업 집합으로 볼 수 있는 반면, MTC는 여러 개의 MCC 작업 집합으로 볼 수 있음.

마지막으로, MLC와 관련된 또 다른 작업으로 Multi-Label Ranking이 있음. Multi-Label Ranking의 목표는 주어진 샘플에 대해 레이블의 관련성 순위를 매기는 것임.

MLC(Multi-Label Classification)는 각 샘플에 대해 관련된 레이블 집합(목표 속성)을 예측하는 작업임. 이 작업은 다양한 실용적 응용에서 등장함. Fig. 1은 기계 학습 커뮤니티에서 MLC에 대한 관심이 증가하고 있음을 보여줌. 이는 새로운 MLC 방법이 등장하고 있다는 것을 의미

2 방법 분류

문헌에서는 다양한 MLC 방법이 제안되어 있으며, 이번 연구에서는 [3]에서 제안된 분류 체계를 따름. MLC 방법은 크게 두 가지로 나뉨:

2.1 문제 변환 방법 (Problem Transformation)

• 다중 레이블 데이터를 단일 레이블 데이터셋으로 변환하여 처리하는 방법
• 변환된 데이터셋을 단일 목표(single-target) 기계 학습 방법으로 학습하고, 하나 또는 여러 개의 단일 목표 모델을 생성하고 이를 이용해서 예측함.

2.2 알고리즘 적응 방법 (Algorithm Adaptation)

• 단일 목표 학습 방법의 학습 및 예측 단계를 다중 레이블 처리에 적합하도록 변경.
• 적응 예시:
  • 트리 기반 방법: 분할 시 사용하는 휴리스틱 변경.
  • SVM(Support Vector Machines): 추가적인 임계값 설정 기술 활용.
• 특징: 레이블 간의 종속성을 직접 처리할 수 있는 메커니즘 제공.
• 분류 체계: 적응 방식에 따라 다음 5가지 그룹으로 나뉨:
  1. 트리 기반(Tree-Based)
  2. 신경망(Neural Networks)
  3. SVM
  4. 인스턴스 기반(Instance-Based)
  5. 확률적(Probabilistic)
     

3 Binary Problem

Binary problems 의 개념

• 다중 레이블 데이터셋을 동일한 특성 공간을 공유하는 여러 단일 목표(single-target) 데이터셋의 조합으로 간주:
• 이 접근 방식은 단일 목표 이진 분류 방법을 간단히 적용할 수 있다는 장점이 있음.
• 예측 시, 학습된 모든 단일 목표 모델을 호출하여 새로운 테스트 샘플에 대한 결과를 생성함.
• 한계가 있는데 , 레이블 간 종속성 정보 손실: 레이블 간의 관계를 고려하지 못함.

One-Vs-One(OvO)-like (Binary Relevance 또는 Pairwise Approach)

• 각 레이블 쌍을 개별 이진 문제로 취급.
• 결과적으로 레이블 쌍을 L 이라 하면 $\frac{|\mathcal{L}|(|\mathcal{L}|-1)}{2}$ 만큼의 단일 목표 이진 데이터셋 생성.

One-Vs-All(OvA)-like (Label Powerset Approach)

• 모든 고유 레이블 집합을 별도의 클래스로 간주하여 문제를 $|L|$개의 단일 다중 클래스 문제로 변환.

장단점

• Binary Relevance (OvO-like):
  • 장점: 단순한 이진 분류기를 사용할 수 있음.
  • 단점: 레이블 간 종속성 정보가 완전히 소실됨.
• Label Powerset (OvA-like):
  • 장점: 단일 모델을 학습하며(모델 수가 크게 줄어듦), 레이블 간 종속성을 유지함.
  • 단점: 학습 데이터에 없는 레이블 집합에 대해 일반화할 수 없음.

3.1 One-Vs-All (OVA)

3.1.1 Binary Relevance (BR)

• 개념:
  MLC 문제를 $|L|$ 개의 이진 분류 문제로 변환.
  각 이진 문제는 하나의 레이블을 목표로 하며, 원래의 특성 공간을 공유.
  이를 통해 각 레이블에 대해 하나의 기본 이진 분류기를 학습함.
• 특징:
  • 장점:
    • 학습 데이터에 없는 레이블 집합에 대해 일반화 가능.
  • 단점:
    • 레이블 간 종속성 무시.
    • 레이블 수가 많을 경우 적합하지 않음.
    • 모든 레이블에 대해 모델을 학습해야 하므로 학습 시간이 길어질 수 있음.

3.1.2 Classifier Chains (CC)

• 개념:
  • |L|개의 이진 분류기를 체인 형태로 연결.
  • 각 분류기는 단일 목표 문제를 처리하며, 입력 특성 공간은 이전 분류기의 예측 결과를 포함.
  • 체인의 첫 번째 분류기는 원래 특성만 사용해 학습.
• 작동 원리:
  • 체인에서의 레이블 순서는 중요하며, 이는 레이블 간의 상관관계를 어느 정도 반영.
• 특징:
  • 장점:
    • 레이블 간 종속성을 일부 반영.
    • 학습 데이터에 없는 레이블 집합에 대해 일반화 가능.
  • 단점:
    • 레이블 수가 많을 경우 적합하지 않음 (BR의 단점 상속).
    • 체인에서 레이블 순서에 의존.

이 세 가지 방법은 각각의 장점과 단점을 가지며, 데이터셋 특성에 따라 성능이 달라질 수 있음.

3.2 One-Vs-One (OVO)

3.2.1 Calibrated Label Ranking (CLR)

• 위처럼 각 샘플에서 어떤 레이블(L1, L2 등)이 다른 레이블보다 우선되는지(L1 > L2)를 판단하는 기준은 샘플의 레이블 집합(Labelset)을 기반으로 함.
• 규칙 1: 두 레이블 중 하나만 레이블 집합에 포함된 경우
  • 레이블 집합에 포함된 레이블을 우선으로 설정.
• 규칙 2: 두 레이블이 모두 레이블 집합에 포함된 경우
  • 두 레이블 간 우선순위를 설정하지 않음(예: L1 = L4)
• 규칙 3: 두 레이블이 모두 레이블 집합에 포함되지 않은 경우
  • 해당 레이블 쌍은 학습 데이터에서 제외(비교할 필요 없음)

• 개념: 다중 레이블 랭킹을 위한 Pairwise 기법
  • $|L|(|L|−1)/2$ 개의 이진 데이터셋을 생성하며, 이는 각 레이블 쌍 간의 관계를 나타냄.
  • 각 데이터셋에서 한 레이블은 긍정(positive), 다른 하나는 부정(negative)으로 분류.
• 작동 원리:
  • 각 레이블 쌍에 대해 이진 분류기를 학습
  • 인공 레이블을 추가하여 총 $|L|$개의 추가 모델을 생성.
  • 결과적으로 각 레이블에 대한 랭킹과 양분화(bipartition)를 생성.
  • 인공 레이블은 관련된 레이블과 그렇지 않은 레이블을 나누는 기준 역할을 함.

• 위 예시에서처럼 인공 레이블을 추가할수도 있음
  • CLR은 랭킹 정보만 제공하지만, 인공 레이블을 사용하면 랭킹을 기준으로 양분화를 수행 가능.
    • 예측된 랭킹: L1 > L3 > None > L2.
    • 양분화 결과: {L1, L3}는 관련 레이블, {L2}는 비관련 레이블.

장점

• 레이블 간 우선순위와 종속성 학습
  • CLR은 레이블 간의 상대적 우선순위를 학습하므로, 다중 레이블 문제에서 중요한 레이블 간의 종속성을 어느 정도 반영할 수 있음.
  • 단순히 독립적으로 레이블을 예측하는 Binary Relevance(BR)와 달리, 레이블 간의 관계를 고려하는 예측이 가능.
• 랭킹과 양분화 동시 제공
  • CLR은 랭킹 정보(레이블의 우선순위)와 양분화(1,0 레이블 구분)를 동시에 제공 가능
  • 사용자는 임계값(Threshold)을 조정하여 랭킹 기반으로 다중 레이블을 유연하게 선택할 수 있음.
• 다양한 기법과 결합 가능
  • CLR은 학습에서 사용하는 기본 분류기(Base Classifier) 에 독립적이기 때문에, SVM, Logistic Regression, Random Forest 등 다양한 모델과 결합 가능.
  • 필요에 따라 더 강력한 모델로 확장 가능.
• 일반화 가능성
  • CLR은 학습 데이터에 존재하지 않는 새로운 레이블 조합에 대해 일반화할 가능성이 있음.
  • 이는 Label Powerset(LP) 방식의 단점을 극복

단점

• 계산 복잡도 증가
  • CLR은 |L|(|L|−1)/2개의 레이블 쌍에 대해 각각 이진 분류기를 학습해야 함.
    • 레이블 수가 많아지면 모델 학습과 예측 시간이 급격히 증가.
    • 예: 10개의 레이블 → 45개의 모델 학습 필요.
• 레이블 쌍 데이터셋의 불균형 문제
  • 특정 레이블 쌍에 대해 샘플 데이터가 충분하지 않으면, 학습된 모델의 성능이 떨어질 가능성이 있음.
    • 예: L1 > L2에 대한 데이터가 많고, L2 > L3에 대한 데이터가 적은 경우, 두 모델 간 성능 차이가 발생.

4 Multi-class problems

4.1 Label Powerset (LP)

작동 원리

• LP는 다중 레이블 문제를 해결하기 위해 각 레이블 집합(label-set)을 하나의 클래스로 취급합니다.
• 다중 클래스 분류에 적합한 기법(SVM, Random Forest 등)을 사용하여 학습합니다.

특징

• 레이블 관계 보존: 레이블 간의 관계를 완전히 보존합니다.
• 단순한 설계: 기존 다중 클래스 분류 기법을 그대로 사용할 수 있음.

제한점

1. 새로운 레이블 조합 예측 불가:
   • 학습 데이터에 없는 새로운 레이블 조합은 예측할 수 없습니다.
2. 클래스 폭발 문제:
   • 고유한 레이블 집합(label-set)이 많아지면 클래스의 수가 급격히 증가하여 학습이 어려워질 수 있습니다.
   • 예: 3개의 레이블이 있다면 최대 23=82^3 = 823=8개의 고유 클래스가 생성될 수 있음.
3. 데이터 불균형:
   • 특정 레이블 집합이 데이터셋에서 드물게 나타날 경우, 학습이 어려울 수 있습니다.

4.2 Pruned Sets (PSt)

작동 원리

• PSt는 LP의 한계를 극복하기 위해 설계된 방법입니다. 드문(label-set) 레이블 집합을 제거하고 이를 적절히 보완하여 학습 데이터의 크기와 복잡성을 줄입니다.

단계

1. Pruning Step:
   • 드물게 등장하는 레이블 집합을 학습 데이터에서 제거.
   • "드문 레이블 집합"의 기준은 하이퍼파라미터(Pruning Value)로 설정됩니다.
2. Reintroduction Step:
   • 제거된 샘플에서 특정 레이블 집합을 부분적으로 재도입.
   • 재도입할 레이블 집합의 최대 개수는 하이퍼파라미터(Maximal Frequent Label-Sets)로 설정됩니다.
3. Threshold Function (옵션):
   • 학습 데이터에 없던 새로운 레이블 조합을 예측 시 생성하도록 함.

특징

• 효율성: LP보다 학습이 훨씬 빠릅니다.
• 적응성: 적절한 하이퍼파라미터 튜닝을 통해 데이터에 맞는 효율적 학습이 가능.

제한점

1. 새로운 레이블 조합 생성 제한:
   • 기본 설정에서는 새로운 레이블 조합 예측이 어렵습니다.
   • Threshold Function을 도입하면 이를 극복할 수 있지만, 성능이 데이터에 따라 달라질 수 있습니다.
2. 가정이 깨질 가능성:
   • 드문 레이블 집합이 중요한 경우, Pruning 과정에서 유용한 정보가 손실될 수 있습니다.

5 Ensembles

이 문제 변환 방법의 카테고리는 앙상블 기법(stacking, bagging, random sub-spacing) 또는 데이터셋의 다양한 변환(예: 임베딩)을 활용하는 모든 방법을 포함.

5.1 Meta Binary Relevance (MBR)

Meta Binary Relevance(MBR), 또는 2BR 방법은 Binary Relevance (BR)의 확장 형태로, 두 단계로 구성되어 있습니다.

MBR 작동 방식

• 1단계: 기본 BR 모델 학습
  • $|L|$개의 이진 분류기를 학습하여 각 레이블에 대해 독립적으로 예측.
  • 이 과정은 기존의 BR 방식과 동일.
• 2단계: 메타 모델 학습
  • 메타 단계에서는 1단계의 예측 결과를 입력 특성에 추가하여 새로운 $|L|$개의 이진 모델을 학습.
    • 기본 특성 공간에 1단계에서 얻은 예측값을 추가해 확장된 특성 공간에서 학습.

예시

• 특성: X = (x1, x2)
• 레이블: L1, L2, L3

Example	특성 (x1, x2)	레이블 (L1, L2, L3)
1	(1, 0)	(1, 0, 1)
2	(0, 1)	(0, 1, 0)
3	(1, 1)	(1, 1, 1)

1단계: 기본 모델 학습

• Classifier_L1, Classifier_L2, Classifier_L3 학습.
• 학습 결과로 각 샘플에 대한 레이블별 예측값 생성:
  • 샘플 1: 예측 결과 = (1, 0, 1)
  • 샘플 2: 예측 결과 = (0, 1, 0)
  • 샘플 3: 예측 결과 = (1, 1, 1)

2단계: 메타 모델 학습

• 확장된 특성 공간:
  • 원본 특성 (x1, x2)에 1단계 예측값 추가.
  • 예: 샘플 1 → (x1, x2, L1_pred, L2_pred, L3_pred) = (1, 0, 1, 0, 1)
• 메타 모델 학습:
  • Meta_Classifier_L1: (x1, x2, L2_pred, L3_pred) → 예측 L1
  • Meta_Classifier_L2: (x1, x2, L1_pred, L3_pred) → 예측 L2
  • Meta_Classifier_L3: (x1, x2, L1_pred, L2_pred) → 예측 L3

MBR의 장점

1. 레이블 간 관계 학습 가능:
   • 1단계에서 생성된 예측값을 메타 모델 입력으로 사용해 레이블 간 상호작용을 고려.
2. 유연한 적용:
   • 기본 BR 방식에 비해 성능 개선 가능.
   • 다양한 변형 기법(Cross-Validation, 상관 계수 필터링 등)과 결합 가능.

MBR의 단점

1. BR의 단점 상속:
   • 레이블 수가 많아질 경우, 학습 및 예측 시간이 크게 증가.
   • 레이블 간 종속성을 완전히 반영하지 못할 수 있음.
2. 추가 계산 비용:
   • 메타 단계 학습으로 인해 학습 과정이 더 복잡하고 시간이 많이 걸림.

5.2 Ensembles of Classifier Chains (ECC)

ECC는 Classifier Chains (CC)의 확장된 형태로, CC를 앙상블 형태로 구성하여 다중 레이블 분류 성능을 향상시키는 방법입니다.

ECC의 작동 원리

1. 샘플링 기반 학습

• 원본 데이터셋에서 복원 추출(sampling with replacement)을 사용하여 여러 개의 샘플링 데이터셋을 생성.
  • 각 샘플링 데이터셋은 원본 데이터셋의 하위 집합.
  • 복원 추출은 동일한 데이터 샘플이 여러 데이터셋에 포함될 수 있음을 의미.
• 복원 추출 방식이 비복원 추출보다 더 나은 결과를 제공한다고 알려져 있음.

2. Classifier Chain 학습

• 각 샘플링 데이터셋에 대해 CC 모델을 학습.
  • CC는 특정 레이블 순서에 따라 학습됨.
  • ECC는 학습 과정에서 레이블 순서를 무작위로 설정하여 다양한 종속성을 학습.

3. 앙상블 구성

• 여러 CC 모델을 사용하여 최종 예측을 생성.
  • 각 모델의 예측 결과를 결합(예: 다수결 투표)하여 최종 결과 생성.

ECC의 하이퍼파라미터

1. CC 모델 수: 앙상블에 포함될 CC 모델의 개수.
2. Bag Size: 각 CC 모델 학습에 사용할 데이터셋의 크기 (전체 데이터셋의 몇 %를 사용할지).

장점

1. 레이블 간 종속성 고려:
   • CC 모델의 특성을 활용하여 레이블 간 상호작용을 학습.
   • 앙상블 형태로 다수의 CC를 사용하므로 종속성을 더 잘 반영.
2. 다양성 확보:
   • 샘플링 데이터셋을 사용하고 레이블 순서를 무작위로 설정하여 모델 간 다양성을 증가시킴.
   • 데이터의 하위 집합과 무작위 순서를 통해 다양한 패턴을 학습.
3. 강건한 성능:
   • 다양한 모델을 결합하여 예측 정확도를 높이고 과적합을 줄일 수 있음.

단점

1. 학습 시간 증가:
   • 여러 CC 모델을 학습해야 하므로 시간이 많이 소요.
   • 각 CC 모델의 학습 시간이 레이블 수에 비례하여 증가.
2. 레이블 순서 의존성:
   • 무작위 레이블 순서 설정으로 종속성을 다루지만, 여전히 레이블 순서에 따른 성능 차이가 발생할 수 있음.

ECC의 작동 예제

• 특성: X = (x1, x2)
• 레이블: L1, L2, L3

샘플 ID	특성 (x1, x2)	레이블 (L1, L2, L3)
1	(1, 0)	(1, 0, 1)
2	(0, 1)	(0, 1, 0)
3	(1, 1)	(1, 1, 1)

샘플링 및 CC 모델 학습

• 복원 추출 샘플링으로 3 개의 데이터셋 생성:
  • Dataset 1: 샘플 $\{1,3,1\}$
  • Dataset 2: 샘플 $\{2,3,2\}$
  • Dataset 3: 샘플 $\{1,2,3\}$
• 각 데이터셋에 대해 CC 모델 학습:
  • 모델 1: 레이블 순서 $L 1 \rightarrow L 2 \rightarrow L 3$.
  • 모델 2: 레이블 순서 $L 3 \rightarrow L 1 \rightarrow L 2$.
  • 모델 3: 레이블 순서 $L 2 \rightarrow L 3 \rightarrow L 1$.

예측
새로운 샘플 X_test $=(0.5,0.5)$ 에 대해:

1. 각 CC 모델로 예측 수행.
   • 모델 1: $(L 1, L 2, L 3)=(1,0,1)$
   • 모델 2: $(L 1, L 2, L 3)=(0,1,1)$
   • 모델 3: $(L 1, L 2, L 3)=(1,1,0)$
2. 최종 앙상블 결과:
   • 다수결 투표: $(L 1, L 2, L 3)=(1,1,1)$

장단점

• 적합한 경우:
  • 레이블 간 상호작용이 중요한 문제.
  • 데이터셋 크기가 적당하고 학습 시간 여유가 있는 경우.
• 부적합한 경우:
  • 레이블 수가 많아 학습 시간이 너무 길어질 수 있는 경우.
  • 빠른 응답 시간이 요구되는 문제.

이후에도 방법론이 많으나, 여기에서는 생략

6 Algorithm adaptation method

• 위는 생략함. (각각의 모델에 이를 해결하는 방법론이 내장되어있다고 생각하면 될 것 같음)

7 내 생각

• Multi Label 에 대해서 많은 생각을 하게 되는 계기
• Catboost 에 이를 해결하기 위한 방법론이 내장되어 있어서 , 이를 사용하면 좀 쉽게 해결할 수 있을 것 같음.