
## 분석 단계

![231209-224151](/posts/final_05/231209-224151.png)

### 형태소 분석

입력된 문자열을 분석하여 형태소 단위로 분석합니다.
형태소 분석은 다음과 같은 목적 활용될 수 있습니다.

- 맞춤법, 철자 교정
- 단어의 품사 분석
- 단어의 의미 추정
- 검색엔진 색인 구성

형태소를 분석하고 나서는 품사를 태깅합니다.
태깅을 할 때는 문장의 구성 원리 등을 이용한 규칙 기반 태깅 방법과, 기계학습 기반 태깅이나, 통계적 기계학습 알고리즘을 사용할 수 있습니다.

이후에는 개체명을 인식합니다.
정보를 검색하거나, 질의응답에서 중요한 역할을 하는 고유명사와 같은 개체명을 인식하는 겁니다.
인명, 지명, 시간, 날짜, 화폐 등이 이에 해당합니다.
개체명을 인식할 때는 사전을 사용하거나, 규칙을 만들거나, 기계학습 기반의 분류기를 사용합니다.

### 구문 분석

구문에 따라 주어진 문장에서 단어들의 역할을 파악하여 문장을 계층적인 트리 구조로 변환하는 작업입니다.
이 역시 규칙 기반 구문 분석방법과 기계학습 기반 구문 분석방법이 있습니다.

하지만, 구문 분석시에는 아래와 같은 문제점이 있을 수 있습니다.

- 구조적 중의성
  하나의 문장이 다수의 구조로 해석될 수 있음.
- 어휘적 중의성
  하나의 단어가 여러 품사로 사용될 때, 다수의 구조로 해석될 수 있음.

규칙 기반 구분 분석에서는 파싱 방식을 자주 사용하는데, 파싱 방식에는 아래와 같은 방식이 있습니다.

- 확장 전이망 기반 파싱
- 차트 파싱 (CKY 파싱 알고리즘)

기계학습 기반 구문 분석에서는 아래와 같은 모델이 사용됩니다.

- SVM
- 조건부 랜덤 필드(CRF) 모델
- 딥러닝 신경망

### 의미 분석

형태소, 구분 분석 결과를 해석하여 문장이 가진 의미를 파악합니다.
이를 위해 담화가 이루어지는 상황에 대한 world model과 상식에 대한 지식이 필요합니다.

이를 위해 단어를 수치화 해야 하는데, ont-hot vector 또는 Word2Vec(word embedding)을 사용합니다.
두 방식 모두 단어를 좌표상에 하나의 위치벡터로 수치화 합니다.

- one-hot vector
  단어 위치에만 1, 나머지는 0으로 설정된 벡터입니다.
  학습에는 편리하지만, 이 방식은 단어간의 유사도를 계산하기가 어렵습니다.

- Word2Vec
  단어의 의미를 충분히 잘 나타내도록 단어를 공간상의 실수 벡터로 표현합니다.
  유사한 의미의 단어는 좌표공간 상에서 근처에 위치하게 되기 때문에 유사도를 판단할 때 유용합니다.

이렇게 단어를 벡터화(수치화) 하고나면, 단어를 유의미하게 배치하기 위한 모델을 구성해야 합니다.
one-hot vector로 수치화된 단어는 아래와 같은 모델에서 사용됩니다.

- CBOW

    ![231209-230325](/posts/final_05/231209-230325.png)
    Continuous Bag-of-Words 모델은 V차원의 one-hot 벡터로 표현된 단어를 N차원의 실수 벡터로 바꾸는 역할을 수행합니다.
    입력에 주변 단어들이 주어질 때, 출력에서 해당 단어가 나타날 확률이 높아지도록 학습합니다.
    e.g. 빈칸 채우기

- Skip-gram

    ![231209-230425](/posts/final_05/231209-230425.png)
    CBOW 모델과 대칭적인 구조를 갖습니다.
    입력에 학습 대상이 되는 단어가 주어질 때, 출력에서 해당 단어의 주위 단어들이 나타날 확률이 높아지도록 학습합니다.
    e.g. 문장 생성

Word2Vec로 수치화된 단어는 아래와 같은 분야에서 사용됩니다.

- 유의어, 어근 비교, 시제 등 한 정보 추출 또는 분석
- 품사 태깅, 의미 분석, 관계 추출, 단위 의미 식별 등
- 기계 번역, 영상 주석달기 등

자연어 처리의 과정에 대해 간략히 알아봅니다.

자연어 처리

## Tensor

텐서플로우에서 사용하는 기본 자료형으로 다차원 배열이다.
텐서는 rank, shape, type의 세가지 속성을 갖는다.

- rank

 ![231209-201955](/posts/final_04/231209-201955.png)
 텐서의 차원수로 rank k는 k차원 배열이다.

- shape

 ![231209-202047](/posts/final_04/231209-202047.png)
 텐서의 구조로, 각 축에 텐서의 원소 개수를 알려준다.

- type
 텐서의 구성원소의 자료형을 알려준다.

<tip>
 `축(axis)`
 
 대괄호의 가장 바깥부터 0, 1, 2 축이 된다.
</tip>

## Flow

텐서를 데이터 플로우 그래프를 이용하여 계산 과정과 모델을 표현하게 된다.

- Op(eration)
 하나 이상의 텐서를 받아 계산을 수행하고 결과를 하나 이상의 텐서로 변환

- Session
 그래프를 실행하기 위한 객체(세션)

- Variables

 그래프 실행 시 파라미터를 저장하고 갱신하기 위해 사용
 ```python:.py
 W = tf.Variable(tf.randon_normal([4, 1]), name="weight")
 b = tf.Variable(tf.randon_normal([1]), name="bias")
 ```

- Placeholder

 데이터 플로우 그래프 실행 시 데이터(텐서)를 전달하기 위해 사용
 ```python:.py
 x = tf.placeholder(tf.float32)
 y = tf.placeholder(tf.float32)
 z = tf.multiply(x, y)
 sess.run(z, feed_dict=[x: 3, y: 4])
 ```

---

## 텐서 변환 연산

### reshape

텐서의 원소를 새로운 shape에 맞게 배치합니다.

> a = [[[1,2,3,4], [5,6,7,8]], [[9,10,11,12], [13, 14, 15, 16]], [[17,18,19,20], [21,22,23,24]]]
> tf.shape(a) &rarr; [3, 2, 4]
> tf.reshpae(a, [3, 8])
> &rarr; [[1,2,3,4,5,6,7,8], [9,10,11,12,13,14,15,16], [17,18,19,20,21,22,23,24]]

### squeeze

텐서에서 크기가 1인 축을 제거합니다.

> a = [**[**[1,2]**]**, **[**[3,4]**]**, **[**[5,6]**]**]
> tf.shape(a) &rarr; [3, 1, 2]
> tf.squeeze(a)
> &rarr; [[1,2], [3,4], [5,6]]

### expand_dims

지정한 축 위치에 차원을 하나 추가합니다.

> tf.expands_dims([[1,2,3], [4,5,6]], 0)
> &rarr; **[**[[1,2,3], [4,5,6]]**]**
> tf.expands_dims([[1,2,3], [4,5,6]], 1)
> &rarr; [**[**[1,2,3]**]**, **[**[4,5,6]**]**]

### slice

텐서에서 일부분을 선택합니다.
**slice(텐서, [축i 시작위치], [축i의 추출길이])**

> a = [[1,2,3,4,5,6,7], [8,9,10,11,12,13,14], [15,16,17,18,19,20,21]]
> tf.slice(a, [0,2], [2,3])
> &rarr; [[3,4,5], [10,11,12]]

### split

지정된 축을 분할개수로 분리합니다.
**spilt(텐서, 분할개수, 축)**

> a = [[1,2,3,4], [5,6,7,8], [9,10,11,12], [13,14,15,16]]
> tf.split(a, 2, 0)
> &rarr; [[[1,2,3,4], [5,6,7,8]], [[9,10,11,12], [13,14,15,16]]]
> tf.split(a, 2, 1)
> &rarr; [[[1,2], [5,6], [9,10], [13,14]], [[3,4], [7,8], [11,12], [15,16]]]

### concat

지정된 축 방향으로 두 텐서를 이어 붙힙니다.

> a = [[1,2], [3,4]]
> b = [[5,6], [7,8]]
> tf.concat([a, b], 0)
> &rarr; [[1,2], [3,4], [5,6], [7,8]]
> tf.concat([a, b], 1)
> &rarr; [[1,2,5,6], [3,4,7,8]]

### reverse

지정된 축을 기준으로 원소를 역순으로 배열합니다.

> a = [[1,2,3], [4,5,6]]
> tf.reverse(a, [0])
> &rarr; [[4,5,6], [1,2,3]]
> tf.reverse(a, [1])
> &rarr; [[3,2,1], [6,5,4]]
> tf.reverse(a, [0, 1])
> &rarr; [[6,5,4], [3,2,1]]

### transpose

지정된 축의 순서로 텐서를 transpose 합니다.
**transpose(텐서, perm=[축])**
(perm을 지정 안하면 [0, 1] 로 간주함)

> a = [[1,2,3], [4,5,6]]
> tf.transpose(a)
> &rarr; [[1,4], [2,5], [3,6]]
> b = [[[1,2,3], [4,5,6]], [[7,8,9], [10,11,12]]]
> tf.transpose(b, [0,2,1])
> &rarr; [[[1,4], [2,5], [3,6]], [[7,10], [8,11], [9,12]]]

### gather

지정된 index의 원소들로 이루어진 텐서를 생성합니다.
**gather(텐서, [index])**

> tf.gather([1,3,5,7,9,0,2,4,6,8], [2,5,2,5])
> &rarr; [5,0,5,0]
> tf.gather([[1,2,3,4,5,6], [7,8,9,10,11,12]], [0,1])
> &rarr; [[1,2,3,4,5,6], [7,8,9,10,11,12]]
> tf.gather([[1,2,3,4,5,6], [7,8,9,10,11,12]], [[0,0], [1,1]])
> &rarr; [[[1,2,3,4,5,6], [1,2,3,4,5,6]], [[7,8,9,10,11,12], [7,8,9,10,11,12]]]

### ont_hot

정수값을 one-hot 벡터로 변환합니다.

> tf.ont_hot([0,1,2], depth=3)
> [[1.0, 0.0, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, 1.0]]
> tf.ont_hot([0,1,2], depth=4)
> [[1.0, 0.0, 0.0, 0.0], [0.0, 1.0, 0.0, 0.0], [0.0, 0.0, 1.0, 0.0]]

---

## 기타

### 텐서 축약 연산

![231209-222217](/posts/final_04/231209-222217.png)

### 텐서 행렬 연산

![231209-222315](/posts/final_04/231209-222315.png)

딥러닝 프레임워크 텐서플로우에 대해 알아봅니다.

TensorFlow

## 딥러닝

일반적인 다수의 퍼셉트론을 이용해서 은닉층을 여럿 두었던 기존 신경망과 거의 유사하지만, 그 은닉층의 개수가 엄청 많은 신경망을 딥러닝 신경망이라고 합니다.

원시 신경망은 은닉층의 개수가 적었기에, 사람이 직접 특징을 추출해서 만든 특징 벡터를 이용해 학습을 시켰던 것에 반해,
딥러닝 신경망은 데이터 그 자체를 입력으로 주고, 특징 추출과 학습을 함께 수행할 수 있습니다.
즉, 스스로 데이터로부터 유의미한 특징을 추출하고 학습하기 때문에 성능이 우수합니다.

### 기울기 소멸 문제

