Linear Regression Models

※ Regression Models

 

Modeling the relationship between one or more explanatory variables \(x\)

and a dependent variable \(y\)

Widely used for predicting and forecasting continuous values

 

x는 하나의 값으로 표현되거나 여러 개의 변수로 구성된 경우가 존재한다.

y는 연속적인 값, 즉 실수형의 데이터로 표현된다.

회귀모델은 보통 날씨 예측이나 온도 예측, 가격 예측 등의 모델에서 활용될 수 있다.

 

 

x가 한개인 경우 Simple, 2개 이상의 변수로 구성되어 있는 경우 Multiple 로 분류된다.

그리고 Simple, Multiple 에서 선형, 비선형으로 구성된다.

 

 

※ Simple Linear Regression

 

Given training data \({(x^{(i)}, y^{(i)}): 1 \leq i \leq  n}\),

Model a linear function for given training data.

\(f(x; w_{0}, w_{1}) = w_{1}x + w_{0}\)
\(w_{0}\): bias 

 

※ Error Function (or Cost Function)

 

Minimizing the sum of squared residuals between actual values and predicted values

\(E(w_{0}, w_{1}) = \sum_{i=1}^{n}(y^{(i)} - \hat{y}^{(i)})^{2}\)
\(E(w_{0}, w_{1}) = \sum_{i=1}^{n}(y^{(i)} - (w_{1}x^{(i)} + w_{0}))^{2}\)

 

 

주어진 x와 y의 차이가 에러로 모든 점에 해당하는 에러를 다 더함으로써 최종적으로 결정이 된다.

이러한 에러들의 합을 최소화할 수 있도록 하는 \(w_{1}, w_{0}\) 를 찾는 것이 목적이다.

 

 

※ Solving the Optimization Problem

 

The regression problem can be calculated analytically(e.g. using normal equation),

but can be solved numerically when all the data cannot be fitted into the memory

of a single computer (e.g. gradient descent).

 

analytic solution 은 정확한 최적의 해를 찾는 것을 보장한다.

또한 일반적으로 수학적 해를 찾기 때문에, 정확도 뿐만 아니라 빠르다는 장점이 있다.

하지만 일반적으로 계산하는 과정에서 데이터가 많을 경우 실제 컴퓨터를 이용해서 계산하는데

한계가 존재하며 메모리가 부족한 현상이 일어날 수 있다.

이러한 문제를 해결하기 위해 numerical solution 을 적용할 수 있다.

numerical solution은 매번 최적의 해를 찾는다고 보장할 수 없지만, 충분히 가까운 근사해를

수많은 데이터 환경 속에서도 찾아줄 수 있다는 장점이 있다.

 

Analytic Solution

 

※ Multiple Linear Regression

 

Finding a hyperplane that best fits the training data on \(d\)-dimensional space

\(f(x; w_{0}, w_{1}, ..., w_{d}) = w_{0} + w_{1}x_{1} + \cdots +w_{d}x_{d} = w_{0} + \sum_{j=1}^{d}w_{j}x_{j}\)

 

이번엔 simple linear regression 에서 확장한 multiple linear regression 모델이다.

다차원의 설명 변수를 가진 데이터 위에서 \(y\) 를 예측하는 모델을 학습하는 것이 목적이다.

 

Training data \(X\in \mathbb{R}^{n\times d}\) can be converted to a matrix \(\mathbb{R}^{n\times (d+1)}\).

 

 

\(w_{0}\) 에 대응되는 \(x_{0}\) 는 항상 1값으로 표현될 수 있기 때문에, 

위와 같이 1값을 모두 가지는 형태라고 볼 수 있다. 

 

\(X\in \mathbb{R}^{n\times (d + 1)}\) matrix, \(y\in \mathbb{R}^{n\times 1}\) vector

\(w\in \mathbb{R}^{(d + 1)\times 1}\) -> \(w_{0}\) is interpreted as the bias

 

 

