머신러닝 수업 3주차 - Supervised Learning

2018.09.19

Supervised Learning

오늘은 Supervised learning을 배우고 다음 챕터들과 연관 있는 Probability (Basic Maths)를 배울 것이다.

먼저 Supervised learning에 대한 general overview를 줄 것이다. 사실 오늘날 머신 러닝의 main power는 unsupervised learning으로부터 나오고 있다. 많은 researcher들도 논문에서 unsupervised learning에 더 초점을 맞추고 있다.

simple case부터 시작할 것이다. simple case를 다루는 건 별로 practical하지는 않지만 그 안에 있는 fundamental idea가 straight forward하다. 그 후에 generalize and discuss the case of "multiple class" 를 하고 move to regression problem 할 것이다.

이 챕터에서, 우리는 positive와 negative 값의 class를 학습하는 simple case부터 시작할 것이다. 지난 주 General overview of machine learning봤는데, 구체적으로 problem statement 를 주면 위와 같다.

system of observation (input) 이 무엇인지는 나에게 중요하지 않다. image, text, speeach, whatever 다 가능할 것이다. 그리고 output (prediction)을 줄 것이다. 이 System이 할 일은 target value y가 나오도록 input x에 대해 output y가 있으면 이들을 mapping하는 것이다. 이때 y가 discrete하면 classification이고 continuous하면 regression problem이다. 우리의 goal은 이 unknown system (for prediction of the output from the observation)을 define하는 것이다.

차의 특성들이 주어져 있다. (given attributes of a car), 차들이 있다고 가정하고 그 차들로부터 feature를 extract할 것이다. Process of machine learning은 1) Collect data 2) Extract feature이다. 위 슬라이드에 있는 attribute들은 kind of feature이다. 지금 주어진 set of feature 혹은 attribute는 'price'와 'engine power'이다. 이를 바탕으로 x에 2-ordered value (벡터) 가 있다. car가 family car인지 아닌지 분류할 것인데, family car는 positive이고 (+), non-family car는 negative이다. (-) 이렇게 2 possible outcome이 있다. 

input인 /x는 2 value를 가지고 있는데, vector를 가지고 다룰 것이다.

/x =  [     price       ]    

/x =  [ engine power]

이것은 kind of feature 혹은 representation of car라고 부르기도 한다. 차로부터 많은 수의 attribute를 extract할 수 있지만, 지금은 simplicity를 위해서 2개만 고려할 것이다. 이 문제는 이제 clear하게 정리되었다. 다음 단계로, 이 값들이 주어졌을 때 (given this value), 우리는 output이 positive인지, negative인지의 make decision을 원한다.

첫번째로 hypothesis class를 설명할 것이다. 이런 value들이 주어졌을 때, 우리가 만드는 prediction들의 set이 있을 수 있다.

x=[  ]   ->   g(x)    ->   + -

이런 관계가 있을 때 어떻게 output을 주도록 g(x)를 정의할 수 있을까 생각해보면, infinite number of possible cases를 떠올릴 수 있을 것이다. 이게 hypothesis class이다.

일단 function g(x)를 rectangular 형태로 simple하게 볼 것이다. 이 function은 어떤 종류의 rectangle로도 정의될 수 있다. 가로로 길죽하든, 세로로 길죽하든 상관없다. 여러 개의 직사각형들을 데이터 위에 그려보면, 이것이 x가 주어졌을 때 prediction을 하기 위한 function들이라는 것을 알 수 있다. 이 function들을 hypothesis class라고 부른다.

그림에 있는 식을 설명하면 다음과 같다. X는 2 value로 구성된 (composed of two values) 데이터이고, y_n은 label of car이다. 이걸 training set이라 부를 것이고 대문자 N은 number of sample을 뜻한다. 수학적으로 {}를 한다면 대부분 set을 나타낸다 (denote). x와 y 아래에 붙은 (subscript) 작은 n은 {} 괄호 밖에 있는대로 n=1부터 N까지이다. 그리고 2개의 variable을 () parenthesis 안에 넣어주면 이 둘이 pair라는 뜻이다. 위 식에서는 (xn, yn) 이렇게 pair로 묶여있다.

car sample들을 denote해보면15 data가 보이기 때문에, 대문자 N (capital N)은 15이다. sample의 scatter plot을 그렸을 때 위와 같은 그림으로 보인다. 가운데 5개의 positive 샘플이 있고, 사이드에 10개의 negative example이 있다. 이 example들을 기반으로 (based on example), my hypothesis를 만든다. 지금 그림 상에 만들어진 것은 rectangular function이다. 이제 function을 define할 것인데, my class C는 +와 - 로 구분하는 것이기 때문에 positive와 negative one을 구분하는 function 개념으로 쉽게 생각할 수 있다.

