## Intro

해당 논문은 Private 5G Network에서 Intent Based Network 관리를 Natural Language를 통해서 수행할 수 있는지를 보인 논문이다. 해당 논문에서는 Design과 실제 구현 사례를 3개의 usecase에 적용한 사례를 보인다. 해당 논문은 2023년에 publish 되었지만, LLM을 적용하지는 않았고, 이에 대한 적용은 Future Work에서도 고려하고 있다고 언급한다.

## Background

### Intent Based Network(IBN)

Non-Public Network(NPN)은 관리자에 의해서 자유롭게 설정이 가능하다는 장점을 갖고 있다. 하지만, 5G를 다룰 수 있는 숙련된 기술자가 아닌 경우 이를 효율적으로 운용하는데에는 한계가 있다. 따라서, 이러한 문제를 해결하기 위해서 **Intent Based Network(IBN)**이 제안되었다. IBN을 활용하면, private 5G network를 네트워크에 대한 지식이 없이도 단순한 의도(Intent)를 작성하는 것만으로 문제를 해결할 수 있다. 즉, IBN의 목표는 Network가 하는 일을 최대한 추상화하여 private network 관리자의 운영을 단순화하는 것이다.

```plaintext
 🤔 Intent란?

 Intent란 사용자의 의도를 의미한다.
 따라서, 사용자는 자신의 요구사항을 작성할 뿐,
 이를 어떻게(How) 구현할지는 기술하지 않는다.
```

### 5G-CLARITY

5G Private nework에 대한 하나의 architecture이다. 이는 이전 논문 "5G-CLARITY: 5G-Advanced Private Networks Integrating 5GNR, WiFi, and LiFi"에서 처음 제시된 구조로, 해당 구조에서는 5G New Radio(5GNR)을 포함한 WiFi, LiFi와 같은 Protocol을 지원한다. 이를 통해서 virtual, physical network function들을 모두 설정하고 관리할 수 있는 구조를 제시한다. 해당 architecture는 5G network를 위한 3가지의 구성 요소를 가진다.

1. **Infrastructure Stratum(계층)** 
 각종 가상화된 장치나 Router, Switch, 통신 단말 등을 실제로 접근할 수 있는 계층으로 이를 통해서 해당 장치를 모니티링하거나 설정 및 관리할 수 있다.
2. **Virtualised Network and Application function Stratum(계층)** 
 실제 Network function을 구현한 계층으로 Infrastructure의 Telemetry를 수집하는 역할이나 Virtual Machine(VM)에서 기능핧 가족 기능들을 포함하는 계층이다.
3. **Management and Orchestration Stratum(계층)** 
 각 장비와 VM을 관리하고, 이를 통해서 Service를 제공하는 계층이다.

### 기존 연구의 한계

기존에도 Intent를 반영하기 위한 여러 시도가 있었다. 하지만, 해당 논문에서는 현재까지 실제로 NLP를 활용하여 Intent를 추출한 사례는 존재하지 않는다고 말한다. 따라서, 해당 연구에서 핵심 골자는 NLP를 통해서 Intent를 추출할 수 있고, 이를 통해서 Network Management를 수행할 수 있음을 보이는 것이다.

## Design

해당 연구는 기존 Background에서 제시한 5G-CLARITY를 구조에서 나아가 하나의 계층(Intelligence Stratum)을 추가적으로 더하는 것을 제안한다. 해당 계층에서는 Machine Learning 모델을 포함한 ML Engine과 NLP 모델에 기반한 Intent Engeine을 포함하고 있는데, 이를 활용하여 기존 5G-CLARITY 구조에 적절한 Query를 전달하여 Network 장치의 상태를 조회하고, 관리를 할 수 있도록 하였다.
해당 시스템에서는 우선 Natural Language로 입력이 들어오면 Intent Engine에서 이를 여러 개의 Intent로 분리한다. 여기서 중요한 것은 실제로 어떻게 Intent를 추출하냐인데, 해당 논문에서는 Intent를 정의하는 것부터 시작한다. 여기서는 Intent를 아래와 같은 형태로 정의한다.

```json
{
 "intent": {
 "request": "Create a slice",
 "parameters": {
 "name": "nova",
 "user-list": [
 {"imsi": "001035432100005"}
 ],
 "location": {
 "latitude": 0.0,
 "longitude": 0.0,
 },
 "technology": [
 "AMRISOFT_CELL",
 "SUB6_ACCESS",
 ]
 }
 }
}
```

`request`는 사용자의 요청을 natural language로 표현하고, `parameters`는 해당 요청에 대한 추가적인 정보를 포함한다. 이를 추출하는 과정에서 NLP를 수행했는데 이때는 굉장히 간단히 Wikipedia data를 활용해서 text distance를 측정하는 방식을 활용했다.

## Usecases

1. Network Slice Provisioning 
 5G에서 서비스마다 다른 QoS를 제공하기 위해서 Network Slicing 기술을 제공하는데 이를 위한 기반을 Intent만 갖고도 적용이 가능하다. 만약, 특정 시스템을 위한 Slicing이 필요하다는 Intent가 들어온다면, 해당 시스템에서는 NLP를 통해서 Intent를 세분화하고, ML을 통해서 더 좋은 Network Configuration을 다시 변경할 수 있도록 구현하였다.
2. NLoS Identification 
 Line of Sight(LoS)는 통신 가용성을 평가하는 지표이다. 통신 장비마다 위치에 따라서 LoS가 다르기 때문에 이를 고려해서 통신 장비를 배치해야 한다. 이를 위해서는 NLoS(Non-Line of Sight)를 식별해야 한다. 이 또한, Intent를 통해서 구현할 수 있다. 단순히 각 Line의 상태를 받아서 처리하면 충분하다.
3. Network Service Provisioning 
 VNF와 같은 Network Service를 제공할 때에도 특정 요구사항에 맞게 Intent를 입력하면 이를 추출해서 수행할 수 있다.

## Evaluation

Evaluation은 아래와 같은 표가 제시된 것이 끝이다. 실제 예측이나 실행 능력에 대한 지표는 제시하지 않았다. 대신에 이는 충분히 잘 되었고, 이를 실행하는데 걸린 시간만 단순히 제시하였다.

| | Network Slice Provisioning | NLoS Identification | Network Service Provisioning |
| ----------------------------- | -------------------------- | ------------------- | ---------------------------- |
| Average intent execution time | 3 minutes | 1 seconds | 4 minutes |

## Opinion

전체적인 구현은 단순했다. 5G Network를 구성할 수 있는 system을 도입하고, 여기서 Intent를 해석하는 시스템을 도입했는데 이 또한 어려운 구현이 없이 Wikipedia data엤서 단순히 word distance만 활용하여 위에서 제시한 usecase를 모두 커버했다고 논문에서 주장하니 직접 확인해보지 않은 이상 뭐라고 말할 수 있는 것은 없는 거 같다. 대신에 전체 흐름 자체가 Natural Language를 입력 받아서 이를 어떻게 Encoding할 지 그리고, 이렇게 Encoding 된 데이터를 어떻게 시각화할지 그리고 이를 어떻게 실제 네트워크에 반영할지에 대한 힌트 정도는 얻을 수 있었다. 해당 시스템에서는 애초에 Natural Language로 다시 Encoding을 했었다. 이러한 구조도 이해하기 쉬운 구조로 만들기 좋은 거 같다. 그러나 현재 Network Configuration을 적용하는 과정에 대한 설명은 전혀없는데 이에 대한 내용도 추가적으로 찾아보아야할 것 같다.

## Reference

- J. Mcnamara et al., "NLP Powered Intent Based Network Management for Private 5G Networks," in IEEE Access, vol. 11, pp. 36642-36657, 2023, doi: 10.1109/ACCESS.2023.3265894.
- T. Cogalan et al., "5G-CLARITY: 5G-Advanced Private Networks Integrating 5GNR, WiFi, and LiFi," in IEEE Communications Magazine, vol. 60, no. 2, pp. 73-79, February 2022, doi: 10.1109/MCOM.001.2100615.
- Thumbnail: Photo by<a href="https://unsplash.com/@annikamaria?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Annika Gordon</a> on <a href="https://unsplash.com/ko/%EC%82%AC%EC%A7%84/cZISY8ai2iA?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Unsplash</a>

NLP Powered Intent Based Network Management for Private 5G Networks

[NLP] 8. Language Parsing

## Intro

해당 Posting에서는 Maximum Entropy를 이용하여 최적의 parameter를 찾아나가는 Machine Learning 접근법에 기반한 NLP 방식을 제안한다. 이를 위해서 NL를 수학적인 형태로 변형하기 위한 기술 중 하나인 word2vec에 대한 설명도 같이 진행한다.

## MaxEnt Model

Maximum Entropy Model(MEM)의 약자로, 이것의 의미는 주어진 dataset을 표현할 수 있는 가장 적절한 분포는 Prior Knowledge를 만족하는 분포들 중에서 가장 높은 Entropy를 가지는 분포라는 것이다. 

이는 다음과 같은 관측에 의해서 정의된 것이다.

1. 다양한 물리현상들은 시간이 지남에 따라 Entropy를 최대화하려는 방향으로 이동하려는 경향이 있다.
2. 더 적은 수의 논리로 설명이 가능한 경우, 많은 수의 논리를 세우지 말라 (오컴의 면도날)

다소 억지같아 보이는 논리일지라도 후에 가서 살펴보면, Machine Learning의 Logistic Regression에 연결되는 것을 볼 수 있다. 우선은 이 정도 논리로 사용하겠다는 정도로 이해해보자.

따라서, 우리가 풀어야할 식은 다음과 같다.

$$
\begin{align*}
 \text{maximize} \quad & H(p) = - \sum_{i=1}^{N}p_i\log p_i &\\
 \text{subject to} \quad & p_i \geq 0, & i = 1, ..., N \\
 & \sum_{i=1}^{N}p_i = 1 &\\
 & \text{Other Prior Knowledge}
