yupsung Computer Science blog

이번 글에서는 통계학에서 기본적으로 사용되는 용어, 개념들을 정리하였다. Sample space (표본공간) : The sample space $S$ is a set that contains all possible experimental outcomes. Experiment (실험) : Any process for which more than one outcome is possible. (Any process that generates data) Event (사건) : A subset of the sample space $S$ Random variable : A function that assigns real number to each element of sample space. $$Real\;numbers = f(Elements\;of\;the\;sample\;space)$$ 확률 변수의 종류 1. Discrete random variables (이산확률변수) : Outputs of a random variable are finite discrete (countable) values. (0, 1, 2, ...) 2. Continuous random variables (연속확률변수) : Outputs of a random variable are continuous (uncountable) values. Probability function ($f$) $$p = f(x)$$ $$x\;:\;Real\;numbers\;that\;the\;Random\;variables\;can\;take$$ $$0 \leq p \leq 1$$ $x$가 이산확률변수이면, $f$는 Probability mass function (p.m.f. : 확률질량함수) 이고 $x$가 연속확률변수이면, $f$는 Probability density function (p.d.f. : 확률밀도함수) 이다. Probability mass function (pmf : 확률 질량 함수) For a discr

05_3 : Semi-Supervised Learning : Graph-based SSL 이번 글에서는 Graph 기반의 Semi-Supervised Learning을 알아보자. Graph-based SSL 가장 기본적인 아이디어는 우리에게 주어진 Data instance들을 Graph의 Node로 표현하고, 각 Data들의 유사성을 Edge로 표현하는 것이다. 여기서 가정은 아래와 같다. A graph is given on the labeled and unlabeled data Instances connected by heavy edge tend to have the same label 구성된 Graph에 대하여 두 instance가 heavy edge, 강한 연결관계를 갖고있다면 두 Instance가 동일한 label일 가능성이 높다고 간주한다. Graph Construction Nodes : $X_l \cup X_u$ Edges : Similarity weights computed from features, e.g. K-nearest neighbor graph : Unweighted (0 or 1 weights) Fully connected graph, weight decays with distance $$ w_{ij} = exp \big(\frac{-||x_i - x_j ||^2} { \sigma^2 } \big) $$ $\epsilon$-radius graph K-nearest neighbor (KNN) 방법은 가장 가까운 K개를 1 weight로 연결한다. 때문에 data의 밀도를 고려하지 못하는 단점이 있다. Fully connected graph의 경우, 모든 경우를 표현하지만, Graph의 크기가 너무 커진다는 단점이 있다. $\epsilon$-radius graph 방법은, 거리가 일정 Cut-off 이하인 Node들 만을 Edge로 연결한다. 이 경우 data의 밀도를 고려 가능하지만, 모든 instance가 연결된다는 보장이 없다는 단점

 05_2 : Semi-Supervised Learning : Self-Training and Co-Training 우선 가장 기본적인 준지도학습 방법 Self-Training에 대하여 알아보자.  Self-Training 우리에게 주어진 정보는 Labeled data $(\mathbf{X}_l,y_l)$과 Unlabeled data $\mathbf{X}_u$이다. Self-training과정은 다음과 같이 진행된다.  1. 우선 주어진 Labeled data $(\mathbf{X}_l,y_l)$를 사용하여 예측함수 $f$를 학습시킨다. $$y_l = f(x_l)$$ 2. 학습이 완료되면, 예측함수 $f$를 사용해 Unlabeled data $\mathbf{X}_u$의 예측값 $\hat{y}_u$를 구한다. $$\hat{y}_u = f(x_u)$$ $$\Downarrow$$ 3. 이제 기존의 Labeled data와 예측함수에 의해 labeling이 된 Unlabeled data를 합치고, 이 data를 사용해 예측함수 $g$를 학습한다. 이때 어떻게 Unlabeled data를 합치는지에 따라서 많은 variation이 있다. 대표적으로 Add all $(x_u,\hat{y}_u)$ to labeled data Add a few most confident $(x_u,\hat{y}_u)$ to labeled data Add all $(x_u,\hat{y}_u)$ to labeled data, weight each by confidence. 모든 Unlabeled data를 합치는 방법, 몇몇개의 가장 예측 confidence가 높은 data만을 합치는 방법, 모든 data를 합치치만 예측 confidence에 따라서 weight를 지정하는 방법 등이 있다. 4. 위와 같은 과정을 Unlabeled data가 없어지거나, 수렴할 때 까지 반복한다. Propagating 1-Nearest Neighbor 다른 예시로 Propagating 1-Nearest Neig