Rectangle을 만들기 위해서는 4개의 value (price를 위한 값 2개, engine power를 위한 값 2개)만 있으면 된다. 그러면 이 4개의 값으로 specific rectangular function의 shape을 결정할 수 있다. The role of machine learning은 이런 specific hypothesis를 위해서 optimal value (p1, p2, e1, e2)를 찾아내는 것이다. correctly well separate from positive one to negative one을 해야 optimal한 value를 찾은 것이다.

* Value란 무엇을 의미하는가? Kind of parameter를 의미한다.

Empirical Error

우리는 pos와 neg를 구분해주는 실제 정확한 정답을 모른다. one real function C가 있을 것인데, 아직 그것을 모르는 상태이다. 정답 C를 모르기 때문에 지금 구한 function이 how function matches target one하는지를 evaluate할 수가 없다.

C는 실제 답이라고 생각한다면, h(x)는 learn from data를 한 your hypothesis이다. 하지만 큰 문제는 우리가 right answer를 가지고 있지 않게 때문에 지금 우리의 답이 맞는지 아닌지 (how good your answer is) evaluate할 방법이 없다. 이때 사용할 trick은 example을 이용하는 것이다. 이는 Empirical Error라고 부른다. Measure empirical error based on your sample 할 것이다. 이런 space에는 원래 infinite number of sample이 있지만, 우리는 15 limited number of sample (from real distribution) 이 있다. 이 sample들을 가지고 이제 answer이 맞는지 아닌지 measure할 것이다.

위의 E(h|X) 식을 보면 capital N까지 given x마다 h(x)의 output이 15개 sample과 equal한지를 비교한다. 델타(δ) function은 뺀 것이 같은 값일 때 1이 나오고, 아니면 0이 나온다. 그래서 사실 위에 식은 오타가 있는데 우변 맨 앞에 1-를 써줘야 한다!!! 내가 세운 h(x)와 실제 답이 같으면 1-1해서 Error가 0이 되고, 다르면 1-0해서 1이 된다.