\end{align*}
$$

이를 이용해서 문제를 세 개 정도 풀어보면 감이 잡을 수 있는데 한 번 따라와보도록 하자.

### Example

> **1. 주사위 던지기**

1부터 6까지의 눈이 있는 주사위가 있다고 할 때, 주사위의 각 눈이 나올 확률을 알고 싶다고 하자. 이때 우리는 간단하게 $1\over6$이라고 말할 것이다. 이것도 Maximum Entropy에 기반한 추론 방법 중에 하나라고 할 수 있다. 다음 식을 보자.

$$
\begin{align*}
 \text{maximize} \quad & H(p) = - \sum_{i=1}^{N}p_i\log p_i &\\
 \text{subject to} \quad & p_i \geq 0, & i = 1, ..., N \\
 & \sum_{i=1}^{N}p_i = 1 &
\end{align*}
$$

정말 아무런 정보가 없을 때에는 위의 식을 Lagrangian을 쓰지 않고도 uniform distribution이라는 것을 알 수 있다. 이는 [🔗 [ML] Base Information Theory](/posts/ml-base-knowledge#Information-Theory)에서 살펴보았었다.

그렇다면, 좀 더 복잡한 경우를 고려해보자. 아래는 Duke University ECE587 수업 PPT의 예제이다.

> **2. 평균이 주어졌을 때의 추론**

우리가 만약 평균 데이터를 알고 있다면, 이를 Maximum Entropy로 어떻게 추정할 수 있는지를 살펴볼 것이다. 아래는 어느 fastfood점의 메뉴라고 하자.

| Item | Price | Calories |
| :------ | :---- | :------- |
| Burger | $1 | 1000 |
| Chicken | $2 | 600 |
| Fish | $3 | 400 |
| Tofu | $8 | 200 |

그리고 특정 학생이 이 가게에서 하루에 하나씩 먹는다고 할 때, 평균 소비 가격이 $2.5라고 하자. 그렇다면, 이 학생이 가장 많이 먹는 메뉴는 무엇일지를 추론해보는 것이다. 
즉, 이를 식으로 정리하면 다음과 같다.

$$
\begin{align*}
 \text{maximize} \quad & H(p) = - \sum_{i=1}^{N}p_i\log p_i &\\
 \text{subject to} \quad & p_i \geq 0, & i = 1, ..., N \\
 & \sum_{i=1}^{N}p_i = 1 &\\
 & E[\text{price}] = 2.5 &
\end{align*}
$$

이를 Lagrangian 방식을 이용해서 표현하면 다음과 같이 나타낼 수 있다.

$$
\mathcal{L} = - \sum_{i}^{N}p_{i}\log{p_{i}} + \lambda_{0}(\sum_{i=1}^{N}p_{i} - 1) + \lambda_{1}(\sum_{i=1}^{N}\text{price}_{i}\times{p_{i}} -2.5)
$$

위 식을 각 각의 $p_{i}$에 대해서 미분하면 다음과 같다.

$$
{\partial \mathcal{L}\over\partial p_{i}} = -\log{p_{i}} -1 + \lambda_{0} + \lambda_{1}\times\text{price}_{i}
$$

따라서, $p_{i}$는 다음과 같다.

$$
\begin{align*}
0 &= -\log{p_{i}} -1 + \lambda_{0} + \lambda_{1}\times\text{price}_{i} \\
\log{p_{i}} &= \lambda_{0} + \lambda_{1}\times\text{price}_{i} - 1 \\
p_{i} &= e^{\lambda_{0} + \lambda_{1}\times\text{price}_{i} - 1}
\end{align*}
$$

여기서 나오는 모든 식과 제한 조건을 정리하면 다음과 같다.

- $p(Burger) = e^{\lambda_{0} + \lambda_{1} - 1}$, $p(Chicken) = e^{\lambda_{0} + 2\lambda_{1} - 1}$, $p(Fish) = e^{\lambda_{0} + 3\lambda_{1} - 1}$, $p(Tofu) = e^{\lambda_{0} + 8\lambda_{1} - 1}$
- $p(Burger) + p(Chicken) + p(Fish) + p(Tofu) = 1$
- $p(Burger) + 2p(Chicken) + 3p(Fish) + 8p(Tofu) = 2.5$

위의 식을 연립해서 풀면, $\lambda_{0} = 1.2371$, $\lambda_{1}=0.2586$이고, 전체 확률은 다음과 같다.

| Item | p |
| :------ | :----- |
| Burger | 0.3546 |
| Chicken | 0.2964 |
| Fish | 0.2478 |
| Tofu | 0.1011 |

> **3. 주사위의 눈의 합**

1번에서 보았던 주사위를 n개 던져서 나온 눈의 합을 알 때, 주사위의 비율을 추정한다고 해보자.

이때 우리는 다음과 같은 변수를 정의할 수 있다.

- 주사위의 갯수 : $n$
- i개의 눈을 가진 주사위의 갯수 : $n_{i}$
- 전체 눈의 수의 합 : $n\alpha$
- 추가되는 Prior Knowledge : $\sum_{i=1}^{6}{i n_{i}} = n\alpha$

이를 Maximum Entropy를 이용해서 풀게 되면 다음과 같은 결론을 얻을 수 있다.

$$
p_{i} = {e^{\lambda_{i}}\over{\sum_{i=1}^{6}{e^{\lambda_{i}}}}}
$$

## Generalization

Maximum Entropy를 위의 식을 통해서 구하는 것도 문제는 없지만 우리는 좀 더 일반화된 식을 원한다. 따라서, 이를 표현하기 위해서 다음과 같은 상황을 고려해보는 것이다. 우리가 마지막 보았던 예시가 사실은 우리가 하고자 하는 과정을 대표하는 하나의 예시이다. 우리가 가진 사전 지식은 이전에 관측한 데이터와 이것의 class이다. 따라서, 우리는 관측 결과의 가짓수(class)가 $K$개이고, 데이터의 input과 결과를 $(X, Y)$ 쌍이 라고 할 때, 특정 input data($X_{i}$)가 class k일 확률은 다음과 같이 표현할 수 있다.

$$
p(Y_{i} = k) = {e^{w^{\top}_{k}X_{i}}\over{\sum_{k^{\prime}=1}^{K}{e^{w_{k^{\prime}}^{\top}X_{i}}}}}
$$

여기서 가장 중요한 Point가 발견된다. 바로 이 식이 **softmax** 함수라는 것이다. 즉, Maximum Entropy를 통한 classification의 의미는 사실상 multinomial logistic regression의 다른 이름일 뿐이다. (logistic regression에 대한 내용은 [🔗 [ML] 3. Logistic Regression](/posts/ml-logistic-regression)에서 다루었다.)

따라서, 여기서는 별도로 Modeling, Estimation, Smoothing 절차를 다루지 않는다. machine learning의 방법과 동일하기 때문이다.

## Features

NL의 가장 큰 특징은 data가 sparse하다는 것이다. domain마다 사용되는 언어와 빈도가 너무나 천차만별이기 때문에 sparse 현상이 필연적으로 발생한다. 이를 극복하기 위해서 대게의 data는 domain 별로 따로따로 수집하는 것이 일반적이다. 또한, data에서 올바른 feature를 추출하는 것이 굉장히 중요하다. 
이를 위해 NL에서 전통적으로 쓰던 방식은 대소문자 여부, 억양 표기, 품사, 문장구조, 뜻 등을 단어에 미리 적용하기도 하여 이를 이용하는 방법도 있다. 그런데 이러한 품사, 뜻 등을 찾아내는 과정도 Statistical Inference가 필요하다. 따라서, 앞으로 chapter에서는 품사와 문장구조 뜻을 정의하기 위한 기술들과 이를 어떻게 찾을 수 있는지를 알아볼 것이다.

또한, Word자체를 Vector로 치환하여 사용하는 Word2Vec방식에 대해서도 살펴보도록 하겠다.

## Reference

- Tumbnail : Photo by [David Ballew](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)
- Maximum Entropy 자료 참고, <https://www2.isye.gatech.edu/~yxie77/ece587/Lecture11.pdf>

[NLP] 7. MaxEnt

## Intro

이전까지 특정 word를 기반으로 하여 modeling을 수행하는 방법을 알아보았다. 하지만, 우리가 특정 word의 sequence를 통해서 각 word에 대한 classification을 한 번에 하고 싶은 경우는 어떻게 할까?(예를 들어, 각 단어의 품사를 지정하는 일) 일반적으로 각 단어가 특정 해당 class일 확률로 구하는 방법이 일반적일 것이다. 하지만, 문맥을 고려하여 확률을 구할 방법은 없을까? 그 방법은 바로 bigram을 이용하면 될 것이다. 그렇다면, 사실 우리가 사용하는 문맥이 단어 자체보다는 이전 class가 더 영향이 크다면, 이는 어떻게 해야할까? 이를 위한 해결책이 HMM이다. NLP 뿐만 아니라 여러 분야에서 넓게 사용되고 있지만, 여기서는 NLP 분야에서 어떻게 이를 사용하는지를 알아볼 것이다.

## Markov Model

HMM을 알아보기전에 Markov Model을 알아야 한다. 이는 특정 sequence의 확률을 추정하는 방법이다. 즉 우리에게 state sequence ($S= {s_{0}, s_{1}, ..., s_{N}}$)가 주어질 때, 각 state에서 다음 state로 전이(이동)할 확률을 이용해서 state sequence의 확률을 구하는 방법이다.

![nlp-markov-model-1](/images/nlp-markov-model-1.jpg)

위의 그림이 state 각 각에서 다음 state로 전이할 확률을 나타낸 것이라면, 우리는 아래 그림과 같은 그림으로 sequence의 확률을 추론할 수 있는 것이다.

![nlp-markov-model-2](/images/nlp-markov-model-2.jpg)

따라서, 위의 그림에서 우리가 만약 $(s_{0}, s_{1}, s_{0}, s_{2})$으로 이루어진 sequence의 확률을 얻기를 바란다면, 그 확률은 아래와 같아진다.
$$
\begin{align*}
p(s_{0}, s_{1}, s_{0}, s_{2}) &= p(s_{0}| \text{start}) \times p(s_{1}|s_{0}) \times p(s_{0}|s_{1}) \times p(s_{2}|s_{1}) \times p(end|s_{2}) \\
&= \pi_{0} \times p_{01} \times p_{10} \times p_{12} \times 1
\end{align*}
$$

이를 잘 살펴보니 bigram에서의 Likelihood를 구하는 공식과 똑같다. 즉, state 각 각을 word라고 본다면, Markov Model을 통해서 구할 수 있는 확률은 bigram의 Likelihood인 것이다.

그리고 이를 일반화하면 다음과 같다.

$$
p(seq) = \prod_{i=1}^{N}p(seq_{i}|seq_{i-1})
$$

그런데, 여기서 n이 3 이상인 ngram을 적용하고 싶다면, 각 state를 n-1 gram으로 설정하면 된다.

$$
\begin{align*}
X_{i} &= (Q_{i-1}, Q_{i}) \text{라면, }\\
P(X_{i} | X_{i-1}) &= P(Q_{i-1}, Q_{i} | Q_{i-2}, Q_{i-1}) \\
&= P(Q_{i} | Q_{i-2}, Q_{i-1})
\end{align*}
$$

따라서, trigram을 적용해보면 아래와 같다.

$$
\begin{align*}
p((start, w_{0}), (w_{0}, w_{1}), (w_{1}, w_{0}), (w_{0}, w_{2})) &= p(w_{0}| \text{start}, \text{start}) \times p(w_{1}|\text{start}, w_{0}) \times p(w_{0}|w_{0}, w_{1}) \times p(w_{2}|w_{1}, w_{0}) \times p(end|w_{0}, w_{2}) \\
&= \pi_{0} \times p_{01} \times p_{10} \times p_{12} \times 1
\end{align*}
$$

## Hidden Markov Model

Hidden Markov Model은 state를 하나 더 만든다는 것이 핵심이다. 그래서, 우리가 직접 관측하는 state(**observed state**)와 직접적으로 관측하지 않지만, 관측한 state들에 의존하는 state(**hidden state**) 총 두 개의 state를 사용한다. 일반적인 예시가 text가 입력되었을 때 우리는 각 단어를 observed state라고 한다면, 각 단어의 품사를 hidden state라고 정의할 수 있다.

![nlp-markov-model-3](/images/nlp-markov-model-3.jpg)

위의 예시는 우리가 관측하는 데이터($O$)가 3개의 state를 가지고, 이 사건에 의존적인 또 다른 사건($H$)이 3개의 state를 가지는 경우이다. 이를 이용해서 기존 Markov Model보다 복잡한 작업을 수행하는 것이 가능하다.

### Estimation

우리가 할 수 있는 작업은 크게 두 가지이다. 일반적인 Markov Model에서 할 수 있던 방식이 **Trellis** 방식이고, 또 다른 방식이 **Viterbi** 방식이다.

1. $(o_{0}, o_{1}, o_{0}, o_{2})$의 확률이 궁금할 때(**Trellis**)
2. $(o_{0}, o_{1}, o_{0}, o_{2})$가 주어질 때, 이것의 hidden state의 sequence 중 가장 유력한 sequence를 찾고자할 때(**Viterbi**)

위의 경우를 각각 풀어보도록 하자.

> **1. Trellis**

우리가 직접 관측한 데이터의 sequence 자체의 확률이 궁금할 때이다. 따라서, 이에 대한 분석은 $(o_{0}, o_{1}, o_{0}, o_{2})$의 확률을 분석해보면서 설명하겠다.

$$
\begin{align*}
p(o_{0}, o_{1}, o_{0}, o_{2}) &= p(o_{0}, o_{1}, o_{0}) \times p(o_{2} | o_{0}, o_{1}, o_{0}) \\
&= p(o_{0}, o_{1}, o_{0}) \times \{p(o_{2} | h_{0})p(h_{0} | o_{0}, o_{1}, o_{0}) + p(o_{2} | h_{1})p(h_{1} | o_{0}, o_{1}, o_{0}) + p(o_{2} | h_{2})p(h_{2} | o_{0}, o_{1}, o_{0})\} \\
&= p(o_{0}, o_{1}, o_{0}) \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\
&= p(o_{0}, o_{1}) \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\
&= p(o_{0}) \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\
&= \sum_{i=0}^{2}p(o_{0}|h_{i})p(h_{i}|start) \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) }
\end{align*}
$$

