Multiple Instance Learning Track (MILTrack)

이 글은 Boris Babenko의 Visual Tracking with Online Multiple Instance Learning 논문을 review한 것이며 자세한 수식이나 배경지식은 필자의 귀차니즘으로 인해 이 글에 담지 못했음. 논문을 읽기전, 간단히 이해하는 수준이 필요하다면 이 포스트로 충분하다고 생각함.

MIL Tracking

이제 본격적으로 Image tracking by detecting을 시작해볼건데요. 이전에 사실 Online Discriminative Feature에 대한 논문을 읽었어요. 그 논문에서 MILTrack과 비교하며 설명하는데 이것을 알아야 그 것도 좀 더 쉽게 이해될 것 같아 읽어봤네요.

MIL은 Multiple Instance Learning의 약자로 여러개의 Instance를 학습하는 classifier를 만드는 거라고 대충은 알아낼 수 있겠죠. 뭐 방법이야 어쨌든 여기에서는 결국 원하는 물체를 화면에서 찾아서 따라다니는 겁니다.

그걸 잘찾는 알고리듬을 계속 변형하거나 업그레이드해서 더 잘 따라다니게 하는것이 이 분야의 길인 것 같습니다. 그러므로 요즘 트랜드의 방법이나 알고리듬을 뜯어보면 여러 단계를 거쳐 진화했다는것을 알수 있을 것입니다. 여기서도 몇가지 방법이 융합되거나 업그레이드되었네요.


1. 사용된 기술

  1)Online MIL Boost
  2)Stump for weak classifier
  3)Randomized Haar-like feature
  4)Simple motion model greedy local search


2. Algorithm

우선 Tracking이 진행되는 순서부터 설명합니다. 이 것은 여느 Tracker와 비슷합니다. Appearance를 Box를 이용해서 자르고 positive, negative를 구분해 학습하네요.

  1). 이미지를 자른다. 이때 $x$와 이전 프레임의 tracked location와의 거리가 $s$이하
이어야 한다. 그리고 그 $x$들의 feature vector($X_s$)를 뽑아낸다.

  2). MIL classifier를 이용해서 $X_s$안에 $p(y=1|x)$를 측정한다.

  3). 측정한값을 가지고 가장 큰 $x$를 찾아서 거기를 새로운 tracked location으로 만든다.

  4). 이번엔 두개의 이미지를 자른다. 하나는 tracked location 거리와 $r$이하로 떨어진 $x$들(positive samples), 또 하나는 $r$보다는 크고 $b$보다는 작은 $x$들(negative samples)의 이미지를 자른다.

  5).MIL appearance model을 하나의 positive bag과 여러개의 negative bag을 가지고 업데이트한다.

여기서 AdaBoost와 다른점은 MIL을 사용하는 부분(appearance model에서 Bag을 사용한다는 것)이 특별합니다. 당연히 appearance model이 다르니깐 classifier가 달라지는것을 생각한다면 달라진 appearance model을 중점적으로 보면되겠네요.

이 Bag이란 것은 positive한 feature가 하나라도 들어있으면, 그 Bag에 들어있는 instance들 모두 positive로 labeling됩니다. 그에 반에 instance모두가 negative feature 이어야 그 Bag이 negative로 labeling되는 거죠. 즉 어떤 범위를 모두 positive로 보아서 그 영역을 찾습니다. 마치 여자인지 판단할때, 머리길이, 신체사이즈, 얼굴생김새, 목소리를 모두 보고 판단하는 것과 같습니다. 어 머리길이만 보고 좀 기내? 여자인것같다. 이렇게 하나의 feature만 보면 틀릴 확률이 더 크겠죠.

그럼 각 instance를 따로 학습하지 않고 Bag을 사용하는 이유는 Tracker를 헷갈리게 하면 안되므로 그러는건데요. 한 물체를 Tracking 할때 시간이 지날수록 Tracking하는 곳이 모호해지고 빗나가게 됩니다. 여러개의 인스턴스를 가지고 있으면 더욱 그러하겠죠? Tracking이 되더라도 tracked location이 자주변경되 Box가 흔들리고 안정적이지 못할겁니다. 물론 그 와중에 계속 새로운 positive를 학습하니깐 tracker는 더 헷갈릴것이고요. 그러므로 Bag을 이용해 여러개의 positive sample들을 사용하면서 헷갈리지는 않는 tracking을 할 수 있어요.