delta(x) =  {1  , x=0

delta(x) =  {0  , other

그래프로 그리면 "ㅗ" 이런 모양이 델타 펑션이다. 특정 값에서만 위로 솟는 듯한 형태이다.

δ(h(/xn)-yn)의 결과를 구체적으로 생각해보면 가능한 결과 (famliy car이고 아니고니까 1과 -1) 는 예상한 값이 1, -1이고 실제 값이 1, -1이니까 -2, 0, 2가 가능하다. 뺄셈 (subtract)니까 같은 값일 때만 0이 나오고 아니면 둘이 다를 때는 +2나 -2가 나온다. 이게 델타 펑션 안에 들어가면 둘이 identical해서 δ(1-1) = δ(-1-(-1)) = δ(0) 일 때만 1 값이 나온다. Σ 1-delta(h(/xn), yn) 에서 delta 값이 1이 나오면 내 prediction이 맞다는 뜻이고 그러면 0 error가 될 것이다. 이런 식으로 moment마다 내 error를 define한다.

Margin

지금 위의 예시에는 2 class를 구별할 수 있는 2개의 different answer (blue & yellow = h1 & h2)를 가지고 있다. Empirical error로 계산을 해봤을 때, blue one이나 yellow one이나 둘다 올바르게 분류를 해서 empirical error값이 똑같다. 이 2개가 다 answer가 될 수 있는데, what if I have another candidate? 옆으로 조금 밀어서 이번엔 6개의 error를 갖게 만들면, 아까의 h들보다 error가 크기 때문에 answer가 될 수 없다. 가능한 answer는 yellow, blue 둘 다인데, 이 외에도 infinite number of rectangle이 존재한다. If you don't car한다면 any answer 중 하나를 선택하면 될 것이다. 그런데 constraint를 갖게 되면 그 기준으로 더 나은 answer를 선택할 수 있을 것이다. 

그림을 다시 보면 yellow는 가장 안쪽에, 가장 바깥쪽엔 blue가 있고, 사이에 하늘색 (skyblue) 이 있다. 이 범위에는 infinite number of rectangle이 존재한다. s는 most specific hypothesis (tightest bound of rectangle)이고 동시에 g는 most general hypothesis이다. 둘다 5개의 positive example이 포함되어 있다. 그런데 만약 여러분에게 s와 g 사이에 positive와 negative를 잘 분류하는 직사각형을 그려보라고 하면 일반적으로 다들 오른쪽 그림과 같은 모양을 그릴 것이다. (black thin line = h) 여러분은 sample로부터 최대한 error를 만들지 않기 위해 most specific one이랑 most general one 사이에서 positive와 negative sample들 사이 거리를 이미 계산했을 것이다. 이것을 우리는 margin이라고 부른다. 

cf) 나중에 svm에서 margin에 대해 더 다룰 것이다. horizontal과 vertical 둘다 distance를 calculate해서 margin을 maximize하는 것을 고른다.

그래서, 이제 이 3개를 비교해보면, S와 G와 middle에 있는 H를 비교해보면, 미래에 새로운 example을 더 넣는다면 이 H가 error를 만들 확률이 적을 것이다. margin 덕분에 error를 만들지 않을 space가 더 있기 때문이다. 아주 작게 혹은 아주 크게 만든다면 small noise만 들어가도 miss classify가 일어나는데, 중간 정도 크기로 만들면 작은 노이즈가 생겨도 여전히 잘 classify한다. 이것이 idea of generalization이다. 그리고 이것은 main goal of machine learning이다. 현재보다는 future unseen example을 classify 하는데 관심이 있다.

VC Dimension

여기까지 rectangular shape function 만 고려했는데, 여기부터는 VC dimension 개념을 소개할 것이다. 

VC는 name of person인데 capacity power of function 이라는 idea를 만들었다. 교재는 shattering이라는 용어부터 시작하고 있다. 이전에 본 example은 15개 sample이 있었고, 각각은 positive 혹은 negative였다. 한 포인트에서 positive거나 negative일 수 있었다. n number of sample이므로 all possible combination 을 구해볼 수 있다. 예를 들어 1 example이면 positive이거나 negative가 될 수 잇으므로 2 possible cases가 있다. n=2 (2 samples)라면 첫 샘플과 두번째 샘플이 pos-pos, pos-neg, neg-pos, neg-neg로 총 4가지 possible cases를 가지고 있다. 3 sample이라면 8 possible cases가 있다. 이 결과가 나오는 induction process는 n number of point를 가지고 있을 때, 2의 n 제곱만큼의 different learning problem이 존재하게 된다. (two to the n) 케이스 조합별로 솔루션이 다를 것이다. hypothesis H가 positive example과 negative example을 구별할 때, 우리는 H가 N points를 shatter한다고 표현한다. 

h가 n examples를 shatters 하는데, 지금 moment에서 이 small h를 rectangle이라고 생각할 수 있다. Based on VC dimension theory에 따르면, capital H는 hypothesis class of rectangle이다. VC dimension은 maximal number of point다. H로 shatter될 수 있는 것의 개수가 VC dimension인 것이다. capacity 개념으로 넘어가는데, complexity of function을 의미한다. 이전 슬라이드에서 rectangle일 때의 function은 {(p1<x<p2)&(e1<x2<e2)} 이런 식으로 매우 심플했다. 이 function은 representing sample을 하는데 limited capacity, limited power를 가지고 있었다.

위의 그림과 같이 4개의 samples를 가지고 있을 때, specific h가 4 points를 correctly shatter 가능하다. 그려보면, 4개의 샘플이니까 2의 4승 (2^4) possible cases = 16 cases 의 조합을 가지고 있다. 그러면 모든 샘플이 positive인 경우... all negative인 경우... one positive & other negative....이런 경우가 총 16개 생기는 것이다.

그런데 사각형의 함수를 가지고 있으면 이 16개 케이스 중 어떤 것이든 solution을 찾을 수 있다. 다른 말로 함수가 good capacity를 가지고 있다고 할 수 있다. 그러나 more than 4 samples를 가지고 있다면, 예를 들어 5개의 샘플을 가지고 있다면 사각형을 그릴 때 트러블이 생긴다. 이때는 사각형으로 shatter를 할 수 없다. 그러므로 이런 형태의 (rectangle)의 capacity는 up to 4 이다. (최대 4)

line의 VC dimension은 몇 일까? 작년 중간고사 문제였다. (생각할 시간 3분을 주셨다) 답은 3이다. + - - 이런 식의 3개의 sample 까지는 어떻게 그리던지 line을 그릴 수 있는데 4 number of sample부터는 single line으로 나누려면 trouble이 생긴다. 

look up table의 VC dimension은 몇일까? look up table은 attribute x1...xD의 value들을 memory에 넣는 것이다.

/x1 | vlaue |  ..  |  ..  |  +  이런 식으로 쭉 표가 그려지게 된다.

 ....

vc(H)는 infinite이다. table에는 가능한 많은 데이터를 밑에 넣을 수 있다. 모든 가능한 경우를 다 computer memory에 넣으면 된다.

다른 function들은 다 own capacity를 가지고 있다. line의 capacity (VC dimension)은 3이었고, rectangle은 4였다. loop up table은 infinite였다. rectangle function을 쓴 논문은 본적이 없는데, line을 쓰는 논문은 많이 봤다. 셋 중 capacity가 제일 낮음에도 불구하고 왜 쓰는 것일까? 내가 데이터를 3개 이상 가지고 있으면 not gonna work할 것이다. 어떤 function은 very limited capacity를 가지고 있다는 것은 매우 pessimistic하게 들린다. 하지만 걱정할 필요는 없다. VC가 작은 line같은 것이더라도 VC가 큰 다른 것들에 비해 여전히 더 선호된다. line이 loop up table보다도 더 선호된다. 

우리의 hypothesis에 따르면 observation 중에서 sample belong to same class 끼리는 (같은 class에 속한 애들 끼리는) 서로 비슷하다. 하지만 다른 class에 속한 애들끼리는 highly different하다. so many number of sample이더라도, 심지어 N=100이 더라도 샘플이 이런 식으로 distribute 되어있을 것이라고 생각하지는 않는다. + - + - + - .... (전혀 뭉쳐있지 않은 것을 표현) 이보다는 이런 식으로 더 distributed 되어 있다.

++   --

++   --

그래서 모든 가능한 경우의 수를 고려하므로 basically VC dimension은 문제를 가지고 있다. 실제로 sample들은 서로 다른 class에 속하면 far away each other하다. 그래서 VC 가 3이나 4라고 말해도 실제에서는 여전히 (practically) useful한 것이다. 그러므로 우리가 line을 많은 sample을 가지고 있더라도 classification에 쓸 수 있는 것이다. line은 때때로 too simple해서 not gonna work할 때가 있는데, 그러면 higher capacity를 가진 다른 hypothesis class를 고려하면 되는 것이다. 다차식 (polynomial) 등등...

Noise

그리고 다음으로 moving to term of noise로 넘어간다. main difficulty of designing system은 대부분 noise에서 나온다. noise는 unwanted information, data that is still inherent in data you observed이다. noise를 ouput에서 clear하게 seperate하는 방법은 없다. noise는 이런 방식으로 interpreted된다. 

- recording observing noise at case of electrical signal measure in your brain

inevitable to heart beat vascular signal (심장 박동으로 인한 noise) 

- what about making mistake form human site? + - labeling 이 human에 의해 적히는데 누군가 label을 잘못 적는다. 그러면 no way to change...하다. (supervised learning에서 theta noise라고 부른다.)

- missing information = not completed. 우리는 limited size of information만을 가지고 있다. target을 찾는데 useful한 information이 missing되거나 unobservable 할 수 있다. 이것은 machine learning을 어렵게 만드는 것들이다. 

아까 VC dimension을 볼 때 line이 loop up table보다 preferable이라고 했는데, simple해서 easy to interpret하기 때문이다. observation이 x에 주어졌을 때, input attribute들을 선으로 나눠서 final decision을 하면 이해하기 쉽지만, rectangle은 interpretation이 line보다 complex하다. Recommendation to build machine learning system은 first start with very simple model (ex. line function) 하는 것이다. 이것이 작동하지 않으면 (doesn't work) complexity, capacity를 증가시킨다. simple model은 easy to train 이라는 장점도 있다.

First order function은 y = ax + b이다. fifth order polynomial은 y = w5x^5 + w4x^4 + w3x^3 + w2x^2 + w1x1+ w0이다. 왼쪽은 linear하고, 오른쪽은 non-linear하다. 왼쪽은 2 parameter만 있어서 define하기 위해서 2 value만 있으면 되는데, 오른쪽은 파라미터가 w5부터 w0까지 6 파라미터가 있어야 한다. 6 values를 learn해야 한다. capacity는 non-linear한 것이 line function보다 high capacity를 가지고 있다. 더 높은 capacity를 가졌다는 것은 line function보다 더 많은 것을 represent할 수 있는 ability가 있다는 것이다. 즉, w5에서 w2까지를 equal to zero로 바꿔주고, w1과 w0을 linear 식과 똑같이 맞춰주면 똑같은 일차식을 learn할 수 있다. represent할 수 있는 power를 가지고 있기 때문이다. 그런데 if i change the input a little bit? 지금 우리가 x=1에 해당하는 ouput인 y1, y2를 가지고 있다.

x=1, y1 (linear 모델의 아웃풋)

x=1, y2 (non-linear 모델의 아웃풋)

그런데 조금 변화가 생겼다고 가정해본다. x=1.1이다. 0.1은 작은 noise이고, change in y1은 작을 것이다.  w1에 따라 조금 변할 것이다. 

x=1.1,  y1'

x=1.1,  y2'은 어떻게 다를 것인가?

noise (small change in input)가 생기면 totally different value를 얻게 될 것이다. 아예 fit된 function의 형태가 달라진다.

=> line function은 less variance를 가졌다고 표현한다. simple model has less variance.

* variance and bias

앞서 noise에 의해 별로 변화가 생기지 않는 것을 less variance라고 표현했는데, more bias는 form을 represent 하는데 limited capacity를 의미한다. sample에 대해 더 복잡한 형태로 train을 시킬 수 없으면 bias가 큰 것이다. simple model은 variance가 적지만 limited capacity를 가지고 있다. 복잡한 모델은 sample feature input과 output에 따라 많이 달라질 수 있다. unstable한 결과가 나오고 good result가 아니라고 할 수 있다. variance와 bias는 trade-off가 있다. 두 개 다 줄이고 싶지만 possible 하지 않다. less bias를 가지면 less variance가 생긴다. 

=> Occam's Razer theory라는 nice theory가 있다. first play with simple model을 먼저 할 것을 추천한다. 더 복잡한 모델을 썼을 때 error가 비슷하게 나오면 더 simple model을 채택하는 것이다. (글쓴이 - 아마 이것이 interpretation 및 generality에 더 도움을 준다는 듯)

Multiple Classes

아까의 내용에서 extended to multiple classes로 간다.

real number x는 vector인데, output이 multiple class이다.

binary number of class k는 k=2이고, 어떤 모델을은  +1, -1 로 표현하는 반면 어떤 모델들은 (it depends on the models) +1, 0으로 표현한다. #(number) of classes k=3 인 경우, {1, 2, 3}, {0, 1, 2}, {+1, 0, -1} 등 가능하다.

One-hot encoding

One-hot vector는 set of ordered value 중에서 only one of them만 1 이고, others 는 0 인 것이다.

각 클래스에 해당하는 것마다 다음과 같이 표현할 수 있다. (글쓴이 - 1,2,3대신에 1번째에 1을 넣고, 2번째에 1을 넣고, 3번째에 1을 넣고 이런 식으로 target 코딩을 바꿔주는 것)

타겟 value를 이런 form으로 바꿔서 yn이 composed of 0, 1이 되게 한다. 그러면 K number of these values를 갖게 되는 것이다. y는 k dimensional vector which element is 0 or 1이다. One-hot encoding은 yth element가 1이고, all other은 0이다.

이제 문제를 다른 방식으로 생각할 수 있다. K개의 two class problems라고 볼 수 있다. k class problems를 위해서한 번씩  sample belong to or not을 판단하는 것이다. 그러면 k number of functions가 필요하다.

for given any x일 때, 그 function들을 다음과 같이 표현해볼 수 있다.

/x => { g1(/x) : C1 or N (= class 1 or not)

/x => { g2(/x) : C2 or N

/x =>{ gk(/x) : Ck

이것을 one-versus-all approach라고 한다. target class별로 one specific function을 갖게 된다.

다른 set of binary classification도 할 수 있다. k=3인 경우에,

1 vs 2 하고

2 vs 3

1 vs 3

이렇게 이 때는 3개 function만 있으면 된다. g12 g23 g13

이것은 one-versus-one approach이다. (multiple classification 논문/paper를 읽어보면 이런 용어들이 등장)

K two class problem은 one-versus-all을 의미한다. k개의 class가 있으면 필요한 function 구하는 공식은 (k x (k-1)) / 2 이다. 이걸로 구해보면, k=3이면 3 classifier가 필요하다는 것을 알 수 있다.  k=4를 계산식에 넣으면 6 number of classifier가 필요하다. 이건 토너먼트 같은 느낌이다. 위의 슬라이드에 total empirical error 구하는 공식이 있는데, 아까 난 오류랑 똑같이 1-델타로 수정해주어야 한다!! error이기 때문에 reasonable to reduce the error가 맞다. 

이건 case one-versus-all에 해당하는 그림이다. 지금 우리는 3개의 클래스를 가지고 있다. 처음 배웠던 family car와 non-family car가 아니라 총 3 different car를 가지고 있다. basically one classifier는 rectangle안에 속하는 sample인지를 판단할 수 있다. 하나는 family car인지 판단하고, 다른 건 luxury와 yellow sports를 classify한다. 위의 그림에 "?" 한 부분이 있는데, sports car에도 속하고 luxury car에도 속하는 영역이다. 바깥에 있는 것은 (outside) simple reject to make decision, 즉 reject가 가능하다. reject option도 another class로 들어올 수 있다. 지금 문제가 되는 부분은 either sports or luxury라고 둘 다 말할 수 있는데, 다른 방법은 check the output value를 하는 것이다. how much the sample away from the boundary를 알고 있다면 얼마나 멀리 있는지가 assign to that class의 기준이 될 수 있을 것이다. 예를 들어, sample이 저쪽 끝에 있다면 luxury에 assign하는게 낫다. boundary가 yellow sports car부터 보면 더 높은 곳에 있기 때문이다. (decision margin) 하지만 나중에는 another way를 사용할 것이다. probability를 고려할 것인데, probability가 높은 것을 better한 것으로 선택할 것이다.

지금 본 것이 multiple class로 확장하는 내용이었는데, 앞으로의 다음 수업에서도 이런 approach를 할 것이다. binary를 먼저 설명하고 extend to case of multiple class로 넘어갈 것이다. fundamental idea는 동일하고 조금의 변화만 있을 것이다.

Regression

앞서 본 것은 classification으로 very general framework를 보았다. 이제 regression으로 넘어오면서 output을 numeric discrete 대신 continuous로 넘어간다. single value, 즉 single continuous value output이다. 

function은 g(x)라고 할 것이다. linear든 whatever인데, 일단 linear way로 denote하였다. 맨 아래 g(x)식을 보면 polynomial with d number of inputs 형태이다. 그리고 (5) 식에서 error는 타겟인 y와의 difference가 된다. kind of distance between target and predicted one이다. 위에 있는 식은 나의 (empirical error) loss function이다. 이것은 required to learn the parameter 과정이 필요한데, learning은 나중에 얘기할 것이다. 아까 나온 델파 function은 basically consider the output value is equal or not이었다. 그런데 regression은 directly measure how similar to each other (target one) 이다. 

이제 make problem statement를 해보면, 지난 시간에 이 케이스에 대해서 이야기 했다. mileage로 price of car 예측하기 문제였다. simplicity를 위해 given simple single x가 주어졌을 때의 linear의 coefficient들을 empirical error에 넣으면 이렇게 쓸 수 있다. 

내 error function은 위와 같이 생겼고, (x_n에 corresponding한) parameter w1과 w0가 the only thing that I do not know한 것들이다. given x_n일 때, my model is gonna give some output how similar to target one 을 줄 것이다. 공식을 보면 제곱을 해서 구하는데, 이 식의 해를 어떻게 구할 것인지 (solve) 는 by calculus! 를 이용한다. taking derivative 방법을 이용할 것이다. 그러면 이제 question은 model function이 아닌 error function을 고려하게 되고, parameter의 space를 다루게 된다. 먼저 x의 파라미터 w1을 먼저 생각하고 w0에 대해서는 잠시 잊을 것이다. different values of w에 따라 (depending) different values of the error를 얻게 된다. 내 에러는 그리면 다음과 같다.

error function이 quadratic이라 (제곱, square 때문에) 이렇게 표현한 것이다. w0에 대해서는 잊고, y_n과 x_n이 constant일 때 (주어진 training set) 에 대해 parameter w1을 이렇게 그릴 수 있다. w를 변화시킴으로써 다른 output을 가지게 된 다는 것을 보여준다. 지금 function은 in terms of error에 관한 것이기 때문에 이것을 minimize해줘야 한다. 이것은 고등학교에서 배운 calculus에서 나오는 것인데, derivative = 0으로 만든다. 이것이 where slop does not change되는 point를 의미한다. 그것이 minimum or maximum point인 것이다. (이 둘 혹은 stationary form이라고 언급해주셨으나, 자세한 설명은 하지 않았다) 이것들이 optimization에서의 candidate of answer이다. 지금은 global minimum point가 있다는 것을 function이 어떻게 생겼는지 알기 때문에 안다. 그 포인트를 알기 위해 이제 derivative를 해보면, y=ax^2 형태인 f(x)=aw^2 를 parameter w에 대해서 (respect) 미분했을 때 df/dw = 2aw를 얻게 된다. In order to get optimal value 를 위해서, 이 식이 equal to 0가 되어야 한다. 2aw = 0 으로 쓰고 그러면 w의 default는 0 이 된다. 이것은 aw^n 형태인 경우에만 그런 것이고 우리는 w0라는 another parameter를 더 가지고 있다.

df/w0을 구해야하는 것인데, 2 parameter를 가지고 있어서 consider jointly하는 경우 w1과 w0에 대해 partial derivative (편미분) 을 한다. w0의 respect에서 df를 derivative한다는 것은 다른 모든 것은 constant가 된다는 것이다. w1에 대해서 편미분하는 경우를 먼저 생각해보면 x bar와 y bar는 (x와 y 머리 위에 -가 씌워진 것을 말함) mean of sample이다. x_n과 y_n이 있고, x bar와 y bar가 있고, number of N을 가지고 있으니 w1을 구하기 위한 all the necessary information는 다 가지고 있다.

what if i use second-order? g(x)가 위와 같이 1차식이 아니라 2차식이라면, derivative를 w2에 대해 구해서 setting default to 0이고 하고, w1에 대해 setting equal to 0하고 값을 얻고 w0 미분값을 또 0으로 두고 값을 얻으면 된다. 여기서 더 나아가 higher order로 올리게 된다면 small error value를 갖게 된다. complexity를 올리면 more expressive power와 high capacity를 갖게 된다.

모델을 위한 function g(x)를 define하고 optimization form을 위해 error function을 어떻게 define하는지 보아야 한다. 그림 상에서 red cross는 sample을 보여준다. (denote) 총 6개의 sample을 가지고 있다. 그리고 파란색 선은 first-order, second-order, 5th order 식을 보여준다. order가 높은 선은 error가 적고 (error가 0이다 = perfectly fit with 6 number of samples), 낮은 선은 high error value를 갖는다. 6개의 sample이 이 function에 정확히 들어맞는다는 것은 straight forward하다. 왜냐하면 내가 6개의 파라미터 (fifth order 이기 때문에)를 가지고 있기 때문이다. 6 sample과 6 equation을 가지고 있으면 unique solution을 가진다. 그러면 그 solution으로 정확히 모든 sample에 error없이 들어맞을 수 있다. 그러나 machine learning perspective에서 error가 0인 모델일지라도 이 모델은 매우 bad하다고 말한다. small change of x에 따라 output의 변화가 매우 크기 때문이다. 이게 아까 말한 모델의 variance이다. 완전히 다른 output을 얻게 된다는 것은 generalize에 실패한다는 것을 의미한다.

지금 이 모델들을 directly 비교하기가 어려운데, model selection problem에 대해서 고려해야 한다. 우리는 3 different models (line, second order, 5th order) 을 가지고 있다. 어떤 것을 답으로 해야하나? 하고 보면 generalization을 고려해야한다. 고려했을 때 5th model은 really bad하다. 머신 러닝에서 대부분 ill-posed problem이 있다. unique solution을 갖지 못한 경우를 의미한다. 대부분 large, infinite number of solution을 가지게 된다. sample을 분류하는 unique solution은 없는데, 어떤게 optimal한 방법인지는 future를 고려해야한다. 먼저 linear 모델을 쓸 것인지, 그 다음에 second order 모델을 쓸 것인지, 그 다음 fifth order model을 쓸 것인지 고려해야한다. (inductive bias - https://en.wikipedia.org/wiki/Inductive_bias)

* loss function을 define할 때 왜 absolute를 쓰지 않고 square를 쓰는가? error function에 제곱을 해주면 U자형 그래프가 그려진다. (E= Σ( y_n - g(/x_n))^2 일 때가 아까 본 그래프에 해당) 그런데 절대값을 씌워준다면 geometrically 표현하면 V자형이 된다. (E = Σ | y_n - g(/x_n) | )

그런데 small error를 allow해준 이런 형태도 가능하다. 양 옆의 linear한 부분에는 error로 penalty가 생기는데, 아래의 평평한 부분에는 penalty를 주지 않는 것이다.

이렇게 다른 error function에 따라 다른 solution을 얻을 수 있는데, 어떤 것을 쓸지는 여러분의 선택에 달려있다. 이것은 다른 종류의 inductive bias이다. 이런 형태는 나중에 svm에서 배울 것이다. 그리고 margin 개념에 대해서 이전에 rectangle 형태를 결정할 때 배웠는데 이것도 역시 한 종류의 bias이다. model selection은 possible option들 중에서 어떤 inductive bias를 고를지 선택하는 것이다. learning은 inductive bias없이는 불가능하다. unique solution이나 single solution을 얻기 위해서는 이런 assumption을 추가해줘야 한다! (그게 inductive bias이다)

Triple trade-off

첫번째 것은 capacity or complexity of model이다. 두번째 것은 amount of training data (information) 이다. 세번째는 generalization error on new sample이다. 이들은 trade-off 관계이다. number of sample이 증가하면 error (generalization)은 감소한다. higher complexity일 수록 처음에는 sample의 error가 내려가지만 어느 포인트에서 start to increase한다. 

Summary

이 슬라이드를 요약하면 다음과 같다.

1) numerical value든지, discrete value든지, classification problem이든지, regression probelm이든지 데이터가 주어졌을 때 모든 step의, 모든 task의 첫 번째로 해야할 것은 model g를 specify하는 것이다. hypothesis class를 define해야한다. complicated model인 neural network를 쓸 건지 같은 게 가장 첫번째 step으로 들어가는 것이다. 그러면 set of parameters를 얻게 될 것이다. 예를 들어 rectangle class인 경우에는 p1, p2, e1, e2해서 4 different values가 있었다. 

2) 모델을 define했다면 다음은 error function을 고려해야한다. 모델이 good인지 bad인지를 어떻게 measure할 것인가와 관련이 있다. empirical error를 통해 구한다.

3) model을 define하고, loss function을 define하고 나면 optimization problem만이 남는다. how to minimize that과 관련된 것이다. ( = how to solve this optimization problem) 선택할 수 있는 lots of optimization 알고리즘이 존재한다. 

이렇게 3가지 것들을 고려해야한다. 1) linear model, 복잡한 neural network, non-linear function 중 어떤 거 쓸지 등등 골라주고 2) how to define loss function? absolute 쓸 건지, square 형태 쓸 건지, cross-entropy 쓸 건지, how many sample correctly classified를 지표로 쓸 건지.. 3) optimization way도 just taking derivative가 있고 나중에 배우는 gradient descent method도 있다. 