이를 그림으로 표현하면 다음과 같다.

![nlp-hidden-markov-model-1](/images/nlp-hidden-markov-model-1.jpg)

또한, 이 식을 다음과 같이 축소가 가능하다.

$$
\begin{align*}
 &\sum_{i=0}^{2}p(o_{0}|h_{i})p(h_{i}|start) \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\
 =& \sum_{i=0}^{2}\alpha_{0 i} \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\
 =& \sum_{i=0}^{2}{\alpha_{1 i} } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\
 =& \sum_{i=0}^{2}{\alpha_{2 i} } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\
 =& \sum_{i=0}^{2}{\alpha_{3 i} }
\end{align*}
$$

우리는 이를 통해서, Markov Model의 특징을 하나 배울 수 있다. 그것은 바로 복잡한 sequence 전체의 확률에서 벗어나서 바로 직전의 확률값만 으로 다음 확률을 추론할 수 있다는 것이다. 이것이 Markov Chain이라는 이론이고, 이를 이용했기 때문에 Markov Model라고 부르는 것이기도 하다.

따라서, $\alpha$는 다음과 같이 정의할 수 있다.

$$
\alpha(t, i) = \sum_{k=1}^{N}{\alpha(t-1, k)p(h_{i}|h_{k})p(o = s_{t}|h_{i})} \quad (s_{t} = \text{input으로 들어온 sequence의 t번째 값})
$$

또, 이를 반대로 할 경우에는 다음과 같은 식을 얻을 수 있다.

![nlp-hidden-markov-model-2](/images/nlp-hidden-markov-model-2.jpg)

$$
\begin{align*}
 &\sum_{i=0}^{2}p(o_{0}|h_{i})p(h_{i}|start) \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{p(o_{2} | h_{i})p(h_{i} | o_{0}, o_{1}, o_{0}) } \\
 =& \sum_{i=0}^{2}p(o_{0}|h_{i})p(h_{i}|start) \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{p(o_{0} | h_{i})p(h_{i} | o_{0}, o_{1}) } \times \sum_{i=0}^{2}{\beta_{3i}} \\
 =& \sum_{i=0}^{2}p(o_{0}|h_{i})p(h_{i}|start) \times \sum_{i=0}^{2}{p(o_{1} | h_{i})p(h_{i} | o_{0}) } \times \sum_{i=0}^{2}{\beta_{2i}} \\
 =& \sum_{i=0}^{2}p(o_{0}|h_{i})p(h_{i}|start) \times \sum_{i=0}^{2}{\beta_{1i}} \\
 =& \sum_{i=0}^{2}{\beta_{0i}} \\
\end{align*}
$$

$$
\beta(t, i) = \sum_{k=1}^{N}{\beta(t+1, k)p(h_{k}|h_{i})p(o = s_{t}|h_{i})} \quad (s_{t} = \text{input으로 들어온 sequence의 t번째 값})
$$

위의 처럼 앞에서부터 풀이를 해나가면서, $\alpha$의 합으로 끝이 나도록 푸는 방법을 forwarding 방식이라하고, 반대로 뒤에서부터 풀이하면서 $\beta$의 합으로 푸는 방법을 backwarding 방식이라고 한다. 사실 이 경우는 HMM이 굳이 아니더라도, MM으로 구할 수 있으니 굳이 필요는 없다. 하지만, 이것은 후에 modeling 단계에서 사용하기 때문에 알아두어야 한다.

> **2. Viterbi**

이는 observed state의 sequence에 의해서 파생되는 가장 적절한 hidden sequence를 구하는 것이 목표이다. 이를 통해서 할 수 있는 대표적인 것이 sequence classification이다.

그렇다면 가장 유력한 hidden state의 sequence를 $\hat{s}^{(H)}$라고 하자. 이는 다음과 같다.

$$
\begin{align*}
\hat{s}^{(H)} &= \argmax_{s^{(H)} \in S^{(H)}}P(s^{(H)}|s^{(O)}) \\
&= \argmax_{s^{(H)} \in S^{(H)}}P(s^{(O)}|s^{(H)})P(s^{(H)}) \\
&= \argmax_{{h_{1}, h_{2}, ..., h_{N}} \in S^{(H)}}\underbrace{P(o_{1}, o_{2}, ... , o_{N}|h_{1}, h_{2}, ... , h_{N})}_{\text{Markov Model}}\underbrace{P(h_{1}, h_{2}, ... , h_{N})}_{\text{Markov Model}} \\
&= \argmax_{{h_{1}, h_{2}, ..., h_{N}} \in S^{(H)}}\prod_{i=1}^{N}p(o_{i}|h_{i})p(h_{i}|h_{i-1})
\end{align*}
$$

![nlp-hidden-markov-model-3](/images/nlp-hidden-markov-model-3.jpg)

즉, 각 layer에서 단 하나의 가장 큰 output만 살아남을 수 있게 되는 것이다. 이 과정이 사실상 HMM의 본질적인 목표이다. sequence를 입력해서 sequence 형태의 classification 결과를 얻는 것이다.

### Modeling

여태까지 HMM을 활용하여 sequential class를 어떻게 estimation 하는지 알아보았다. 그렇다면, 이제는 이를 위해서 사용되는 확률값을 구해야한다. 필요한 확률값은 다음과 같다.

