Stanford CS229: Machine Learning | Lecture 7 강의 정리

Stanford에서 2018년 가을학기에 열린 Andrew Ng 교수의 CS229 머신러닝 강의의 대부분의 내용을 번역 정리한 글입니다.

---

Course : Stanford CS229: Machine Learning Full Course taught by Andrew Ng | Autumn 2018
Course 소개 : CS229는 기계 학습과 통계적 패턴 인식에 대한 포괄적인 소개를 제공합니다. 지도 학습(생성적/판별적 학습, 모수/비모수 학습, 신경망, 서포트 벡터 머신); 비지도 학습(클러스터링, 차원 축소, 커널 메소드); 학습 이론(편향/분산 트레이드오프, 실용적인 조언); 강화 학습 및 적응 제어에 대한 강의를 다룹니다. 또한 기계 학습의 최근 응용에 대해 논의되며, 로봇 제어, 데이터 마이닝, 자율 항법, 생명 정보학, 음성 인식, 텍스트 및 웹 데이터 처리 등이 포함됩니다.
강의 제목 : Lecture 7 - Kernels | Stanford CS229: Machine Learning Andrew Ng (Autumn 2018)
강의 영상: https://youtu.be/8NYoQiRANpg?si=sFg3vGmrjlAfPlLh
강의 자료 (복원): https://github.com/maxim5/cs229-2018-autumn
강의 syllabus : http://cs229.stanford.edu/syllabus-autumn2018.html
강의를 듣기 전에 알고 있어야 하는 내용
선형대수학 : https://cs229.stanford.edu/notes2022fall/cs229-linear_algebra_review.pdf
확률이론 : https://cs229.stanford.edu/notes2022fall/cs229-probability_review.pdf

---

Outline

• Optimization problem
• Representer Theorem
• Kernels
• Examples of Kernels

Optimization Problem

저번 강의에서 classification problem이 유도되는 과정에 대해 이야기하지 않아 간단하게 다뤄보려고 한다.

$$
\large
\begin{align}
\min_{w,b} &\quad \frac{1}{2}\lVert w\rVert^2\\
s.t&\quad y^{(i)}\left(w^{T}x^{(i)}+b\right)\geq 1
\end{align}
$$

우리는 아래의 geometric margin을 최대화하면서 $\large w$와 $\large b$로 parameterized 되어 있는 decision boundary를 찾아야한다.

$$
\large
\gamma^{(i)}=\frac{y^{(i)}\left(w^{T}x^{(i)}+b\right)}{\rVert w \lVert}
$$

$$
\large \gamma=\min_{i}\gamma^{(i)} 
$$

아래 식으로 optimization problem을 제기할 수 있다.

$$
\large
\begin{align}
\max_{\gamma,w,b} & \quad \gamma\\
s.t.&\quad \frac{y^{(i)}\left(w^{T}x^{(i)}+b\right)}{\lVert w\rVert}\geq \gamma,\quad i=1,\dots,m
\end{align}
$$

이 식은 모든 example들이 $\large \gamma$보다 크거나 같은 geometric margin을 가지고 있다는 것이고 이것은 최악(최소)의 경우의 geometric margin을 최대화 한다는 것을 의미한다. 예를 들어 $\large \gamma$가 17이라면 모든 example들의 17보다 geomeric margin을 가지고 있다. 이런 $\large \gamma$를 최대화 하도록 $\large w,b$를 찾아야한다. 흥미로운 사실은 위 식의 분자가 functional margin이라는 것이다. functional margin은 $\large w$와 $\large b$에 상수를 곱해 decision boundray가 같은 상태를 유지하면서 값을 바꿀 수 있다. 위의 식을 간단하게 하기 위해 $\large \lVert w\rVert=\frac{1}{\gamma}$가 되도록 상수를 곱해주면 아래와 같은 식을 얻을 수 있다.

$$
\large
\begin{align}
\max_{w,b} & \quad \frac{1}{\lVert w \rVert}\\
s.t.&\quad y^{(i)}\left(w^{T}x^{(i)}+b\right)\geq 1,\quad i=1,\dots,m
\end{align}
$$

위 식에서 $\large \frac{1}{\lVert w \rVert}$를 최대화 하는 대신 $\large {\lVert w \rVert}^{2}$를 최소화 해준다면 아래 식을 얻을 수 있다.

