글

라벨이 artificial-intelligence인 게시물 표시

Generative Adversarial Nets (Ian J. Goodfellow et al., 2014 NIPS)

이미지
Motivation Deep learning experienced most striking success in discriminative models. However, Deep generative models have had less of an impact because it is hard to approximate intractable probabilistic computations and leverage the benefits of piecewise linear units. The proposed new generative model sidesteps these difficulties by using minimax two-player game. The good analogous of two players are the team of counterfeiters and the police. Solution Minimax two-player game: $\displaystyle \min_{G}\max_{D} V(D, G) = \mathbb{E}_{x \sim p_{data}} \left [ \log D(x) \right ] + \mathbb{E}_{x \sim p_z(z)} \left [ \log (1 - D(G(z)) \right ]$. - Discriminative model $D$: Estimates the probability $D(x)$ that a sample came from the training data rather than $G$. - Generative model $G$: Transforms probability distribution $p_z(z)$ to the generated data distribution $p_g$. Unique solution is $\displaystyle \frac{1}{2}$. This means discriminator can't discriminate sample came from $G...

Multimodal Deep Learning (Jiquan Ngiam et al., 2011 ICML)

이미지
Motivation - Learn features over multiple modalities (ex. audio + video). - Human understands speech with audio+visual information. McGurk effect: visual /ga/ with a voiced /ba/ is perceived as /da/ by most subjects. (McGurk, H. and MacDonald, J. Hearing lips and seeing voices. Nature, 264(5588):746–748, 1976.) Learning architecture - Input: Audio + Visual (lip motion) of single letter & digit. - Find correlation between viseme and phoneme, not raw visual and audio. 1. Sparse RBM (Figure 2-a, b) Baseline. Also use as pretraining models. Informally, these models transform raw data into viseme and phoneme. 2. Bimodal DBN (Figure 2-d) By using RBM pretraining models, find correlation between viseme and phoneme. 3. Single Deep Autoencoder (Figure 3-a) For Bimodal DBN, there is no objective and it is hard to train when only single modality appears. Single Deep Autoencoder solved these two issues, focused on training with single modality. This model uses a RBM pretrain...

Machine Learning (CPSC 540): Markov Chain Monte Carlo

이미지
I'm going to explain MCMC with finite case. Essentially, we don't need MCMC method for finite case but this would be good example for understanding this method. Before this, I recommend reading  http://blog.kleinproject.org/?p=280  which is a good introduction for Markov Chain. Suppose that we want to sample from following distribution. We will sample by exploring the state space $X=\left\{1, 2, 3\right\}$ using a Markov Chain mechanism. Let $T$ be a transition matrix which is aperiodic and irreducible. Then, for any initial probability vector $v$, $vT^t \to \pi \ \textit{as} \ t \to \infty$. Now, if $\pi = \left(\frac{1}{6}, \frac{1}{3}, \frac{1}{2} \right)$, we can sample from object distribution by taking any distribution of initial state and traverse state space with $T$ until convergence. Thus, all we have to do is finding $T$ which is aperiodic, irreducible, and $\pi T = \pi$. This exactly agrees with continuous case which is our aim. In this case, $T$ become...

Machine Learning (CPSC 540): Importance sampling

이미지
Importance sampling is all about distribution changing. I'm going to explain this first with simple coin toss example, and move on to the posterior case. Suppose that we want to toss a coin which has the probability $P(H)=\frac{1}{3}, P(T)=\frac{2}{3}$. However, we don't have that kind of coin. Then, how to simulate this situation with an ordinary coin? Suppose that we tossed an ordinary coin $2N$ times and we get $N$ heads and $N$ tails. We want to regard $N$ heads as $\frac{1}{3}\cdot2N$ heads and $N$ tails as $\frac{2}{3}\cdot2N$ tails. If we assign weights to each event like $\frac{2}{3}$ for head and $\frac{4}{3}$ for tail, we can get desired result. Let's extend this result to the posterior case. We want to simulate $P(\theta\mid D)$ with $q(\theta)$. With some calculations we can get $$P(\theta \mid D) = \frac{P(D \mid \theta)P(\theta)}{\int P(D \mid \theta)P(\theta)\mathit{d}\theta} = \frac{1}{z}\frac{P(D \mid \theta)P(\theta)}{q(\theta)}q(\theta) = \frac{w(\th...

Machine Learning (CPSC 540): Deep Learning

이미지
In this lecture, the professor used image recognition to introduce deep learning. I think the model for learning image is an imitation of heuristics of recognizing image. When we try to imagine what we saw, we combine some features to restore that. That is exactly what autoencoder does. Encoding is abstraction process. It extract features from image data. Next, decoding is restoration process. It combine features to get an image. Why is it plausible to use same weight vector for encoding and decoding? Consider the above linear autoencoder and the image. The activation values are $0.3, 0.5, 0.7, 0, 0, 0$ because there is $30\%$ of $W_1$, $50\%$ of $W_2$, $70\%$ of $W_3$ in the image. Here, we can interpret $W_i$ as a feature. Since we got features of the image, we can restore the image with features. Remember that there is $30\%$ of $W_1$, $50\%$ of $W_2$, $70\%$ of $W_3$ in the image. Then, we can restore the image by $0.3W_1 + 0.5W_2 + 0.7W_3$ and the restored image is an...

Machine Learning (CPSC 540): Neural networks

이미지
In the previous lecture, we learned about neuron and a recipe for learning. In this lecture, we can get a recipe for Neural networks. Actually, steps are very abstract. Just build a neural network, and add probabilistic model to the network. Then, derive likelihood function and take negative log to get cost/objective function which is also cross-entropy. Last, calculate gradient and Hessian analytically (back propagation) and use Newton's method to find optimum. How does Neural network works? and why we need it? First, think about XOR gate. Can we implement this with single neuron (Logistic regression)? No, because we can't separate red points and blue points by a line. So, how can we get orange curve? Let's write orange curve by a implicit function $f(x_1,x_2)=0$ and build only the end part of the Neural network. All we have to do is to approximate $f(x_1, x_2)$ by filling up the unknown orange part of the Neural network. Let's use following basis function. ...

Machine Learning (CPSC 540): Logistic regression

이미지
Basically, logistic regression regressing a binary variable. I drew a diagram different from the lecture, and I think it will help you to understand well. We can see logistic regression is just training single neuron. I understood neuron is a function with properties $\Pi, \theta$ and the training means to determine $\theta$ given data and $\Pi$. In this regard, $\theta_0$ is a bias term which is the property of a neuron. We shouldn't give $0$ whenever the input is $0$ so this is plausible. We can get a recipe for learning here. After we construct probabilistic model, we can derive likelihood function $P(\mathbb{y} \mid \mathbb{X}, \theta)$ and take negative log to get cost/objective function. If we can calculate gradient and Hessian analytically, we can use Newton's method to find optimum. In the logistic regression case, the Hessian of the negative loglikelihood $-\mathrm{log}P(\mathbb{y} \mid \mathbb{X}, \theta)$ is everywhere positive definite. Thus, the objec...

Machine Learning (CPSC 540): Unconstrained optimization

이미지
I'm going to show two kinds of view to the one-dimensional Newton's method and extend it to the multivariate case. In one-dimensional case, gradient descent method is simply $x_{n+1} = x_n - \eta f'(x_n)$. So, how do we choose $\eta$? We can use curvature, the change rate of gradient. Like the figure below shows, if curvature is high, we have to be careful when we proceed and if not, we can move faster. Thus, it is reasonable to choose $\eta = \frac{1}{f''(x_n)}$. Then, we get the following familiar formula. $$x_{n+1} = x_n - \frac{f'(x_n)}{f''(x_n)}.$$We can see this by the following familiar figure. Second view of Newton's method is Taylor series. Second order Taylor expansion at $x_n$ is $f(x) \approx f(x_n) + f'(x_n)(x - x_n) + \frac{1}{2}f''(x_n)(x - x_n)^2$. This is a quadratic curve which approximates $f(x)$ at $x_{n}$. So, we can move $x_{n+1}$ from $x_n$ where $f(x_n) + f'(x_n)(x_{n+1} - x_n) + \frac{1}{2}f''...