- $p(h_{i}|h_{i-1})$ : Hidden State에서 Hidden State로 넘어가기 위한 확률이다.
- $p(o_{i}|h_{i})$ : 방출 확률로 특정 Hidden State에서 다음 State의 Observed State로 넘어가는 방법이다.
- $\pi_{i}$

Trelli 방식에서 만들었던, $\alpha$와 $\beta$의 의미를 이해해야 한다. 각 각은 해당 과정까지 오면서 누적해온 확률이라고 할 수 있다. 그리고, 우리가 원하는 것은 입력으로 주어진 데이터를 잘 반영할 수 있는 확률 값을 찾는 것이다. 그렇다면, 우리가 생각할 수 있는 방법은 평균을 활용하는 것이다. 이를 구하는 과정을 먼저 살펴보자.

$$
\begin{align*}
 c(i, j, k) &= h_{i}\text{에서 } h_{j}\text{로 넘어가고, } o_{k}\text{가 관측될 확률의 합} \\
 &= \sum_{t=2}^{T} \alpha(t-1, i)p(h_{j}|h_{i})p(o_{k}|h_{j}) \beta(t, j) \\
 \\
 c(i,j) &= h_{i}\text{에서 } h_{j}\text{로 넘어갈 확률의 합} \\
 &= \sum_{k=1}^{K}\sum_{t=2}^{T}{\alpha(t-1, i)p(h_{j}|h_{i})p(o_{k}|h_{j}) \beta(t, j)} \\
 \\
 c(i) &= h_{i}\text{에서 상태를 변경하는 확률의 합} \\
 &= \sum_{j=1}^{N}\sum_{k=1}^{K}\sum_{t=2}^{T}{\alpha(t-1, i)p(h_{j}|h_{i})p(o_{k}|h_{j}) \beta(t, j)} \\
\end{align*}
$$

위의 값을 통해서 우리는 우리가 가지고 있던 확률을 업데이트할 수 있다.

$$
\begin{align*}
p(h_{j}|h_{i}) &= {c(i,j)\over c(i)} \\
p(o_{k}|h_{i}) &= {c(i,j,k)\over c(i,j)}
\end{align*}
$$

즉, 우리는 다음 과정을 수행하여 Modeling을 수행할 수 있는 것이다.

1. 초기값 ($p(h_{i}|h_{i-1})$, $p(o_{i}|h_{i})$, $\pi_{i}$)을 초기화 한다. 
2. Trelli를 통해서 $\alpha$, $\beta$를 계산한다.
3. $p(h_{i}|h_{i-1})$, $p(o_{i}|h_{i})$를 업데이트 한다. 
 ($pi_{i}$같은 경우는 발생 빈도로 업데이트 한다.)
4. 임계치에 도달할 때까지 2,3번을 반복한다.

이 과정을 대게 10번 정도만 하면 수렴하게 되고, 이를 확률로 사용하는 것이다.

## Reference

- Tumbnail : Photo by [David Ballew](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)

[NLP] 6. Hidden Markov Model

## Intro

Naive Bayes Model은 가장 쉽게 Classification을 수행할 수 있는 Model이지만, 성능이 다른 Model에 비해 뛰어나지는 않다. 그럼에도 Naive Bayes는 가장 기본이 되는 Model이기에 비교 대상으로 많이 사용되고, Classification의 insight를 키우는데 많은 도움을 줄 수 있다. 여기서는, 전반적인 개념과 이를 직접 Spam Filtering에서 어떻게 사용하는지 살펴본다.

## Naive Bayes Model

특정 class에서 해당 데이터가 얼마나 자주 발생되는지와 실제로 해당 class의 빈도를 활용하여, classification을 수행하는 것이다. 우선 이를 수식적으로 표현하기 위해서 다음 변수들을 먼저 정의해보자.

- **documents($D$)**: 여러 개의 Document를 의미하며, 하나의 Document는 대게 여러 개의 words를 포함한다. 각 document는 $d_{i} \in D$의 형태로 표현한다.
- **classes($C$)**: class는 두 개 이상을 가진다. 각 클래스는 $c_{i} \in C$의 형태로 표현된다.
- **labeled dataset**: 이는 (document($d_{i}$), class($c_{i}$))가 하나씩 mapping된 형태로 존재한다. 우리가 가지는 dataset으로 학습, 평가 시에 사용한다. 대게 평가에 사용되는 데이터는 학습 시에 사용하는 것을 금지하기 때문에 별도로 분리하여 사용한다.
- **word($w$)**: 하나의 word를 의미하며 NLP 학습 시에 사용하는 가장 작은 단위이다. 대게 document 하나에 있는 단어의 수는 N으로 표기하고, unique한 단어의 수는 V(size of vocabulary)로 표시한다.

따라서, 우리가 찾고자 하는 가장 높은 확률을 가진 class는 다음을 통해서 구할 수 있다.

$$
\begin{align*}
c_{MAP} &= \argmax_{c \in C}{P(c|d)} \\
&= \argmax_{c \in C}{p(d|c)p(c)\over p(d)} \\
&= \argmax_{c \in C}{p(d|c)p(c)} \\
&= \argmax_{c \in C}{p(w_{1}, w_{2}, ... , w_{N} | c)p(c)} \\
&= \argmax_{c \in C}{\prod_{i=1}^{N}p(w_{i}|c)p(c)} \\
&= \argmax_{c \in C}{\log(\prod_{i=1}^{N}p(w_{i}|c)p(c))} \\
&= \argmax_{c \in C}{\sum_{i=1}^{N}\log p(w_{i}|c) + \log{p(c)}} \\
\end{align*}
$$

여기서 우리가 language model을 무엇으로 정했는지가 중요하다. 위에서는 uni-gram이라고 가정해서 풀이했지만, bi-gram인 경우 document의 형태가 $d={(w_{1}, w_{2}), (w_{2}, w_{3}), ... , (w_{N-1}, w_{N})}$이다. 따라서, 전체적인 크기와 vocabulary자체도 바뀌게 된다.

즉, 우리는 train set을 통해서 vocabulary를 완성한다. 그리고, 각 word의 count 및 필요에 따라 필요한 word sequence의 count를 수집하여 $p(w_i)$를 구한 후 위에 방법을 통해서 특정 class를 추측할 수 있는 것이다.

이제 구체적인 Naive Bayes의 동작 절차는 Spam Filtering이라는 Case Study를 통해서 자세히 살펴보도록 하자.

## Case Study. Spam Filtering

초기 NLP가 가장 많이 사용되었던 예시 중에 하나이다. 여러 개의 메일에 spam인지 ham인지를 labeling한 데이터를 갖고 후에 input으로 mail 데이터가 들어왔을 때, 이를 filtering하는 것이다. 위에서 살펴보았던 확률을 그대로 적용하면 된다. 예측에 필요한 확률을 습득하고, 예측하는 방법과 이를 평가하는 방법의 순으로 설명하겠다.

### 0. Preprocessing

사실 mail data의 형태가 이상할 수도 있다. Subject부터 시작하여 날짜 데이터 그리고 특수 문자 등이 존재할 수 있는데, 이를 먼저 처리해서 후에 있을 Modeling 단계에서 잘 사용할 수 있도록 형태를 변형해주어야 한다.

[🔗 이전 Posting(Text Processing)](/posts/nlp-text-processing)에서 배웠던 기술들을 활용하여 이를 해결할 수 있다.

대표적으로 해줄 수 있는 작업들은 다음과 같다.

1. 대소문자 통일
2. alphabet이 하나라도 들어있지 않은 데이터는 삭제
3. date, 참조 등을 의미하는 데이터 삭제

### 1. Modeling

Parameter Estimation / Learning / Modeling 등으로 불리는 단계이다. 일단 우리는 train set으로부터 우리가 원하는 확률을 추출해야 한다. 그 전에 우리가 어떤 language model을 이용할지 선택해야 한다. 먼저 uni-gram인 경우에는 다음과 같은 방법으로 train set이 정의된다.
$$
\text{TrainSet} = {(d_{1}, c_{1}), (d_{2}, c_{2}), ..., (d_{N}, c_{N})}
$$
$$
d_{i} = \begin{cases}
 {w_{1}, w_{2}, ... , w_{M_{i}}} \quad&\text{unigram} \\
 {(<s>, w_{1}), (w_{1}, w_{2}), ... , (w_{M_{i}}, </s>)} \qquad&\text{bigram}
\end{cases}
$$

이제 우리가 원하는 parameter, 즉 확률은 다음과 같은 데이터이다.

> **unigram**

$$
\begin{align*}
p(w_{i}|c_{j}) &= {\text{count}(w_{i}, c_{j}) \over \sum_{w \in V} \text{count}(w, c_{j})} \\
p(c_{j}) &= {\sum_{i = 1}^{N}{1[c_{i} = c_{j}]} \over N}
\end{align*}
$$

> **bigram**

$$
\begin{align*}
p(w_{i}|w_{i-1},c_{j}) &= {\text{count}((w_{i-1}, w_{i}), c_{j}) \over \sum_{(w^{(1)}, w^{(2)}) \in V} \text{count}((w^{(1)}, w^{(2)}), c_{j})} \\
p(c_{j}) &= {\sum_{i = 1}^{N}{1[c_{i} = c_{j}]} \over N}
\end{align*}
$$

여기서 우리는 반드시 Smoothing을 해주어야 한다. 왜냐하면, spam mail에서 안 본 단어가 나올 가능성이 너무나 높기 때문이다. 따라서, 실제 $p(w_{i}|c_{j})$는 아래와 같이 변경된다. (간단한 예시를 들기 위해서 Add-1 방식을 사용했다. - 해당 내용이 기억이 나지 않는다면, [🔗 이전 포스팅](/posts/nlp-language-modeling)을 다시 보고 오자.)

$$
p(w_{i}|c_{j}) = {\text{count}(w_{i}, c_{j}) + 1 \over \sum_{w \in V} \text{count}(w, c_{j}) + |V|}
$$