단, 딥러닝시 문제가 있습니다.
컴퓨팅 파워가 많이 필요하단 것은 둘 째 치고, 학습하는 과정에서 역전파를 할 때, 역전파 하는 과정에서 전파될수록 기울기(gradient)가 점점 줄어들다가 소멸하는 문제가 있습니다.

기울기 소멸 문제가 발생하는 이유는 sigmoid, typertangent와 같은 활성함수를 사용하기 때문에 발생하는 것인데, 이런 활성함수의 특징이 있습니다.
바로, 0에서 멀어질수록 도함수(기울기)의 값이 0에 가까워진다는 점입니다.

따라서 아무리 멀어져도 기울기가 0으로 수렴하지 않도록 ReLU 함수나 ReLU 파생 함수를 사용하곤 합니다.

![231209-165142](/posts/final_03/231209-165142.png)

### 가중치 초기화 문제

신경망을 학습하는 과정에서 경사하강법을 사용한다고 했었는데, 경사하강법의 문제가 있습니다.
바로 국소 최적해에 빠질 수 있다는 것입니다.
gradient의 반대 방향으로 이동하는 과정에서 더이상 움직이지 않는 지점까지 내려왔는데, 알고보니 그 지점보다 더 낮은 지점이 존재하는 것이죠.

즉, 학습에 있어, 초기에 가중치를 어떻게 초기화하느냐에 따라 학습 방향이 변하게 될 수 있다는 뜻입니다.

보통은 초기값으로 0에 가까운 무작위 값을 넣곤하는데, 균등 분포, Xavier 초기화, He 초기화 방법 등이 있습니다.

### 과적합 문제

학습을 너무 완벽하게 시켜도 문제입니다.

![231209-170008](/posts/final_03/231209-170008.png)

해당 모델은 학습 데이터를 완벽하게 분류할 수 있을 뿐, 테스트데이터에 대해서는 좋지 못한 성능을 보일 수 있기 때문입니다.

따라서 여러 과적합 완화 기법이 있습니다.

- 규제화 기법

 오차함수에 error 뿐 만 아니라 모델 복잡도도 평가요소로 사용하는 방법입니다.

 **오차함수 = 오차 항 + $\alpha$ 모델 복잡도 항**

 모델 복잡도는 가중치(weight)를 이용하여 정의할 수 있으며 아래와 같이 사용할 수 있습니다.

 - L1-norm: $\sum_{i=1}^{n}|w_i|$
 - L2-norm: $\sum_{i=1}^{n}w_i^2$

- 드롭아웃 기법

 일정 확률로 노드들을 무작위로 선택해 선택된 노드 앞뒤로 연결된 가중치 연결선은 없는 것으로 간주하고 학습하는 기법입니다.

 ![231209-170524](/posts/final_03/231209-170524.png)

 미니배치(mini-batch)나 학습주기(epoch)마다 드롭아웃할 노드를 선택하는데, 모든 노드는 한 번 이상은 특정 주기에 속해 학습되어야 합니다.

 <tip>
 `미니배치(mini-batch)`
 
 전체 학습 데이터를 일정 크기의 데이터로 나누어 놓은 것으로, 학습 데이터가 큰 경우에 사용하는 것이 좋습니다.
 단, 그레디언트를 계산할 때는 매 데이터마나 역전파해서 업데이트 하는 것이 아닌, 일정 수 이상의 데이터가 들어올 때 마다 평균을 계산해서 한 번에 업데이트 해야합니다.
 
 미니배치의 장점은 데이터에 포함된 오류에 대해 둔감하게 학습할 수 있기에 과적함 문제 완화에 도움이 됩니다.
 </tip>
 
- 배치 정규화

 신경망의 각 층에서 미니배치의 각 데이터의 가중치 연산 결과의 분포를 정규화 하는 것으로, 간단하게 말하면 출력을 \[-1, 1\] 범위로 스케일링 하는 것입니다.

 이게 도움이 되는 이유는 내부 공변량 이동 문제를 완화할 수 있기 때문인데요, 간단하게 설명하면 학습에 따라 가중치가 변하면 같은 학습 데이터에 대해 출력이 변하는 문제입니다.

 하지만, 배치 정규화를 통해 출력을 정규화하면 같은 학습 데이터에 대해 시차가 있더라도 비슷한 출력을 내보낼 수 있게 되어 학습 효율이 올라갑니다.

 ![231209-171350](/posts/final_03/231209-171350.png)

 연산 결과를 활성화 함수에 통과시키기 전에 배치 정규화 블록을 삽입하여 구현합니다.

---

## 컨볼루전 신경망 (CNN)

Convolution이란, 신경망에 컨볼루전을 처리하는 층이 추가된 딥러닝 신경망으로, 해당 컨볼루턴 층에서는 색상, 밝기, 에지 등등 특정 영역에 대한 특징을 추출하는 역할을 진행합니다.
(컴퓨터 비전의 그 컨볼루전임)

![231209-171707](/posts/final_03/231209-171707.png)

이런 컨볼루전은 여러개 두어 각 영역 특징들을 추출하고, 해당 특징을 이용해 딥러닝 신경망의 새로운 입력으로 사용해 의미있는 정보로 변환되게 됩니다.

### 컨볼루전

![231209-171759](/posts/final_03/231209-171759.png)

컴퓨터 비전과 비슷하게 일정 영역의 값에 가중치를 적용하여 하나의 값을 얻는 과정입니다.
단, 여기에 threshold에 해당하는 bias 도 더해진다는 차이점이 있습니다.

$$
y_{11} = w_{11}x_{11} + w_{12}x_{12} + ... + w_{33}x_{33} + w_0 (bias)
$$


![231209-172107](/posts/final_03/231209-172107.png)

컨볼루전시 padding과 stride 요소에 따라 연산이 조금 달라지게 되는데요,
피연산 배열을 확장하는 것을 padding, 커널의 이동거리를 stride라고 합니다.

### 특징지도

컨볼루전 필터의 적용 결과로 만들어지는 2차원 행렬(N차원 배열)을 feature map 이라고 합니다.
단순히 컨볼루전의 연산 결과라고 생각해도 됩니다.

![231209-172428](/posts/final_03/231209-172428.png)

k개의 커널을 컨볼루전하면 k개의 2차원 특징지도가 만들어집니다.
커널은 RGB, 모서리, 경계선, 주파수 등등 필요한 정보를 추출할 수 있는 커널을 사용할 수 있습니다.

### 풀링

일정 크기의 블록을 통합하여 하나의 대푯값으로 대체하는 연산을 pooling 이라고 합니다.
특징지도의 크기를 축소함으로서 다음 단계에서 사용할 메모리 크기와 연산량을 감소하는데 사용되며,
특정 영역내의 특징을 결합하거나, 위치변화에 둔감한 특정을 선택하는 효과를 얻을 수 있습니다.

풀링 방식의 종류에 대해 알아봅시다.

- 최댓값 풀링

 ![231209-172746](/posts/final_03/231209-172746.png)

 지정된 블록 내의 원소 중에서 최대값을 대푯값으로 선택하는 풀링입니다.

- 평균값 풀링

 ![231209-172815](/posts/final_03/231209-172815.png)

 지정된 블록 내의 원소의 평균값을 대푯값으로 선택하는 풀링입니다.

- 확률적 풀링

 ![231209-172848](/posts/final_03/231209-172848.png)

 지정된 블록 내의 원소의 값의 크기에 비례하는 확률로 선택하는 풀링힙니다.
 **학습시에는 확률적으로 학습**하기에 랜덤성이 부여되는 장점이 있고,
 **추론시에는 확률에 가중치를 둔 평균**으로 구하는 방식으로 동작합니다.

### CNN 구조

특징을 추출하는 컨볼루전 부분과 추출된 특징을 사용하여 분류, 회귀하는 다층 퍼셉트론 부분으로 구분됩니다.

컨볼루전 부분은 보통 아래의 층드로 구성된 블록들을 여럿 반복하여 배치합니다.

- Conv: 컨볼루전 연산
- ReLU: 활성화 함수
- Pool: 풀링

ReLU, Pool은 둘 다 쓰거나 둘 중 하나만 사용할 수도 있습니다.

다층 퍼셉트론 부분은 전 방향 연결되어있기에 FC(Fully Connected) 로 표현하며, 마지막 층은 출력을 정규화하기 위해 SM(SoftMax) 층을 둡니다.

이에 대한 예시는 다음과 같습니다.

![231209-173733](/posts/final_03/231209-173733.png)
![231209-173744](/posts/final_03/231209-173744.png)

Pool을 제외하고는 가중치 연산이 필요합니다.
노드는 Conv에서 많은 경향이 있고, 가중치는 FC에서 많은 경향이 있습니다.

### CNN 학습

CNN의 학습 방법은 여러 방법이 있지만, 제가 수식을 이해못한 관계로(...) 종류와 특징만 기술하도록 하겠습니다.

- 경사 하강법
 그레디언트의 반대방향으로 학습률($\eta$) 만큼의 보폭으로 이동하는 방식입니다.

- 모멘텀을 고려한 경사 하강법

 ![231209-174536](/posts/final_03/231209-174536.png)

 이전 그레디언트의 누적값을 반영하여 이동하는 방식입니다.

- NAG

 ![231209-174626](/posts/final_03/231209-174626.png)

 직전 모멘텀으로 이동한 위치에서의 그레디언트로 이동하는 방식입니다.
 
- AdaGrad
 가중치별로 별도의 학습률($\eta$)을 적용하는 방식입니다.
 예로 들어 x축보다 y축의 움직임이 크다면, y축에는 낮은 학습률을 적용하는 방식입니다.

- AdaDelta
 AdaGrad의 변형으로 과거 그레디언트의 영향을 점점 줄이는 방식입니다.

- RMSprop

- ADAM (best?)

---

## CNN 모델 종류

전부 깊이 다뤄보지는 않고, ILSVRC 대회에서 좋은 성적을 거둔 모델 중 새로운 방식을 적용한 사례에 대해서만 알아봅시다.

### LeNet

![231209-175915](/posts/final_03/231209-175915.png)

- 대회에서 최초로 컨볼루전을 사용

### AlexNet

![231209-175924](/posts/final_03/231209-175924.png)

- 대회에서 최초로 ReLU 함수를 사용
- FC층에 드롭아웃 기법 적용
- 최댓값 풀링 사용

### VGGNet

![231209-175939](/posts/final_03/231209-175939.png)

- 모든 컨볼루전 층에서 3by3 필터를 사용

<tip>
 3by3을 2번 적용하면 5by5를 적용한 효과를 낼 수 있고, 3번 적용하면 7by7을 적용한 효과를 낼 수 있습니다.
 여기서 작은 필터를 여러번 사용하는게 큰 필터 한 번을 사용하는 것 보다 좋은 효과를 얻을 수 있었는데요,
 그 이유는 가중치 개수가 적어지는 효과도 있고, 컨볼루전만 하면 선형 변환이라 중간에 ReLU 같은 비선형 변환을 사용해야 하는데, ReLU를 많이 사용할수록 복잡한 결정 경계를 표현할 수 있게되기 때문입니다.
</tip>

### GoogleNet

![231209-175950](/posts/final_03/231209-175950.png)

- 인셉션 모듈 사용
- 1by1 컨볼루전 사용
- FC층 단 1개 사용
- 보조 분류기 사용해 기울기 소멸 문제 완화

<tip>
 `인셉션 모듈`
 
 ![231209-180142](/posts/final_03/231209-180142.png)
 특징을 동시에 추출할 수 있습니다.
</tip>