=> 1) 첫번째로 모델은 enough capacity를 고려해야한다. simple model에서부터 complex model로 넘어가야 한다.

2) loss function을 구할 때는 number of training sample이 중요하다. small number로 구한 error는 reliable하지 않다. 

3) good optimization 방법이 필요하다. complexity 이점에서 고려를 할 수도 있고, 여러 알고리즘 중에서 computer science적인 problem으로 1 day 걸리는 알고리즘과 1 hour 걸리는 알고리즘 사이에서 선택을 할 수도 있다. 

=> 여러분이 라이브러리를 쓰더라도 이런 것들은 determine해줘야 한다.

다음주에는 베이지안을 나갈 것이다. 시간이 허락한다면 symbolistic decision tree 같은 것들도 할 것이다. performance를 improve하기 위해서 multiple model을 combine하는 것도 가능하다. 이 방법을 앙상블 모델이라고 부른다. 어쨌든 오늘까지 챕터 2를 끝까지 나갔는데, 이 챕터는 very general concept을 다뤘다. 다른 모델들을 보더라도 이 3가지 things는 기억을 해야한다. 

SupervisedLearning_2P(1).pdf

probability and statistics

Probability 의 정의는 "A measure of the likeliness that an event will occur"이다. 여러분은 probability 개념에 친숙한가? likeliness는 uncertainty와 관련이 있는데, 이 uncertainty가 machine learning을 하는 사람들이 probability model을 볼 때 어려움을 느끼게 만든다. not clear하기 때문인데, 사실 beauty of probability는 바로 이 not clear함에서 나온다. 그래서 uncertainty를 어렵다고 생각하지 말고 그냥 그렇구나 느끼는게 좋다.