기계학습 그리고 패턴인식.

기계학습에 있어서 패턴인식은 가장핵심적인 부분인 동시에 대체되는 단어로도 사용할 수 있을 것 같에요. 인공지능 프로그램은 상황을 인지할 때, 어떤 패턴을 이용하여 인식한 후에 원하는 행동을 하게 되는 것이겠죠. 즉 학습하기 위해서는 인지한 것을 자기것으로 소화시켜야 하는거죠. 그 부분이 패턴인식이고요.

패턴 인식

Pattern Recognition system은 어떤 객체를 분석해서 올바르게 분류해내는 시스템이에요. 사물을 보고 어떤 물체인지 알아내거나 어떤 행동을 하기 위한 기준을 만드는 것이죠. 이러한 작업에는 공통된 일련의 작업들이 있어요.

1. sensing
2. pre-processing and segment
3. feature extraction
4. classification

5. post-processing

대충 제목들만 봐도 알겠죠? 인공지능과 흡사하기때문에 사람이 인지하고 생각하기까지를 예를 들어볼게요.

1. sensing은 인간으로 치면 오감을 이용해서 상황을 느끼는 거에요. (여자들은 sixsense를 가지고 있다는데 정말인가요?)
2. pre-processing and segment 는 전처리부분으로 눈이 않 좋은 사람들이 안경을 끼는 것과 비슷하죠. sensing을 더 확실히하기 위한 방법이죠. 노이즈가 많은 음성데이터나 영상데이터등을 분석하기전에 좀 더 깔끔하게 하는 것입니다.
3. feature extraction은 여자를 볼때 얼굴, 가슴, 다리, 엉덩이, 목, 어깨, 팔,,, 성격 등을 보며 판단 하는 것과 같습니다. 이렇게 sensing으로 얻은 데이터를 feature로 표현해서 판단의 근거를 만드는 것이죠.
4. classification 으로 위의 feature들을 가지고 판단을 하는 부분입니다. 사전에 데이터를 가지고 이 정도면 Positive이다, Negative이다 선택 하는 것이죠. 이전에 Positive와 비슷한 feature들을 가지고 있으면 Positive라고 분류될 확률이 크겠죠?
5. post-processing은 위에서 잘못판단을 할 수도 있으니깐 최대한 맞추려고 노력하는 것입니다. 한가지 예로는 사진을 인식할 때 바다 한가운데 피아노가 있으면 이상하니깐 이 피아노는 잘못된 분류라고 생각하는 것입니다.

이 단계들은 모두 중요합니다. 그런데 제가 하려는 패턴인식은 3번과 4번이 중점이 되겠어요. sensing은 하드웨어 쪽에서 카메라를 잘만들고 자이로센서, 마이크등 센서를 잘만드는 분들이해 주셨으니 전 열심히 최선을 다해서 특징추출하고 분류해서 답내고 또 답이 잘안나올거같으면 후처리를 합니다.


특징생성
특징생성이란 단어가 특징추출로도 쓰이기도 합니다. 여기선 특징생성은 특징을 추출해서 그러한 특징을 선택하는 것까지 를 특징생성이라고 할게요. 즉, 특징생성 = 특징추출+특징선택

위에서 말한것과 같이 어떤 객체를 분류하기전에 그것을 대표할 특징들이 필요하겠죠. 이것을 특징벡터라고할게요. 이 특징벡터은 첫째, 분별력이 좋아야하고 둘째는 또 차원이 낮아야합니다. 어떤 특징들의 분별력은 좋지만 계산할 때 너무 오래걸릴만큼의 차원이면 실용적이지 못하겠죠. 반대로 계산이 가능할 정도의 차원이지만 분별력이 낮은 특징벡터는 쓸모가 없겠네요. 그러므로 이 두가지를 고려해서 특징벡터를 만들어야해요.


특징 추출