<tip>
 `1by1 컨볼루전`
 
 ![231209-180225](/posts/final_03/231209-180225.png)
 특징지도를 압축할 수 있습니다.
</tip>

### ResNet

![231209-180954](/posts/final_03/231209-180954.png)

- 잔차 모듈 사용

<tip>
 `잔차 모듈`
 
 ![231209-180447](/posts/final_03/231209-180447.png)
 입력값을 그대로 넘기는 과정이 추가된 모듈로 이를 이용하면 기울기 소멸 문제를 완화할 수 있습니다.
 뿐만 아니라, 작은 변화에도 민감하며, 다양한 경로를 통해 복합적인 특징을 추출할 수도 있습니다.
 
 ![231209-180724](/posts/final_03/231209-180724.png)
 즉, 여러 층이 연결된 효과를 볼 수 있습니다.
 때문에, 필요한 출력이 얻어지면 컨볼루전 층을 건너뛸 수도 있습니다.
</tip>

### DenseNet

![231209-180943](/posts/final_03/231209-180943.png)

앞 층에서 올 수 있는 지름길 연결구성 방식이기에 연산 방식이 ResNet과 좀 다릅니다.

- ResNet: Conv-배치정규화-ReLU
- DenseNet: 배치정규화-ReLU-Conv

따라서 이전 단계의 동일한 특징 정보가 진차모듈을 통해 각 단계에 전달되기 때문에 새로운 특징을 만드는데 소극적이었던 ResNet과 달리
새로운 특징이 추출될 가능성이 높아졌습니다.

![231209-181230](/posts/final_03/231209-181230.png)

또한, 전이층을 두어 층이 과도하게 늘어나는 현상을 예방하고 학습 효율을 높였습니다.

### DPN

ResNet + DenseNet 으로, DenseNet의 단점인 특징이 중복해서 추출될 수 있는 문제를 마이크로 블록을 사용하여 극복한 모델입니다.

딥러닝 및 CNN 방식의 종류와 모델들을 알아봅니다.

딥러닝 & CNN


## 퍼셉트론

![231209-160856](/posts/final_02/231209-160856.png)

인간의 신경세포를 모방한 신경망 모델에서 하나의 신경세포에 해당하는 뉴런 유닛입니다.
다른 퍼셉트론의 출력들을 입력으로 받아 하나의 출력을 생성하게 되는데요, 입력들의 합이 threshold를 넘으면 1, 아니면 0을 출력하게 됩니다.