$$
\large
\begin{align}
\min_{w,b} & \quad {\lVert w \rVert}^{2}\\
s.t.&\quad y^{(i)}\left(w^{T}x^{(i)}+b\right)\geq 1,\quad i=1,\dots,m
\end{align}
$$

parameter $\large w, b$에 대한 최적화 문제를 푼다면 optimal margin classifier를 얻을 수 있다.

Represented Theorem

우리는 나중에 $\large x^{(i)}$가 수십조, 무한개의 차원을 가지는 상황에 대해 다룰것이다. 그리고 $\large w$가 training exmaple들의 linear combination이라고 가정한다.

$$
\large w=\sum\limits^{m}_{i=1}\alpha_{i}x^{(i)} 
$$

위 assumption은 아무런 성능 저하를 일으키지 않는다고 representation theroem에 의해 밝혀졌다. representation theorem의 증명은 매우 복잡하기 때문에 수업에서 다루지 않고 왜 이것이 의미있는 가정인지에 대해서 이야기할것이다. 관례적으로 $y^{(i)}$를 곱한 아래 식을 사용한다. 수학적으로 조금 더 쉽게 downtream(최종 결과물)이 나오게 하지만 여전히 training example들의 선형조합으로 이루어져 있다.

$$
\large w=\sum\limits^{m}_{i=1}\alpha_{i}y^{(i)}x^{(i)},\quad y^{(i)}=\pm1
$$

이것이 왜 합리적인 assumption인지 (representation theorem에 의해 증명된 optimal $\large w$갑에서의 사실이지만) 2가지 방법으로 (덜 공식적으로) 보일것이다.

 

Intuation #1

logistic regression을 stochastic gradient descent와 실행시킬 때 $\large \theta=0$으로 초기화 하고 $\large \theta := \theta + \alpha \left(h_{\theta}(x^{(i)})-y^{(i)}\right)x^{i}$로 $\large \theta$를 업데이트 한다. 이 식으로 매 iteration마다 prameter $\large \theta$를 training example에 상수를 곱한 것을 더하거나 빼서 업데이트 한다는 것을 알 수 있다. 귀납적으로 $\large \theta$의 초기값이 0이고 gradient descent의 모든 반복이 training example에 곱한 것을 더하기 때문에 iteration이 얼마나 반복되는지에 관계 없이 $\large \theta$는 training exmaples의 linear combination이다. 이것은 batch gradient descent를 사용할때도 같다. 따라서 support vector machine에서 gradient descent를 이용하여 $\large w$를 최적화 할 때에도 $\large w$가 training example들의 linear combination이라는 것을 귀납적으로 증명할 수 있다.

Intuation #2

cs229

$\large g\left(\begin{bmatrix}2 \ 1 \end{bmatrix}x-2\right)$라는 classifier가 있을 때 vector $\large w$는 항상 decision boundary와 수직이다. $\large w$는 decision boundary의 방향을 정하고 $\large b$는 decision boundary의 위치를 정한다.

cs229

$\large x_{1},x_{2},x_{3}$ 총 3개의 feature들이 있다고 할 때 모든 example들이 $\large x_{1}x_{2}$평면에 있다고 하자. 모든 example들은 $\large x_{3}=0$이다. decision boundary는 평면에 수직으로 만들어 질 것이다. decision boundary $\large w^{T}x+b=0$이고 $\large w_{3}=0$이다. 이것은 vector $\large w$가 $\large x_{1},x_{2}$의 span, training example들의 span으로 표현된다는 것을 의미한다.

Dual Optimization Problem

$$
\large w=\sum\limits^{m}_{i=1}\alpha_{i}y^{(i)}x^{(i)},\quad y^{(i)}=\pm1
$$

위 식을 아래의 식에 optimal margin classifier의 $\large w$에 대입하면 아래와 같이 전개된다.

$$
\begin{align}
&{{1}\over{2}} {\lVert w \rVert}^{2}\\
&=\frac{1}{2}\left(\sum\limits^{m}_{i=1}\alpha_{i}y^{(i)}x^{(i)}\right)^{T}\left(\sum\limits^{m}_{j=1}\alpha_{j}y^{(j)}x^{(j)}\right)\\
&=\frac{1}{2}\sum\limits^{m}_{i=1}\sum\limits^{m}_{j=1}\alpha_{i}\alpha_{j}y^{(i)}y^{(j)}<x^{(i)},x^{(j)}>
\end{align}
$$