10분안에 비가 올 확률, likely to rain in 10 min? No! 이런게 확률일 것이다. 확률 부분은 교재의 appendix에 있는데, 다음주까지 꼭 이 부분을 읽어와야 한다. 그리고 appendix를 읽고 1 page로 직접 자기가 요약해와야 한다. 하지만 너무 많은 시간을 쓰진 말고 그냥 읽어오기만 하면 된다.

Probability distribution과 density function을 강조하고 싶다. 슬라이드에서 random variable은 mapping an event to specific value해주는 kind of function이다. 이 function은 assign a number in sample space of random experiment 해준다. 이 F(a)는 random variable로 "a" value보다 작거나 같은 확률을 얻어준다. mapping value to outcome events smaller than a 해서 얻은 것이 distribution function이다. 이것을 PDF라고 부른다. 그런데, P(X = 0.01) 이런 식으로 쓸 수 없다. P (X=0.01)은 0이다. define할 수가 없다. probability를 define하는 방법은 위 슬라이드에 있듯이 P{a<X<=b} 즉, between a and b 이렇게 해야한다.

probability density function을 보았는데, discrete의 경우에는 probability mass function (pmf) 라고 부른다.

joint distribution은 more than 2 random variable을 고려하는 것이다. Discrete value는 capital P를 쓰고, continuous value는 small p를 쓸 것이다. capital P는 mass function을 의미한다. small p는 pdf이다.

