yupsung Computer Science blog

1. Difference from other ML paradigms There is no supervisor, only a reward signal Feedback is delayed, not instantaneous Time really matters (sequential, non i.i.d. data) Agent’s actions affect the subsequent data it receives 2. Reward Reward $R_t$ : a scalar feedback signal Agent’s job is to maximize cumulative reward Reward hypothesis : all goals can be described by the maximization of expected cumulative reward 3. Sequential Decision Making Goal: select actions to maximize total future reward Reward may be delayed It may be better to sacrifice immediate reward to gain more long-term reward (greedy $\leftrightarrow$ optimal) 4. RL Agent Policy: agent’s behavior function Map from state to action Deterministic policy : $a = \pi (s) $ Stochastic policy : $\pi (a|s) = P[A_t = a | S_t = s] $ Value function: how good is each state and/or action Prediction of future reward. Evaluate the goodness/badness of states State-Value function $$v_{\pi}(s) = E_{\pi} [R_{t+1} + \gamma R_{t+2} +...

1. Ensemble Learning Set of models is integrated in some way to obtain the final prediction Homogeneous : It uses only one induction algorithm SVM1 + SVM2 + SVM3 ... Heterogeneous : It uses different induction algorithms SVM + DT + DNN + Bayesian ... Adds complexity Violation of Occam's Razor Decision boundary may become simpler Data manipulation : Changes the training set in order to obtain different models Manipulating the input features Sub-sampling from the training set Modeling process manipulation : Changes the induction algorithm Manipulating the parameter sets Manipulating the induction algorithm Combine Models Algebraic method : Average, Weighted Average, etc. Voting method : Majority Voting, Weighted Majority Voting, etc. Base Models : The base classifiers should be as accurate as possible and having diverse errors, while each classifier provides some positive evidences 2. Bagging (Bootstrap AGGregatING) Averaging the prediction over a collection of predictors genera...

1. Artificial Neural Network (인공신경망) Overfitting이 문제점이 되어 잘 사용되지 않았었음 2000년 초 해당 여러 문제가 해결되면서 많이 사용되기 시작 Training Decide input, output, hidden layer's number of node Find weight using training algorithm (Back-propagation algorithm) 2. Back-propagation algorithm Input layer에서 멀어질수록 Chain Rule에 의해서 Update되는 Weight의 양이 적어진다. Activation function 미분 가능한 함수! Sigmoid : 미분식 계산이 쉬움 $f^{\partial}(x) = f(x)(1-f(x))$ 3. Deep Neural Network Multiple hidden layers Vanishing gradient problem Sigmoid의 미분값은 0~0.25사이의 값 여러 layer를 update 하게 되면 계속 작아지는 문제가 발생 ReLU Layer-wise training Overfitting Collecting more data : consuming and expensive Data augmentation Dropout $\rightarrow$ Thinner model, ensemble, focus on more features(less idle node) Local minima Problem even with enough training data Start with multiple random points 4. Deep Neural Networks (cont.) 기존의 Machine Learning 방법의 경우 사람이 직접 feature를 선택(Hand crafted)하였고, 정보의 손실이 있어서 학습에 어려움이 있었다 반면 DNN은 학습을 통해 Data에서 적합한 feature를 추출하여 사용한다 유연하고 범용적으...

 1. Feature extraction / Dimensionality reduction Given data points in $d$ dimensions Convert them to data points in $k(<d)$  dimensions With minimal loss of information 2. Principal Component Analysis (PCA) Find k-dim projection that best preserves variance Process compute mean vector $\mu$ and covariance matrix $\Sigma$ of original data $$\Sigma = \frac{1}{N}\sum_{i=1}^N (x_i - \mu)(x_i-\mu)^T $$ Compute eigenvectors and eigenvalues of $\Sigma$ $$\Sigma v = \lambda v $$ Select largest $k$ eigenvalues (also eigenvectors) Project points onto subspace spanned by them $$y = A(x - \mu)$$ Eigenvector with largest eigenvalue captures the most variation among data $X$ We can compress the data by using the top few eigenvectors (principal components) Feature vector $y_k$'s are uncorrelated (orthogonal) 3. Linear Discriminant Analysis (LDA) PCA vs. LDA PCA does not consider "class" information LDA consider "class" information PCA maximizes projected total scatter LDA ...

 1. What is Clustering? Unsupervised learning Requires only data, no labels Detect patterns Useful when don't know what you're looking for Group together "similar" instances 2. Partition algorithms K-means Mixture of Gaussian Spectral clustering 3. Hierarchical algorithms Bottom up : Agglomerative Top-down : Divisive 4. K-means Clustering Objective : $$ \min_{\mu} \min_C \sum_{i=1}^k \sum_{x\in C_i} |x - \mu_i|^2$$ Initialize : Choose K points as cluster centers Alternate : (EM algorithm) Assignment step (Expectation) : Assign data points to closest cluster center $$Fix \;\mu,\; optimize\;C \\ \min_C \sum_{i=1}^k \sum_{x\in C_i} |x - \mu_i|^2 = \min_C \sum_{i=1}^n |x - \mu_{xi}|^2$$ Refitting step (Maximization) : Change the cluster center to the average of its assigned points $$Fix \;C,\; optimize\;\mu \\ \min_{\mu} \sum_{i=1}^k \sum_{x\in C_i} |x - \mu_i|^2$$ Stop : when no point assignment change 5. K-means Clustering (Properties) Guaranteed to converge in finite n...

  1. 언제 사용하는가 ? Vector features Less than 20 attributes (Computational cost 가 높기 때문) Training data가 충분히 많을 때 2. 장점 Training이 매우 빠르다 복잡한 형태의 target function (decision boundary)도 학습 가능 원본 Data 정보 손실이 없다 3. 단점 Query 답변이 느리다 (거리 계산이 느림) 상관없는 attribute나 outlier에 취약하다 (Smoothing 이 없음) 4. Voronoi Diagram KNN 방법은 모든 training data를 저장 -> 많은 Memory 소모 Voronoi Diagram을 형성하여 Memory 소모량을 줄인다. Training time 증가 Test time 감소 5. Distance Metric Nearest를 결정하는 방법은 distance metric에 달려있음 Euclidean (L2) distance Manhattan / City-block (L1) distance 각 Dimension을 다르게 Scale 하는 Weighted 방법도 있음 그 외에도 다양... 6. Standardization (표준화) 원본(Raw) feature들을 새로운 Z-score로 변경 $$ z_{ij} = \frac{x_{ij} - \mu_j }{\sigma_j} $$ i번 sample의 j번 feature를 표준화 7. Efficient searching 효율적인 검색을 위해 데이터를 구조화 KD tree Choose dimension Choose pivot (median) Split data <repeat> 8. Choosing K Validation data가 없고, Train data만 있다면, N-fold cross validation을 사용 각 K에 대하여 K-NN을 Train, Test 진행 cross validation error가 가장 작은 K를 선택 (일반적으로 홀수...

이번 글에서는 통계학에서 기본적으로 사용되는 용어, 개념들을 정리하였다. 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 ...

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년이 걸렸...