$$
\begin{align}
&y^{(i)}\left(w^{T}x^{(i)}+b\right)\\
&=y^{(i)}\left({\left(\sum\limits^{m}_{j=1}\alpha_{j}y^{(j)}x^{(j)}\right)}^{T}x^{(i)}+b\right)\\
&=y^{(i)}\left(\sum\limits^{m}_{j=1}\alpha_{i}y^{(i)}<x^{(j)},x^{(i)}>+b\right)
\end{align}
$$

위 결과를 정리하면 아래와 같다.

$$
\large
\begin{align}
\min_{\alpha} & \frac{1}{2}\sum\limits^{m}_{i=1}\sum\limits^{m}_{j=1}\alpha_{i}\alpha_{j}y^{(i)}y^{(j)}<x^{(i)},x^{(j)}>\\
s.t.&\quad y^{(i)}\left(\sum\limits^{m}_{j=1}\alpha_{i}y^{(i)}<x^{(j)},x^{(i)}>+b\right)\geq 1,\quad i=1,\dots,m
\end{align}
$$

feature vector가 등장하는 부분은 $\large <x^{(i)},x^{(j)}>$ (내적) 부분이다. Kernel Trick과 Kernel의 응용을 이용하여 $\large <x^{(i)},x^{(j)}>$를 효율적으로 계산할 수 있다면 무한의 차원을 가진 feature vector도 쉽게 계산할 수 있다. 내적에 대한 알고리즘의 전체를 적은 이유는 무한 차원의 feature vector의 내적도 모든 요소를 곱해서 더하는 반복없이 구할 수 있어 중요하기 때문이다.

교과서나 논문에선 위 식을 더욱 간단히 한 parameter $\large \alpha$에 대한 식을 사용한다.

$$
\large
\begin{align}
\max_{\alpha} & \sum\limits_{i}\alpha_{i}- \frac{1}{2}\sum\limits^{m}_{i=1}\sum\limits^{m}_{j=1}\alpha_{i}\alpha_{j}y^{(i)}y^{(j)}<x^{(i)},x^{(j)}>\\
s.t.&\quad \alpha_{i} \geq0,\quad \sum\limits_{i}y^{(i)}\alpha_{i}=0 \end{align}
$$

이 식은 dual optimization problem이라고 부른다.

prediction을 만들기 위한 방법이다.

1. optimization problem을 $\large \alpha_{i}$'s와 $\large b$에 대해 푼다.
2. $\large h_{w,b}(x)=g(w^{T}x+b)=g\left(\sum\limits^{m}_{i=1}\alpha_{i}y^{(i)}<x^{(i)},x>+b\right)$를 계산한다.

$\large \alpha$'s를 컴퓨터 메모리에 저장하고 나면 내적($\large <x^{(i)},x>$)만을 사용해서 prediction을 만들 수 있다. Algorithm 전체에서, 파라미터를 최적화하고 학습을 하는 것과 prediction을 만드는 것 둘 다 내적에 대해서만 표현된다.</x^{(i)},x>

Kernel

Kernel Trick

1. 알고리즘을 $\large <x,z>$항에 대해 적는다.
2. $\large x \mapsto\phi(x)$에 대한 mapping을 정의한다.
   • original input을 더 높은 차원인 $\large \phi(x)$에 mapping 한다.
3. $\large K(x,z)=\phi(x)^{T}\phi(z)$를 계산하는 방법을 찾는다
   • $\large K$는 kernel function이다.
   • $\large \phi(x)$와 $\large \phi(z)$가 매우 고차원이어도 $\large x$와 $\large z$의 내적을 계산할 수 있다.
4. 알고리즘의 $\large <x,z>$를 $\large K(x,z)$로 바꾼다.
   algorithm을 실행하는 동안 고차원의 feature 집합과 $\large x$가 $\large \phi(x)$로 바뀌면서 계산적으로 매우 비싸졌다는 문제가 발생하지만 이것은 $\large x$를 순진하게 $\large \phi(x)$로 바꿀때 발생하는 문제이다. algorithm이 $\large <x,z>$에 대해서만 쓰여졌기 때문에 명시적으로 $\large\phi(x)$를 구하지 않고 kernel을 계산하기만 하면된다.