Machine Learning (CPSC 540): Random forests

이미지
I think we use random forests because in a real problem, there is lots of data and there are lots of features. Basically, we normally choose $\sqrt{n}$ data points from $n$ training data points and $p$ features out of $m$ features randomly to make a random tree. Then we make ensemble from those trees and this is a random forest. Choosing subset of training data set for each tree is reasonable because there is a infinite number of data points and there is uncertainty in data. However, we can't escape from high variance for each tree because we trained tree with small amount of data and small number of features. By bias-variance trade off, we can assume that bias is low. (Question, Machine Learning (CPSC 540)) Also, we can assume that every tree is not correlated because we chose randomly. Thus, we can expect that if we average all of them, we will get good results.dd There is a theoretical result that when $n$ tends to infinity, the result from forest is consistent while the re...

Machine Learning (CPSC 540): Decision trees

이미지
At first, I want to recommend visiting this website. https://brilliant.org/wiki/entropy-information-theory/ This site describes the meaning of entropy in information theory very nicely. I'm going to describe information content with following condition to help you understand well. Suppose that there are two doors in a lobby. First door is a main entrance, and second door is a entrance that only important people use. We know that the probability the first door opens is larger than the probability the second door opens. You are a supervisor of the lobby and your staff tells you which door opens. Now which information do you think is important? Would you interested in the event that the first door opens? No. This describes following formula in the site. $$I(x_i) = \mathrm{log}_2\left(\frac{1}{p_i}\right).$$Now, how the entropy and uncertainty related? The definition of the entropy is the expectation of information gain which is described by $$\sum_{i=1}^{n}p_i\mathrm{log}\left...