특징생성에서 데이터의 종류가 무엇인가에 따라서 2차원 이미지인가, 음파처럼 파형을 이루는 데이터인가 등등 실세계에 나오는 데이터마다 추출방법이 바뀔 수 있고 데이터의 종류가 같더라도 분류방법에 따라서도 바뀔 수 있어요. 그리고 데이터의 종류가 같고 분류방법이 같아도도 어떤 객체를 구분해낼 것인가, 어떤 상황에서 그객체를 구분해 낼것인가에 따라서 추출방법이 다양해요


특징 선택

특징선택은 특징추출에서 나온 특징벡터에서 필요한 특징만을 뽑아내 차원을 줄이는 단계에요. 이 필요한 특징을 추려냄에 있어서 특징마다 분별력을 측정해야죠. 분별력이란 그 특징이 가지고 있는 성질로, 같은 특징부류이면 동일성을 같고(분산이 작은) 다른 특징부류들과는 구분될수 있는 (분산이 큰) 능력을 말해요. 분별력을 측정할수 있는 방법은 여러가지가 있네요. 예를들면 KL divisions, training sample distance 측정, 특정한 classifier를 위한 selection 등등. 이렇게 분별력을 토대로, 생성된 특징벡터에서 쓸모 없는 특징을 빼내면서 특징 벡터를 최적화하는 거죠. 이 때 부분집합 선택문제를 가지겠죠. 즉, 분별력이 높은 특징들만으로 특징벡터를 만든다고 그 특징벡터가 가장 좋은 특징벡터라고 말할 수 없는거죠. 어떤 특징들로 한 객체를 표현하는데 구분력이 높은것만 가져다 놓을때엔 조합의 문제를 신경쓰지 않은것 이므로 오히려 더 않좋은 특징벡터가 될수 있는것이죠. 예를 들면 이쁘고 안이쁜 여자를 구분할 때 허리사이즈와 몸무게그리고 키가 있는데,개별적으로 봤을때 몸무게로 구분하는게 가장 구분하기 쉽고, 그 다음 허리사이즈 마지막으로 키로 구분할때 가장 쉽다는 결과가 나왔다고 해볼게요. 그러면 몸무게와 허리사이즈를 선택해야할까요? 아니죠. 몸무게와 허리사이즈는 어느정도 연관관계가 있어서 몸무게만봐도 허리사이즈를 어느정도 가늠할수있습니다. 그러므로 몸무게와 키를 선택하는게 가장 좋은 특징벡터일수 있죠. 이렇게 특징 을 선택할땐, 최종조합의 분별력도 고려해야되요.

AdaBoost

AdaBoost

AdaBoost는 Boost의 종류의 하나로 Adaptive Boot의 줄임말입니다. 적응한다는 것인데요. 어디에 적응하냐 하면 'error'에 적응하는 것입니다.

샘플을 잘 살펴보고 에러를 최소화 할수 있는 weak classifier로 분류를 합니다. 그래도 error가 생기는 샘플이 있을 수 있겠죠? 원래 Positive인데 Negative로 분류되었거나 그 반대인 경우입니다. 이 error가 발생한 샘플에 가중치를 더 두고, 다시 그 것을 잘 분류 할 수 있는 weak classifier를 고릅니다. 그리고 다시 에러 난 샘플에 가중치를 더두고 weak classifier를 찾습니다. 이 행위를 여러 번하면 충분한 weak classifier들을 만들어지고, 그 것들을 합치면 가지고 있는 샘플들에 대한 에러가 거의 없게 되겠죠. 그 합친 classifier를 Strong classifier라고 부르며, weak classifier들의 선형 조합으로 표현됩니다.

$$F(x)={ \alpha }_{ 1 }{ f }_{ 1 }(x)+{ \alpha }_{ 2 }{ f }_{ 2 }(x)+\cdots +{ \alpha }_{ n }{ f }_{ n }(x)$$
여기서 $F$는 strong classifier, $\alpha$는 weight, $f$는 weak classifier 입니다.

Pseudo-code
입력: 라벨링된 데이터
w를 초기화한다.
T번 반복(T개의 weak classifier)
    weighted error를 보고 가장 좋은 weak classifier를 선택해 추가한다.
    틀린 샘플에 weight를 더 준다.
