기계학습37 [ML개론] (14) dual SVM with Kernel 이전글을 통해 dual SVM을 풀어내는 방식은 알아냈다. 그러나 여전히 trend가 존재하는, nonlinear한 형태의 data를 어떻게 분류할지에 대해선 모른다. 그 방법인 Kernel fn에 대해 알아보자. 우리는 좌측그림과 같은 XOR문제를 2차원상에서 해결할 수 없다. 따라서 이를 특정 standard basis 위로 옮겨 3차원 상에 mapping(L -> H)하여 classification을 진행할 수 있다. 그러나 feature의 갯수가 많아질수록 Φ(x) 또한 무한히 커지게 되어 연산과정에 부담이 된다. 따라서 이를 보완하기 위해 등장한 것이 kernel이다. 솔직히 아직도 그 방식을 완벽히 이해하진 못하겠지만 추후 실습코드와 함께 보충을 기약하며 이해한 것을 정리해보겠다. mappin.. 2022. 2. 21. [ML개론] (13) dual problem of SVM SVM은 inequality constraint인 (wx+b)y>=1 아래 w*w를 최소화하는 convex problem과 마찬가지다. 이는 이전글(https://alba-tross.tistory.com/95)에서 살펴볼 수 있듯이 primal fn을 Lagrangian dual fn으로 변형함으로서 더욱 쉽게 해결할 수 있다. 따라서 SVM의 primal fn을 duality를 이용하여 dual problem으로 해결하고자 한다. 풀이방법은 다음과 같다. 첫째, optimal solution w,b를 구하기 위해 Lagrangian fn인 L(w,b,λ)를 w,b로 편미분한다. 그 결과는 위의 식과 같다. 둘쨰, 구한 w*, b* 값을 Lagrangian dual fn인 q(λ)에 대입한다. 그리고나서.. 2022. 2. 21. [최적화] (11) solving dual problem with KKT 그럼 Regularity condition이 충족되었다는 가정하에 inequality constraint가 주어진 primal problem을 duality를 활용하여 풀어보자. 이 때 KKT가 활용된다. 우선 del_x L=0으로 L을 최소화하는 x*를 찾고, del_λ,μ q(λ,μ)=0으로 q를 극대화하는 λ,μ값을 찾는다. 후술하겠지만 간단히 얘기하자면 Lagrangian fn이 x,λ,μ의 함수이기 때문에 del_x L=0의 x*는 x(λ,μ)의 형태로 나오는데, 이 λ,μ를 del_λ,μ q(λ,μ)를 통해 찾아 optimal solution인 x*를 찾아낸다는 얘기다. 자 그럼 처음보는 q(λ,μ), Lagrangian dual problem을 정의해보자. q(λ,μ) = min(L(x,λ,.. 2022. 2. 21. [최적화] (10) KKT condition Lagrangian을 복습해보면 위 두 조건이 optimal solution의 필요조건이었기에 이를 만족하는 lambda를 찾으면 x*를 구할 수 있었다. 그럼 위 수식과 같이 inequality constraint가 존재하는 문제의 필요조건은 무엇인가? 바로 KKT다. KKT는 총 5가지로 구성된다. stationarity, complementary slackness, dual feasibility, primal feasibility가 바로 그것이다. 이 5가지 조건을 모두 만족하는 lambda, mu가 존재하는데 이를 구하면 x*를 얻을 수 있다. 그런데 3,4,5번에 해당하는 feasibility condition은 사실상 주어지는 것과 마찬가지다. g(x*)=0이어야만 한다. 그럼 stationa.. 2022. 2. 21. [최적화] (9) Backtracking Line Search 이전 게시글에서 살펴본 Infeasible Start Newton's Method을 실제로 활용할 때는 W_k+1 = Wk - t*(R(w)/R'(w))로 업데이트해준다. 차이점은 t가 붙었다는 것인데 이 t는 Backtracking Line Search를 융합해준 결과다. 그렇다면 Backtracking Line Search는 어떠한 tool인지 알아보자. 우선 Backtracking을 알기 이전에 Line-Search의 개념을 짚고 넘어갈 필요가 있다. Line Search는 주어진 del x, 즉 newton's method에선 -f'(xk)/f''(xk), gradient method에선 -f'(xk)에다가 상수 t만큼 곱하여 알고리즘을 돌리는 방법이다. 가령 t=0이면 움직이지 않는 것이니 f(.. 2022. 2. 21. [최적화] (8) Infeasible Start Newton's Method 시작에 앞서 양질의 강의를 무료로 제공해주시는 혁펜하임(https://www.youtube.com/watch?v=Nj2aLgatB1Y)님께 감사인사를 전합니다. 본 게시물은 강의를 듣고난 후 정리용도에 불과하니 강의 수강을 권합니다. 지속적으로 강조하지만 연산과정의 복잡성 때문에 optimization problem의 대부분을 algorythm으로 푼다. newton's method의 핵심을 복기해보면 결국 2차 이상의 목적함수 f(x)의 local min/max를 알고리즘적으로 찾는 것이다. 이 때 우리는 taylor series를 활용한다. 만약 f(x)가 2차함수라면 아래 그림과 같이 특정 지점 Xk에서 talyor series로 근사한다. 근사된 함수의 local min/max point가 있을텐.. 2022. 2. 21. [최적화] (7) Lagrangian Multiplier Method 여지껏 우리는 convex problem을 풀기 위한 방법인 gradient method와 newton method를 살펴봤다. 사실 좌측 그림과 같이 2차함수의 경우 미분한 도함수가 0이 되는 지점을 찾으면 convex problem이 해결된다. 그러나 우측 그림과 같은 고차함수의 경우 이를 미분하는 연산 자체가 복잡할 뿐더러 미분이 불가한 함수일 수도 있다. 따라서 우리는 gradient method, newton method와 같이 initial point만 주어진다면 바로 인근의 local minimum을 찾을 수 있는 방법론들을 살펴봤다. "도함수가 0이다"라는 조건은 해당지점이 local minimum이기 위한 필요조건이다. 실제로 해당지점이 local max, saddle point일 수도 .. 2022. 2. 21. [ML개론] (10) Naive Bayes to Logistic Regression 두괄식으로 결론부터 말하자면 NBC는 Generative model의 한 종류이며, LR은 DIscriminative model의 한 종류다. Generative는 joint distribution인 P(X,Y)를 학습에 활용한다. 그러나 P(X,Y)를 활용할 수는 없고 Bayes Thm으로부터 파생되는 prior * likelihood를 사용한다. NBC의 argmax function의 원소가 P(X|Y)P(Y)라는 점에서 이는 P(X,Y)를 학습하는 것과 마찬가지다. P(X,Y)는 (X,Y)라는 instance가 관찰될 확률을 뜻하는데, NBC의 경우에는 P(X=긍정적단어들, Y=긍정)과 같이 특정 X에 대해 특정 Y가 함께 관측될 확률을 학습한다. 반면 Discriminative는 사후확률인 P(Y.. 2022. 2. 20. [최적화] (5) Symmetric Rank-one Update(SR1) A가 nonsymmetric한 경우를 방지하기 위해 symmetric rank-one update가 도입된다. 이는 u*v에서 u*u로 broyden's method의 단점이 보완된 형태다. Hk+1 = Hk + u*u의 양변에 yk를 곱한다. Hk = inverse of (yk / sk) 이기 때문에 Hk*yk는 sk가 된다. 이 식을 정리해주면 우측 상단의 식이 전개된다. u*u*x를 (u*u) * x가 아닌 u*(u*x)로 본다면 괄호 안의 항은 scalar의 형태가 된다. 그럼 이 식은 vector u에다가 특정 scalar값을 곱해주면 z가 된다는 뜻이 된다. 그러면 u는 z와 무조건 평행한 일직선상 위에 놓여야하며 u*x는 무조건 특정한 값이어야만 한다. 따라서 x와 z값만 알고 있다면 u는 .. 2022. 2. 5. [최적화] (4) Broyden's Method 이전글에 이어서 Broyden's Method를 살펴보자. Bk의 관계식 중 A를 우리는 Rank-one mtx라 부른다. 이는 yk - BkSk가 열벡터 u이고, S / SS는 행벡터 v이기 때문이다. 둘이 외적되어 형성된 것이 A다. A는 외적되었기 때문에 그 column 들이 모두 linear independent하다. 따라서 rank one matrix라 불리운다. 사실 우리가 구해야하는 것은 inverse of Bk다. Bk만 구해버리면 이를 다시 inverse 취해주어야하기 때문에 계산을 두번하는 셈이 된다. 이런 번거로움을 해소한 방법이 Broyden's method다. Broyden's method는 아예 inverse of B_k+1과 inverse of B_k 간의 관계식을 정의한다. .. 2022. 2. 5. [최적화] (3) quasi Newton Method 다음은 Newton's Method를 변형한 quasi Newton Method다. 기존 방법은 x_k에서의 순간변화율, 즉 미분값을 구해서 x_k+1을 구했다면, quasi newton method에서는 x_k와 x_k-1간의 평균변화율을 통해 x_k+1을 구한다. 평균변화율은 함수값 차분을 x값 차분으로 나눠주면 된다는 점에서 연산처리가 더욱 간편하다는 장점이 있다. 또한 실제로 미분을 통해 구한 x_k+1값이나 평균변화율을 통해 구한 값이 유사하기 때문에 비효율적이진 않다. 다만 quasi newton을 배우기에 앞서 수식이 어마무시하기 때문에 이를 사전에 간편한 표현들로 약속하고 넘어가자. 평균변화율을 Bk라는 matrix로 설정하는데 이는 y_k-1 / s_k-1 이다. 각 기호에 대한 정의는.. 2022. 2. 5. [ML개론] (12) error handling with loss function 위 그림과 같이 SVM이 처리하는 dataset 중 error가 존재하기 마련이다. 이 error를 대처하기 위한 방법은 크게 두가지가 있다. 첫째, error 그 자체의 존재를 인정하되 penalty를 부여함으로서 SVM 모델 간의 성능을 구분한다. 둘째, linear한 decision boundary를 nonlinear하게 변경해준다. 이번 글에선 전자를 살펴볼 계획이다. penalty는 기존의 min ||w|| 에다가 loss function을 더해줌으로서 부여된다. 더해지는 loss function의 종류에 따라 그 방법이 세분화된다. 첫번째 loss function은 0-1 loss다. Decision Boundary를 넘어서기 전까지 옳은 분류를 하고 있었다면 loss가 0인데, decisio.. 2022. 2. 5. 이전 1 2 3 4 다음 반응형