Example of Kernel

예시를 들기 위해 input feature가 3차원이고 $\large \phi(x)$가 각 요소들의 곱이라고 하자.

$$
\large
x = \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \end{bmatrix},
\quad x\in\mathbb{R}^{n,}\quad

\phi(x)=\begin{bmatrix}x_{1}x_{1} \\ x_{1}x_{2} \\ x_{1}x_{3}\\ x_{2}x_{1}\\ x_{2}x_{2}\\ x_{2}x_{3}\\ x_{3}x_{1}\\ x_{3}x_{2}\\ x_{3}x_{3}\end{bmatrix}, \quad \phi(x) \in \mathbb{R}^{n^{2}}
$$

$\large \phi(x)$가 $\large n^{2}$개의 요소가 있기 때문에 $\large \phi(x)$ 또는 $\large \phi(x)^{T}\phi(z)$를 계산하는데 $\large O(n^{2})$ 만큼의 시간이 소요된다. 하지만 이것을 계산하는 더욱 쉬운 방법이 있는지 즉, $\large K(x,z)$를 찾아보자.

$$
\large
K(x,z)=\phi(x)^{T}\phi(z)=(x^T z)^{2}
$$

위 식의 좋은 점은 $\large x,z$가 n차원이기 때문에 $\large (x^T z)$를 계산하는데에 $\large O(n)$이 소요된다. 이제 위 식을 증명해 볼 것이다.

$$
\large
\begin{align}
(x^T z)^{2}&=\left(\sum\limits^{n}_{i=1}x_{i}z_{i}\right)\left(\sum\limits^{n}_{j=1}x_{j}z_{j}\right)\\
&=\sum\limits^{n}_{i=1}\sum\limits^{n}_{j=1}x_{i}z_{i}x_{j}z_{j}\\
&=\sum\limits^{n}_{i=1}\sum\limits^{n}_{j=1}(x_{i}x_{j})(z_{i}z_{j})\\
&=\phi(x)^{T}\phi(z)
\end{align}
$$

이것은 이전에는 $\large n^{2}$번 계산 했던 것을 $\large n$번 계산해도 된다는 것을 증명한다.

Kernel의 다른 예시를 들어보자

$$
\large K(x,z)=(x^{T}z+c)^{2}, \quad c\in\mathbb{R}
$$

위 Kernel은 아래의 $\large \phi(x)$에 대응한다.

$$
\large
x = \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \end{bmatrix},
\quad x\in\mathbb{R}^{n,}\quad

\phi(x)=\begin{bmatrix}x_{1}x_{1} \\ x_{1}x_{2} \\ x_{1}x_{3}\\ x_{2}x_{1}\\ x_{2}x_{2}\\ x_{2}x_{3}\\ x_{3}x_{1}\\ x_{3}x_{2}\\ x_{3}x_{3} \\ \sqrt{2c}x_{1} \\ \sqrt{2c}x_{2} \\ \sqrt{2c}x_{3} \\ c\end{bmatrix}, \quad \phi(x) \in \mathbb{R}^{n^{2}}
$$

상수 $\large c$의 역할은 일차항과 비교하여 이차항의 상대적 가중치를 상쇄시키는 역할을 한다.

$$
\large K(x,z)=(x^{T}z+c)^{d}, \quad c\in\mathbb{R}
$$

다른 예시로 아래의 Kernel을 고른다면 $\large \phi(x)$는 $\large \binom{n+d}{d}$개의 $\large d$차까지의 단항식을 얻을 수 있다. 예를 들어 $\large d=5$라면 $\large x_{1}x_{2}^{2}x_{3}x_{4},\ x_{1}x_{2}x_{5}x_{17}x_{25}$등의 5차까지의 단항식을 포함한다. $\large \binom{n+d}{d}$는 $\large (n+d)^{d}$로 아주 근사를 할 수 있어 매우 큰 수의 feature들이다. 하지만 $\large d$가 증가한다고 해서 계산이 지수적으로 증가하지는 않는다.

Summarize

optimal margin classifier와 Kernel trick이 합쳐진 것이 support vector machine이다. 위에서 예시를 든 Kernel들을 고른다면 매우 고차원인 feature space에서 SVM을 실행할 수 있고 계산시간은 input feature의 dimension에 따라 선형적으로 ($\large O(n)$) 증가한다.