\(n\times (d+1)\) 의 matrix 형태인 \(X\) 라는 데이터가 주어졌을 때,

이에 대응되는 \(y\) 라는 dependent variable은 \(n\times 1\) 차원의 벡터로 표현된다.

이때 \(w\)를 찾는 것이 목적이다.

 

 

\(X\)가 정방행렬이 아닌 경우 역행렬을 구할 수 없으므로 위와 같은 트릭을 사용한다.

\(X\) 에 transpose 를 취한 matrix \(X^{T}\) 를 양변에 곱하여 행과 열이 같도록 한다.

\(X^{T}X\) 는 정방행렬이 되었으므로 양변에 역행렬을 곱하여 찾고자 하는 \(w\) 를 찾을 수 있다.

그러나 정방행렬이라고 항상 역행렬을 구할 수 있는 것은 아님을 명시해야 한다. (\(\left|X^{T}X \right| = 0\) 인 경우)

Normal equation: \(w = (X^{T}X)^{-1}X^{T}y\)

 

다루는 데이터의 사이즈가 크지 않을 경우에는 위와 같이 normal equation 을 이용해서

최적의 해를 찾을 수 있다.

 

 

※ Solving Multiple Linear Regreession

 

Given a dataset \(D = {(x^{(i)}, y^{(i)}) : 1 \leq i \leq n}\),

  - \(x^{(i)} = (x_{i0}, x_{i1}, ..., x_{id})\) is the input on \((d + 1)\)-dimensional space.

  - \(y^{(i)}\) is the output.

 

Finding the hyperplane \(f(x)\) which best fits the dataset \(D\)

  - Make \(f(x^{(i)})\) close to \(y^{(i)}\) as much as possible for \(i = 1, ..., n\)

 

\(E(w) = \sum_{i=1}^{n} (y^{(i)} - f(x^{(i)}))^{2}\)
\(f(x^{(i)}) = \sum_{j=0}^{d}w_{j}x_{ij} = w_{0}x_{i0}+w_{1}x_{i1}+\cdots +w_{d}x_{id}\)

 

위와 같이 error function 을 최소화하도록 \(w\) parameter 를 찾는 것이 목적이다.

error function 에서 \(w\) 를 잘 조정함으로써 최소화하는 것이다.

 

When a function is convex, continuous, and differentiable,

a necessary and sufficient condition for a point \(w^{*}\) to be optimal is \(\bigtriangledown E(w^{*}) = 0 \)

\(\frac{\partial }{\partial w_{j}} E(w_{0}, w_{1}, ..., w_{d}) = 0\) for  \(j = 0, ..., d\)
\(\frac{\partial }{\partial w_{j}} E(w) = \sum_{i=1}^{n}\left ( \frac{\partial }{\partial w_{j}}\left ( y^{(i)} - f(x^{(i)}) \right )^{2} \right ) = \sum_{i=1}^{n} -2x_{i0}\left ( y^{(i)} - f(x^{(i)}) \right ) = 0\)

 

위와 같이 편미분한 식이 \(-2x_{i0}\left ( y^{(i)} - f(x^{(i)}) \right )\) 으로 된다.

유도과정에 대해 살펴보도록 하자.

 

 

※ Detail: Chain Rule for the Derivative

 

By using the chian rule,

\(\frac{\partial E}{\partial error} \frac{\partial error}{\partial w_{j}} = 2error \times (-x_{ij}) = -2x_{ij}(y^{(i)} - f(x^{(i)}))\)
\(error = y^{(i)} - f(x^{(i)})\)

 

 

위와 같이 \(error\) 에 대해서 편미분하고 \(w_{j}\) 에 대해서 편미분하여 곱하면 위와 같이 나타난다.

 

Obtain \(w = (w_{0}, w_{1}, ..., w_{d})\) by solving these equations.

 

 

위와 같이 \(w_{0}\) 에 대해 편미분한 식부터 \(w_{d}\) 에 대해 편미분한 식까지 구한다면,