이 posterior 값은 likelihood와 prior을 곱하고 evidence로 나눠서 구한다. 분모에 있는 것은 marginal distribution by summing up to the random variable들이다. 이 내용들은 appendix에서 다룬다.

expectation은 probability와 관련이 있다. expected output은 value of random variable x와 확률을 곱해서 얻어진다. sum of all possible cases가 expected value가 되는 것이다. discrete case와 continuous case 별로 각각 있다. expectation 은 모든 function에 다 적용할 수 있다. deterministic function g와 probability of x가 있을 때, expectation을 구할 수 있다.

variance는 이렇게 define이 된다. x가 mean으로부터 얼마나 다른지 (varies from around the mean value) 이다. standard deviation은 단순히 square root를 입히기만 하면 된다.

"co"는 "two"를 의미한다. how random variable are related to each other =  how covariated 이다. x와 y가 독립일 때, 이 둘이 동시에 일어날 확률은 x와 y의 곱이고, covariance는 0이 나온다. correlation은 normalized version of covariance일 뿐이다. 항상 값이 +1과 -1 사이에 있도록 standard deviation으로 나누주는 것이다.

베르누이의 경우 동전던지기에서 나오는 head or tail처럼 2 possible outcomes가 있다. 그런데 실험을 multiple time repeat 하게 되면 binomial distribution을 고려해야한다. 베르누이는 오직 하나의 파라미터 p만 있으면 된다.

