kmhana.tistory.com/4?category=838050
Active Learning 이란 - 기본
dsgissin.github.io/DiscriminativeActiveLearning/about/ About An introduction to the active learning framework, from classical algorithms to state of the art methods for neural networks. A new method..
kmhana.tistory.com
을 우선 보시는 걸 추천드립니다.
2. Active Learning을 위한, 딥러닝
- Core-set
- Loss for Active Learning
- Discriminative Active Learning
중 Core-set에 대해서 소개하고자 합니다.
본 딥러닝을 위한, Active Learning - Core-set부터는 논문을 중심으로 소개할 예정입니다.
종합 : ⭐⭐⭐⭐⭐
1. 논문 중요도 : 5점
2. 실용성 : 5점
설명 : 딥러닝 모델을 직접활용하는 Active Learnig
- Task-agnostic(Task와 무관) ∵ CNN의 Feature를 활용
- 실용성 또한 높다 (단, 쉬운 알고리즘을 사용했을 때)
- End-to-End 학습이 아닌 것은 아쉬움
( * 개인적인 의견이며, 제 리뷰를 보시는 분들에 도움드리기 위한 참고 정도로 봐주세요)
Core-set 의의
1. Label정보가 필요한 Uncertainty 말고, 딥러닝의 Feature를 사용하자.
∵ CNN은 매우 뛰어난 표현력을 가지고 있다.
2. Batch 단위의 Query 전략 - 기존의 AL 방법들은 Batch 단위에 부적합
∵ Instance 단위에 Query 전략 시, 매 Instance 뽑을 때마다 딥러닝 모델을 뽑는 것은 비효율적
3. Core-set을 통해 추출한 Sample들이, 전체 Dataset을 대표
4. Core-set은 사전에 선별된 Subset들과 구별되는 data-point를 찾음 (Diversity)
∵ 기존의 Uncertainty기반 방법론은, 선별한 data points간의 상관성(correlation)이 높다.
- 즉, 유사한 데이터가 뽑힐 가능성이 높음
굉장히, 중요한 논문이라고 생각합니다.
Diversity(다양성)에 관점에서 딥러닝 모델을 활용한 연구로써 가치가 높습니다.
딥러닝과 Active Learning을 접목하고자 하시는분은
논문을 자세히 읽어보시는 것도 권장드립니다.
※ Core-set 아이디어를 정의하고 구현(최적화)하는데, 다소 어려우실 수 있습니다.
Active Learning 문제의 재정의
Active Learning의 목적은
기존의 레이블된 Subset \( \textbf{S}_{0} \) 이 있을때, 새로운 추출한 Subset \( \textbf{S}_{1} \) 을 통해,
미래 기대 Future Expected Loss를 줄여야 한다.
Future Expected Loss : $$ \min_{\mathbf{s^{1}}:\left | \mathbf{s^{1}}\right | \leq b } E_{\mathbf{x},y\sim pz}\left [ l\left ( \mathbf{x}, y; A_{\mathbf{s^{0}}\bigcup\mathbf{s^{1}} } \right ) \right ] $$
-
b(Budget) : 뽑아야 할 데이터 포인트 수
-
\( \textbf{S}_{1} \) : 1회(iteration) AL 실행으로, 뽑은 Subset
Future Expected Loss는 다음 식과 같이 분리시킬 수 있다.
저자는 Upper bound를 설정하여, 문제를 정의한 후 솔루션(Core-set)을 제안한다.
CNN의 뛰어난 성능덕분에, Future Expected Loss 중 Generalization Error와 Training Error를 0으로 가정할 수 있다.
위의 가정을 통해서, Future Expected Loss는 Core-set Loss만 해결하면 된다.
위에서의 Core-set Loss를 재정의 하면, 다음과 같은 식으로 변환이 되며,
이 식의 의미는 결국,
"the performance of the model on the labelled subset and that on the whole dataset will be as close as possible."
"Subset에서의 모델 성능과 전체 데이터 셋에서의 성능 차이를 최소화" 문제가 된다.
이 그림이 Core-set을 이해하는데 많은 도움을 준다.
Core-set을 찾으려면
1. 다른 data들(빨간 점)을 모두 Cover 할 수 있는 최적의 거리 \( \delta_{s} \)를 구하고
2. 그에 해당하는 핵심 포인트, Core-set(파란점)을 찾으면 된다.
이제부터는, Radius \( \delta_{s} \) 를 어떻게 최소화할 수 있을 집중적으로 고민하면 된다.
※ 위에 식을 도출하는 과정 동안, 몇 가지 증명 과정이 있지만 필요하신 분만을 위해서 간단한 설명을 남깁니다.
Core-set Loss 중 , \( \frac{1}{\left | \textbf{s} \right |}\sum_{j\in \textbf{s} }l\left ( \textbf{x}_{j}, y_{j}; A_{\textbf{s}}) \right ) \) 은 딥러닝이 학습하는 과정에서 training error를 0으로 수렴하므로
으로 식을 변경할 수 있습니다.
Lipschitz continuity 를 활용하여, Loss 함수의 Upper Bound를 \( \delta_{s} \)와 관련된 식으로 정의했습니다.
1. Gradient Descent로 학습하는 비용 함수가 만약, Lipschitz continuity 하다면
2. 상한(Upper Bound)가 존재합니다.
3. 그리고 그 상한(Upper Bound)이 Radius로 구성되어 있다면,
4. 우리는 Radius 찾는 솔루션만 만들면 된다.
* 말은 쉽지만.. 증명과정과 구현은 쉽지 않다.
Lipschitz continuity 참고 light-tree.tistory.com/188
Lemma1.을 통해, Class수와 관련된 Lipschitz 함수라는 것을 확인했습니다.
* 실제 실험에서도, Class가 증가할수록 Core-set의 성능이 저하되었습니다.
저자는 cross-entropy가 아닌, \( l_{2}-distance \) 를 사용하여 증명했지만,
실제 실험에서는 Cross-entropy를 썼으며, 문제가 없다고 합니다.
Core-set 구현 알고리즘
Core-set 문제를 해결하기 위해서, 크게 두 가지 알고리즘을 제안했다.
1. k-Center-Greedy
-
장점 : 1) 구현이 간단하다. 2) 탐색 시간이 낮아 효율적이다.
-
단점 : 1) 위에 문제를 완벽하게 해결하는 것은 아니다. 2) Outlier에 취약하다.
K-CENTER PROBLEM 식:
$$ \min_{ \textbf{s}^{1} : \left | \textbf{s}^{1} \right |\leq b} \max_{i} \min_{j\in \textbf{s}^{1} \bigcup \textbf{s}^{0} }\Delta \left ( \textbf{x}_{i}, \textbf{x}_{j} \right ) $$
"Choose b center points such that the largest distance between a data point and its nearest center is minimized."
위에 식을 해석하자면 다음과 같다.
데이터 포인트\( \textbf{X}^{0} \) 와 Subset \( \textbf{S}^{0} \) 중심들 간의 거리 중
가장 큰 거리를 최소로 만드는 \( \textbf{b} \)를 선택한다.
... ◎ _ ◎ .. 조금 복잡.. 하다..
이해를 돕기 위해서, 알고리즘 과정을 도식화해봤다.
2. Robust k-Center
-
장점 : 1) Outlier에 견고하다(Robust). 2) 최적의 Core-set을 탐색한다.
-
단점 : 1) 구현이 어렵다( - MIP(mixed integer program)를 사용해야 한다.
2) 탐색 시간이 k-Center-Greedy에 비해 오래 걸린다.
Algorithm의 단점을 보완하기 위해서,
1. 이상치를 고려
- 이상치의 개수가 \( \Xi \) 를 넘어가면 안 됨 \( \Xi =\)1e-4 x N ; N은 데이터 수)
2. 몇 가지 제한사항과 Lower Bound를 추가
- 모든 data point들은 하나의 center에게 커버되어야 한다.
- 초기 Lower bound는 Upper bound의 1/2
- 초기 Upper bound는 \( \max_{j} \min_{j\in \textbf{S}_{g} } \Delta \left ( \textbf{x}_{i}, \textbf{x}_{j} \right )\ \) 이다.
- Feasible 조건 만족 시, UB를 낮춤
- Feasible 조건 불만족 시, LB를 낮춤
- UB와 LB가 같을 때 ( 최적의 \( \delta_{s} \) )까지 반복
- 최적의 \( \delta_{s} \) 기반으로, Center node 추출
※ 실제 구현된 코드를 확인해 보니, Radius정보를 바탕으로 Graph를 탐색하여 center point를 찾는다
Greedy 알고리즘 VS MIP 차이
정확도 : MIP를 사용한 Robust Algorithm이 좀 더 좋은 성능을 보인다.
* 저자는 k-Center Greedy를 사용해도, 다른 AL 방법보다 뛰어났다고 한다.
탐색 속도 : MIP가 약 122배 느리다.
* 저자는 쓸만한 속도라고 설명했다.
Uncertainty VS Diversity 차이
Active Learning 모델 선택 관점 두 가지:
1. Uncertainty(불확실성) : 모델이 헷갈리는 데이터
2. Diversity : 데이터의 분포를 커버할 수 있는 데이터 포인터
AL 접근법들은 Uncertainty와 Diversity 간의 Trade-off가 있다.
파랑점 : 초기(initial) labeled 데이터
초록점 : Active Learning을 통해 선택한 데이터 포인트
빨간점 : 뽑히지 않은 데이터 포인트
- Core-set(b)의 초록점은 골고루 퍼졌지만,
Uncertainty(a)는 치우쳐 저서 뽑힌 것을 알 수 있다(초록점 그룹이 Decision Boundary로 추정된다).
Uncertainty 단점
1. Uncertainty는 Dicision Boundary에 치우쳐서 데이터를 선별 → 모델 학습 시, 치우쳐진 데이터로 학습
2. Dicision Boundary에서 멀리 떨어진 그룹에 대해선 학습할 수 없음
3. 유사한 데이터들을 뽑을 가능성이 높아짐
4. Test set에 대한 Genalization이 약함
Diversity 단점
1. Dicision Boundary 근방의 분류에 도움이 되는 정보를 적게 가지고 있다.
2. 데이터의 밀집도에 영향을 받는다. ( + 불균형 데이터나 Class의 난이도 차이가 큰 경우 포함)
* 밀집도가 높은 Space에서 적은 Sample을 뽑게 된다. ( ∵ 작은 radius 만으로도 Cover가 가능하기 때문에)
3. 이상치(Outlier)에 취약하다.
마무리 코멘트
-
Core-set 논문은 딥러닝을 적용한 Active Learnig 논문에서 꼭 인용될 중요한 논문이 될 것이다.
- k-Center greedy 알고리즘은 구현이 매우 쉬워서, 실용성이 높다고 생각한다.(게다가 성능도 좋다.)
- MIP 알고리즘은 개인적으로 쓰지는 않을 거 같다.
- k-Center greedy 알고리즘에 Outlier를 처리하는 정도로 사용할 거 같다.
- MIP 알고리즘보다는 차라리, 앞으로 다룰 딥러닝을 위한 AL 알고리즘을 우선적으로 테스팅하려고 한다.
P.S. 작성하던 글이 날아가 버려.. Core-set 정리하는데 많은 시간이 걸렸다...
'실용적인 AI > Active Learning' 카테고리의 다른 글
| Active Learning을 위한 딥러닝 - Discriminative Active Learning (5) | 2021.02.02 |
|---|---|
| Active Learning을 위한 딥러닝 - Learning Loss for Active Learning (0) | 2021.02.02 |
| Active Learning 이란? - 기본전략 (4) | 2021.01.22 |
| Active Learning 이란 - 기본 (2) | 2021.01.22 |
| 실용적인 Deep Learning 적용을 위한 시작 (1) | 2021.01.22 |