Ch5.3 Linear Discriminant Functions - Generalized linear discriminant functions

 2020-2학기 서강대 김경환 교수님 강의 내용 및 패턴인식 교재를 바탕으로 본 글을 작성하였습니다.

 

5.3 Linear Discriminant Functions and Decision Surfaces

---

▶ the linear discriminant function

$$
g(\mathbf{x})=w_{0}+\sum_{i=1}^{d} w_{i} x_{i} \tag{1}\label{1}
$$

▶ the quadratic discriminant function

$$
g(\mathbf{x})=w_{0}+\sum_{i=1}^{d} w_{i} x_{i}+\sum_{i=1}^{d} \sum_{j=1}^{d} w_{i j} x_{i} x_{j} \tag{2}\label{2}
$$

 $x_i x_j = x_j x_i$이므로, 일반성의 손실 없이 $\omega_{ij} = \omega_{ji}$라고 가정할 수 있다. 따라서, 2차 판별 함수는 더 복잡한 분리 표면들을 만드는 데 임의로 쓸 수 있는 $d(d+1)/2$개의 계수를 추가로 가진다 $g(\mathbf{x})$에 의해 정의되는 분리 표면은 2차 또는 초 2차(Hyperquadratic) 표면이다. (e.g. 직선 to 포물선)

▶ the class of polynomial discriminant functions

• $w_{i j k} x_{i} x_{j} x_{k}$와 같은 항들을 계속해서 추가하면 다항 판별 함수들을 얻을 수 있다.

▶ generalized linear discriminant function

$$
g(\mathbf{x})=\sum_{i=1}^{\hat{d}} a_{i} y_{i}(\mathbf{x}) \tag{3}\label{3}
$$

$$ 
g(\mathbf{x})=\mathbf{a}^T \mathbf{y} \tag{4}\label{4}
$$

• $\mathbf{a}$ is now $\hat{d}$-dim weight vecgtor and $\hat{d}$ functions $y_i{\mathbf{x}}$ can arbitrary functions of $\mathbf{x}$.

 여기서, $\hat{d}$개 함수 $y_i{\mathbf{x}}$는 $\mathbf{x}$를 $\mathbf{y}$ space로 매핑하는 과정 ($\varphi$ function로 불림)

• $\hat{d} \gt d$로, 현명하게 설정한다면, 어떠한 원하는 판별 함수도 위 과정을 통해 근사화할 수 있다. (즉, "차원을 늘려 판별함수를 잘 만들어 보자!"라는 관점)

• the resulting discriminant function is not linear in $\mathbf{x}$ but it is linear in $\mathbf{y}$. (판별 함수는 $\mathbf{x}$에 대해서는 선형적이지 않으나, $\mathbf{y}$에서는 선형적임)
• $\hat{d}$ functions $y_i{\mathbf{x}}$ merely map points in $d$-dim $\mathbf{x}$-sapce to points in $\hat{d}$-dim $\mathbf{y}$-space.
• the mapping from $\mathbf{x}$ to $\mathbf{y}$ reduces the problem on one of finding a homogeneous linear discriminant fucntion. 

이 방식의 장단점은 단순한 예제를 보면 이해하기 쉬울것이다.

$$
g(x)=a_{1}+a_{2} x+a_{3} x^{2} \tag{5}\label{5}
$$

로 놓아서 3-dimensional vector $\mathbf{y}$는 

$$
\mathbf{y}=\left(\begin{array}{c}
1 \\
x \\
x^{2}
\end{array}\right) \tag{6}\label{6}
$$

으로 주어진다고 하자. $x$로부터 $\mathbf{y}$로의 매핑을 그림 5.5가 보여준다.

위 매핑은 점들을 더 낮은 차원의 공간으로부터 더 높은 차원의 공간으로 옮기면, 아주 단순하게 $H$로부터 분리(linearly seperable O)할 수 있다.