T개의 weak classifier를 합쳐서 Strong Classifier로 만든다.


밑에 애니메이션을 보면 이해하기 쉽습니다.

AdaBoost 애니메이션 from a presentation by Qing Chen, Discover Lab, University of Ottawa

Machine Learning은 뭐죠?

Machine Learning이 뭔지 알고 시작해야죠


1) Arthur Samuel은 Machine Learning은 컴퓨터에게 프로그램되지도 안고 배울 수 있는 능력을 주는 분야라고 하네요

2) Tom Mitchel은 Machine Learning은 경험(E)으로부터 계산(P)해서 어떤 일(T)에 대해 배우는 컴퓨터 프로그램이라고 하기도합니다.

  즉, 컴퓨터가 스스로 데이터를 처리하는 일련의 과정인 것입니다. machine learning은 데이터가 방대해진 요즘 가장 각광받기도하고 가장 많이 쓰이는 컴퓨터 과학이기도 합니다. 그래서 예시들도 모두 우리와 밀접해 있어요.
  하루 10억건이나되는 구글의 검색은 누가 랭크를 올리고 내릴까요? 배워먹은 컴퓨터입니다. 수천개의 언론사로 부터 같은 주제의 내용을 묶어 보여주는 것도 컴퓨터가 합니다. 그 외 스팸메일을 막기도하고 사용자에 맞는광고도 보여주고 많은걸 컴퓨터가 알아서하는거죠.

 데이터 홍수를 지나서 쓰나미처럼 몰려오는 지금 이러한 자동 데이터 처리는 필요가 아닌 필수가 되어버린 시대입니다.






1) Arthur Samuel. Machine Learning:Field of study that gives computers the ability to learn without being explicitly programmed.

2) Tom Mitchel. Well-posed Learning Problem: A computer program is said to learn from experience E with respect to some task T and some performance measure P, if its performance on T, as measured by P, improves with experience E.

(위에서 말한 아서와 탐이말한 원본인것같은데 내나름대로 의역했으니 이 원본을 보시고 이해하는 것이 나을지 모르겠네요.)

Supervised learning And Unsupervised learning

기계학습에는 크게 두 가지 방법으로 나눌 수 있어요. 첫 번째로 supervised이에요.
이 방법은 데이터와 그 데이터가 의미하는 결과 값을 미리 학습시킴으로써 그 외의 데이터들이 어떤 결과 값을 가질 것인지 판단하게 하는 거에요. 그러므로 이 방법은 올바른 결과를 가지고 있는 데이터들을 사용해야 하겠죠?. 예를 들면 교사가 남아서 썩은 음식물, 어디에다도 쓰지못하는 핵폐기물, 모니터가 안 나오는 노트북이란 데이터에 쓰레기라는 결과 값으로 데이터를 입력해주었네요. 그러면 학생은 ‘곽진산’ 을 보고 당연히 이건 쓰레기라는 결과 값을 내놓겠죠. 결국 사전데이터에 입각한 결론을 내는 알고리즘들이 이 방법이라고 할 수 있습니다.

이렇게 사전데이터를 주고 결과값을 받을 땐 continuous한 것과 discrete한 것이 있죠? 예를 들면 내가 어떤 집을하나 장만할려고 해서 그 집을 어느정도 가격에 사야되는건가? 할때는 그 결과값이 1276003656원일수도있고 23412.23원이 될 수 있죠? 그에 비해 이 집을 사야될지 말아야될지를 구분하는 것은 discrete 결과이죠. 이렇게 Regression과 Classification을 구분할 수 있겠네요.

두번째는 Unsupervised는 supervised랑 비교되는 몇 가지 특징이있죠. 우선 사전데이터, 그에 따른 결과가 필요없어요. clustering을 생각해보죠. clustering은 데이터들의 속성 값을 계산해서 인접한 데이터끼리 묶어내는 것으로 사전데이터가 필요없죠. 어떤 속성을 측정해서 인접성을 찾아낼 것인가가 중요한 것이죠. 예를 들면 눈,코,입이란 공통적인 속성을 가진 데이터끼리 비교해 이쁘고 착한친구와 못생긴 나쁜 괴물을 구분짓는 것입니다.