yupsung Computer Science blog

03_1 : Anomaly Detection : Overview 이번에 알아볼 Anomaly Detection은 Data를 기반으로 다른 패턴, 특성을 보이는 객체를 찾아내는 방법이다. 이에 앞서 앞에서 지금까지 공부했던 Machine learning을 지도학습과 비지도학습으로 분류해보자.  Machine Learning 정의된 task T 가 있고, 성능을 측정할 수 있는 방법 P 가 있을 때 경험(Data) E 로부터 성능이 향상되는 컴퓨터 프로그램을  학습(Learn) 한다고 지칭한다. Machine Learning 은 이러한 조건을 만족한다. Machine learnnig은 주어진 Data의 특징에 따라 크게 두가지로 분류한다. Supervised learning 주어진 Data에 Target value (Y)를 알고있다. 주어진 Data (X, Y)를 사용하여, X와 Y사이의 관계, 이를 표현 가능한 함수 $Y=f(X)$를 알아내는 것이 목표이다. 지금까지 공부했던 Classification, Regression등이 여기에 해당한다. Unsupervised learning 주어진 Data에 Target value (Y)가 주어지지 않는다. 하지만 Data (X) 자체가 가지고 있는 특징$f(X)$를 알아내는 것이 목표이다. 주어진 Data (X)를 사용하여, 각각의 객체들의 밀도를 추정하거나, 객체들의 군집을 찾거나 변수들 간의 연관성을 유추한다. Anomaly Detection (이상치 탐지) Anomaly는 두가지 관점에서 정의된다. 데이터 생성 메터니즘 " Observations that deviate so much from other observations as to arouse suspicious that they were generated by a different mechanism (Hawkins, 1980) " 일반적인 데이터와 다른 메커니즘으로 발생한 data를 anomaly라고 한다. 데이터 분포 (밀도) ...

02_4 : Kernel based learning : Support Vector Regression (SVR) 앞에서 공부했던 SVM은 binary classification을 하기 위한 방법이었다. 이번 글에서 알아볼 SVR은 함수를 추정하여 연속적인 수치변수를 예측하는 회귀 방법이다.  SVR을 알아보기에 앞서 우리가 하려는 함수추정의 목적을 살펴보자. Fitting function 함수를 추정하고 싶을 때 우리의 목적은 크게 2가지로 나뉜다. Minimize an error measure (Loss function) 한마디로 error를 최소화 하여야 한다. (잘 맞춰야 한다) Function to be simple 같은 성능이라면, 함수는 최대한 단순해야 한다. 함수가 단순하다는 뜻은 아래의 조건들을 의미한다. Fewest basis functions Simplest basis functions Flatness is desirable Support Vector Regression (SVR) 위에서 살펴보았던 Loss function과 Flatness를 반영하도록 목적함수를 만들 것이다. SVR에도 여러 종류가 있는데, 우선 $\varepsilon$-SVR에 대하여 알아보자. 현실의 Data들은 어쩔 수 없이 발생하는 noise가 존재한다. 아래 식에서 noise는 $\varepsilon$이다. $$y = f(x)+\varepsilon$$ $\varepsilon$-SVR에서 핵심 아이디어는 $\varepsilon$ 보다 작은 noise에 대해서는 Loss를 주지 말자는 것이다.  왼쪽 그림에서 색이 칠해진 영역을 Epsilon-tube 라고 하는데, 이 영역안에 있는 객체들에게는 Loss를 부여하지 않는다. 이를 위한 Loss function은 오른쪽에 표현된다. 이 Loss function은 hinge를 닮았다고 해서, Hinge Loss 라고 불린다. 차이가 $\varepsilon$ 보다 작은 경우 loss는 0이고, $\vareps...

02_3 : Kernel based learning : Support Vector Machine (SVM) - Soft margin 이전 글에서는 Hard margin을 사용하는 SVM에 대하여 알아보았다. 이번에는 Soft margin을 사용하는 경우를 알아보자.  SVM - Case 2 : Linear case & Soft margin 지금까지는 분류경계면에 대하여 margin을 넘어가는 객체가 없다고 가정하고 Hard margin을 적용하였다. 하지만 실제 데이터에는 noise가 존재하기 때문에 위와 같은 경우가 발생하기 마련이다. 위의 경우에 Hard margin을 사용하면 분류경계면의 생성이 불가능하다. 그래서 모든 객체가 margin의 밖에 존재해야 한다는 제약을 제거하고 margin 안쪽에도 존재할 수 있도록 예외를 허용해주는 방법이 Soft margin이다. 물론 margin 안쪽에 존재하는 경우를 그냥 허용하는 것이 아니라 Penalty를 준다.  위 예시에서 $\xi$에 해당하는 값이 error 객체에 대한 Penalty이다. Penalty를 부여하는 방법에 따라 C-SVM과 nu-SVM으로 나뉘는데, 이 글에서는 C-SVM에 대하여 알아볼 것이다. Optimization problem (C-SVM) - Objective function $$ min\;\;\;\;\frac{1}{2}||\textbf{w}||^2+C\sum_{i=1}^N\xi_i $$ - Constraints $$ s.t.\;\;\;\;y_i(\textbf{w}^T\textbf{x}_i+b)\geq 1-\xi_i,\;\;\;\xi_i\geq 0,\;\;\forall i$$ Objective function의 $\frac{1}{2}||\textbf{w}||^2$은 기존의 Hard margin에서 사용했던 Margin이 최대화 되도록 한다. 그리고 위에서 말했던 Penalty를 주는 부분이 $C\sum_{i=1}^N\xi_i$식이다. 이 식을 통해 예외를 허...

 