하지만, 모든 선형변환이 단순한것은 아니다 위 매핑처럼 비교적 단순한 변환을 했음에도 불구하고 $H$로부터 상당히 복잡하게 분류될 가능성도 충분히 존재한다.

 안타깝게도 차원의 저주는 보통 실제에서 이 유연성을 이용하는 것을 어렵게 만든다. 완전한 2차 판별 함수는 $\hat{d}=(d+1)(d+2)/2$개의 항을 포함한다. $d$가 상당히 커도, 예를 들어 50인 경우에 많은 계산을 요구할 것이다. 다항식에 3차, 그리고 일반적으로 $k$차 요소들을 포함하면 복잡도 $\mathbf{O}(d^k)$항이 된다. 더욱이, 가중치 벡터 $\mathbf{a}$의 $\hat{d}$ 요소들은 훈련 샘플들로부터 결정되어야 한다. $\hat{d}$을 판별 함수에 대한 자유도를 규정하는 것으로 간주하면, 샘플 수는 자유도보다 작지 않아야 할 것이 당연히 요구된다. 분명히 $g(\mathbf{x})$의 일반적 급수 전개는 어쩌면 계산과 데이터에 대한 완전히 비현실적 요구사항으로 이끌 수 있다. 그렇지만, 5.11절에서 이 결점이 훈련 패턴들 사이에 큰 틈 또는 띠를 두어야 하는 제한을 부과함으로써 조정될 수 있음을 보게 될 것이다. 이 경우, 엄밀한 의미에서, 모든 자유 파라미터를 맞추는 것을 말하고 있지 않다. 그 대신, 고차원 공간으로의 매핑은 훈련 점들 사이에 어떠한 불필요한 구조나 관계도 부과하지 않는다는 가정에 의존한다. (manifold 가정) 대안적으로, Ch6에서는 DNN을 사용하여 입력 특징들의 단일 비선형 함수를 여럿 복제한 것들을 사용해서 이 문제에 접근한다. 

일반화된 선형 판별 함수의 잠재적 장점을 실현하는 것은 어려울 수 있으나, 적어도 $g(\mathbf{x})$를 homogeneous 꼴인 $\mathbf{a}^T \mathbf{y}$로 쓸 수 있는 편리성을 이용할 수 있다. 선형 판별 함수의 특수한 경우에 

$$
g(\mathbf{x})=w_{0}+\sum_{i=1}^{d} w_{i} x_{i}=\sum_{i=0}^{d} w_{i} x_{i} \tag{7}\label{7}
$$

이며, 여기서 $x_0 = 1$로 설정했다. 따라서,

$$
\mathbf{y}=\left[\begin{array}{c}
1 \\
x_{1} \\
\vdots \\
x_{d}
\end{array}\right]=\left[\begin{array}{l}
1 \\ \\
\mathrm{x} \\ \\
\end{array}\right] \tag{8}\label{8}
$$

로 쓸 수 있으며, $\mathbf{y}$는 때로 augmented feature vector(증보된 특징 벡터)라고 불린다. 마찬가지로, augmented weight vector(증보된 가중치 벡터)는 다음과 같다.

$$
\mathbf{a}=\left[\begin{array}{c}
w_{0} \\
w_{1} \\
\vdots \\
w_{d}
\end{array}\right]=\left[\begin{array}{l}
w_{0} \\ \\
\mathbf{w} \\ \\ 
\end{array}\right] \tag{9}\label{9}
$$

$d$차원 $\mathbf{x}$-space으로부터 $d+1$-차원 $\mathbf{y}$-space으 ㅣ이 매핑은 수하적으로 사소하나, 매우 편리하다. $\mathbf{x}$에 상수 요소를 더하는 것은 샘플 간의 모든 거리관계를 보존한다. 그 결과인 $\mathbf{y}$ vector들은 모두 $\mathbf{x}$-space 그 자체인 $d$-차원 부공간(subspace)에 놓인다. 

Reference

---

• pattern classification by richard o. duda