주의할 점은 다시 한 번 강조하지만, $V$는 후에 Estimation에서 input으로 사용하는 단일 document까지 포함한 Vocabulary이다.

### 2. Estimation

이제 우리가 얻은 parameter를 이용해서 실제 input data에 대한 estimation을 수행할 수 있다.

이 경우 다음과 같은 과정을 수행할 수 있다.

$$
\hat{c} = \argmax_{c \in C} p(c)\prod_{w \in d_{\text{input}}}p(w|c)
$$

물론 어떤 n-gram을 쓰냐에 따라 $d_{\text{input}}$도 형태가 달라질 것이다.

### 3. Evaluation

이제 평가를 수행할 것이다. 평가는 우리가 알아봤던 Accuracy와 F1 Score를 추출할 수 있다. Binary Classification이기 때문에 쉽게 구할 수 있을 것이다.

| prediction\answer | True | False |
| :---------------- | :------------------------------------------------------------------------- | :------------------------------------------------------------------------ |
| Positive | $\sum_{(d, c) \in D_{\text{test}}} 1[\hat{c}_{d} = c, c = \text{spam}]$ | $\sum_{(d, c) \in D_{\text{test}}} 1[\hat{c}_{d} \neq c, c = \text{ham}]$ |
| Negative | $\sum_{(d, c) \in D_{\text{test}}} 1[\hat{c}_{d} \neq c, c = \text{spam}]$ | $\sum_{(d, c) \in D_{\text{test}}} 1[\hat{c}_{d} = c, c = \text{ham}]$ |

## Reference

- Tumbnail : Photo by [David Ballew](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)

[NLP] 5. Naive Bayes

## Intro

이전 Posting에서는 sentence의 적절성을 확인한다든지 다음 단어를 유추한다든지 오타를 정정하는 등에 필요한 기본적인 Language Modeling 방식을 살펴보았다. 이번에는 실제로 가장 많이 사용되는 예제인 Classification을 Language Model을 이용하여 어떻게 구현하는지를 다룬다.

## Classification

Classification은 input이 들어왔을 때, 이를 알맞은 분류로 나누는 것이 목표이다. 단순히 Rule에 기반하여 이를 수행할 수도 있지만, Statistic한 Language Modeling을 이용하면, 더 정확도가 높은 분류를 수행할 수 있다. 결국 Statistic Prediction을 수행하기 위해서 우리는 3개(Estimation, Modeling, Evaluation)를 중점적으로 봐야 하는 것은 Classification도 동일하다. 따라서, 이에 대해서 살펴볼 것이고, 그 전에 먼저 Classification Model 의 종류를 살펴보도록 하겠다.

## Generative Model vs Discriminative Model

Classification에서 이용되는 Model을 크게 두가지로 나눌 수 있는데 이에 대해서 먼저 알아보도록 하자.

1. **Generative Model(생성 Model)**
 1. Naive Bayes
 2. Hidden Markov Model(HMM)
2. **Discriminative Model(판별 Model)**
 1. Logistic Regression
 2. K Nearest Neighbors
 3. Support Vector Machine
 4. Maximum Entropy Model(MaxEnt)
 5. Neural Network(Deep Learning)

두 Model의 가장 큰 차이점은 추론의 과정이다. 우리가 원하는 데이터 $P(\text{class}=c | \text{input} = \text{data})$(특정 data가 주어졌을 때, 각 class의 속할 확률)를 얻는 과정이 서로 다르다.

**첫 번째**로, $P(\text{class}=c, \text{input} = \text{data})$일 확률을 구하여 **간접적**으로 구하는 방법이다.

$$
\begin{align*}
P(\text{class}=c | \text{input} = \text{data}) &= {{P(\text{class}=c, \text{input} = \text{data})}\over{P(\text{input} = \text{data})}} \\
&\propto {P(\text{class}=c, \text{input} = \text{data})}
\end{align*}
$$

이런 식으로 생성하여 추론하는 방식을 Generative Model이라고 한다. 이 방식은 결국 Conditional Probability를 추론하기 위해서 Joint Probability를 이용하는 방식이기 때문에 어느정도 한계가 존재한다는 점을 유의하자.