02_2 : Kernel based learning : Support Vector Machine (SVM) - Linear & Hard margin Discriminant Function in classification Binary Classification 문제가 주어졌을때 classification을 수행하는 방법은 크게 4가지가 있다. 우리가 이번에 공부해볼 Support Vector Machine (SVM)은 이 중 Linear Function $g(\textbf{x})=\textbf{w}^T\textbf{x}+b$을 사용한 Classification 방법이다. Binary Classification Problem 우선은 우리가 해결할 Binary classification 문제를 정의해보자. Training data Sample drawn i.i.d from set $X\in\mathbb{R}^d$ according to some distribution D $$S=\{(x_1,\,y_1),\,(x_2,\,y_2),\,\cdots ,\,(x_n,\,y_n)\} \in X \times \{-1,+1\}$$ i.i.d는 independent and identically distributed를 뜻한다. binary classification임으로 각 class를 구분하는데, 0, 1이 아니라 +1과 -1로 구분하는 이유는 SVM의 수학적 formulation을 좀더 간략히 하기 위해서이다. Problem Find hypothesis $h\;:\;X\rightarrow \{-1,+1\}$ in H(classifier) with small generalization error $R_D(h)$ 구조적 위험 최소화 관점에서 일반화 된 error $R_D$를 최소화 하는 분류기 H를 만드는 것이 목표이다. 또한 SVM은 linear classifier임으로 고차원 상에서 high-dimensional data를 분류하는 Hyperplane을 찾는것이 목표이다....

02_1 : Kernel based Learning : Theoretical Foundation 이번 글에서는 Kernel 기반 알고리즘의 이해를 위해 기본적으로 필요한 개념을 공부해 볼 것이다. Shatter "A set of points is said to be shattered by a class of functions if, no matter how we assign a binary label to each points, a member of the class can perfectly separate them." 위의 정의를 살펴보면, 개별적인 각각의 point에 대하여 가능한 모든 binary label을 할당 하였을때 어떤 함수 F를 사용해 모든 point의 구분이 가능하다면, 이 point들의 집합을 Shatter 되었다 고 한다. 어떤 직선 분류기(linear classifier)가 있고, 직선 분류기에 의해 구분되는 Class를 +1, -1라고 생각하자. 그렇다면 이러한 직선 분류기를 사용하여 한 점을 +1, -1로 표현 가능하다. 그렇다면 직선 분류기를 사용하여 두 점의 모든 경우를 표현할 수 있을까? 다음과 같이 4개의 직선 분류기를 사용하면 각 직선 분류기가 각각의 A, B 두 점의 경우의 수를 표현한다. 따라서 모든 경우의 수를 표현 가능하다. 이처럼 함수 F에 대하여 n개의 point를 임의의 +1, -1을 Target value로 하는 분류 경계면의 생성이 가능하면, 함수 F가 n개의 point를 Shatter 할 수 있다고 한다. 2차원 상의 점 3개도 직선 분류기를 사용하여 모든 경우의 수($2^3 = 8$가지)를 표현 가능하다. 그렇다면 2차원 상에서 점 4개를 직선 분류기를 사용하여 모든 경우의 수($2^4 = 16$가지)를 표현 가능할까? 14개의 경우를 표현 가능하지만, 우측 하단의 두 경우를 표현하지 못한다. (이 두 경우는 XOR 문제라고도 불린다) 직선 분류기는 각 차원마다 최대 몇개의 점을 Sha...

01_7 : Dimensionality Reduction : t-SNE Introduction t-SNE는 최근 가장 많이 사용되는 비선형 차원축소 방법으로써 데이터의 시각화에도 자주 사용된다. t-SNE에 대하여 알아보기에 앞서, 그 기반이 되는 Stochastic Neighbor Embedding(SNE)에 대하여 알아보자. Stochastic Neighbor Embedding (SNE) 이란? non-local distance를 보존하는 것 보다, local distance를 보존하는 것이 더 중요하다. Local distance를 최대한 보존할 수 있도록 새로운 좌표계를 만드는 것이 LLE와 SNE의 목표이다.  SNE은 LLE와 유사하지만, neighbor를 선택하는 방법에서 차이점이 있다. LLE가 Deterministic(결정론적인)한 방법을 사용한 반면, SNE는 Stochastic(확률론적인)방법을 사용한다. 기존의 LLE에서는 Deterministic하게 가장 가까운 k개의 neighbor를 선택하여 그 local distance를 보존하도록 하였다. SNE는 LLE와 다르게 Probabilistic하게 neighbor를 선택하고, 각 pairwise local distance를 보존한다. 즉, 각각의 pairwise distance가 local인지 non-local인지 확률적으로 결정한다. SNE에서 하나의 data point가 다른 data point를 neighbor로 선택할 확률을 어떻게 나타내는지 알아보자. $i$라는 data point를 기준으로, high dimension(원본 Data의 차원)과 low dimension(차원 축소한 Data의 차원)으로 나누어 생각해보자. Probability of picking $j$ given in high D  원본 Data (차원 $d$)에서 객체 $i$가 $j$를 이웃으로 선택할 확률 $$p_{j|i} = \frac{e^{-\frac{||x_i-x_j||^2}{2\sig...