Machine Learning (CPSC 540): Bayesian optimization and multi-armed bandits

I want to know more about four acquisition functions PI, EI, GP-UCB, Thompson sampling . After I understand these things, I will post this on my blog. I think these are important. (Question, Machine Learning (CPSC 540))

Machine Learning (CPSC 540): Gaussian process

이미지
First, I misunderstood the gaussian process because of the name "process". I thought it was a statistical process like the bernoulli process. However, the basic idea of the gaussian process is distribution over functions. We can't represent distribution over functions easily. Thus, we think about values of a function for any arbitrary points $\mathbb{x}_1, \mathbb{x}_2, \cdots, \mathbb{x}_n$ and consider those values follow multivariate gaussian, i.e. $p(f(\mathbb{x}_1), f(\mathbb{x}_2), \cdots, f(\mathbb{x}_n)) \sim N(\mu, \sum)$. In my opinion, I view this as marginal distribution. I imagine that there is original distribution over functions, and we know the marginal distribution over arbitrary points although we don't know the exact distribution over functions. We denote this by $f(\mathbb{x}) \sim GP(m(\mathbb{x}), \kappa(\mathbb{x}, \mathbb{x}'))$ where $m(\mathbb{x}) = E(f(\mathbb{x}))$ and $\kappa(\mathbb{x}, \mathbb{x}') = E((\mathbb{x} - m(\mathbb{x})...

Machine Learning (CPSC 540): Bayesian learning

이미지
In the Frequentist's view, they treat event that can be repeated many times. They use just likelihood for the prediction and they regard the parameter $\theta$ as a fixed constant. However, in the Bayesian's view, they regard the $\theta$ as a random variable and they set a prior hypothesis (or initial belief) to the $\theta$. This view is useful when the event can not be repeated many times and for solving reverse problems. Generally, reverse problem is much harder, for example, it is easy to transform text to sound but reverse problem is hard. Bayesian's view is similar to how machines learns. They have a prior knowledge and that prior knowledge would be updated when machines encounter data. Here, it is good to use conjugate prior for the likelihood function so that posterior distribution are in the same family as the prior probability distribution. We call this conjugate analysis. It is easy to understand Bayesian's view by the example of a coin toss. First, we wan...

Machine Learning (CPSC 540): regularization, cross-validation and data size

이미지
We have regularised quadratic cost function, $J(\theta) = (y-X\theta)^T(y-X\theta) + \delta^2\theta^T\theta$. Then, how do we choose the regularization coefficient? This means "how do we control the model complexity?" because if $\delta$ is large, the model complexity is small and vice versa. We have a method called cross-validation. We divide the data set into two pieces and use one of them as a train data set and use another one as a test data set. Then, we change the value of $\delta$ and calculate test set error and train set error (mean square error) to choose the right value of delta. Similar to the above graph, it is usual that the larger $\delta$, the larger the train set error since larger $\delta$ means low model complexity. However, the test set error improves because too complex model doesn't fit to the all of data. Since we know that even if true model have an error, it is good to choose $\delta$ where the test set error is the lowest. There is an anoth...

Machine Learning (CPSC 540): Regularization and regression

이미지
Frequentist learning assumes that there exists a true model, say $\theta_0$. We estimate model $\hat{\theta}$ in this method by $\hat{\theta} = \mathrm{argmax}_{\theta} \ p(x_1, x_2, \cdots, x_n \mid \theta)$ where $x_1, x_2, \cdots, x_n$ are sample data. We can also apply this method to the Neural Network. Why this method is reasonable? First, MLE is consistent. That is, $\lim_{N \to \infty} P(\| \hat{\theta} - \theta_0 \| > \alpha) = 0 \ \ \textit{for any} \ \ \alpha$. Second, MLE is asymptotically optimal. That is, $\hat{\theta} - \theta_0 \sim N(0, I^{-1}) \ \textit{where N is large}$. ($I$ is a Fisher information matrix.) MLE always have a bias-variance trade off $\mathrm{MSE} = \mathrm{bias}^2 + \mathrm{variance}$. Here, bias is $\bar{\theta} - \theta_0$ and variance is $E(\hat{\theta} - \bar{\theta})^2$. If we have a big variance oscillation, we have small bias and vice versa. I want to note that if basis function is given, nonlinear model becomes linear. Thu...

Machine Learning (CPSC 540): Maximum likelihood and linear regression

이미지
Suppose we have a training data set $(\mathbb{x}_i, y_i)_{i=1}^{n}$ where $\mathbb{x}_i = (x_0=1, x_1, \cdots, x_m), \theta = (\theta_0, \theta_1, \cdots, \theta_m)$ which follows gaussian distribution $y_i \sim N(\mathbb{x}_i^T\theta, \sigma^2)$ with unknown $\theta$ and $\sigma^2$. Then we can estimate $\theta$ and $\sigma^2$ by using Maximum Likelihood Estimation (MLE)$^{1)}$. $$P(Y \mid X, \theta, \sigma^2) = (2\pi\sigma^2)^{-n/2}e^{-\frac{1}{2\sigma^2}\sum(y_i - \mathbb{x}_i^T\theta)^2}.$$All we have to do is just minimizing $P(Y \mid X, \theta, \sigma^2)$. We can get estimated value by $\hat{\theta} = (X^TY)^{-1}X^TY$ and $\hat{\sigma^2} = \frac{1}{n}\sum_{i=1}^{n}(y_i - \mathbb{x}_i^T\theta)^2$. Here, we can see that if each $y_i$ in data set follows gaussian distribution, the cost function of linear regression is related with MLE. After the estimation, we can predict the output of new input value $\mathbb{x}_*$ with the probability distribution $y_* \sim N(\mathbb{x}_*^T\...

Machine Learning (CPSC 540): linear prediction

이미지
The basic of supervised machine learning is all about finding an optimal function with a given training dataset. Formally, for an input space $X^n$ and a output space $Y$ with a training dataset of n instances of input-output pairs $(\mathbb{x}_i, y_i)_{i=1}^{n}$ we find a hypothesis $h:X^n \to Y$ in the hypothesis class $H$ such that $\mathrm{argmin}_{h \in H} J(h)$ where $J$ is the cost function. The linear model represents the core concept of supervised machine learning well. For linear model, we define the hypothesis class $H = {\sigma_{i=0}^{n}w_ix_i}$ where $x_0=1$ is a bias (or offset) under the assumption that there is no outliers and the data follows linear pattern. (For non-linear case, we have to use another setting.) In matrix form, the expression for the linear model is $\hat{\mathbb{y}} = X\mathbb{w}$. If we define the mean square error for the cost function, we can find a hypothesis of this model easily by normal equation $\hat{\mathbb{w}} = (X^TX)^{-1}X^T\mathbb{y}$....

Machine Learning (CPSC 540): Introduction

이미지
Lecture: Machine Learning (2013, UBC). Professor: Nando de Freitas. Link:  http://www.cs.ubc.ca/~nando/540-2013/lectures.html In our brain, each neuron is activated for each stimulus. For example, figure below shows neural responses of cat for different angle of bar. We can emulate the behavior of neurons with artificial neurons and connect them to get desired results.