📼 SVM with polynomial kernel visualization
data를 더 높은 차원으로 mapping으로 하여 고차원 공간에서의 linear decision boundary를 찾는것은 original space에서 아주 non-linear한 decision boundary를 찾는것이다.

How to Make Kernels

• 만약 $\large x,z$가 비슷하다면 $\large K(x,z)$가(내적이) 크다.
• 만약 $\large x,z$가 비슷하지 않다면 $\large K(x,z)$가(내적이) 작다.

$$
\large K(x,z)=\exp\left(-\frac{\lVert x-z\rVert^{2}}{2\sigma^{2}}\right)
$$

Kernel을 유사도 측정 함수(similarity measure function)라고 생각한다면 이것은 유사도 측정 함수의 예시이고 $\large x,z$가 매우 가깝다면 kernel 값이 1이되고 $\large x,z$가 멀다면 0에 가까워지며 작아진다. 따라서 이 함수는 위의 기준에 만족한다. 여기서 질문은 “이 함수를 kernel 함수로 사용해도 괜찮은가?” 이다. $\large K(x,z)$는 $\large K(x,z)=\phi(x)^{T}\phi(z)$를 만족하는 $\large \phi$가 존재할 때에만 kernel function으로 사용할 수 있다. 우리는 모든 알고리즘을 이 조건을 만족한다고 가정하고 유도하였기 때문에 이것이 사실이 아닐 때 kernel function을 대입한다면 모든 유도가 무너지게 되고 매우 이상한 해(solution)를 갖게 된다. 이것으로 인해 우리가 고를 수 있는 kernel function에 제약이 생긴다. 그 중 하나가 $\large K(x,x)=\phi(x)^{T}\phi(x)\geq 0$ 이다. 자기 자신과의 내적은 음수가 될 수 없다. $\large K(x,x)$가 $\large 0$보다 작아진다면 이것은 유효한 kernel function이 아니다. 누군가 이것에 대한 증명을 아주 간략하게 제시했다.

Kernel Matrix

$\large\{x^{(1)},\dots,x^{(d)} \}$를 $\large d$개의 점이라고 하고 $\large K\in\mathbb{R}^{n\times n}$ 를 "kernel matrix” 라고 할 때 $\large K_{ij}=K(x^{(i)},x^{(j)})$이다. 점들의 모든 쌍에 대해 kernel function을 적용해 d by d matrix에 넣은 것이다. 임의의 vector 가 주어졌을 때 아래 식을 만족한다.

