5. Linear Model (3)

Eunji·2026년 4월 20일

Data Mining

목록 보기
8/12

1. Matrix Representation: Data and Error

1.1 Data Matrix and Target Vector

Data Matrix

  • X∈RN×(d+1)X \in \R^{N \times (d+1)}
  • rows: inputs xn\mathbf{x}_n as row vectors

각 개별 데이터 벡터xn\mathbf{x}_n에 1(bias coordinate)이라는 항목을 추가한 뒤, 데이터 행렬 XX를 만들 때는 개별 벡터들을 행 벡터 형태인 xnT\mathbf{x}^T_n로 변환하여 차례대로 쌓는다.

Target Vector

  • y∈RN\mathbf{y} \in \R^N
  • components: target values yny_n

타겟 벡터 y\mathbf{y}의 n번째 요소인 yny_n은 데이터 행렬 XX의 n번째 행 xnT\mathbf{x}^T_n에 1:1로 대응되는 실제 결과값을 의미한다.

E.g., d = 1, N = 4

1.2 Matrix Form of Ein(w)E_{in}(\mathbf{w})

In-sample Error

  • A function of w\mathbf{w} and data XX, y\mathbf{y}
  • ∣∣⋅∣∣|| \cdot ||: Eculidean norm of a vector
  • Scalar yTXw=(wTXTy)T=wTXTy\mathbf{y}^T \mathbf{X} \mathbf{w} = (\mathbf{w}^T \mathbf{X}^T \mathbf{y})^T = \mathbf{w}^T \mathbf{X}^T \mathbf{y}

학습 오차 EinE_{in}를 행렬 형태로 표현하는 것은 수만 개의 데이터를 하나씩 계산하지 않고 한 번의 행렬 연산으로 전체 오차를 정의하기 위함이다.

  1. 합산 형식에서 행렬 형식으로의 변환
    • 예측값 벡터 Xw\mathbf{Xw}, 잔차 벡터 Xw−y\mathbf{Xw-y}
  2. 행렬식의 전개 과정
    • 벡터의 2-norm은 a2=aTa\mathbf{a}^2 = \mathbf{a}^T\mathbf{a}
  3. 스칼라 성질을 이용한 단순화

정리하면 2차 함수 형태, 미분 가능하며 볼록한 모양을 가진다. 이는 기울기가 0인 지점을 찾았을 때 그곳이 반드시 최솟값임을 보장한다.

E.g., d = 1, N = 4

2. Getting the Solution wlin\mathbf{w}_{lin}

5.1 Minimization of Ein(w)E_{in}(\mathbf{w})

wlin\mathbf{w}_{lin}

  • The solution to linear regression
  • Derived by minimizing Ein(w)E_{in}(\mathbf{w}) over all possible w∈Rd+1w \in \R^{d+1}
  1. 모든 데이터의 예측값 XwX\mathbf{w}과 실제 정답 y\mathbf{y}의 차이를 구함 →\rightarrow 잔차
  2. 잔차의 제곱합을 평균 내어 전체 오차 EinE_{in}을 구함
  3. EinE_{in}이 가장 낮아지는 지점의 가중치 wlin\mathbf{w}_{lin}을 찾음

Ein(w)E_{in}(\mathbf{w}) is continous, differentiable, and convex

  • Convexity: 함수 그래프 위의 임의의 두점을 연결했을 때, 그 선분이 함수 공간을 빠져나가지 않는 형태

Ein(w)=1N(wTXTXw−2wTXTy+yTy)E_{in}(\mathbf{w}) = \frac{1}{N} (\mathbf{w}^T \mathbf{X}^T \mathbf{X} \mathbf{w} - 2\mathbf{w}^T \mathbf{X}^T \mathbf{y} + \mathbf{y}^T \mathbf{y})

  • We can use standard matrix calculus to find w\mathbf{w} that minimizes Ein(w)E_{in}(\mathbf{w}) by requiring
  • ∇Ein(w)=0\nabla E_{in}(\mathbf{w})=0
  • General optimization techniques
    • E.g., gradient descent

Gradient Identities

∇w(wTAw)=(A+AT)w\nabla_{\mathbf{w}} (\mathbf{w}^T \mathbf{A} \mathbf{w}) = (\mathbf{A} + \mathbf{A}^T) \mathbf{w}
∇w(wTb)=b\nabla_{\mathbf{w}} (\mathbf{w}^T \mathbf{b}) = \mathbf{b}

Scalar ww

  • Ein(w)=aw2−2bw+cE_{in}(w) = aw^2 - 2bw + c
  • ∂∂wEin(w)=2aw−2b\displaystyle \frac{\partial}{\partial w} E_{in}(w) = 2aw - 2b

Vector w\mathbf{w}

  • Ein(w)=wTAw−2wTb+cE_{in}(\mathbf{w}) = \mathbf{w}^T A \mathbf{w} - 2\mathbf{w}^T \mathbf{b} + c
  • ∇Ein(w)=(A+AT)w−2b\nabla E_{in}(\mathbf{w}) = (A + A^T)\mathbf{w} - 2\mathbf{b}

2.2 The Solution

  • From Ein(w)E_{in}(\mathbf{w})
    • Both w\mathbf{w} and ∇Ein(w)\nabla E_{in}(\mathbf{w}) are column vectors
  • Finally, one should solve for w\mathbf{w} that satisfies the linear equations
    • to get ∇Ein(w)\nabla E_{in}(\mathbf{w}) to be 0

XTXw=XTyX^TX\mathbf{w} = X^T\mathbf{y}

3. The Linear Regression Algorithm

3.1 Two Scenarios for the Solution

1. Invertible

  • If XTXX^TX is invertible, w=X†y\mathbf{w} = X^{\dagger}\mathbf{y}
    • X†=(XTX)−1XTX^{\dagger} = (X^TX)^{-1}X^T is pseudo-inverse of XX
    • Resulting w\mathbf{w} is the unique optimal solution to wlin\mathbf{w}_{lin}

2. Not Invertible

  • A pseudo-inverse can still be defined, but no unique solution
  • There will be more solutions for w\mathbf{w} that minimizes EinE_{in}

In Practice

  • XTXX^TX is invertible in most cases
    • Since NN is often much bigger than d+1d+1
    • There will likely be d+1d+1 linearly independent vectors xn\mathbf{x}_n
  • When XTXX^TX is (almost) singular (not invertible)
    • Use a well-implemented X†X^{\dagger} routine instead of (XTX)−1XT(X^TX)^{-1}X^T
    • This is for numerical stability

3.2 Algorithm

1. Construct matrix XX and vector y\mathbf{y} as follows

  • Use data set (x1,y1),...,(xN,yN)(\mathbf{x_1}, y_1), ..., (\mathbf{x_N}, y_N)
  • Each x\mathbf{x} includes x0=1x_0 = 1 bias coordinate

2. Compute pseudo-inverse X†X^{\dagger} of XX

3. Return wlin=X†y\mathbf{w}_{lin} = X^{\dagger}\mathbf{y}

profile
Eunji
이전 포스트

5. Linear Model (2)

다음 포스트

5. Linear Model (4)

0개의 댓글