**두 번째**로는, $P(\text{class}=c | \text{input} = \text{data})$를 **직접적**으로 구하는 방법이 있다. 이를 위해서, 마친 Conditional Probability를 구한 것과 유사한 효과를 내는 **Discriminant Function(판별 함수)**이라는 특별한 함수를 input에 적용하는 방법이다. 이 함수 중에서 가장 대표적인 것이 Softmax function이다. 우리가 만약 input을 softmax function에 입력하게 되면, 이 값은 [0, 1] 사이의 값으로 표현된다. 이를 통해서 우리는 해당 input이 class인 경우 1에 가깝게, 그렇지 않은 경우 0에 가깝게 표현하여 여러 데이터에 적용하면, class의 inpuut에 따른 분포 양상을 확인할 수 있다. 그리고, 이 분포 양상을 확률로 즉각적으로 표현할 수 있기 때문에 softmax function을 취한 결과가 $P(\text{class}=c | \text{input} = \text{data})$과 비례한다는 결론을 낼 수 있다. 자세한 설명이 필요하다면, [🔗 Logistic Regression](/posts/ml-logistic-regression#Logistic-Regression)을 참고하도록 하자. 이러한 방식을 우리는 Discriminative Model이라고 한다.

위에서 제시한 방법들 중 대표적인 방법들은 별도의 Posting을 통해서 정리하였다. 해당 링크를 참조하여 확인해보도록 하자.

- **Generative Model(생성 Model)**
 - [🔗 Naive Bayes](/posts/nlp-naive-bayes)
 - [🔗 Hidden Markov Model(HMM)](/posts/nlp-hmm)
- **Discriminative Model(판별 Model)**
 - [🔗 Maximum Entropy Model(MaxEnt)](/posts/nlp-maxent)
 - [🔗 Logistic Regression](/posts/ml-logistic-regression)

## Estimation

어떤 Model을 선택했다고 하더라도 결국 우리가 Class를 결정하는 과정을 동일하다. 위의 과정을 통해서 어찌되었든 다음 값을 찾으면 된다.

$$
\begin{align*}
c^{\prime} &= \argmax_{c \in C}{P(\text{class}=c | \text{input} = \text{data})}
\end{align*}
$$

## Modeling

Model을 만드는 과정, 즉 학습하는 과정은 결국 Model의 구현마다 천차 만별이다. Naive Bayes는 단순하게 data의 word와 count를 활용하고, HMM은 EM algorithm을 활용하며, Linear Regression은 Gradient Descent를 활용한다. 따라서, 여기서는 자세히 다루지 않고 위에서 제시한 링크를 따라가서 각 Model마다의 학습법을 확인해보도록 하자.

## Evaluation

Classification의 성능을 평가하는 것 역시 중요한 일이다. 가장 쉬운 Binary Classification부터 알아보자.

binary classificaiton의 결과는 아래와 같이 4개 중 하나로 결정된다.

| prediction\answer | True | False |
| :---------------- | :------------- | :------------- |
| Positive | true positive | false positive |
| Negative | false negative | true negative |

이를 쉽게 이해할려면, 병(코로나)의 양성/음성 판정이 row에 해당하고, 실제 병의 여부를 column으로 생각하면 쉽다. 또한, 각 cell의 값이 헷갈릴 수 있는데, 우리가 원하는 것이 예측의 정확도를 확인하는 것이기 때문에 예측 결과는 그대로 보여주면서, 이것이 틀렸는지 맞았는지를 앞에 true/false로 표현했다고 생각하면 쉽다.

classification의 성능을 측정하는 지표는 대표적으로 4 가지가 있다.

1. **Accuracy(정확도)** 
 가장 쉽게 그리고 일반적으로 생각하는 지표다. 위의 표에서는 전체 경우의 수를 더하여 옳게 예측한 것(true postive, true negative)의 합을 나누는 것이다.
 $tp + fn \over tp + fp + fn + tn$ 
 하지만, 이 방식은 한계가 있다. 바로, 데이터가 한쪽으로 치우쳐져있을 때이다. 예를 들어, 우리가 진짜를 진짜라고 맞출확률은 높지만, 가짜를 가짜라고 맞출 확률이 낮다고 할 때, 이를 제대로 반영하기가 어렵다. 그런데 데이터에서 진짜가 가짜보다 압도적으로 많을 경우 정확도는 좋은 지표로 쓰기 어렵다는 것이다.
2. **Precision(정밀도, 정답률)** 
 쉽게 정답 자체를 맞힐 확률입니다. 
 $tp \over tp + fn$
3. **Recall(재현율)** 
 예측이 맞을 확률을 의미합니다. 
 $tp \over tp + fp$
4. **F1 Score** 
 좀 더 세분화된 평가지표이다. 조화 평균에 기반하여 모델의 성능을 정확하게 평가할 때 사용한다. 
 ${2\over{{1\over\text{Precision}} + {1\over\text{Recall}}}} = 2 \times {\text{Precision} \times \text{Recall} \over \text{Precision} + \text{Recall}}$

여기까지 봤으면, 슬슬 multi class의 경우에는 어떻게 해야할지 궁금할 것이다. 대게 두 가지 방법을 통해서 수행할 수 있다.

> **1. Micro Average**

전체 class를 하나의 binary table로 합치는 것이다. 즉, 클래스가 A, B, C 3개가 있다면, 각 클래스 별로 예측 성공도를 binary로 표시하고, 이를 하나의 테이블로 합치는 것이다. 그 후에는 binary에서 계산하는 식을 그대로사용할 수 있다. 

> **2. Macro Average**

multi class의 경우에도 별로 다를 것은 없다. 단지 Precision과 Recall 그리고 Accuracy가 어떻게 바뀌는지만 알면 쉽게 이해할 수 있을 것이다. 

| prediction\answer | c1 | c2 | c3 | c4 |
| :---------------- | :------------ | :------------ | :------------ | :------------ |
| c1 | true positive | x | x | x |
| c2 | x | true positive | x | x |
| c3 | x | x | true positive | x |
| c4 | x | x | x | true positive |

- Precision: $c_{ii} \over \sum_{j}c_{ij}$
- Recall: $c_{ii} \over \sum_{j}c_{ji}$
- Accuracy: $c_{ii} \over \sum_{i}\sum_{j}c_{ij}$

## Reference

- Tumbnail : Photo by [David Ballew](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)

[NLP] 4. Classification

[NLP] 3. Language Modeling


## Intro

NLP를 수행할 때, 우리는 sequence of character를 처리하는 방식을 제대로 알아야 제대로 된 전처리와 후처리 등이 가능하다. 따라서 해당 chapter에서는 어떻게 원본 문자/단어/문장을 처리하는 방식을 다룰 것이다.

## Regular Express

아주 기본적인 문자열 처리 방법이다. 이를 알고 있어야 실질적인 처리가 가능하다. 해당 내용은 별도의 Posting으로 분리하여 다루었다. ([🔗 Regex](/posts/regex))를 살펴보도록 하자.

## Text Normalization

우리가 사용할 NL은 정제되어 있지 않아서 여러 전처리를 수행해야 한다. 그 중에서 대중적으로 좋다고 알려진 방법들을 살펴볼 것이다. 기본적으로는 아래 단계를 처리하는 것이 일반적이다.

1. Word Tokenization  
   말 그대로 NL 데이터가 입력되었을 때, 이를 단어 단위로 쪼개는 것이다.
2. Word Reformating  
   단어를 나누었다면, 각 단어의 형태를 처리하기 쉬운 형태로 Normalizing하는 것이다.  
3. Sentence Segmentation  
   문장 단위로 구분해는 과정이다.

이제 각 단계를 세부적으로 다뤄보겠다.

### 1. Word Tokenization

우선 쉽게 생각할 수 있는 것은 단순히 띄어쓰기를 기준으로 구분하는 것이다. 그렇게 하면, 우리는 입력으로 주어진 Corpus에서 token을 추출할 수 있다.

하지만, "San Francisco"와 같은 단어가 두 개의 token으로 나누는 것이 아니라 하나의 token으로 처리되기를 원할 수 있다. 뿐만 아니라 일부 언어들(특히 중국어와 일본어)의 경우 띄어쓰기 없이 작성하는 언어들의 경우 문제는 더 커질 수 있다. 이 경우에는 **Word Segmenting**이라는 알고리즘을 활용할 수도 있는데, 원리는 매우 간단하다. 언어의 모든 단어를 포함하는 사전을 기반으로 문장에서 사전에 일치하는 가장 긴 문자열을 찾을 수 있을 때까지 token을 연장해서 만드는 방식이다.

그러나 이 방식도 결국은 특정 언어(중국어, 등)에서는 잘 작동하지만, 일부 언어(영어 등)에서는 잘 작동하지 않는 경우가 많다. 따라서, 최근에는 확률에 기반하여 같이 등장하는 횟수가 많을 경우 하나의 token으로 묶는 형태의 tokenization을 더 선호한다.

이 과정에서 우리가 추가적으로 수행하는 것이 바로 word의 갯수를 추출하는 것이다. 대게 우리가 관심 있어하는 수는 총 3가지이다.

1. **number of tokens**  
   즉, 띄어쓰기로 나뉘어지는 token들의 총 갯수를 의미한다.
2. **number of types(Vocabulary)**  
   띄어쓰기로 나뉘어진 token들의 중복을 제거한 종류들의 갯수를 의미한다. 대게 이러한 type들의 모음을 Vocabulary라고 한다.
3. **number of each type's tokens**  
   각 종류의 token이 얼마나 많이 등장했는지를 의미한다.

여기서 이러한 token이나 type이 서로 같나는 것을 어떻게 구분할 수 있을까? 이를 위해서 Word Reformating을 수행하여 좀 더 일반적인 형태로 변형하여 위의 수들을 파악하기도 한다.

### 2. Word Normalization and Stemming(Word Reformating)

대게의 언어는 word의 형태가 여러 개로 존재한다. 이 과정에서 우리가 고려해야 할 것이 정말 많다. 그 중에서 가장 기본적으로 수행되어야 할 내용은 다음과 같다. 해당 내용은 영어에 중심을 둔 설명이다.

1. **Uppercase**  
   영어에서 첫 글자는 대문자로 시작한다는 규칙이 있다. 또는 강조하고 싶은 단어를 대문자로 표현하기도 한다. 그 결과 token의 종류를 추출하는 과정에서 문제를 일으키기도 한다. 따라서, 이를 모두 lowercase로 바꿔버리는 것이다. 하지만, 모든 경우에 이를 적용할 수 잇는 것은 아니다. 가장 대표적인 예시로 US와 us의 의미가 다르다는 것이다. 또, 고유 명사인 General Motors와 같은 경우도 다르게 처리하는 것이 좋다. 따라서, 이를 고려해서 먼저 처리한 이후에 전체 데이터를 lowercase로 변환하는 방식을 수행한다.  
2. **Lemmatization**  
   Lemma(기본형, 사전형)로 단어를 변환하는 것이다. 가장 기본적인 것은 am, are, is와 같은 be동사를 모두 be로 변환하거나 car, cars, car's를 모두 기본형태인 car로 바꾸는 것이다. 대게의 경우에는 이 과정에서 의미를 일부 잃어버리기 때문에 lemma + tag로 기존 token을 복구할 수 있도록 하는 tag를 포함하는 것이 좋다.
3. **Stemming**  
   morpheme(형태소)은 중심 의미를 가지는 stem과 핵심 의미는 아니지만 stem에 추가 의미를 더해주는 affixes로 나누어 word를 나눌 수 있다. 따라서, 각 token을 가장 core의 의미를 가지는 stem으로 나타내는 방식이다. 대표적인 예시가 automate, automatic, automation을 automat으로 변환하는 것이다. 이는 lemmatization보다 넓은 범위의 word를 하나로 묶기 때문에 세부의미가 더 손실될 수 있다. 따라서, 기존 의미로 복구할 수 있는 tag를 포함하는 것이 좋다.

### 3. Sentence Segmentation

문장을 구분할 수 있는 도구로 우리는 "?", "!", "."을 활용한다. "?"와 "!" 같은 경우는 문장의 끝을 의미하는것이 대게 자명하다. 하지만, "."은 꽤나 애매할 수 있다. 소수점, Abbreviation(Mr., Dr., Inc.)와 같은 경우에 빈번하게 사용되기 때문이다. 따라서, 이를 판단하기 위해서 Decision Tree를 만들어서 이를 수행한다. 아래와 같이 사람이 직접 규칙을 정할 수도 있지만 현재는 대게 통계 기반으로 수행한다.

![nlp-sentence-segmentation](/images/nlp-sentence-segmentation.jpg)

## Collocation(연어) processing

Text Normalization을 통해서 우리는 sentence를 구분하고, word를 추출할 수 있었다. 하지만, 단순히 하나의 word를 기반으로 처리하는 것이 아니라 주변 단어를 활용하여 처리해야만 얻을 수 있는 정보들이 있다. 우리는 이를 Collocation(연어)를 활용하여 수행한다. 이는 특정 단어쌍이 높은 빈도로 같이 붙어 사용되는 현상을 말한다. **"모든 단어는 이를 동반하는 주변 단어에 의해 특성 지어진다."** 따라서, 우리는 이 collocation을 co-ocurrence로 생각할 수 있다. 이를 통해서 우리는 다음과 같은 것들을 할 수 있다.

1. **lexicography(사전 편찬)** : 같가니 유사한 뜻을 가지는 단어는 빈번하게 붙어서 사용되는데 이를 이용해서 하나의 단어의 뜻을 안다면, 이를 통해서 다른 단어의 뜻을 추론하며 확장해나갈 수 있다.
2. **language modeling** : NL를 통해서 원하는 결과를 얻기 위해서 특정 parameter를 추정해내는 것을 language modeling이라고 하는데 이 과정에서 collocation을 활용하는 것이 단일 단어를 활용하는 것보다 context를 활용할 수 있다는 점에서 장점을 발휘할 수 있다.
3. **NL generation** : 우리는 문맥상 매끄러운 문장을 원한다. 즉, "감을 잡다"를 "감을 붙잡다"라고 했을 때, 뜻을 이해할 수는 있지만 어색하다고 느낀다. 따라서, 이 관계를 활용해서 NL을 생성해야 하기 때문에 collocation을 고려해야 한다.

그렇다면, 이러한 Collocation을 어떻게 찾을 수 있을까?

1. **Frequency**  
   가장 간단하게 단순히 동시 발생 빈도를 확인하는 것이다. 정확한 파악을 위해서는 빈번하게 등장하는 의미 없는 단어를 먼저 filtering할 필요가 있다. 대표적인 예시로 a, the, and 등이 있다.
2. **Hypothesis Testing**  
   가설 검증으로 우리가 가정한 collocation을 지정하고, 이 사건이 일어날 가능성을 굉장히 낮게 하는 가설을 반대로 가정한 후에 이것이 불가능하다는 것을 증명하는 Null Hypothesis를 이용한 증명으로 타당성을 확보하는 것이다. 따라서, 우리가 보이고자 하는 것은 word1, word2가 있을 때, 두 단어가 서로 의존적이라는 것을 증명하고 싶은 것이다. 따라서, Null Hypothesis로 두 단어는 독립이다라고 지정하면, 우리는 다음 식을 얻을 수 있다.  
   $p(w_{1}, w_{2}) = p(w_{1})p(w_{2})$  
   이를 바탕으로 t-검증을 다음과 같이 수행할 수 있다.  
   $t = {{p(w_{1}, w_{2}) - p(w_{1})p(w_{2})} \over \sqrt{p(w_{1}, w_{2})\over{N}}} $  
   t값이 이제 커질 수록 우리는 해당 가설이 틀렸음을 증명하여 collocation임을 주장할 수 있다.

## Minimum Edit Distance

단어 또는 문장 간 유사도를 측정할 때, 사전을 기반으로 수행할 수도 있지만 참고할 corpus가 마땅하지 않거나 더 추가적인 수치가 필요하다면, Minimum Edit Distance로 유사도를 측정하기도 한다. 즉, 두 문자열이 같아지기 위해서 어느정도의 수정이 필요한지를 수치화한 것이다. 여기서 연산은 새로운 문자 추가, 삭제, 대체만 가능하다.

```plaintext
S - N O W Y  | - S N O W - Y
S U N N - Y  | S U N - - N Y
distance : 3 | distance : 5
```

다음과 같이 표현이 가능하다.

1. 문자열 x, y가 있을 때, $E(i, j)$는 x의 0\~i까지를 포함하는 문자열과 y의 0~j까지를 포함하는 문자열의 distance라고 하자.
2. 이렇게 되면, $E(i,j)$에서 우리는 끝문자의 규칙을 볼 수 있다.

    오른쪽 끝 문자가 가질 수 있는 조합은 3가지 밖에 없다.

    ```plaintext
    x[i]        | -           | x[i]
    -           | y[j]        | y[j]
    distance: 1 | distance: 1 | distance: 0 or 1
    ```

3. 그렇다면 우리는 하나의 사실을 알게 된다.

    $E(i,j)$는 다음 경우의 수 중 하나여야만 한다.

    - $E(i-1, j) + 1$
    - $E(i, j-1) + 1$
    - $E(i-1, j-1) + ((x[i] == y[j])\text{ ? 0 : 1} )$
4. 따라서, 다음과 같은 식을 유도할 수 있다.

    $E(i, j) =\min( \\
      \quad E(i-1, j) + 1, \\
      \quad E(i, j-1) + 1,  \\
      \quad E(i - 1, j-1) + ((x[i] == y[j])\text{ ? 0 : 1} )\\
    )$

만약, 각 연산의 비용이 다를 경우라면, 1 대신에 그 값을 넣어주면 충분히 풀 수 있으며, 추가적으로 최적의 이동형태를 알고 싶다면, back pointer 하나를 추가하는 것으로 충분하다.

## Reference

- Tumbnail : Photo by [David Ballew](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)


[NLP] 2. Text Processing

## Intro

Natural Language(자연어, 사람이 사용하는 통상 언어)를 input으로 활용하고자 하는 노력은 컴퓨터의 등장부터 시작하여 여러 번 시도되어 왔다. 지금까지도 완벽하게 이를 처리하는 것은 힘들다. 왜 Natural Language를 다루는 것은 어렵고, 이를 해결하기 위해서 NLP에서는 어떤 방식을 활용할지에 대한 개략적인 overview를 제시한다. 또한, Natural Language의 특성과 분석 단계를 이해하기 위해서 Linguistics(언어학)을 간략하게 정리한다.

## NLP

Natural Language Processing의 약자로 사람이 사용하는 언어를 input으로 하여 원하는 값을 추출해내는 것이 목표이다. 이를 위해서 우리는 사람의 언어를 이해하거나 다룰 수 있는 능력을 컴퓨터에게 부여해야 한다.

먼저, 이러한 필요가 있는 대표적인 usecase를 살펴보면 다음과 같다.

### Usecase

- **Spam Detection** 
 가장 간단한 예시로 mail에서 spam 여부를 확인하는 기능이다.
- **POS tagging / NER** 
 특정 단어 단위의 처리를 수행하게 되는데 단어의 품사와 대략적인 의미를 가진 category로 분류로 tagging하는 과정이다. 이를 기반으로 하여 다른 usecase에서 활용하는 경우가 많다. 품사와 category는 단어의 뜻을 추론하는데 큰 도움을 주며, 이것이 문장의 이해 등에 도움을 주기 때문이다.
- **Sentiment Analysis** 
 감정/여론 분석 등의 영역을 의미하며, 텍스트 또는 대화에서의 긍정/부정 여부를 판단하거나 평점 등을 추출하는 기능이다.
- **Conference Resolution** 
 "he", "she" 등 대명사, 생략 단어 등을 원래의 단어로 대체하거나 채우는 과정을 수행한다. 이 역시도 여러 영역에서 이를 기반으로 추가적인 작업을 할 수 있다. 
- **Word Sense Disambiguation(WSD)** 
 특정 단어가 주어졌을 때, 동의어, 동음이의어 등에서 가르키는 진짜 의미를 헷갈리지 않게 명확하게 다시 한 번 처리한다. 이 역시도 다른 NLP usecase에서 두루 사용된다.
- **Parsing** 
 문장에서 단어들을 의미를 가지는 단위(구, 절, 문장)로 다시 grouping한다. 이 과정을 잘 수행하기 위해서는 이전 단계에서 WSD와 Conference Resolution, POS tagging, NER이 이루어지면 좋다. 이 과정을 통해서 문장의 개략적인 의미를 파악할 수 있다.
- **Machine Translation(MT)** 
 특정 언어를 또 다른 Natural Language로 변경하는 기능이다.
- **Information Extraction(IE)** 
 특정 문장에서 사용자에게 의미있을만한 데이터를 추출하는 것이다.
- **Q&A** 
 특정 사용자가 질문을 하였을 때, 이 뜻을 이해하고, 이에 적절한 대답을 수행하는 방식이다.
- **Paraphrase** 
 문장의 뜻을 이해하고, 더 쉬운 형태의 표현으로 변환하는 기능이다.
- **Summarization** 
 여러 문장으로 이루어진 글의 의미를 이해하고, 적절한 내용으로 요약하는 기능이다.
- **Dialog** 
 Natural Language를 사용하는 사람과 1:1로 담화를 주고 받는 것이다. 의미를 이해할 뿐만 아니라 자신이 내보낼 output에 대해서도 적절하게 생성할 수 있는 능력이 필요하다.

위와 같이 많은 usecase가 있는데 이를 구현하는 것은 지금까지도 굉장히 challenge한 부분이다. 그것은 Natural Language가 가지는 몇몇 특징 때문이다.

### Why is NLP difficult?

여기서는 Natural Language 중에서 영어를 기반으로 한 설명이지만, 한국어도 매우 유사하다.

- **non-standard** : Natural Language를 사용하는 사람들이 표준을 항상 따르지는 않는다는 것이다. 우리는 약어를 사용하거나 문법에 맞지 않는 비문을 사용하여 의사소통을 하기 때문에 이것을 시스템이 이해하게 하는 것은 어렵다.
- **segmentation** issues : 의미를 가지는 단어 단위로 묶는 것이 어렵다는 것이다. 우리는 문장의 띄어쓰기를 어디로 받아들이냐에 따라서 의미가 달라지는 것을 본 경우가 있을 것이다.
- **idioms** : 관용구의 사용은 NLP에서 예외처리로 해주어야 하는 것이다. 단어 그대로의 의미와 다른 의미를 가지기 때문이다.
- **neologisms** : 신조어는 계속해서 생겨나기 때문에 이를 계속해서 업데이트 해주는 것도 부담이 된다.
- **world knowledge** : 사전 지식을 알고 있어야 이해할 수 있는 단어, 문장이 존재한다. 즉, 어떤 지식을 가지고 있느냐에 따라서 해석이 달라진다는 것이다.
- **tricky entity names** : 고유 명사 중에서 특히 contents(노래, 그림, 소설) 등의 제목이 해석 시에 헷갈리게 한다. 예를 들면, "Let it be"라는 비틀즈의 노래는 문장 중간에 들어가면, 하나의 문장으로 받아들여지게 되는데 이를 잘 해결할 수 있도록 해야 한다.

위의 내용을 요약하자면, 다양한 단어가 다양한 현상과 다양한 법칙(Grammer)의 영향을 받기에 어려우며, 단어가 가지는 모호성이 문제를 야기한다는 것이다.

### Solutions

이러한 문제를 해결하기 위해서 크게 두 가지 방식을 사용할 수 있다.

- Rule based approach 
 Gammer와 같은 법칙을 모두 적용해서 prgoramming을 하는 것이다. 하지만, 이 방식은 비문과 같은 문장을 제대로 처리할 수 없을 뿐만 아니라 정확한 형태의 문장이라도 여러 의미로 해석되는 문장에서 경향성과 문맥을 전혀 파악할 수 없다.
- Statistic based approach 
 그래서 최근에는 경향성과 문맥을 파악할 수 있도록 AI 기술, ML, Deep Learning을 이용하여 NLP를 수행하는 것이 하나의 trend로 자리 잡았다. 그렇다면, 어떻게 통계적인 접근법이 경향성과 문맥을 포함할 수 있을까? 이는 통계가 가지는 경향성이라는 특징과 conditional probability를 사용할 때의 문맥을 포함한 경향성을 파악할 수 있다는 점을 활용해서 가능하다.

## Linguistics

결국 앞으로 통계적인 방식을 활용하더라도 우리는 최소한의 언어학적인 기본이 필요하다. 왜냐하면, 통계에 사용할 데이터를 처리하기 위해서이다. 우리가 사용할 데이터는 text 또는 음성이다. 이를 적절하게 처리하여 통계에 사용할 유의미한 데이터로 변환하는 과정이 필요하다. 이를 위해서 언어학에 대한 이해가 필요한 것이다.

일반적으로 언어를 분석할 때, 사용할 수 있는 도구는 **Grammar**이다. 이는 특정 language에서 허용되는 규칙의 집합을 정리한 것이다. 이것의 종류는 크게 두 가지로 나뉜다.

- **Classic Grammar** 
 사람이 실제로 언어를 사용함에 있어 발생하는 이상한 습관과 같은 언어 표현이다. 이러한 법칙들은 대게 예제들을 통해서 정의되는데 이런 것을 명확하게 구분할 수 있는 명백한 도구가 존재하지는 않는다. 예를 들면, 감탄사와 같은 것들이 여기에 포함되겠다. 이는 이러한 변칙적인 형태 때문에 programming적으로 표현하는 것이 불가능하다.
- **Explicit Grammar** 
 명백하게 정의되어 있는 언어 규칙을 의미한다. 이는 Programm으로 구현할 수 있으며, 여러 Grammar 정리 내용이 이미 정리되어 있다. (CFG, LFG, GPSG, HPSG, ....) 
 이를 문법적으로 분석하기 위해서 우리는 6단계의 순차적인 처리가 필요하다.

### 6 Layers in Language

각 단계는 input과 output을 가진다. 단계적으로 진행되기 때문에 이전 단계의 output이 다음 단계의 input이 되며, 때때로 몇 단계는 생략될 수 있기에 유연하게 생각하도록 하자.

각 단계에서 실제로 특정 문장이 처리되는 과정을 이해하기 위해서 "Astronomers saw stars with telescope"라는 문장이 음성 또는 text로 들어왔을 때를 가정하여 각 단계에는 무엇을 하고 이를 통해서 어떻게 이 문장을 바꿀 수 있는지를 확인해보겠다.

> **1. Phonetics/Orthography(음성학/맞춤법)**

먼저 Orthography는 맞춤법 검사를 의미하며, character sequence로 input이 들어오면, 이를 맞춤법에 맞는지를 확인하여 이것이 수정된 sequence로 반환한다. 
예시 문장에 있는 "telescope"는 문법에 맞지 않으므로 "telescopes"로 바뀌어야 한다.

| input | output |
| :------------------------------------ | :------------------------------------- |
| Astronomers saw stars with telescope. | Astronomers saw stars with telescopes. |

Phonetics는 음성학을 의미하며, 혀와 음성의 영향을 주는 다양한 근육의 위치 형태, 모양, 빈도를 활용하여 자음과 모음을 분류하는 작업을 수행한다. Orthoography와는 달리 억양이라는 것을 추가적으로 활용할 수 있다.

| input | output |
| :---------------------------------------------------------- | :------------------------------------- |
| Astronomers saw stars with telescopes.를 의미하는 음성 신호 | əsˈtrɒnəməz sɔː stɑːz wɪð ˈtɛlɪskəʊps. |

*<https://tophonetics.com/> 을 통해서 변환하여 얻을 수 있다.

> **2. Phonology/Lexicalization(음운론/어휘화)**

Phonology은 음운론으로 소리와 phonemes(음소)사이의 관계를 이용하여, 음소를 특정 word로 변환하고, Lexicalization에서는 해당 단어를 사전에서의 형태로 변환하는 과정을 수행한다.

| input | output |
| :------------------------------------- | :------------------------------------- |
| əsˈtrɒnəməz sɔː stɑːz wɪð ˈtɛlɪskəʊps. | Astronomers saw stars with telescopes. |

> **3. Morphology(어형론)**

Morphology는 어형론으로 음소의 구성을 기본형(lemma)의 형태로 변환하며, 각 단어들을 형태학적인 의미를 갖는 카테고리(category, tag)로 분류한다.
여기서 사용되는 lemma와 category가 무엇인지 좀 더 자세히 살펴보자.

- **lemma** 
 - 사전에 표기되는 단어의 기본형으로, 사전에서 word를 찾는 pointer가 된다. 
 - 동음이의어의 경우 특정 뜻을 지칭하고 싶은 경우에는 numbering을 수행하기도 한다.
 - 더 나아가서는 형태소(morpeheme)까지 구분하기도 한다. 이는 혼자서 쓰일 수 있는 자립 형태소(root)와 의존 형태소(stem)으로 나눌 수 있다. 
 - 예를 들면, quotations -> quote[root] + -ation[stem] + -s[stem]
 - 위와 같은 형태로 세분화할 수도 있지만, 대게는 lemma 단위에서 그친다.
- **categorizing** 
 - category는 정하기 나름이며, 이미 정해져있는 tagset들도(Brown, Penn, Multext) 많이 존재하고, 억양이나 실제 분류 등을 수행하는 것도 가능하다.
 - **POS tagging**은 category를 분류하는 방법 중에서 가장 유명한데, 이는 여러 언어에서 거의 호환되기 때문에 이 방식을 활용하여 분석하는 것이 가장 안정적인 방법이라고 할 수 있다. 이는 별도의 Posting에서 더 자세히 다루도록 하겠다.

또한, 단어의 형태는 언어마다 다양하기 때문에 어느정도 언어마다 다른 작업을 해주어야 한다. 크게 구분되는 형태로 언어를 3개의 종류로 나눌 수 있다.

1. **Analytical Language(고립어)** 
 하나의 단어가 대게 하나의 morpheme을 가진다. 따라서, 하나 이상의 category로 구분되어질 수 있다. 
 ex. English, Chinese, Italian
2. **Inflective Fusional Language(굴절어)** 
 prefix/suffix/infix가 모두 morpheme에 영향을 미치며, morpheme의 정의 자체가 애매해지는 언어 형태 
 ex. Czech, Russian, Polish, ...
3. **Agglutinative Language(교착어)** 
 하나의 단어에는 morpheme이 명확하게 구분되고, prefix/suffix/infix 또한 명확하게 구분 가능하다. 따라서, 각 morpheme에 명확한 category를 mapping하는 것이 가능하다. 
 ex. Korean, ...

| input | output(based on Brown tagset) |
| :------------------------------------- | :-------------------------------------------------------------------- |
| Astronomers saw stars with telescopes. | (astronomer/NNS) (see/VBD) (star/NNS) (with/IN) (telescope/NNS) (./.) |

> **4. Syntax(통사론)**

lemma나 morpheme을 구문의 요소인 S(Subject, 주어), V(Verb, 동사), O(Object, 목적어)와 같은 요소로 분류한다. 이 분류를 수행할 때에는 문장의 구성요소를 알아야 한다. 이를 bottom-up으로 살펴보자.

- **Word(단어)** 
 사전에 명시된 하나의 단위라고 볼 수 있다. 이는 관용어(dark horse)를 포함한다.
- **Phrase(구)** 
 둘 이상의 단어 또는 구의 결합으로 만들어진다. 대게 하나의 문법적인 의미로 변환되어진다. 
 - 대표적인 예시
 - Noun : a new book
 - Adjective : brand new
 - Adverbial : so much
 - Prepositional : in a class
 - Verb : catch a ball
 - **Elipse(생략)** 
 대게 단어 또는 구가 생략되는 경우가 많다. 특히 담화의 경우 더욱 그렇다. 
 이를 추론을 통해서 추가할 수도 있다.
- **Clause(절)** 
 절은 주어와 서술어를 갖춘 하나의 문장과 유사하지만, 문장 요소로서 더 상위 문장에 속하는 경우이다. 
 또한, 영어에서는 특히 접속사로 연결된 절이 아닌 경우에는 해당 절이 지칭하는 대상이 절 내부에서 생략된다. 이를 gap이라고 한다.
- **Sentense** 
 하나 이상의 절로 이루어지고, 영어에서는 시작 시에 대문자로 표기하며 종료 시에는 구분자로 .?!로 끝난다.

결국 우리는 이러한 요소를 적절하게 표시해야 하는데, 이를 위해서 tree 구조를 사용하는 것이 일반적이다. 대표적으로 두 가지의 구조가 있다.

1. **phrase structure(derivation tree)**
 문장을 기점으로 절, 구, 단어로 top-down으로 내려가는 구조를 가진다. 
 각 단위를 묶을 때에는 ()를 이용하고, 그 뒤애 해당하는 내용이 무슨 구, 절인지를 표기한다.
2. **dependency structure** 
 단어 간의 관계에 더 집중하여 나타낸다. 따라서, 사람이 보기에는 불명확해 보일 수 있지만 특정 usecase에서는 유용하다.

| input | output (phrase structure) |
| :-------------------------------------------------------------------- | :------------------------------------------------------------------------------------- |
| (astronomer/NNS) (see/VBD) (star/NNS) (with/IN) (telescope/NNS) (./.) | ((astronomer/NNS)NP ((see/VBD)V ((star/NNS)NP ((with/IN)P (telescope/NNS)NP)PP)NP)VP)S |

![nlp-phase-structure](/images/nlp-phase-structure.jpg)

> **5. Semantics(Meaning, 의미론)**

간단하게는 주어, 목적어와 같은 tag나 "Agent"나 "Effect"와 같은 tag를 적용하며, 전체적인 의미를 유추해낸다.

| input | output |
| :------------------------------------------------------------------------------------- | :---------------------------------------------------------------------------------------------------- |
| ((astronomer/NNS)NP ((see/VBD)V ((star/NNS)NP ((with/IN)P (telescope/NNS)NP)PP)NP)VP)S | ((astronomer/NNS)NP/agent ((see/VBD)V ((star/NNS)NP/affected ((with/IN)P (telescope/NNS)NP)PP)NP)VP)S |

> **6. Discourse/Pragmatics(담화/화용론)**

실제 대화 등과 같은 목표를 해결하기 위해서 앞서 보았던 문장 구조를 이용한다.

만약, 해당 데이터를 통해서 하고자 하는 것이 이 이야기를 한 사람이 식당 내부에 있는지를 판단하고자 한다고 가정해보자.

| input | output |
| :---------------------------------------------------------------------------------------------------- | :----- |
| ((astronomer/NNS)NP/agent ((see/VBD)V ((star/NNS)NP/affected ((with/IN)P (telescope/NNS)NP)PP)NP)VP)S | False |

## Reference

- Tumbnail : Photo by [David Ballew](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](https://unsplash.com/@daveballew?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)
- text to phonetic converter, <https://tophonetics.com>