$$
\large
\begin{align}
z^{T}Kz&=\sum\limits_{i}\sum\limits_{j}z_{i}K_{ij}z_{j}\\
&=\sum\limits_{i}\sum\limits_{j}z_{i} \phi(x^{(i)})^{T} \phi(x^{(j)})z_{j}\\
&=\sum\limits_{i}\sum\limits_{j}z_{i} \sum\limits_{k}\left(\phi(x^{(i)})\right)_{k} \left(\phi(x^{(j)}\right)_{k}z_{j}\\
&=\sum\limits_{k}\sum\limits_{i}\sum\limits_{j}z_{i}\left(\phi(x^{(i)})\right)_{k} \left(\phi(x^{(j)}\right)_{k}z_{j}\\
&=\sum\limits_{k}\left(\sum\limits_{i}z_{i}\phi(x^{(i)})_{k}\right)^{2}\\
&\geq0
\end{align}
$$

따라서 $\large K\geq0$ 이다.

Mercer Theorem

$\large K$가 유효한 kernel 함수인것 (즉, $\large K(x,z)=\phi(x)^{T}\phi(z)$를 만족하는 $\large \phi$가 존재하는 것)과 임이의 d개의 점들 $\large{x^{(1)},\dots,x^{(d)} }$에 대응하는 kernel matrix $\large K \geq 0$ 인 것은 필요충분 조건이다.

이것은 kernel function의 유효성을 증명하는 하나의 테스트이다.

Gaussian Kernel

$$
\large K(x,z)=\exp\left(-\frac{\lVert x-z\rVert^{2}}{2\sigma^{2}}\right)
$$

이것은 유효한 kernel로 gaussian kernel이라고 한다. 가장 넓게 사용되는 kernel은 linear kernel인데 gaussian kernel은 linear kernel 다음으로 가장 넓게 사용되는 kernel이다. linear kernel은 $\large K(x,z)=x^{T}z,\quad \phi(x)=x$이다. 이것은 고차원으로의 feature mapping을 사용하지 않는다는 것을 의미한다. 이것이 가장 일반적으로 사용되는 kernel이고 다른 말로 kernel의 장점을 사용하지 않는다는 것을 의미한다.

Gaussian kernel의 feature space는 무한한 차원에 대응한다. $\large \phi(x)\in\mathbb{R}^{\infty}$. 이것이 kernel function이기 때문에 모든 단항식 feature들을 사용한다. 따라서 이 kernel은 끊임없는 임의의 고차원 feature들을 사용하며 아주 높은 차원에는 더 적은 가중치를 준다.

kernel trick은 내적의 관점에서 쓰인 모든 algorithm에서 사용할 수 있다. kernel trick을 적용하는 방법은 learning algorithm의 모든 것을 내적의 관점으로 작성하고 내적을 적절한 kernel function으로 치환하면 된다. 앞으로 배우게될 모든 discriminative learning algorithm들은 kernel trick을 적용할 수 있다. 이것은 원한다면 무한한 차원의 feature space에서 알고리즘을 적용할 수 있다는 것을 의미한다.

Soft Margin SVM

data가 noisy하게 섞여 있을 경우 완벽하게 분리하려고 하면 decision boundary가 매우 복잡해진다. 고차원의 feature space에서도 linear하게 분리되지 않는 경우 training set에 대해 error가 0인 알고리즘을 원하지 않을 수 있다. 이런 algorithm을 L1 nrom soft margin SVM이라고 한다.

$$
\large
\begin{align}
\min_{w,b,\xi} &\quad \frac{1}{2}\lVert w\rVert^2+C\sum\limits_{i=1}^{m}\xi_{i}\\
s.t&\quad y^{(i)}\left(w^{T}x^{(i)}+b\right)\geq 1-\xi_{i}, \quad\xi_{i}\geq0
\end{align}
$$

functional margin이 0보다 크다면 algorithm이 example을 알맞게 분류했다는 것을 의미한다. SVM은 알맞게 분류한 것 뿐만 아니라 1보다 큰 functional margin과 함께 알맞게 분류해야한다. 0보다 큰 $\large \xi_{i}$는 이 제약을 완화시킨다. 하지만 우리는 $\large \xi_{i}$가 너무 커지는 것을 원하지 않기 때문에 optimization cost function에 $\large \sum\limits_{i=1}^{m}\xi_{i}$를 추가하여 $\large \xi_{i}$에 cost를 추가한다.
L1 norm soft margin SVM을 사용하는 또 다른 이유는 이상치와 관련이 있다. 기존의 SVM은 최악의 경우의 margin을 최적화 하였다. 따라서 하나의 이상치가 decision boundary에 큰 영향을 줄 수 있다. L1 norm soft margin SVM은 기존의 SVM보다 이상치에 영향이 적다.

L1 norm soft margin SVM의 dual form은 아래와 같다.

$$
\large
\begin{align}
\max_{\alpha} & \sum\limits_{i}\alpha_{i}- \frac{1}{2}\sum\limits^{m}_{i=1}\sum\limits^{m}_{j=1}\alpha_{i}\alpha_{j}y^{(i)}y^{(j)}<x^{(i)},x^{(j)}>\\
s.t.&\quad 0\leq\alpha_{i} \leq C,\quad \sum\limits_{i}y^{(i)}\alpha_{i}=0 \end{align}
$$

기존의 식에서 $\large C$와 관련된 제약만 추가되었다.

Examples of SVM Kernel

Hand Written Digit Classifier

$$
\large K(x,z)=(x^{T}z)^{d}
$$

$$
\large K(x,z)=\exp\left(-\frac{\lVert x-z\rVert^{2}}{2\sigma^{2}}\right)
$$

위 두 polynomial kernel과 gaussian kernel은 손글씨 분류에 좋은 성능을 보였다.

Protein Sequence Classifier

단백질은 알파벳의 시퀀스이다. 여기서 질문은 feature $\large \phi(x)$를 어떻게 표현할 것인가이다. feature vector를 디자인하는 한 가지 방법은 4개의 아미노산의 조합을 모두 나열하여 각 아미노산 조합이 시퀀스에서 등장하는 횟수를 사용하는 것이다.