05_1 : Semi-Supervised Learning : Overview 이번 글에서는 Semi-Supervised Learning 준지도학습이 어떤 것인지, 목적이 무엇인지 알아볼 것이다. Machine Learning Categories 일반적으로 Machine Learning 방법은 크게 두가지로 분류된다. Supervised Learning (지도학습) 모든 Data에 Labeling이 완료되어, 입력 X와 출력 Y를 알고있다. 학습을 통해서 $f(x)=y$를 잘 추정하는 함수 $f$를 찾는 것이 목적이다. Unsupervised Learning (비지도학습) Data의 Labeling이 수행되지 않았고, 입력 X만을 알고있다. 학습을 통해서 data 고유의 특징이나 분포를 찾는 것이 목적이다. 그렇다면 지도학습을 하려 하는데, 아래와 같이 $N$개의 데이터에 대해서는 $Y$값을 알고있지만 나머지 $M$개에 대해서는 $Y$값을 모른다. 그렇다면 $M$개의 data는 그냥 사용하지 못하고 버려야 하는걸까? 우리가 지금부터 알아볼 Semi-supervised Learning (준지도학습) 은 unlabeled된 $M$개의 data도 학습에 활용하여 labeled된 data만 사용한 Supervised Learning보다 더 좋은 성능의 모델을 만들고자한다. Backgrounds 준지도학습이라는 방법이 만들어진 계기는, Labeling을 하는 것이 매우 비싸고 소모적이기 떄문이다. 일반적으로 Machine Learning에 사용할 데이터는 Row Data인 경우가 많다. 이를 지도학습에 사용하기 위해서 인력과 시간과 돈을 들여 일일이 Labeling을 하는 과정이 필요하다. 의료 data와 같이 Data를 전문가만 이해할 수 있고 labeling이 가능한 경우도 있고, 반도체 공정 data와 같이 최첨단 장비를 사용해 검사를 수행해야 labeling이 가능한 경우도 있다. 중국어 data와 같은 경우 4000문장을 labeling하는 과정에서 4년이 걸렸

 04_7 : Ensemble Learning : XGBoost : A Scalable Tree Boosting System 이 글은 XGBoost를 공부하면서 이해한 내용들을 정리한 글이다. 논문에는 생략되어있는 수식 전개를 나름 쉽게 설명해보려 하다보니 내용도 많고 수식도 많다. 정리하는데 너무 힘들었다ㅠㅜ  각 항목별로 논문의 몇번째 항목인지 부제목 옆에 적어놓았으니, 글을 읽을 때 논문을 함께 보도록 하자! ( 논문 )  XGBoost는 기존 Gradient Boosting 방법에 Approximation 방법을 적용하여 Parallelize를 가능하게 하고, 하드웨어적인 최적화를 하여 더 빠르게 학습을 진행하면서 동시에 좋은 성능을 보인다. XGBoost가 각광받은 이유 중 하나는 Scalability(확장성)이다. 여러 종류의 데이터들과 목적에 잘 적용되고, 빠르고, 좋은 성능을 보인다. 우선 앞서 다른 글에서 이야기 했었지만, 다시한번 기본적인 Ensemble : Tree Boosting 방법에 대하여 짚고 넘어가자. Regularized Learning Objective (Article 2.1) 주어진 Dataset이 $n$개의 example(instance)들과 $m$개의 feature(variable)로 이루어져 있다고 가정하자. 그렇다면 Ensemble model의 추정값은 아래와 같다. $$\hat{y}_i = \phi (x_i) = \sum_{k=1}^K f_k(x_i),\;\;\;\;\;\;f_k \in \mathcal{F}$$ $$where\;\;\mathcal{F} = \{f(x) = w_{q(x)}\}\;\;(q:\mathbb{R}^m \rightarrow T,\;w\in \mathbb{R}^T)$$ $\mathcal{F}$는 모든 가능한 함수들을 포함하는 Function space이고, 함수 $f_k$는 각각의 Classification and regression tree(CART)이다. CART에서는 각 data들을 $q(x)

  04_6 : Ensemble Learning : Gradient Boosting Machine (GBM) 이번 글에서는 Boosting 방법 중 하나인 Gradient Boosting Machine (GBM)을 알아보도록 하자. GBM에서 파생된 많은 Boosting 알고리즘들이 있다. 예를들어, XGBoost, LightGBM, CatBoost가 있는데, 이후 포스팅 할 글들을 통해 천천히 알아보도록 하자. Gradient Boosting 이란? Gradient Boosting = Gradient Descent + Boosting Ada Boost 방법의 경우, 이전 base(weak) learner가 잘 분류/반영하지 못했던 단점(point들)을 다음 data sampling과정에서 high-weight를 주는 방법으로 성능을 개선하였다. Gradient Boost 방법의 경우, 이름처럼 이전 base learner의 단점을 gradient로 나타내고, 이를 통해 Loss function이 최소가 되는 방향으로 base learner들의 학습을 진행해 나간다. Gradient Boosting 또한 Regression, Classification, Ranking 모든 경우에 적용 가능하지만, Loss function 미분을 정의하기 어려운 순서대로 Regression<Regression<Ranking 순으로 이해가 더 어렵다. 우선 가장 직관적으로 이해하기 쉬운 Regression을 예시로 생각해보자. Motivation (for Regression problem) Data point를 예측한 Linear regression model이 위와 같은 함수를 예측했다고 생각해보자. 그렇다면 모델이 실제 data point를 반영하지 못한 오차는 전차(residual)로 나타난다. $$the\;predicted\;value\;:\;\; \hat{y}_i = f_1(x)$$ $$residual\;:\;\;y-f_1(x)$$ 이때 GBM의 아이디어는 다