a set of discrete outcome은 multinomial distribution이다. 또 Uniform distribution도 있다. 우리에게 친숙한 가우시안은 다음과 같이 정의된다. 

univariate 가우시안은 single random variable인 single standard deviation만 알면 fully specify gaussian distribution을 할 수 있다. 그러면 이것을 extend하는 것도 straight forward하다.

a set of random variable 들이 들어가는데, 형태는 아까와 동일하다. 이제는 dimension of random variable과 covariance를 고려해야한다. 첫 번째 시간이 물어보았던 ∫ exp [ -1/2 (x- μ) ^2 ] dx의 답은 여기서 나온다. sigma 제곱 값이 식에 없는데, 이것은 sigma가 1이란 뜻이다. sigma 부분은 normalizer의 역할을 하는 것 뿐이다. 그러면 결과는 2 pi가 나온다. 나중에 detail은 다룰 것이니 먼저 appendix를 읽고 오길 바란다. 그리고 가우시안이 어떻게 생겼나를 볼 수 있는데, 왜 벨 모양으로 생겼는지도 나중에 커버할 것이다. 

beta distribution 같은 건 advance term으로 챕터 16 정도부터 있기 때문에 다루지 않을 것이다. 궁금하면 개인적으로 읽어보길 추천한다.

ML_Basic_Maths_2P.pdf