연립방정식을 통해 \(w\) 를 찾을 수 있다.

 

 

구하고자 하는 \(w_{0}\) 부터 \(w_{d}\) 까지를 벡터로 묶어서 표현할 수 있다.

위의 식을 벡터로 표현하여 행렬의 곱으로 표현하게 된다면 아래와 같이 나타낼 수 있다.

 

 

\((d + 1) \times  (d + 1)\) 행렬을 자세히 보면 \(X^{T}X\) 의 행렬로 구성되어 있음을 알 수 있다.

결국 정리해보면 \(w = (X^{T}X)(X^{T}y)\) 으로 w를 구할 수 있게 된다. (단, \(X^{T}X\) 의 역행렬이 존재할 때)

 

 

※ Example: Normal Equation

 

 

위와 같이 행렬로 표현하여 w 값을 구할 수 있게 된다.

 

Numerical Solution

 

Simple concept: follow the gradient downhill

Process

  1. Pick a starting position: \(w^{0} = (w_{0}, w_{1}, ..., w_{d})\)

  2. Determine the descent direction: \(\bigtriangleup w = \bigtriangledown E(w^{t}) \)

  3. Choose a learning rate: \(\eta \)

  4. Update your position: \( w^{t + 1} = w^{t} - \eta ^{t} \bigtriangleup w \)

  5. Repeat from 2) until stopping criterion is satisfied.

 

위 방식은 대표적인 방식으로 gradient descent 를 이용해서 해를 찾는 방식이다.

문제는 \( \bigtriangleup w \) 를 어떻게 계산할지와 \(\eta ^{t}\) 를 어떻게 결정할지이다.

위 문제를 해결할 수 있는 방안에 대해 알아보도록 한다.

 

 

※ Batch Gradient Descent

 

Most machine learning models rely on the gradient descent and its variants.

Gradient on a full training set -> Batch Gradient Descent

  -> Computed empirically from all available training samples.

 

\(g^{t} = \frac{1}{2n} \sum_{i=1}^{n} \bigtriangledown E(w) = - \frac{1}{n} \sum_{i=1}^{n} \left ( y^{(i)} - f\left ( x^{(i)} \right ) \right ) x^{(i)}\)

 

모든 데이터를 사용하여 구해야 한다.

그리고 모든 데이터를 사용하여 error의 평균을 표현하기 위해 \(\frac{1}{2n}\) 으로 normalization 하여

계산할 수 있다.

그렇다면 \( \bigtriangleup w \) 이 어떻게 구해지는지 살펴보도록 하자.

 

 

※ Detail: Chain Rule for the Derivative

 

 

편미분을 이용하여 w에 대해 편미분한 값들을 확인할 수 있다.

이 식이 정리가 된다면 그 다음부터 w, gradient 값을 이용하여 매번 업데이트 하는데 활용할 수 있다.

 

 

※ Example: Multiple Linear Regression

 

Randomly choose an initial solution \(w^{0}\),

Repeat
\(\bigtriangleup w = -\frac{1}{n} \sum_{i=1}^{n} \left ( y^{(i)} - f(x^{(i)}) \right ) x^{(i)}\)
\(w^{t + 1} = w^{t} - \eta\) \(\bigtriangleup w \)

Until stopping condition is satisfied

 

 

※ Disadvantages of Batch GD Learning

 

모든 데이터에 대해 한 번씩 업데이트하기 때문에 한 번에 gradient 를 계산하는 과정에서

\(O(n)\) 의 시간복잡도가 소요된다.

계산 과정을 t번 반복하게 될 경우 \(O(n \times t)\) 으로 볼 수 있고 \(d\) 차원에서 수행하게 된다면

결국 \(O(n \times t \times d)\) 으로 볼 수 있게 된다.

너무 많은 시간이 걸림을 알 수 있다.

