Linear Models

- Linear model 이란 직선이 boundary가 되어 classification을 해결하거나 input과 output 사이의 관계가 선형인 모델을 말한다.

- 목차 순서와는 다르게 Appendix부터 시작

- 제약 조건을 만족하는 최적화 문제를 constrained optimization problem이라고 한다.

- 한 번에 해결하기 위해 objective function과 제약식을 하나로 묶는 방법

- 제약식들을 더하되, 앞에 coefficient를 추가한다. 이를 Lagrange multipliers (또는 KKT multipliers)라고 한다.

- 이를 합친다는 것의 의미는 제약을 penalty로 치환하는 것과 같다. 예를 들어, g(x)가 0이 아닌 양수면 $\lambda$를 특정 양수로 줘서 penalty를 증가시키는 방식이다. h(x)가 제약을 어겨 양수라면$\alpha$도 0 이상의 값을 준다.

- 최종적으로 제약을 어기면 minimize가 잘 이루어지지 않도록 하게 된다.

- x에 대해서 minimize만 하는 것이 아니고, $\lambda$와 $\alpha$에 대해서는 maximize를 하도록 되어 있다. x뿐만 아니라 $\lambda$와 $\alpha$의 함수로 생각한다.

- x는 F에 속해있어야 하고, F는 제약식을 모두 만족하는 영역이다.

- 목적함수를 만족하는 $x$를 $x$* 라고 한다.

- g(x)는 0이 되므로 신경 쓸 필요 없고, h(x)는 0보다 작거나 같기 때문에 작을 경우를 보면 $\alpha$가 0이 된다.

- 제약을 만족하면 f(x)와 같고, 위반하면 무한대가 된다.

- 제약을 어긴 solution을 infeasible solution이라고 한다. infeasible

 

- 일반적으로, min max E>= max min E 부등호가 성립된다.

- x가 min인 값으로 정하면 왼쪽항이 더 크다.

- maximize하는 y로 한정하면 모든 y라는 제약이 필요 없어진다.

- 다시 양쪽에 min x 를 씌운다. 오른쪽 항은 이미 min x가 존재한다. minimize하는 x가 추가되었기 때문에 모든 x의 조건을 제거한다.

- x에 관해서 minimize를 진행한 것을 $L_{d}$라고 하고, dual function 이라 부른다.

- dual function으로 바꾼 뒤에, $\lambda$와 $\alpha$에 대해서 maximize하는 방법으로 문제를 해결한다. 더 쉽다.

- optimal solution일 때, h(x)=0인 제약을 active constraint라고 한다.

- 해석적으로 풀어지지 않는다면 Gradient ascent search를 활용한다.

 

- 제약이 있음으로 인해서 더 좋은 minimal을 배제하기도 함

 

- parametric한 모델은 structure는 고정되어 있고 구체적인 모양을 결정하는데에 파라미터들이 쓰인다.

- tree나 rule 모델은 사전에 정해둔 구조가 없다.

- Linear model은 stable 하다. training data에 조금 변화가 있더라도 결과가 크게 달라지지 않는다.

- 또한 overfitting의 위험이 적다.

 

- Error (MSE)은 Bias와 Variance로 구성된다.

- Bias는 모델의 예측 값의 평균과 실제값의 차이이고, Variance는 모델의 예측값과 평균 예측값의 차이를 나타낸다.

 

- Bias와 variance는 둘 중에 하나를 해결하려고 하면 나머지 하나가 커지는 경우가 많다.

- 간단한 모델은 variance은 작은 경우가 많지만 bias가 크고, 복잡한 모델은 bias를 줄일 수 있지만 training data에 따라 민감하게 fitting하기 때문에 variance가 커진다.

- Linear model은 variance가 낮고 bias는 큰 모델이다. 주어진 데이터가 제한적일 때 쓸만하다.

 

- loss를 최소화할 수 있는 weight를 찾는 것이 목적

- Batch gradient descent는 모든 training data를 보고 weight update를 한다. 느린 대신 convergence를 보장한다.

- Stochastc gradient descent는 일부 data를 보고 weight update를 한다. convergence를 보장하지 않지만 빠르다.

- irrelevant한 feature들의 weight를 줄이기 위해 regularization function을 추가한다.

- irrelevant한 weight 값을 0에 가깝게 최소한으로 줄일 수 있게 된다.

 

- Regularization을 Constrained optimization의 관점으로 해석 가능

- R1은 직선 형태기 때문에 특정 weight를 0으로 만들어 아예 날려버릴 수 있다. -> sparse model

- R2를 사용하게 되면 closed form solution을 만들 수 있다. 

- hypothesis가 주어졌을 때 데이터의 확률을 likelihood라고 부름

- logistic regression model이 주어졌을 때 데이터의 확률

- log likelihood를 maximazation 하는 것이 목적

 

- SVM은 linear model을 이용함에도 불구하고 space transform을 하기 때문에 class boundary가 nonlinear 해질 수 있다.

- example들이 표현되는 feature space를 nonlinear mapping을 통해 새로운 space로 (보통 dimension이 높아짐) transform 하면서 nonlinear boundary를 생성한다.

- 아래의 식과 같이 class를 모두 포함하여 나타낼 수 있다.

 - solution이 무한할 수 있기 때문에 $\rho$||w|| = 1로 고정한다. 따라서 $\rho$는 maximize하면서 ||w||를 minimize하는 문제로 바뀌게 된다.

- problem을 dual problem 형태로 바꾸면 d에 의존하던 complexity를 N에 의존하게 된다.

- kernel trick을 사용할 수 있다.

 

- w는 support vector의 weighted sum이 된다.

- support vector와 test example의 내적을 취하고 $\alpha$곱하고 summation 하는 방식으로 판별식 계산

- m보다 크거나 작다고 판별하지 않고 0을 기준으로 판별한다.

- SVM은 결과적으로 support vector만 중요하지 나머지는 중요하지 않다. -> simple classifier (logistic 등)를 사용해서 경계에서 매우 멀리있는 example들을 filter out한다. 그 후에 계산을 하면 시간이 훨씬 줄어든다.

 

- dimension이 높은 space로 가서 내적을 취하게 되면 computational cost가 높아짐 -> 내적 후에 kernel을 씌움 -> efficient

- 위의 Polynomial 의 예로 보면 2 dimension에서 6 dimension으로 증가

- q가 증가할 때마다 dimension이 크게 증가함

- 이론적으로는 q만 충분히 크면 원하는 accuracy만큼 boundary가 복잡해지도록 만들 수 있다.

 

- Polynomial kernel의 q만 증가시키는 것이 아니라, 문제에 따라서 여러 커널을 선택할 수 있다.

- RBF kernel: RBF neural network와 비슷하다.

- Sigmoid kernel: neural network에서 MLP와 비슷하다.

- 자이 값이 1보다 크면 loss의 역할을 한다.

- C가 클수록 complex한 모델이 더 큰 페널티를 받게 됨

- C가 작을수록 경계선을 넘나드는 것을 허용함. 모델이 지나치게 nonlinear 하지 않도록 하게 된다.