$$
y = \left\{\begin{matrix}
0 \; otherwise \\
1 \; \sum_{i=1}^{d}w_ix_i > threshold
\end{matrix}\right.
$$

이 때, $\sum_{i=1}^{d}w_ix_i > threshold$ 부분을 아래와 같이 수정해봅시다.

$$
\sum_{i=1}^{d}w_ix_i - threshold> 0
$$

threshold를 마찬가지로 하나의 입력으로 생각할 수도 있을 것입니다.
즉, 가중치(w)가 1이고, 값(x)이 bias 라고 생각하면 아래와 같이 식이 정리됩니다.

$$
s = \sum_{i=1}^{d}w_ix_i + b = \sum_{i=0}^{d}w_ix_i
$$

이제 s의 값이 0보다 작으면 0을 출력하고, 0보다 크면 1을 출력하면 퍼셉트론 완성입니다.

퍼셉트론을 이용해서 OR 회로를 만들어봅시다.

![231209-161940](/posts/final_02/231209-161940.png)

그럼 AND 회로는 만들 수 있을까요?
bias(1)에 연결된 weight에 -0.5가 아닌 -1.5와 같은 값을 넣으면 만들 수 있습니다.

그렇다면 XOR 회로는 만들 수 있을까요?
위와 같이 퍼셉트론 1개만으로는 구현이 불가능합니다.
하나의 퍼셉트론은 선형 분리가능 문제만 해결할 수 있기 때문입니다.

XOR와 같은 선형 분리불가 문제는 2개 이상의 퍼셉트론으로 해결할 수 있습니다.

### 다층 퍼셉트론

여러 개의 퍼셉트론을 층 구조로 구성한 신경망 모델을 의미하며, 이를 이용하면 단일 퍼셉트론의 한계였던 선형 분리불가 문제도 해결할 수 있습니다.

다층 퍼셉트론을 이용해서 XOR 회로를 만들어봅시다.

![231209-162649](/posts/final_02/231209-162649.png)

### 학습

다층 퍼셉트론을 학습을 시킨다는 것은 입력-출력 학습데이터에 대해 출력값과 오파의 차이가 최소가 되도록 가중치(weight)를 조정하는 것을 의미합니다.

이를 위해 역전파 알고리즘을 사용하는데, 역전파 알고리즘은 미분을 사용합니다.
따라서 수식화된 퍼셉트론이 미분 가능해야 하는데, threshold(bias)보다 크다/작다로 1/0이 나뉘는 step 함수를 사용하는 경우에는 미분이 불가능합니다.

![231209-162951](/posts/final_02/231209-162951.png)

그렇기에 미분이 가능한 sigmoid 함수나 다른 함수를 사용하여 출력값을 결정합니다.

XOR와 같은 간단한 회로는 학습이 필요없이 바로 weight를 결정할 수 있지만, 사물 인식과 같이 상상할 수 없는 회로의 경우에는 퍼셉트론 층들을 많이 두고, 학습하는 방식으로 회로를 구성하게 됩니다.

![231209-163157](/posts/final_02/231209-163157.png)

n개의 은닉층을 둔 n+1층 퍼셉트론을 구성하면 복잡한 회로도 만들 수 있습니다.
단, weight을 계산하는 것은 사실상 불가능하기 때문에 학습이라는 이름의 노가다(?)를 통해 weight이 오류가 적어지는 방향으로 조정하는 것입니다.

학습 데이터의 입력은 $x_i$들의 벡터로 주어지고, 출력은 $y_i$의 벡터로 주어지는데, $y_i$ 중 하나만 1이고 나머지는 0인 ont-hot 벡터로 주어지는게 일반적입니다.

오류를 줄이는 방향으로 학습하기 위한 방식으로 최대경사법 또는 경사하강법이라는 태크닉이 사용됩니다.
원리만 설명하면, 각 스탭에서의 x, y 편미분을 구합니다(gradient).
그리고, gradient의 반대 방향으로 weight를 수정하면 에러가 작아지는 방식입니다.

### 기타

최종 출력시 모든 속성값에 대한 확률을 0~1로 표현하기 위해 마지막 층으로 소프트맥스 층을 두기도 합니다.
`소프트맥스 층`은 최종 출력을 분류 확률로 변환하는 층으로 모든 퍼셉트론 출력의 합이 1이 됩니다.

가중치를 사용하는 대신, 퍼셉트론이 기존 벡터와 입력 벡터의 유사도를 측정하는 방식인 `RBF망` 이라는 방식도 있습니다.

인공지능 신경망의 구조와 원리에 대해 알아봅니다.

신경망

## 결정 트리

의사결정 지식을 트리의 형태로 표현한 것으로, 구성요소는 다음과 같습니다.

| 구성요소 | 역할 |
|---|---|
| 내부노드 | 비교 속성 |
| 간선(edge) | 속성 값 |
| 단말노드 | 부류(class), 대표 값 |

이런 결정 트리를 학습하는 알고리즘의 종류에 대해 알아보도록 하겠습니다.

### 정보 이득(IG)

데이터로부터 결정 트리를 생성하는 알고리즘으로, 모든 데이터를 포함한 하나의 노드로 구성된 트리에서 시작하여, 반복적인 노드 분할 과정을 거치며 서브 트리를 만들어갑니다.

트리는 간단하게 표현될수록(depth가 낮을수록) 좋은데, 이를 달성하기 위해서는 **분류력이 높은$^*$** 속성을 상위 노드에 배치하는 것이 좋습니다.
($^*$분류력이 높다: 분류된 결과들이 비슷한 부류일수록 분류력이 높음)

이 때, 분할 속성을 결정할 때, 분류력이 높음을 수치화할 수 있을까요?
이 척도로 엔트로피 개념이 사용됩니다.

엔트로피는 비동질(불순도) 정도의 척도로, 클수록 비동질적이라는 뜻입니다.
즉, 엔트로피가 작을수록 동질성이 크다는 의미인데, 정보량 측정 목적의 척도로 사용됩니다.

정보량(I) 및 정보 이득(IG)은 아래와 같이 수식화 할 수 있으며, 정보 이득이 클수록 엔트로피의 차이가 크다는 뜻이고, 이는 우수한 분할 속성으로 분할되었다는 의미입니다.

$$
I = -\sum_{c}p(c)log_2p(c) \\
I_{res} = -\sum_{v}p(v) \sum_{c}p(c|v)log_2p(c|v) \\
IG = I - I_{res}(A)
$$

여기서 **p는 부류별 확률**이고, 위 수식을 해석하면 다음과 같습니다.
부모 엔트로피가 $I$이고, 자식 트리의 엔트로피 가중 평균이 $I_{res}$일 때, 그 차이가 커야 부모 노드(속성)을 잘 선택해서 분류했다는 뜻입니다.

예를 들어 이해해봅시다.

![231208-220043](/posts/final_01/231208-220043.png)

이런 데이터를 분류한다고 가정해봅시다.
이 때의 I는 아래와 같이 계산할 수 있습니다.

$$
I = - \frac{5}{14}log_2\frac{5}{14} - \frac{9}{14}log_2\frac{9}{14} = 0.940
$$

- Case 1: Pattern으로 분류

 ![231208-220649](/posts/final_01/231208-220649.png)

 Pattern이 수평, 대각선, 수직인지에 따라 분류할 경우 $I_{res}$를 계산해봅시다.

 $$
 I_{horizontal} = - \frac{2}{5}log_2\frac{2}{5} - \frac{3}{5}log_2\frac{3}{5} = 0.971 \\
 {}\\
 I_{digonal} = - \frac{0}{4}log_2\frac{0}{4} - \frac{4}{4}log_2\frac{4}{4} = 0 \\
 {}\\
 I_{vertical} = - \frac{3}{5}log_2\frac{3}{5} - \frac{2}{5}log_2\frac{2}{5} = 0.971 \\
 {}\\
 I_{res}(Pattern) = \frac{5}{14} \cdot 0.971 + \frac{4}{14} \cdot 0 + \frac{5}{14} \cdot 0.971 = 0.694
 $$

 즉, 분류 기준이 Pattern인 경우 IG = 0.246이 나옵니다.

- Case 2: Outline으로 분류

 ![231208-221128](/posts/final_01/231208-221128.png)

 Outline이 점선, 실선인지에 따라 분류할 경우 $I_{res}$를 계산해봅시다.

 $$
 I_{dashed} = - \frac{4}{7}log_2\frac{4}{7} - \frac{3}{7}log_2\frac{3}{7} = 0.985 \\
 {}\\
 I_{solid} = - \frac{1}{7}log_2\frac{1}{7} - \frac{6}{7}log_2\frac{6}{7} = 0.592 \\
 {}\\
 I_{res}(Outline) = \frac{7}{14} \cdot 0.985 + \frac{7}{14} \cdot 0.592 = 0.789
 $$

 즉, 분류 기준이 Outline인 경우 IG = 0.151이 나옵니다.

- Case 3: Dot으로 분류

 ![231208-221413](/posts/final_01/231208-221413.png)

 Dot이 있는지, 없는지에 따라 분류할 경우 $I_{res}$를 계산해봅시다.

 $$
 I_{no} = - \frac{2}{8}log_2\frac{2}{8} - \frac{6}{8}log_2\frac{6}{8} = 0.811 \\
 {}\\
 I_{yes} = - \frac{3}{6}log_2\frac{3}{6} - \frac{3}{6}log_2\frac{3}{6} = 1 \\
 {}\\
 I_{res}(Dot) = \frac{8}{14} \cdot 0.811 + \frac{6}{14} \cdot 1 = 0.892
 $$

 즉, 분류 기준이 Dot인 경우 IG = 0.048이 나옵니다.

즉, 이 경우에는 첫번째 분류 기준으로 Pattern을 선택하는 것이 합리적입니다.
다음 분류기준을 선택할 때도 이와 동일한 방법으로 진행하면 되지만, 다음 분류기준을 Pattern으로 선택하는 것은 의미가 없기에 선택하지 않도록 주의합니다.

![231208-221914](/posts/final_01/231208-221914.png)

하지만, 정보 이득(IG) 척도의 단점 역시 존재합니다.
분류기준을 선택함에 있어 **속성값이 많은 것을 선호**한다는 것입니다.

예로 들어 학번같은 경우, 학번은 유니크하기 때문에 분류시 학번별로 노드가 만들어지고, 그에 따라 엔트로피가 아주 낮게 측정되어 학번이 분류기준으로 선택될 것입니다.
하지만, 학번으로 분류하는 것은 의미가 없죠.

뿐만 아니라, **학습 데이터 셋에 없던 속성값의 경우 분류가 불가능**하다는 단점 또한 존재합니다.

### 정보 이득 비(IG Ratio)

속성값이 많은 것을 선호하는 문제를 해결하기 위한 개선된 알고리즘으로, 속성값이 많은 속성에 대한 불이익을 주는 방향으로 동작합니다.

$$
GainRatio(A) = \frac{IG(A)}{I(A)} = \frac{I - I_{res}(A)}{I(A)} \\
{}\\
I(A) = - \sum_{v}p(v)log_2p(v)
$$

여기서 I(A)는 고유 엔트로피로, 속성 A의 속성값을 부류로 간주하여 계산한 엔트로피를 의미합니다.
즉, 속성값이 많아질수록 엔트로피가 커지게 되므로, 학번을 분류기준으로 삼았을 때의 오류를 해결할 수 있습니다.

앞의 `Case - Pattern`을 예로 들어봅시다.


![231208-220649](/posts/final_01/231208-220649.png)

$$
I_{res}(Pattern) = \frac{5}{14} \cdot 0.971 + \frac{4}{14} \cdot 0 + \frac{5}{14} \cdot 0.971 = 0.694 \\
{}\\
I(Pattern) = - \frac{5}{14}log_2\frac{5}{14} - \frac{4}{14}log_2\frac{4}{14} - \frac{5}{14}log_2\frac{5}{14} = 1.58 \\
{}\\
GainRatio(Pattern) = \frac{IG(Pattern)}{I(Pattern)} = \frac{0.940 - 0.694}{1.58} = 0.156
$$

같은 방식으로 다른 분류기준에 대해 계산하면 다음과 같은 결과가 나옵니다.

| 분류속성 | 속성의 개수 | IG | IG Ratio |
|---|---|---|---|
| Pattern | 3 | 0.247 | 0.156 |
| Outline | 2 | 0.152 | 0.152 |
| Dot | 2 | 0.048 | 0.049 |

### 지니 이득(Gini Gain)

다른 분류 알고리즘으로 지니 지수를 사용하는 방법도 있습니다.

$$
Gini = \sum_{i \neq j}p(i)p(j)
$$

지니 지수는 위와 같이 수식화하며, 순도가 높을수록 낮은값이 나오게 됩니다.
이를 이용한 지니 지수 이득은 아래와 같습니다.

$$
Gini(A) = \sum_{v}p(v) \sum_{i \neq j}p(i|v)p(j|v) \\
{}\\
GiniGain(A) = Gini - Gini(A)
$$

부모의 지니 지수에서 분류된 자식 트리의 지니 지수의 가중평균을 뺌으로서 구할 수 있습니다.
마찬가지로 앞의 `Case - Pattern`을 예로 들어봅시다.

![231208-220649](/posts/final_01/231208-220649.png)

$$
Gini = \frac{5}{14} \times \frac{9}{14} = 0.230 \\
{}\\
Gini(Pattern) = \frac{5}{14} \times (\frac{2}{5} \times \frac{3}{5}) + \frac{4}{14} \times (\frac{0}{4} \times \frac{4}{4}) + \frac{5}{14} \times (\frac{3}{5} \times \frac{2}{5}) = 0.171 \\
{}\\
GiniGain(Pattern) = 0.230 - 0.171 = 0.058
$$

같은 방식으로 다른 분류기준에 대해 계산하면 다음과 같은 결과가 나옵니다.

| 분류속성 | IG | IG Ratio | Gini Gain
|---|---|---|---|
| Pattern | 0.247 | 0.156 | 0.058 |
| Outline | 0.152 | 0.152 | 0.046 |
| Dot | 0.048 | 0.049 | 0.015 |

### 회귀(Regression)

단말노드가 부류(class)가 아닌 수치(대표)값에 해당하는 경우 사용할 수 있는 분류법입니다.

표준편차 축소 SDR를 최대로 하는 속성을 선택하는게 졸으며, SDR은 아래와 같은 수식으로 표현 가능합니다.

$$
SDR(A) = SD - SD(A) \\
{}\\
SD = \sqrt{\frac{1}{N} \sum_{i=1}^{N} (x_i-m)^2} \\
{}\\
SD(A) = \sum_{v}p(v) \sqrt{\frac{1}{N_v} \sum_{i=1}^{N_v} (x_i-m_v)^2}
$$

---

## 단순 베이즈 분류기

결정 트리의 학습 알고리즘과 다르게 부류(class) 결정 지식을 조건부 확률로서 결정하는 분류기 입니다.

<tip>
 조건부 확률
 $$
 P(c|x_1, x_2, ..., x_n)
 $$
 
 베이즈 정리
 $$
 P(c|x_1, x_2, ..., x_n) = \frac{P(x_1, x_2, ..., x_n|c)P(c)}{P(x_1, x_2, ..., x_n)} \\
 {}\\
 사후확률 = \frac{가능도 \times 사전확률}{증거}
 $$
</tip>

단순 베이즈 분류기는 베이즈 정리를 이용해서 분류를 하는데, 단순의 정의는 다음과 같습니다.

> 가능도가 조건부 독립이라고 가정

즉, 베이즈 정리를 다음과 같이 정의합니다.

$$
P(c|x_1, x_2, ..., x_n) = \frac{P(x_1|c)P(x_2|c)...p(x_n|c)P(c)}{P(x_1, x_2, ..., x_n)}
$$

예를 들어 이해해봅시다.

![231208-220043](/posts/final_01/231208-220043.png)

여기서 수직이며, 점선이고, 점이 없을 때 삼각형일 확률을 구해봅시다.

$$
P(삼각형|수직,점선,무) \\
{}\\
= \frac{P(수직|삼각형)P(점선|삼각형)P(무|삼각형)P(삼각형)}{P(수직,점선,무)} \\
{}\\
= \frac{3/5 \cdot 4/5 \cdot 2/5 \cdot 5/14}{2/14} = 0.48
$$

결정 트리의 형태, 학습 알고리즘, 회귀와 단순 베이즈 분류기에 대해 알아봅니다.

결정 트리 & 단순 베이즈 분류기

## 비지도학습

지도학습은 학습 데이터에 입력-출력이 명시되어 있었는데, 비지도학습은 학습 데이터에 어떠한 레이블도 붙지 않은 데이터를 이용한 학습 방법을 의미한다.

비지도학습을 통해 데이터에 대한 잠재적인 구조나 계층 구조를 찾을 수 있고, 문서들을 주제에 따라 구조화 하거나, 로그를 분석한 사용 패턴을 알아내는데 적용할 수 있다.

---

## 군집화

유사성에 따라 데이터를 분할하는 것으로, 데이터가 하나의 군집에만 소속되는 일반 군집화(Hard clustering)와 퍼지 군집화(Fuzzy clustering)으로 나뉜다.

군집화는 보통 아래와 같은 용도로 사용된다.

- 데이터에 내제된/일반적 구조 추정/통찰
- 가설 설정
- 이상 감지
- 데이터 압축
- 데이터 전처리 (부류(class)를 부여하는 방식)

성능은 군집 내의 분산은 작을수록, 군집간의 거리는 멀수록 좋다고 평가한다.

### 밀도 추정

![231022-230608](/posts/mid_08/231022-230608.png)

부류(class)별로 데이터를 만들어 냈을 것으로 추정되는 확률 분포를 찾는 과정으로, 각 부류 별로 주어진 데이터를 발생시키는 확률을 계산하여 가장 확률이 높은 부류로 데이터를 분류한다.

분포가 수학적인 형태를 갖고있을 것을 가정하여 데이터의 분포를 가장 잘 수학적으로 표현하려고 하는 추정 방식을 `모수적 밀도 추정` 이라고 하며, 전형적으로 **Gaussian 함수의 혼합**으로 표현한다.

또는, 분포에 대한 수학적 함수를 가정하지 않고, 주어진 데이터를 사용하여 밀도함수의 형태로 표현하는 방식을 `비모수적 밀도 추정` 이라고 하며, 전형적으로 **히스토그램**과 같은 방식으로 표현한다.

### 차원 축소

고차원의 데이터를 정보의 손실을 최소화 하면서 저차원으로 변환하는 것으로, 시각화를 직관적으로 하기 위해, 그리고 `차원의 저주 문제`를 완화하기 위해 사용한다.

<tip>
 `차원의 저주 문제`
 
 ![231022-231121](/posts/mid_08/231022-231121.png)
 차원이 커질수록 거리분포가 일정해지는 경향
</tip>

![231022-231254](/posts/mid_08/231022-231254.png)

이를 위해 주성분을 분석하여 분산이 큰 축을 기준으로 데이터를 projection하는 방식을 사용해서 저차원으로 변환한다.

### 이상치 탐지

다른 데이터와 크게 달라서 관심 대상으로 봐야하는 데이터를 탐지하기 위해 사용한다.
이런 관심대상의 데이터는 `노이즈`일 확률이 높으나, `신규성 탐지`의 경우도 항상 염두해야 한다.

이상치는 아래와 같은 방식으로 탐지할 수 있다.

- 점 이상치
 다른 데이터와 비교하여 차이가 큰 데이터

- 상황적 이상치
 상황에 맞지 않는 데이터

- 집단적 이상치
 여러 데이터를 모아서 보면 비정상으로 보이는 데이터

이러한 이상치 탐지는 **부정사용감지 시스템**이나 **침임감지 시스템** 등에 사용할 수 있다.

---

## 반지도학습

비지도학습과 마찬가지로 미분류 데이터를 이용하는데, 이를 지도학습에 사용하는 방법이다.

![231022-231828](/posts/mid_08/231022-231828.png)

이런 식으로 같은 군집에 속하는 것은 가능한 동일한 부류에 소속하도록 학습하는 방식이다.
미분류 데이터는 획득 비용이 낮기 때문에 이러한 지도학습 방식도 고려하면 좋다.

단, 반지도학습을 위해서는 데이터가 아래와 같은 경향을 보인다는 가정하에 이루어져야 한다.

- 평활성 가정
 가까이 있는 점들은 서로 같은 부류에 속할 가능성이 높음

- 군집 가정
 같은 군집에 속하는 데이터는 서로 같은 부류에 속할 가능성이 높음

- 매니폴드(Manifold) 가정
 원래 차원보다 낮은 차원의 매니폴드에 데이터가 분포할 가능성이 높음

비지도 & 반지도학습에서 사용되는 개념에 대해 알아봅니다.

기계학습 - 비지도 & 반지도학습

## 기계학습

사례들(examples)을 일반화하여 패턴 또는 모델을 추출하는 과정으로 학습 데이터를 잘 설명할 수 있는 패턴을 기계 스스로 학습하는 것을 유도하는 것이다.

![231022-220530](/posts/mid_07/231022-220530.png)

단, 오컴의 면도날(Occam's razor) 원리에 따라 가능하면 학습 결과가 간단한 형태로 표현되면 좋다.

기계학습의 종류에는 지도학습, 비지도학습, 반지도학습, 강화학습과 같은 방법이 있는데, 이번에는 지도학습에 대해서만 알아보자.

### 지도학습

주어진 학습 데이터 - **(입력, 출력)** 과 같은 데이터를 이용해서 학습하는 과정.
학습이 완료된 모델은 새로운 **(입력)** 이 있을 때 **(출력)** 을 유추할 수 있어야 한다.

출력이 불 연속적인 값이어야 한다면 데이터를 `분류`하는 방향으로 학습을 해야하고,
출력이 연속적인 값이어야 한다면 `회귀`하는 방향으로 학습을 해야한다.

---

## 분류 (Classification)

이상적인 분류기는 학습에 사용되지 않은 데이터에 대해서 분류를 잘 해야한다.
즉, 일반화의 능력이 좋은것이 이상적인 분류기이다.

<tip>
 데이터의 종류
 1. 학습 데이터
 분류기를 학습하는데 사용하는 데이터 집합.
 2. 테스트 데이터
 학습된 모델의 성능을 평가하는데 사용하는 데이터 집합.
 학습에 사용되지 않은 데이터여야 함.
 3. 검증 데이터
 학습 과정에서 학습을 중단할 시점을 결정하기 위해 사용하는 데이터 집합.
</tip>

![231022-221446](/posts/mid_07/231022-221446.png)

학습 데이터를 충분히 학습하지 않은 상태를 `부적합` 이라고 한다.

반대로학습 데이터에 대해 지나치게 잘 학습된 상태를 `과적합` 이라고 하는데, 학습되지 않은 데이터에 대해 좋지 못할 성능을 보일 가능성이 크다.
과적합을 회피하기 위해서 검증 데이터를 사용하게 된다.

![231022-221636](/posts/mid_07/231022-221636.png)

검증 데이터에 대한 오류가 증가하기 시작하면 학습 데이터에 대해 과적합이 일어나는 시점이기 때문에 이 때 학습을 중지하는 것이 좋다.

### 불균형 데이터 문제

특정 부류에 속하는 학습 데이터의 개수가 **다른 부류에 비해 지나치게 많은 경우** 정확도에 의한 성능 평가가 무의미해진다.
이게 무슨 의미냐면, A 부류의 데이터가 전체 데이터의 99%를 차지한다면, 분류기의 출력을 항상 A로 설정하는 경우 해당 학습 데이터에 대해 99%의 정확도를 보일 것이다.
하지만, 테스트 데이터에선 A/B가 각각 50% 비율로 들어있다면, 분류기의 정확도는 50%로 감소할 것이다.

![231022-222326](/posts/mid_07/231022-222326.png)

이런 경우 SMOTE 알고리즘을 이용해 어느정도 해결할 수 있다.
간단하게 설명하면 빈도가 낮은 학습 데이터의 `k-근접 이웃`을 이용해 새로운 데이터를 생성하여 빈도가 낮은 부류의 데이터 개수를 늘리는 알고리즘이다.

### 이진 분류기 성능 평가

이진 분류기는 두 개의 부류만을 갖는 데이터에 대한 분류기로 A/B 둘 중 하나로 분류하는 분류기이다.
이 분류기는 아래와 같은 예측-결과 표를 생성하는데,

![231022-222646](/posts/mid_07/231022-222646.png)

이것을 이용한 여러가지 지표로 성능을 평가한다.

- 민감도/재현율/진양성율
 실제 양성일 때, 양성이라고 예측하는 확률이다.
 > 민감도 = $\frac{TP}{TP + FN}$
 >
 > e.g. 불이났을 때, 불이 났다고 민감하게 알려주는 화재경보기

- 특이도/진음성률
 실제 음성일 때, 음성이라고 예측하는 확률이다.
 > 특이도 = $\frac{TN}{TN + FP}$
 >
 > e.g. 불이 안났을 때, 울리지 않는 화재경보기

- 정밀도
 양성으로 예측을 했는데, 실제로 양성일 확률.
 > 정밀도 = $\frac{TP}{TP + FP}$
 >
 > e.g. 화재경보기가 경보를 울렸는데, 실제로 불이 난 상황이었음

- 음성 예측도
 음성으로 예측을 했는데, 실제로 음성일 확률.
 > 음성 예측도 = $\frac{TN}{TN + FN}$
 >
 > e.g. 화재경보기가 안울렸는데, 실제로 불도나지 않았음

- 위양성율
 1에서 특이도를 뺀 값.
 > 위양성율 = $\frac{FP}{TN + FP}$ = 1 - 특이도

- 위발견율
 1에서 정밀도를 뺀 값.
 > 위발견율 = $\frac{FP}{TP + FP}$ = 1 - 정밀도

- 정확도
 예측한대로 결과가 나올 확률.
 > 정확도 = $\frac{TP + TN}{TP + FP + TN + FN}$

- F1 측도
 > F1 = 2$\frac{정밀도 \times 재현율}{정밀도 + 재현율}$

### ROC 곡선

위양성률, 민감도 그래프로 ROC 곡선의 아래 면적, AUC(Area Under the Curve)가 클수록 바람직하게 분류한다는 뜻이다.

![231022-224153](/posts/mid_07/231022-224153.png)

---

## 회귀 (Regression)

학습 데이터에 부합되는 출력값이 실수인 함수를 찾는 문제로, 앞에서 언급했 듯, 출력이 연속적이어야 하는 경우에 사용하는 방법이다.

![231022-224546](/posts/mid_07/231022-224546.png)

파란 점과 같은 학습 데이터가 주어졌을 떄, 해당 데이터를 가장 잘 설명하는 모델 **$f$** 를 찾기 위해서는 $f$의 오차를 계산하는 함수 **$f*$** 이 최소가 되도록 인자를 조정해야 한다.

$$
f*(x) = argmin_f \sum_{i=1}^{n} (y_i - f(x_i))^2
$$

### 회귀 성능 평가

학습 방향성과 같다.
테스트 데이터에 대한 오차값의 평균이 작을수록 좋다.

![231022-225021](/posts/mid_07/231022-225021.png)

하지만 처음에 언급했 듯 과적합되는 현상은 피해야 한다.

이를 위해 모델의 복잡도를 일종의 **패널티**로써 성능 평가(목적함수)에 반영하여, 모델의 복잡도를 최소화 하는 방향으로 학습을 유도해야 한다.

### 로지스틱 회귀 (Logistic regression)

모델의 출력이 [0, 1] 사이의 값을 갖도록 조정해야 하는 경우 sigmoid 함수와 같은 로지스틱 함수를 이용해서 학습 데이터의 출력을 근사하는 방식을 사용할 수도 있다.

![231022-225434](/posts/mid_07/231022-225434.png)

단, 이 때의 목적 함수는 `교차 엔트로피`(오차가 0~1 사이로 조정됨)가 적용된 함수를 사용해야 한다.

로지스틱 회귀는 경사 하강법을 사용하는 학습에서 자주 사용된다.

지도학습에서 사용되는 개념에 대해 알아봅니다.

기계학습 - 지도학습


## 추론

구축된 지식과 주어진 데이터, 정보를 이용해 새로운 사실을 생성하는 것으로 전향(순방향) 추론과 후향(역방향) 추론으로 나뉜다.

### 전향 추론

규칙의 조건부와 만족하는 사실이 있을 때 규칙의 결론부를 실행하거나 처리하는 방식으로 아래와 같이 순방향으로 추론하는 방식이다.

![231022-200403](/posts/mid_06/231022-200403.png)

### 후향 추론

어떤 사실을 검증하거나 확인하고 싶은 경우에 관심 대상의 사실을 결론부에 갖고 있는 규칙을 찾아서 조건부가 만족하는지를 확힌하는 방식으로 아래와 같이 역방향으로 추론하는 방식이다.

![231022-200616](/posts/mid_06/231022-200616.png)

---

## 규칙 기반 시스템

지식을 규칙과 사실로 기술하며 아래와 같은 구조로 관리된다.

![231022-200851](/posts/mid_06/231022-200851.png)

**문제 해결을 위한 지식**인 `규칙`은 규칙 베이스에서 관리되며, 생성 메모리 라고도 불린다.

**문제에 대해 알려진 데이터나 정보**인 `사실`은 작업 메모리에서 관리된다.
참고로, 추론 과정의 중간 결과나 사용자로부터 받은 문제에 대한 정보 역시 여기서 관리된다.

### 추론 엔진

실행할 수 있는 규칙을 찾아 해당 규칙을 실행하는데 아래의 3단계의 과정을 반복한다.

1. 패턴 매칭
  작업 메모리의 사실과 규칙 메모리에 있는 규칙의 조건부를 대조하여 일치하는 규칙을 찾아냄.

2. 경합 해소
  찾아낸 규칙 중 경합되는 규칙(경합 집합)에 대해 하나의 규칙을 선택함.
  경합 해소 전략에는 다음과 같은 전략이 있음.

    > 1. 규칙 우선
    > 미리 규칙에 우선순위를 부여하고, 경합시 우선순위가 높은 규칙을 우선 선택
    > 우선순위 태그 기준
    > ![231022-201805](/posts/mid_06/231022-201805.png)
    >
    > 2. 최신 우선
    > 가장 최근에 입력된 데이터와 매칭된 규칙을 우선 선택
    > 시간 태그 기준
    > ![231022-201845](/posts/mid_06/231022-201845.png)
    >
    > 3. 최초 우선
    > 경합 집합에서 가장 먼저 매칭된 규칙을 우선 선택
    >
    > 4. 상세 우선
    > 조건부가 가장 상세하거나 복잡한 규칙을 우선 선택
    > 태그말고 조건문의 길이 기준
    > ![231022-201826](/posts/mid_06/231022-201826.png)
    

3. 규칙 실행

지식을 규칙의 형태로 표현하는 방법에 대해 알아봅니다.

규칙 기반 시스템

인과성이 약하거나, 연관성이 애매하거나, '얼마나?'에 해당하는 정도가 모호한 문장을 정량화 하는 방법에 대해 알아봅니다.

## 확신도 (Certainty factor)

규칙과 사실의 신뢰정도를 [-1, 1] 구간의 값으로 표현합니다.

| 확신도 | 대응되는 단어 |
|---|---|
| −1.0 | 절대 아니다 (definitely not)|
| −0.8 | 거의 확실히 아니다 (almost certainly not) |
| −0.6 | 아마 아니 것이다 (probably not) |
| −0.4 | 어쩌면 아닐 것이다 (maybe not) |
| −0.2 ~ 0.2 | 모르겠다 (unknown) |
| 0.4 | 어쩌면 그럴 것이다 (maybe) |
| 0.6 | 아마 그럴 것이다 (probably) |
| 0.8 | 거의 확실하다 (almost certainly) |
| 1.0 | 확실하다 (definitely)|

### 추론결과의 확신도

추론에 대한 확신도는 각 명제에 대한 확신도를 계산하여 도출해야 합니다.

- IF A THEN B _($\{A \rightarrow B, \; A\} \vdash B$)_
 기본적으로 정형식들의 확신도를 곱하는 방식으로 구합니다.
 > **$cf(B) = cf(A) \times cf(A \rightarrow B)$**

- IF A and B THEN C _($\{A \wedge B \rightarrow C, \; A, \; B\} \vdash C$)_
 **and**의 경우 조건부에 해당하는 정형식의 확신도 중 작은 값을 고릅니다.
 > **$cf(C) = min\{cf(A), cf(B)\} \times cf(A \wedge B \rightarrow C)$**

- IF A or B THEN C _($\{A \vee B \rightarrow C, \; A, \; B\} \vdash C$)_
 **or**의 경우 조건부에 해당하는 정형식의 확신도 중 큰 값을 고릅니다.
 > **$cf(C) = max\{cf(A), cf(B)\} \times cf(A \vee B \rightarrow C)$**

아래는 예시입니다.

![231022-192422](/posts/mid_05/231022-192422.png)

만약, 여러 사실에 의해 동일한 사실을 추론하는 경우 추론 결과는 같지만, 확신도는 다르게 계산될 수 있습니다.
이런 경우, 확신도를 하나로 통합하는게 좋습니다.

![231022-192640](/posts/mid_05/231022-192640.png)

---

## 확률 (Probability)

어떤 사건이 일어날 가능성을 표현할 때 사용합니다.

### 결합 확률

사건 A, B가 동시에 일어날 확률을 가리키며, 아래와 같이 수식화 할 수 있습니다.

> A: 첫 번째 주사위가 짝수
> B: 두 번째 주사위가 홀수
>
> $P(A,B) = P(A \cap B) = P(AB)$
> $= 1/2 \times 1/2 = 0.25$

### 조건부 확률

사건 B가 일어났을 때, 사건 A가 일어날 확률을 가리키며, 아래와 같이 수식화 할 수 있습니다.

> A: 두 주사위의 합이 8
> B: 첫 번째 주사위가 3
>
> $P(A|B) = \frac{P(A,B)}{P(B)}$
> $= \frac{1/36}{1/6} = 1/6$

`베이즈 정리`에 의해 조건부 확률의 조건부를 변형할 수 있습니다.

> $P(A|B) = \frac{P(B|A)P(A)}{P(B)}$

---

## 퍼지 이론 (Fuzzy theory)

기존 집합론과 다르게 퍼지 이론은 0/1의 이분법적으로 분류하지 않고, 0~1로 모호하게(어느정도 포함되게) 구분함.
즉, 어느 정도(degree)의 문제는 퍼지 집합을 도입하여 해결.

### 퍼지 집합

원소가 모임(collection)에 어느 정도 속한다는 것을 표현한 것으로, 해당 집합은 부분적으로 참이 됨.
소속정도는 [0, 1] 범위의 실수값으로 표현함.

작다, 평균이다, 크다의 표현을 아래와 같이 다르게 할 수 있음.

![231022-194330](/posts/mid_05/231022-194330.png)

### 퍼지 규칙

소속함수로 표현된 언어항을 표함하는 규칙.

> IF service = 나쁘다 OR food = 별로이다 THEN tip = 적다
> IF service = 보통이다 THEN tip = 보통이다
> IF service = 훌륭하다 OR food = 맛있다 THEN tip = 많다

<tip>
 `언어항`
 '나쁘다', '맛있다', '많다'와 같은 자연어에 해당하는 항으로 소속함수로 표현될 수 있다. 
 ![231022-194851](/posts/mid_05/231022-194851.png)
</tip>

### 퍼지 추론

소속함수로 표현돤 언어항을 사용하는 퍼지 규칙들의 모음으로 수치적인 추론이 가능해진다.

![231022-195645](/posts/mid_05/231022-195645.png)

추론된 영역의 무게중심을 결과로 사용하면 `비퍼지화`가 가능하다.

불확실한 지식을 표현하는 방법에 대해 알아봅니다.

불확실한 지식 표현

말로 표현된 문장을 타당한 추론을 위해 기호를 사용하여 표현하고, 기호의 조작을 통해 참과 거짓을 판정하는 분야이다.

## 명제 논리

### 명제 (Proposition)

`명제`란, 참과 거짓을 분평하게 판정할 수 있는 문장으로 P, Q와 같은 기호로 표현된다.

중요한 점은, 명제 그 자체는 참, 거짓을 결정할 수 없고, 반드시 기호의 진리값을 설정해 줘야 한다는 점이다.
이게 무슨 말이냐면, 아래의 문장을 예로 들어 설명해보겠다.

> 오징어 다리는 10개 이다.

이 명제는 우리나라에서는 참이다.
하지만 북한에서는 오징어 라는 명사는 우리나라의 낙지를 가리키는 말 이기 때문에 북한에서는 거짓인 명제이다.

즉, 문장 자체의 내용에 대해서는 관심을 갖지 말고, 문장의 설정된 `진리값에만 관심`을 가져야 한다.

_**용어 설명**_
| 용어 | 의미 |
|---|---|
| 기본 명재 | 하나의 진술로만 이루어진 최소 단위의 명제 |
| 복합 명제 | 기본 명제들이 결합되어 만들어진 명제 |

### 논리식 (Logical expression)

명제를 기호로 표현한 형식으로 명제기호, T/F, 논리 기호를 사용하여 구성되는데, 가장 기본이 되는 논리 기호는 다음과 같다.

| 논리기호 | 이름 | 논리식 | 의미 |
|---|---|---|---|
| $\neg$ | 부정 (negation) | $\neg P$ | $P$가 아님 |
| $\vee$ | 논리합 (disjunction) | $P \vee Q$ | $P$ 또는 $Q$ |
| $\wedge$ | 논리곱 (conjunction) | $P \wedge Q$ | $P$ 그리고 $Q$ |
| $\rightarrow$ | 함의 (implication) | $P \rightarrow Q$ | $P$ 이면 $Q$ |
| $\equiv$ | 동치 (equivalence) | $P \equiv Q$ | $(P \rightarrow Q) \wedge (Q \rightarrow P)$ |

_**용어 설명**_
| 용어 | 의미 |
|---|---|
| 리터럴 | 명제 기호 또는 명제 기호의 부정 |
| 절 | 리터럴들이 논리합이나 논리곱으로만 연결 (논리합 절, 논리곱 절) |
| 논리곱 정규형 (CNF) | 논리합 절들이 논리곱으로 연결되어 있는 논리식 |
| 논리합 정규형 (DNF) | 논리곱 절들이 논리합으로 연결되어 있는 논리식 |
| 정형식 (WFF) | 진리값(T/F)과 명제, 그들과 논리 기호를 사용하여 구성된 논리식을 의미함 |

### 진리표 (Truth table)

논리기호에 따라 T/F를 결합하는 방법을 나타낸 표

| $P$ | $Q$ | $\neg P$ | $P \vee Q$ | $P \wedge Q$ | $P \rightarrow Q$ | $P \equiv Q$ |
|---|---|---|---|---|---|---|
| F | F | **T** | F | F | **T** | **T** |
| F | **T** | **T** | **T** | F | **T** | F |
| **T** | F | F | **T** | F | F | F |
| **T** | **T** | F | **T** | **T** | **T** | **T** |

- 타당한 논리식 (Valid logical expression), 항진식
 모든 가능한 해석에 대해 항상 참인 논리식
 _e.g. $P \vee \neg P$_

- 항위식
 모든 가능한 해석에 대해 항상 거짓인 논리식
 _e.g. $P \wedge \neg P$_

- 츙족가능한 논리식
 참으로 만들 수 있는 해석이 하나라도 있는 논리식

- 충족불가능한 논리식
 참으로 만들 수 있는 해석이 하나도 없는 논리식. 즉, 항위식.

### 동치 관계 (Equivalence relation)

어떠한 해석에 대해서도 같은 진리 값을 갖는 두 논리식

- $\neg(\neg p) \equiv p$
- $p \vee F \equiv p$
 $p \wedge T \equiv p$
- $P \vee \neg P \equiv T$
 $P \wedge \neg P \equiv F$
- **$\neg (p \wedge q) \equiv \neg p \vee \neg q$**
 **$\neg (p \vee q) \equiv \neg p \wedge \neg q$**
- **$p \rightarrow q \equiv \neg p \vee q$**
- $p \vee (q \vee r) \equiv p \vee q \vee r$
 $(p \wedge q) \wedge r \equiv p \wedge q \wedge r$
- **$p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$**
 **$p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$**

### 논리적 귀결 (Logical entailment)

정형식(Well-Formed Formula, WFF)의 집합 $\Delta$가 다른 정형식 $\omega$를 참으로 만든다면 두 관계를 아래와 같이 정의한다.

> $\Delta \models \omega$
> e.g. $\{P, \; P \rightarrow Q\} \models Q$
>
> $\Delta$는 $\omega$를 논리적으로 귀결한다.
> $\omega$는 $\Delta$를 논리적으로 따른다.
> $\omega$는 $\Delta$의 논리적 결론이다.

### 추론 (Inference)

논리적 귀결을 도출하는 과정을 추론이라고 한다.

관측된 복수의 사실들을 일반화하여 일반적인 패턴(명제)를 도출하는 것을 `귀납적 추론` 이라고 하고,
참인 명제(사실)들로부터 새로운 명제(사실)을 도출하는 것을 `연역적 추론` 이라고 한다.

논리에서의 추론은 보통 **연역적 추론**을 가리키는데, 이걸 도출하는 테크닉에 대해 살펴보자.

- 긍정 논법
 $\{p \rightarrow q, \; p\} \vdash q$
 _(\{새이다 &rarr; 날 수 있다, 새이다\} &rarr; 날 수 있다)_

- 부정 논법
 $\{p \rightarrow q, \; \neg q\} \vdash \neg p$
 _(\{새이다 &rarr; 날 수 있다, 날 수 없다\} &rarr; 새가 아니다)_

- 삼단 논법
 $\{p \rightarrow q, \; q \rightarrow r\} \vdash p \rightarrow r$
 _(\{새이다 &rarr; 날개가 있다, 날개가 있다 &rarr; 날 수 있다\} &rarr; 새이다 &rarr; 날 수 있다)_

- **논리 융합 (Resolution)**
 긍정, 부정, 삼단 논법을 포함한 일반화된 추론 규칙으로 
 두 개의 **논리합 절**이 같은 기호의 긍정-부정 리터럴을 서로 포함하고 있을 때, 해당 리터럴을 제외한 나머지 리터럴의 논리합 절을 만들어 내는 것.

 | 논법 | 변환 | WFF (논리 융합식, Resolvent) |
 |---|---|---|
 | $p \rightarrow q, \; p$ | **$\neg p$** $\vee q$, **$p$** | $q$ |
 | $p \rightarrow q, \; \neg q$ | $\neg p \vee$ **$q$**, **$\neg q$** | $\neg p$ |
 | $p \rightarrow q, \; q \rightarrow r$ | $\neg p \vee$ **$q$**, **$\neg q$** $\vee r$ | $\neg p \vee r$ ($p \rightarrow r$) |

 즉, 논리 융합을 사용하면 모든 추론 규칙을 일반화 할 수 있다.

- 정당성 (sound)
 $\Delta \vdash \omega \; \rightarrow \; \Delta \models \omega$ (아야 sound)

- 완전성 (complete)
 $\Delta \models \omega \; \rightarrow \; \Delta \vdash \omega$ (야아 complete 하네)

 <tip>
 정당성과 완전성을 동시에 만족하는 추론 규칙은 논리적인 귀결과 동일시 할 수 있다.
 </tip>

### 증명 (Proof)

- 구성적 증명 (Constructive proof)
 공리(참인 논리식)들에 추론 규칙을 적용하여 참을 만들어 보이는 증명.
 정리하다가 결론이 참으로 끝나면 된다.

- 논리융합 반박 (Resoultion refutation)
 증명할 정리를 일단 부정하고, 논리융합 방법을 적용해 모순이 발생함으로 보이는 증명.
 부정된 정리가 모순이니, 원상태의 정리는 참이 된다.

 ![231022-171322](/posts/mid_04/231022-171322.png)

---

## 술어 논리

명제의 내용을 다루기 위해 변수, 함수 등을 도입하고, 이들의 값에따라 T/F가 결정되도록 명제 논리를 확장한 논리.

### 술어 (Predicate)

대상의 속성이나 관계를 기술하는 기호로, 대상에게 T/F를 부여하는 명제의 기본 형식이다.

| 문장 | 명제 논리 | 술어 논리 |
|---|---|---|
| 모든 사람은 죽는다 | P | $\forall x(사람(x) \rightarrow 죽는다(x))$ |
| 소크라테스는 사람이다 | Q | $사람(소크라테스)$ |
| 소크라테스는 죽는다 | R | $죽는다(소크라테스)$ |

<tip>
 `존재 한정사`
 Existential quantifier로 존재함을 알려준다. (**$\exist$**)
 
 `전칭 한정사`
 Universal quantifier로 모든 범위를 가리킨다. (**$\forall$**)
</tip>

### 함수 (function) / 항 (term)

주어진 인자에 대해 T/F를 반환하는 것이 아닌, 일반작인 값을 반환하는 것을 `함수`라고 한다.
즉, 인자를 지칭하기 위해 쓰인다.

함수의 인자가 될 수 있는 것을 `항` 이라고 한다.
**상수, 변수, 함수**만이 항이 될 수 있다.

<tip>
 명제 논리식의 정형식(WFF)과 마찬가지로, 술어 논리식의 정형식 역시 비슷한 정의를 갖는다.
 항, 논리 기호, 한정사로만 이루어진 식을 정형식이라고 부른다.
</tip>

### N차 술어 논리 (N-order predicate logic)

**변수에만** 한정사를 사용할 수 있도록 한 술어 논리를 `일차 술어논리(FOL)` 라고 한다.
엄밀히는, 술어기호의 인자로 사용될 수 있는 객체나 대상만을 변수화 할 수 있고, 이들 변수에만 전칭 한정사와 존재 한정사를 쓸 수 있도록 한 술어논리를 말한다.

**변수, 함수, 술어기호**에 대해 한정사를 쓸 수 있도록 한 술어 논리를 `고차 술어논리(HOL)` 라고 한다.
엄밀히는, 함수나 술어기호도 변수화 할 수 있고, 이들 변수에만 전칭 한정사와 존재 한정사를 쓸 수 있도록 한 술어논리를 말한다.

인공지능 분야에서는 **연산량의 한계** 때문에 `일차 술어논리`를 주로 사용한다.

### CNF 변환

아래의 변환 과정을 거친면 된다.

1. 한정사를 논리식의 맨 앞으로 끌어내는 변환
 일반적으로 한정사를 맨 앞으로 끌어내도 의미는 변하지 않지만, 그래도 최다한 할 수 있는 변환을 한 뒤에 끌어내자.

2. 전칭 한정사 제거
 $\forall$은 바로 제거해도 상관없다.

3. 존재 한정사 제거
 우선 아래와 같은 방식으로 전칭 한정사로 변환한 뒤 전칭 한정사를 제거하는 방법을 사용한다.
 **$\neg \exist x P \equiv \forall x \neg P$**

 만일 함수에 변수가 2개 이상 사용된 경우 변환이 어려울 때는 상수를 집어넣거나 스콜렘 함수로 변환한다.
 $\forall x \exist y [P(x) \wedge$ **$Q(x, y)$**$] \rightarrow \forall x [P(x) \wedge$ **$Q(x, s(x))$**$]$

4. 단일화
 논리 융합을 적용할 때, 대응되는 리터럴이 같아지도록 상수를 변수화 함.
 ![231022-175353](/posts/mid_04/231022-175353.png)

변환 과정을 거쳐 논리융합 반박을 통해 증명하는 예시를 살펴보자.
아래의 예시는 (5)의 모순을 보임으로써 $\neg$(5)가 참임을 보이는 논리융합 반박이다.

![231022-175534](/posts/mid_04/231022-175534.png)

지식을 표현하는 방법 - 논리에 대해 알아봅니다.

명제 논리 & 술어 논리

## 프레임 (Frame)

특정 객체 또는 개념에 대한 전형적인 지식을 슬롯(slot)의 집합으로 표현하는 것으로, 컴퓨터를 표현한 프레임은 다음과 같이 기술할 수 있다.

![231022-153840](/posts/mid_03/231022-153840.png)

### 슬롯 (slot)

객체의 속성(attribute)를 기술하는 것으로 슬롯 이름과 값으로 구성된다.
슬롯 값은 복수개의 `패싯`과 `데몬`으로 구성된다.

- 패싯 (facet)
 속성에 대한 부가적인 정보를 저장하기 위해 사용되며 아래와 같은 패싯 이름들을 사용할 수 있다.
 - value: 속성 값
 - data-type: 속성의 자료형
 - default: 기본 값
 - require: 슬롯에 들어갈 수 있는 값이 만족해야 할 제약조건

- 데몬 (demon)
 ![231022-154436](/posts/mid_03/231022-154436.png)

 지정된 조건을 만족할 때 실행할 절차적 지식을 기술하는데 사용되며, 아래와 같은 데몬 이름들을 사용할 수 있다.
 - if_needed: 슬롯 값을 알아야 할 때(즉, 사용하려고 할 때)
 - if_added: 슬롯 값이 추가될 때
 - if_removed: 슬롯 값이 제거될 때
 - if_modified: 슬롯 값이 수정될 때

### 클래스 프레임

위에서 프레임을 설명할 때 사용한 프레임이 클래스 프레임이다.

<tip>
 하위 프레임이 상위 프레임을 상속받는 계층구조도 가질 수 있음.
</tip>

### 인스턴스 프레임

![231022-154657](/posts/mid_03/231022-154657.png)

클래스 프레임을 특정 객체에 대한 정보로 표현하면 인스턴스 프레임이 된다.
그냥 OOP와 같은 개념이다.

---

## 의미망 (Semantic network)

![231022-184947](/posts/mid_03/231022-184947.png)

노드와 방향성 간선으로 구성되는 그래프를 이용해 지식을 표현하는 방법으로, 이항 관계만을 표현한다.
그렇기에 다항 관계도 이항 관계로 전개하여 표현해야 하는데, 그 때문에 관계(relation) 역시 객체로 간주하여 표현한다.

![231022-185755](/posts/mid_03/231022-185755.png)

- `is-a`
 자식 is-a 부모, 인스턴스 is-a 클래스와 같은 관계의 간선을 표현한다.

- `has-a`
 전체 has-a 부분, 부분 part-of 전체와 같은 관계의 간선을 표현한다.

<tip>
 is-a, has-a는 추이적 관계를 만족하는데, 추이적 관계란, 3단논법과 같은 관계를 의미함.
 
 > is-a(팽귄, 조류) $\wedge$ is-a(조류, 동물) &rarr; is-a(팽귄, 동물)
</tip>

지식을 시각적으로 표현할 수 있어 직관적으로 이해할 수 있고, 노드 추가 및 변경이 자유롭다는 장점이 있다.
하지만, 양이 많아지면 관리가 복잡해지고, 개념이나 관계를 임의로 정의하기에 통일성이 떨어진다는 단점이 있다.

### 추론

상속관계를 이용해서 추론한다.
예로 들어 '바둑기사의 키는?' 이라는 질문은 다음과 같이 추론할 수 있다.

![231022-190024](/posts/mid_03/231022-190024.png)

뿐만 아니라, 주어진 지식으로부터 새로운 사실을 이끌어내는 추론도 가능하다.
예로 들어 '사람1이 사람2에게 사물1을 준다'는 지식으로부터, '사람2는 사물1을 소유하게 된다'는 사실을 추론한다.

![231022-190213](/posts/mid_03/231022-190213.png)

### 프레임으로 변환

![231022-190324](/posts/mid_03/231022-190324.png)

노드별로 프레임으로 변환할 수 있는데, 노드에서 나가는 간선들을 슬롯으로 구성하면 된다.

---

## 스크립트 (Script)

일반적으로 발생할 수 있는 전형적인 상황에 대한 절차적 지식을 일목요연하게 표현한 것이다.

![231022-190644](/posts/mid_03/231022-190644.png)

- 진입 조건
 스크립트에 기술된 사건들이 일어나기 전에 만족되어야 하는 전제조건

- 역할자
 스크립트에 관련된 사람, 대상

- 자산
 사건 진행 과정에서 사용되는 객체

- 트랙
 스크립트에서 발생할 수 있는 사건들이 변형된 형태 식별자 (장소)

- 장면
 실제 일어나는 일련의 사건
 
- 결과 조건
 스크립트의 장면에 있는 사건들이 일어난 후에 만족되는 조건

지식을 표현하는 방법 - 프레임, 의미망, 스크립트에 대해 알아봅니다.

프레임 & 의미망 & 스크립트

## 게임 트리

`상대가 있는 게임`에서 자신과 상대방의 가능한 게임 상태를 나타낸 트리.
자신의 턴인지, 상대의 턴인지에 따라 탐색하는 방식이 다르게 적용됨.
(나에겐 유리하게, 상대에겐 불리하게)

정해진 시간 내에 최대한 많은 수를 보는 것이 유리하기 때문에 탐색 효율을 높이는 것이 중요하다.

### Mini-max Algorithm

특이하게 단말 노드로부터 위로 올라가면서 최소-최대 연산을 반복하여 자신이 선택할 수 있는 방법 중 가장 좋은 값을 선택하는 방법이다.

자신의 턴인 Max 노드에서는 자신에게 유리한 값을 선택하고,
상대의 턴인 Min 노드에서는 상대에게 불리한 값을 선택하는 방식을 취한다.

![231021-230224](/posts/mid_02/231021-230224.png)

하지만 트리가 넓을 수록 모든 상태공간을 탐색하는건 시간상 너무 오래 걸리기 때문에 최적화 기법이 들어가야 한다.
바로 **$\alpha - \beta$ 가지치기(prunning)** 기법이다.

검토해 볼 필요가 없는 부분을 탐색하지 않도록 하는 기법인데, 어떻게 해야 검토할 필요가 없다는 걸 알 수 있을까?

깊이 우선 탐색(DFS)로 제한 깊이까지 탐색을 하면서 Min, Max 노드의 $\alpha$, $\beta$값을 업데이트 하는데, 각 $\alpha$, $\beta$값은 다음과 같은 값을 저장한다.

- $\alpha$
 Max 노드에서만 값이 업데이트되며, 현재까지 확보한 자식의 값 중 최댓값을 저장함

- $\beta$
 Min 노드에서만 값이 업데이트되며, 현재까지 확보한 자식의 값 중 최솟값을 저장함

이 때, 탐색 후 값을 업데이트 하다가 **$\alpha \geq \beta$** 되는 순간이 오는데, 그 때부터 나머지 자식노드는 탐색할 필요가 없어진다.
그 이유는, 상한선($\alpha$)과 하한선($\beta$)이 정해질 때, 그 부모노드의 상한선과 하한선을 넘지 못하면 부모노드를 업데이트 할 수 없기에, 업데이트를 할 가능성이 없다면 가지치기를 해버리는 것이다.

알고리즘의 이해가 안된다면 아래 영상을 참고하면 좋을 거 같다.

<YT id="_i-lZcbWkps" />

속성으로 빠르게 탐색하고 싶다면 이런 방식으로 탐색해도 된다.

<YT id="6qN5ReC2SUA" />

빠르게 업데이트 가능한 조건을 적어놓고, 그 조건이 업데이트가 절대로 불가능하다면 나머지 노드를 가지치기 하는 방식이다.

### 몬테카를로 트리 탐색 기법 (Monte Carlo Simulation)

![231022-003000](/posts/mid_02/231022-003000.png)

탐색 공간을 무작위 표본추출을 하면서 탐색 트리를 확장하여 가장 좋아보이는 것을 선택하는 휴리스틱 탐색 방법으로,
시간이 허용되는 동안 위의 4단계를 반복하여 시뮬레이션 및 트리를 확장한다.

1. 선택
 선택은 **트리 정책**을 적용하여 선택한다.
 정책은 개발자 마음대로 정하는 거지만, 보통 승률과 노드 방문횟수를 고려하여 선택한다.
 일반적으로 `승률이 높으며`, `방문횟수가 적은` 노드에 우선권을 부여한다 (UCB, Upper Confidence Bound 정책).

2. 확장
 단말 노드에서 트리 정책에 따라 노드를 추가한다.

3. 시뮬레이션
 기본 정책에 의한 `몬테카를로 시뮬레이션`을 적용한다.
 무작위 선택, 또는 약간 똑똑한 방법으로 게임이 끝날 때 까지 진행한다.

 <tip>
 `몬테카를로 시뮬레이션`
 
 특정 확률 분포로 부터 무작위 표본(또는 약간 똑똑한 방법으로)을 생성하고, 이 표본에 따라 행동을 하는 과정을 반복하여 결과를 확인하고 이 과정을 반복해 최정 결정을 하는 것.
 
 특정 상태의 유불리를 상태판단함수로 판단하는 것이 아닌, 시뮬레이션으로 판단하게 된다.
 </tip>

4. 역전파
 게임의 결과를 단말 노드에서 루트 노드까지 올라가면서 반영한다.

---

## 제약조건 만족 문제

주어진 제약조건을 만족하는 조합 해(combination solution)을 찾는 문제로 N-Queens problem과 같은 문제가 이에 해당한다.

### 백 트래킹 탐색 (Backtracking search)

깊이 우선 탐색(DFS)을 하는 것처럼 변수에 허용되는 값을 하나씩 대입해보고, 가능한 모든 값을 대입했는데도 만족하는 것이 없으면 이전 단계로 돌아가서 이전 단계의 변수에 다른 값을 대입하는 전형적인 백 트래킹 방식이다.

### 제약조건 전파 (Constraint propagation)

인접 변수 간의 제약 조건에 따라 각 변수에 허용될 수 없는 값들을 제거하는 방식으로, 이름 그대로 주변에 제약조건을 전파하여 선택 가능한 가지수를 줄여가는 방식이다.

![231022-004410](/posts/mid_02/231022-004410.png)

A에 1을 선택하는 순간 B\~D에 각각 제약사항이 전파되어 B\~D에서 선택할 수 있는 가지수가 제한된다.
여기서 B가 3을 선택하는 순간 C, D에 각각 제약사항이 또 전파되는데, 이 때 C는 더이상 아무것도 선택할 수 없기에 이전 스탭에서 다른 제약사항을 걸어야 한다.

---

## 최적화

여러가지 가능, 혀용되는 값들 중에서 주어진 기준을 가장 잘 만족하는 것을 선택하는 것으로, 크게 `조합 최적화`와 `함수 최적화`로 나뉜다.

### 조합 최적화

TSP와 같이 주어진 항목들의 조합으로 해가 표현되는 최적화 문제로, 이 경우에는 경로의 길이를 최소화 하는 문제이다.

![231022-005505](/posts/mid_02/231022-005505.png)

이를 달성하기 위해 생물의 진화를 모방한 집단 기반 확률적 탐색 기법인 `유전 알고리즘`을 사용하기도 한다.

개체는 염색체로 표현되며 다음과 같이 기술된다.

![231022-005704](/posts/mid_02/231022-005704.png)

이런 염색체들의 집합을 `모집단`이라고 하는데, 이런 모집단(후보해)가 문제의 해로서 적합한 정도를 `적합도 함수`가 판단하게 되고, 적합하다면 최적 개체로서 알고리즘이 종료되지만, 적합하지 않다면 **진화의 과정**을 거치게 된다.

모집단이 진화를 할 때는 우선 `부모 모집단` 중 개체를 선택하게 되는데, **가능한 높은 적합도의 개체가 선택되도록 확률을 높게** 조정한다.
자연선택과 같이 **랜덤**한 요소가 있어야 하기에 반드시 적합한 녀석이 선택되지는 않는다.

이후에는 선택된 부모 개체가 `유전 연산`을 거쳐 자식 개체를 양산하게 되는데, 유전 연산에는 다음과 같은 연산을 고려할 수 있다.

![231022-010201](/posts/mid_02/231022-010201.png)

이후에는 생성된 여러 자식 개체를 이용해서 `세대를 교체`하게 되는데, **최대한 많은 우수한 계체가 다음 세대에 유지**될 수 있도록 `엘리트주의`를 적용한다.

### 목적 최적화

어떤 목적 함수(Objective function)가 있을 때, 이 함수를 최대로 하거나 최소로 하는 변수 값을 찾는 최적화 문제이다.

![231022-010440](/posts/mid_02/231022-010440.png)

`최소 평균제곱법`을 사용해서 회귀(Regression) 문제의 최적함수를 찾거나,

![231022-010602](/posts/mid_02/231022-010602.png)

함수의 최소값 위치를 찾는 문제에서 `경사 하강법`과 같은 방법을 사용할 수 있다.

게임 트리를 탐색하는 기법과 최적화에 대해 알아봅니다.

게임에서의 탐색 및 최적화

## 상태공간

문제 해결 과정에서 초기 상태로부터 도달할 수 있는 모든 상태들의 집합을 의미한다.
한 마디로 `문제의 해가 될 가능성`이 있는 모든 상태들의 집합을 의미한다.

## 탐색

상태공간에서 최적의 해를 찾기위해 공간을 체계적으로 찾아보는 것을 의미한다.
탐색은 아래와 같은 방식으로 크게 구분지을 수 있다.

1. 맹목적 탐색
2. 정보이용 탐색

이렇게 구분짓는 이유는 탐색의 방식에 따라 달라지는데,
탐색 방식이 다양해 질 수 밖에 없는 이유는 일반적인 문제에서는 상태공간이 매우 크기 때문에
미리 공간 그래프를 그릴 수 없어 탐색 과정에서 그래프를 생성할 수 밖에 없기 때문이다.

---

## 맹목적 탐색

정해진 순서에 따라 상태공간 그래프를 점차 생성해 가면서 해를 탐색하는 방법을 의미한다.

### 깊이 우선 탐색 (Depth-first search)

![231021-223045](/posts/mid_01/231021-223045.png)

초기 노드부터 깊이가 깊어지는 방향으로 우선 탐색하는 기법.
더이상 진행할 수 없다면 백 트리킹으로 돌아와 다음 노드 탐색.

루트 노드에서 현재 노드까지의 경로 하나만 유지한다는 특징이 있기에 메모리 공간 사용이 효율적이라는 장점이 있다.
하지만, 깊이가 무한히 깊어지는 무한루프의 가능성 때문에 항상 최단 경로의 해를 보장할 수 없다는 단점이 있다.

### 너비 우선 탐색 (Breadth-first search)

![231021-223311](/posts/mid_01/231021-223311.png)

초기 노드부터 시작하여 모든 자식 노드를 확장하여 탐색하는 기법.
목표 노드가 없다면 단말 노드에서 다시 자식노드 확장 탐색.

최단 경로의 해를 보장하지만, 메모리 효율적이지 못하다.

### 깊이 제한 탐색 (Depth-limited search)

![231021-223510](/posts/mid_01/231021-223510.png)

기본적인 탐색 방식은 깊이 우선 탐색 방식임.
단, 깊이에 제한을 둬서 특정 깊이 이하로는 탐색을 진행하지 않고 백 트래킹 하는 것이 특징임.
특정 깊이에서 목표를 찾지 못한 경우 깊이를 늘려가며 처음부터 다시 탐색을 진행함.

최단 경로의 해를 보장하며, 메모리 사용도 효율적이다.
상위 노드는 반복해서 탐색하기에 약간의 비효율성이 있으나, 무시할만한 수준임.

즉 맹목적 탐색시에는 이 방식을 우선적으로 고려하는 것이 좋음.

---

## 정보이용 탐색

휴리스틱한 방법으로 목표까지의 예상 비용을 구하고, 그 값에 의거해 순간순간 최선의 선택을 해가며 탐색하는 방법을 의미한다.

<tip>
 `휴리스틱 (heuristic)`
 신속하게 어림짐작 하는 것.
</tip>

### 언덕 오르기 방법 (Hill climbing method)

![231021-224206](/posts/mid_01/231021-224206.png)

현재 노드에서 휴리스틱에 의한 평가값이 가장 좋은 이웃 노드 하나를 확장해가는 탐색기법.
단, 국소 최적해에 빠질 가능성이 있다.
(경사 하강법과 유사)

### 최상 우선 탐색 (Best-first search)

확장 중인 노드들 중에서 목표 노드까지 남은 거리가 가장 짧은 노드를 확장하여 탐색하는 기법.
일종의 그리디한 방식임.

![231021-224403](/posts/mid_01/231021-224403.png)

예시로 휴리스틱 함수를 제자리가 아닌 타일의 개수라고 할 때, 다음과 같은 순서로 탐색을 진행하게 된다.

> a &rarr; c &rarr; e/f &rarr; h &rarr; j

### 빔 탐색 (Beam search)

최상 우선 탐색(BFS) 의 확장판으로, 휴리스틱에 의한 평가값이 우수한 일정 개수(K개)의 확장 가능한 노드만을 메모리에서 관리하면서 탐색.

![231021-224723](/posts/mid_01/231021-224723.png)

예시로 K=2일 때, A~E를 일단 탐색하고, 평가값이 우수한 B, E를 제외한 노드는 메모리에서 제거하며 B, E에서 그 자식노드에 대해 같은 방식을 적용하며 탐색한다.

### A* 알고리즘 (A-star algorithm)

최상 우선 탐색(BFS) 의 개선판으로, 휴리스틱에 의한 평가값 + 현재까지의 코스트의 결과인 휴리스틱한 전체 비용을 기준으로 탐색하는 기법.

![231021-225028](/posts/mid_01/231021-225028.png)

최초 상태를 탐색한 후, 그 자식 노드 3개의 휴리스틱한 전체 비용을 계산하면 `1(현재까지의 코스트)+3(휴리스틱 평가값)`의 값을 갖는 가운데 자식 노드가 비용이 가장 작기에 다음 탐색 대상으로 한다.

이런 식으로 **탐색한 모든 노드를 메모리 상에서 관리**하며, 그 순간 휴리스틱 전체 비용이 가장 낮은 노드를 다음 탐색 대상으로 삼는다.

상태공간과 탐색의 의미와 예시를 알아봅니다.

상태공간 & 탐색

3학년 2학기 인공지능 수업 아카이브

// 대학 - 인공지능