따라서, 이러한 문제를 해결하고자 일부의 데이터만을 가지고 샘플링하여 샘플링된 데이터를 가지고

gradient 를 계산하는 sample gradient 방식을 이용한다.

 

 

※ Batch Size in GD

 

The number of training samples is a hyperparameter for learning the model.

  - Batch Gradient Descent: Batch size is set to the total number of examples in the training data.

  - Stochastic Gradient Descent: Batch size is set to one.

  - Minibatch Gradient Descent: Batch size is set to more than one and less than the total number

     of examples in the training data.

 

 

일반적으로 Minibatch Gradient Descent 를 많이 활용한다고 하며 보통 batch 사이즈를

128 ~ 1024 를 보통 활용한다고 한다.

Batch gradient descent 는 모든 데이터를 활용하기 때문에 목적지에 빨리 도달할 수 있겠지만

한 스텝마다 모든 데이터를 활용한다는 점에서 데이터 양에 따라 시간 소요가 많을 수 있다.

하지만, Minibatch나 Stochastic gradient descent 는 미리 데이터를 샘플링하여 접근하기 때문에

목적지에 도달하는데 Batch 에 비해 느릴 수 있지만, 시간 소요가 Batch 에 비해 적다는 장점이 존재한다.

 

 

※ Stochastic Gradient Descent (SGD)

 

Introducing an approximation in computing the gradients

  - Stochastically sample mini-batches from a training dataset

\(B = sample(D)\)
\(w^{t+1} = w^{t} - \frac{\eta ^{t}}{|B|}\sum_{i\in B^{t}}^{} \bigtriangledown _{t} E_{i} (w)\)

 

When computed from continuous streams of data(training data only seen once),

SGC minimizes the generalization error.

Use a small subset or mini-batch of the data, and use it to compute a gradient

which is added to the model.

\(E(w) = \frac{1}{2n}\sum_{i=1}^{n}\left ( y^{(i)} - f(x^{(i)}) \right )^{2}\)
\(E(w) = \frac{1}{2|B|}\sum_{\left ( x^{(i)}, y^{(i)} \right )\in B}^{}\left ( y^{(i)} - f(x^{(i)}) \right )^{2}\)

 

It is possible to compute high-quality models with very few passes in a large-scale dataset.

 

여기서 달라지는 부분은 n개의 데이터가 아닌, B개의 데이터로만 계산한다는 것이다.

mini-batch 를 이용하여 gradient 를 계산하게 된다면 훨씬 큰 데이터에서 효과적으로 

gradient descent 를 계산할 수 있는 장점을 가지게 된다.

 

 

※ Example: Multiple Linear Regression

 

Randomly choose an initial solution \(w^{0}\),
Repeat
Choose a random sample set \(B \subseteq D\)
\(\bigtriangleup w = -\frac{1}{|B|}\sum_{\left ( x^{(i)}, y^{(i)} \right )\in B}^{}\left ( y^{(i)} - f(x^{(i)}) \right ) x^{(i)}\)
\(w^{t + 1} = w^{t} - \eta \bigtriangleup w \)
Until stopping condition is satisfied

 

이전에 봤었던 gradient descent 방식와 동일하지만 랜덤 샘플을 고르는 점이 다르다.

그리고 샘플링한 데이터를 가지고 \(\bigtriangleup w\) 을 구하면서 매번 이렇게 업데이트하는

과정을 거치게 된다.

 

 

※ Effect of Smaller Batch Sizes

 

batch 사이즈를 줄인다는 것은 기본적으로 computational power 측면에서 훨씬 더 빠르게

계산할 수 있다는 장점을 가지고 있다.

그리고 error function 이 복잡할 경우에 Stochastic 또는 minibatch 를 쓴 경우 local optima가

완만한 경우에 해당 구간에 멈추지 않고 다른 지점으로 이동할 수 있도록 하는 효과를 가진다.

따라서 global optima 에 도달할 수 있도록 하는 장점을 가지고 있다.