문제:

풀이방법:

트리 구조를 알고 있는지 물어보는 문제인 것 같다. 따라서 Tree라는 class를 만들고, 이 클래스는 x,y 좌표와 left, right를 만들어서 node 연결을 하도록 한다.

우선 부모 노드를 찾고, 자식 노드들을 알기 위해서 정렬을 하는 작업을 먼저 한다. y가 큰 순으로, x가 작은 순으로 정렬하도록 하기 위해 sorted의 key를 사용하였다.

이렇게 root를 찾고 남은 node들은 root부터 시작하여서 x 좌표를 비교해서 이 값이 left 혹은 right인지 확인을 한다. 만약 현재 node에서 이미 left나 right 값이 있다면 그 노드로 이동해서 다시 비교를 하고 지정해주는 작업을 계속해서 반복한다. 따라서 얼마나 많은 반복을 해야할지 모르기 때문에 while을 사용하였으며, 연결을 완료하면 break로 나오도록 하였다.

node 연결을 마친 뒤에 preorder와 postorder는 정의대로 재귀를 사용해서 배열에 담아서 return 하도록 한다. 다만 이 때 많은 node들이 있으면 python의 재귀 메커니즘상 런타임 에러가 발생한다고 한다.

(python은 재귀가 최대 1000회로 제한되어 있다.)

따라서 이를 해결하기 위해서 sys.setrecursionlimit()를 사용해서 최댓값을 넉넉히 늘려주도록 한다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/42892

문제:

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다.

제일 왼쪽 도시에서 6리터의 기름을 넣고 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2x5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고 (3x2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1x4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다.

또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2x5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4x2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

입력:

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2<=N<=100.000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.

출력:

표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다.

풀이방법:

제일 적은 비용을 지불하기 위해서는 제일 가격이 낮은 주유소에서 남은 거리에 해당하는 기름을 다 넣어야 한다.

하지만 왼쪽에서 오른쪽으로 순차적으로 진행이 되는 것이으므로 지금까지 이동한 곳에서 가장 낮은 가격의 주유소의 기름을 넣어야 한다. 예시로 보면 다음과 같다.

- 첫 도시의 주유소에서 가격이 5이고 다른 선택지가 없고 다음 도시까지는 2km를 가야하기 때문에 10원(2x5)을 지불한다. (minP =5)

- 두번째 도시에 도착해서 가격을 보니 2원이다. 따라서 minP를 2로 바꾸고 다음 주유소까지 가기 위해 6원(3x2)을 지불한다.(minP=2)

- 세번째 도시의 가격은 4원이다. 따라서 두번째 도시에서 미리 기름을 더 넣어두고 오는 것이 이득이였기 때문에 마지막 도시까지 이동하는 것도 두번째 도시에서 넣고 와야 한다. 따라서 2원(1x2)을 추가 지불한다.

따라서 최저 비용은 18원이 된다.

이를 반복문 하나로 표현하였고, 인덱스를 편하게 맞춰주기 위해서 간격배열에 0을 임의로 추가하였다.(답에 영향을 주진 않는다.)

문제링크:

https://www.acmicpc.net/problem/13305

아래 모든 내용들은 Christopher Bishop의 pattern recognition and machine learning에서 더 자세히 볼 수 있습니다.

Mixture models and EM

• 관측 변수와 잠재 변수들에 대한 결합 분포를 정의한다
  • 그러면 이에 해당하는 관측변수들만의 분포는 주변화를 통해서 구할 수 있다.

• 복잡한 관측 변수들에 대한 주변 분포를 상대적으로 더 다루기 쉬운 관측 변수와 잠재 변수 확장 공간상의 결합 분포를 통해서 표현할 수 있도록 한다.
  • 잠재 변수를 도입하면 단순한 원소를 복잡하게 만들 수 있다.

• 혼합 모델은 clustering에서도 사용가능하다.
  • 대표적으로 K-means 알고리즘이 있다.

• 일반적인 혼합 모델에서 가장 많이 사용하는 알고리즘인 EM알고리즘에 대해서 알아본다.

K-means clustering

• 다차원 공간 데이터 포인트들에서 해당 데이터들이 어떤 군집에 해당하는지 알아내는 작업을 수행한다.

• 데이터 집합 (x₁,...,x_N)를 고려하자.

  • 이는 D차원을 가지며 K개의 집단으로 나눈다.

  • μ_k는 k번째 클러스터의 중심을 나타내는 값이라고 하자.

    • 각각의 데이터 포인트로부터 가장 가까운 μ_k까지 거리의 제곱합들이 최소가 되도록 하는 것이 목표다.

• 데이터 포인트들을 집단에 할당하는 것을 설명하는 표현법을 정의한다.

  • 변수 r_nk ∈ 0,1을 정의한다.
  • 만약 x_n이 집단 k에 할당된다면 r_nk=1이며 아닌 경우는 0이라 한다.
    • 이를 one hot encoding이라 한다.

• 목적 함수를 정의한다. 이를 distortion measure(뒤틀림 척도)라고도 부른다.

  

• 이는 같은 클러스터에 속하는 각각의 점들로부터 그 클러스터의 평균과의 거리의 합을 제곱한 함수를 뜻한다.

• 이제 여기서 r_nk, μ_k를 구해야 한다.

  • 물론 J의 값이 최소가 되어야 한다.
  • 반복적인 절차를 통해서 이를 해결하는 방법을 알아본다.

• r_nk 와 μ_k 를 구하기 위해 크게 2개의 단계로 나누게 된다.

  • 먼저 μ_k의 임의의 초기값을 설정한다.
  • 첫 번째 단계에서는 이 μ_k 값을 고정한 채로 J를 최소화하는 r_nk 값을 구한다.
  • 두 번째 단계에서는 r_nk를 고정하고 μ_k를 구한다.
  • 값이 수렴할 때까지 이 두 단계의 최적화 과정을 반복하게 된다.
  • 각각의 두 단계를 E(expectation, 기댓값) 단계와 M(maximization, 최대화) 단계로 이를 합쳐 EM 알고리즘이라고 부른다.

• 이제 E,M을 이용한 K-means 알고리즘을 알아본다.

• r_nk를 구하는 과정을 알아본다.

  • J가 r_nk에 대한 선형 함수이므로 쉽게 최적화 할 수 있고, 닫힌 형태의 해를 얻을 수 있다.

  • 서로 다른 n에 해당하는 항들은 각자가 독립적이므로 각각의 n에 대해서 따로 최적화가 가능하다.

  • 각 클러스터 중심과 데이터 포인트들의 거리를 측정해서 가장 가까운 클러스터를 선택한다.

    

• 이제 μ_k를 구해보도록 한다. 물론 r_nk는 고정한다.

  • 목적 함수 J는 μ_k에 대해서 제곱 함수이므로 미분을 통해 최솟값이 되는 지점을 얻을 수 있다.

  

• 이 식을 μ_k에 대해 풀면 다음과 같다.

  

  • 이 식의 분모는 집단 k에 할당된 포인트들의 숫자에 해당한다. 결국 집단 k에 할당된 모든 데이터 포인트들의 평균이라는 것이다. 따라서 이러한 이유로 이 과정을 K -means 알고리즘이라 한다.

• 그림을 통해서 K-means가 수렴하는 과정을 살펴보도록 한다.

  

• 그림으로 보면 쉽게 이해 할 수 있다.

  • 우선 K=2로 설정을 하였고, (a)에서 임의의 μ_k 두 개를 설정한 것을 알 수 있다.
  • (b)과정에서 두 개의 평균 값을 이용해서 E 과정을 거쳤고, (c)에서 M 과정을 거친다.
  • 계속해서 EM 과정을 반복하고, 수렴 조건이 만족할 때까지 반복한다.

  

• 위 그림은 EM 과정을 반복할 때마다 목적 함수 J의 값이 줄어드는 것을 나타내는 단계이다.

• 각 단계에서 J의 값이 감소하기 때문에 수렴은 보장되어 있지만 전역 최솟값으로 간다는 보장은 존재하지 않는다.

• 평균 μ_k의 초기 값이 어디에 위치하는지에 따라 성능의 차이가 발생한다.

  • 실제 반복 횟수의 차이가 발생하게 된다.

• K-means 알고리즘은 유클리드 거리를 사용하고 있기 때문에 매우 느릴 수 있다.
• 따라서 이를 빠르게 하는 방법들이 있다.
  • 서로 근접한 포인트들이 같은 서브트리에 속하게 하는 방식의 트리와 같은 데이터 구조를 미리 계산한다.
  • 삼각 부등식을 사용해서 불필요한 거리 계산을 줄인다.

• K-means 알고리즘은 모든 데이터 포인트들과 평균 간의 유클리드 거리를 계산해야 하기 때문에 느릴 수 있다.
  • 따라서 유클리드 거리를 사용할 수 있어야 하고, outlier에 영향을 많이 받는 알고리즘이다.
• 따라서 이러한 문제를 해결할 수 있도록 k-medoids 알고리즘, 중간값을 활용하도록 한다.

k-medoids 알고리즘

• 유클리디안 거리 측정 대신 v(x,x')를 정의해서 사용한다.

• 목적 함수는 다음과 같다.

  

• E 단계은 앞서 살펴본 방식과 동일한 방법으로 O(NK)가 된다.

• M 단계는 이전보다 더 복잡할 수 있다.

  • v 의 비용이 이전보다 커지게 되고, 연산량을 줄이기 위해서 중심점을 클러스터에 속하는 데이터 중 하나로만 선정하기도 한다.
  • 이 경우 O(N_k²)의 비용이 필요하게 된다.

• K-means 알고리즘은 모든 데이터 포인트들이 정확하게 단 하나의 집단에만 할당된다.
  • 하지만 가끔 모두 비슷한 거리에 위치에 어디에 속하게 해야 할지 애매할 수 있다.
  • 이러한 경우 확률적인 접근 방식을 이용하여 특정 클러스터에 대한 할당을 클러스터에 포함될 확률값으로 결정할 수 있다.

혼합 가우시안

• 앞서 가우시안 성분들을 선형으로 중첩시킨 가우시안 혼합 모델을 사용하면 단일 가우시안을 사용할 때보다 더 다양한 종류의 밀도 모델들을 표현할 수 있다.

• 이번 절에서는 이산 잠재(latent) 변수들을 이용해서 혼합 가우시안 모델을 만든다.

• 가우시안 혼합 분포를 다음과 같이 선형 중첩 형태로 적을 수 있다.

  

• 이제 K차원을 가지는 이산 확률 변수 z를 도입한다. 이 변수는 특정 원소 z_k는 1이고 나머지는 0인 one-hot encoding 방법을 사용한다.

• 결합 분포는 다음과 같이 정의 한다.

  • p(x,z)=p(z)p(x|z)

    

  • 이제 z_k의 주변 분포를 혼합 계수 π_k를 사용하여 정의한다.

    

  • 매개변수 π_k는 다음의 두 제약 조건을 만족해야 한다.

    

  • 또한 z가 one-hot-encoding을 사용하므로 이 분포를 다음의 형태로 적을 수 있다.

    

• 이와 비슷하게 특정 z 값이 주어졌을 때의 x에 대한 조건부 분포는 다음 형태의 가우시안 분포다.

  

• 이는 다음의 형태로 적을 수 있다.

  

• 결합 분포는 p(z)p(x|z)의 형태로 주어진다. 이때 모든 가능한 z의 상태에 대한 결합 분포를 합산함으로써 x의 주변 분포를 구할 수 있다.

• x의 주변 분포는 식 9.7 형태의 가우시안 혼합 분포가 된다. 여러 개의 값 x₁, ... x_N을 관측했을 경우, 주변 분포를 p(x)의 형태로 표현했기 때문에 모든 관측된 데이터 포인트 x_n에 대해서 해당 잠재 변수 z_n이 존재한다.

• 명시적으로 잠재 변수를 사용하는 가우시안 혼합 분포를 보았다.
  • 이 결과로 주변 분포 대신에 결합 분포를 직접 활용할 수 있다.
  • 이것이 계산 과정을 매우 단순하게 만들어 준다.
• x가 주어졌을 때의 z의 조건부 확률을 구하는 것도 중요하다. 그 확률은 다음과 같이 정의하도록 한다.

• 우리는 π_k가 z_k=1일 때의 사전 확률 값이라는 것을 안다.
  • 이제 γ(z_k)는 관찰 데이터 x가 주어졌을 때의 사후 확률 값이 된다.
  • 이를 성분 k에 대한 responsibility라고 한다.

• ancestral sampling를 통해서 가우시안 혼합 모델에 부합하는 random 표본을 추출해 내는 것이 가능하다.

  • 이를 위해서 z 값 하나를 주변 분포 p(z)에서 추출하여 z_hat이라고 한다.
  • 조건부 분포 p(x|z_hat)로부터 x 값을 추출한다. 정확한 내용은 11장에서 소개한다.

  

• 결합 분포로부터의 표본들은 (a)에 해당한다. 여기서 x 값에 해당하는 포인트들을 그리고 이에 대한 해당 z 값에 따라 그 포인트를 색칠(빨강, 초록, 파랑)하는 방식을 사용했다.

  • 어떤 가우시안 성분이 x 값을 만들어 낸 책임이 있는지 표현할 수 있다.

• 주변 분포 p(x)로부터 표본들은 z 값을 무시하고 결합 분포에서 표본들을 추출해서 생성할 수 있고 이는 (b)에서 표시되어 있다.

• 데이터 포인트 각각에 대해서 데이터 집합이 생성된 혼합 분포의 각 성분에 대한 사후 분포를 구하는 방식을 이용하면 합성 데이터를 이용해 책임 정도를 표현할 수 있다.

  • 즉 각 색의 비율로 표현할 수 있고, (c)에 표현되어 있다.

• (a)와 같은 결과를 complete하다고 표현하고, (b)와 같은 경우엔 imcomplete 하다고 표현한다.

9.2.1 최대 가능도 방법

• 관찰 데이터가 x₁,...,x_N으로 주어져 있다.

  • 이 데이터 집합은 N x D 행렬 X로 표현한다. (N은 sample 수,D는 한 sample의 차원)

  • 이와 비슷하게 해당 잠재 변수들은 N x K 행렬 Z로 표현할 수 있다.

  • 모든 데이터가 독립이라고 가정하면 그래프를 이용해서 표현할 수 있다.

    

  • 이제 로그 가능도 함수는 다음과 같이 주어진다.

    

• MLE를 통해 이 함수를 최대화하기 위해 발생하는 문제들에 대해 알아본다.

특이점(singularity) 문제

• 공분산 행렬이 Σ_k=σ²_kI 인 가우시한 혼합 모델을 고려한다.

• j번째 성분이 평균으로 μ_j를 가지며, 이것이 데이터 포인트들 중 하나의 값과 정확히 일치한다고 하자.

  • μ_j=x_n이다.

• 이 데이터 포인트는 가능도 함수 식의 항에 다음과 같이 기여한다.

  

• 만약 σ_j가 0으로 간다면 무한대의 값을 가지게 될 것이고, 로그 가능도 함수를 최대화하는 것은 적절하지 않다.

  • 이러한 특이점들은 항상 존재하고, 하나가 문제가 발생해도 이러한 문제는 발생할 수 있다.

• 하지만 단일 가우시안 분포의 경우에는 문제가 없었다.

  • 하나의 위치로 거의 수렴하는 단일 가우시안 모델은 평균 값 외에는 밀도 값이 0이 된다.
  • 곱 인자에 기여하게 되므로 전체 가능도 함수값이 0 값을 가지게 될 것이다.
    • 따라서 모든 데이터 포인트들에 유한한 확률을 부여할 수 있게 된다.

• 사실 MLE 방식은 오버 피팅 문제가 존재하는데 베이지안 접근법을 활용하면 이러한 문제가 발생하지 않는다.

• 평균값을 임의로 선택한 값으로 설정하고, 공분산값을 임의의 큰 값으로 설정한 후 계산을 진행하는 방식을 사용한다.

식별 문제(identifiability)

• 최대 가능도 해에 대해서 K!개의 동일한 해가 존재할 것이다.
  • K개의 매개변수들을 K개의 성분들에 할당하는 K!개의 서로 다른 방법들이 있다.

이 문제는 12장에서 더 자세히 다루도록 한다.

9.2.2 가우시안 혼합 분포에 대한 EM

• 잠재 변수를 포함한 모델의 최대 가능도 해를 찾기 위한 좋은 방법 중 하나는 EM 알고리즘이다.

• 우선 가우시안 혼합 모델의 맥락에서 약식으로 EM 알고리즘을 살펴보도록 한다.

• 가능도 함수의 최댓값에서 만족되어야 하는 조건들을 적는 것으로 논의를 해본다.

  • 식 9.14를 가우시안 성분의 평균 μ_k에 대해 미분한 값을 0으로 설정하면 다음을 얻게 된다.

    

• 양변에 Σ_k를 곱하고 전개하면 다음을 얻게 된다. (이 때 행렬이 정칙이라고 가정한다.==역행렬이 존재한다.)

  

• N_k는 집단 k에 할당되는 유효 데이터 포인트의 숫자로 해석한다.

• 수식을 자세히 살펴보면 사실 k번째 가우시안 성분의 평균은 데이터 집합의 모든 포인트들의 가중 평균으로 구할 수 있다.

  • 이때 데이터 포인트 x_n에 대한 가중치는 x_n을 생성하는 데 있어서 성분 k의 책임 정도에 해당하는 사후 확률로 주어진다.

• 위와 동일하게 Σ_k에 대한 미분값을 0으로 놓고 단일 가우시안 공분산 행렬에 대한 해를 바탕으로 비슷한 추론 과정을 거치면 다음과 같다.

  

• 이는 데이터 집합에 근사한 단일 가우시안 분포의 경우와 비슷하다.

  • 다른점은 각각의 데이터 포인트들이 해당 사후 확률로 가중되며, 해당 성분에 연관된 유효 데이터 포인트의 숫자가 분모에 추가된다는 점이다.

• 마지막으로 π_k에 대해 최대화를 해보도록 한다. 이 때에는 이 값들의 합이 1이어야 한다는 제약 조건식을 생각해야 한다. 따라서 라그랑주 승수법을 사용하도록 한다.

  

• 양변에 π_k를 곱하면 γ(z_nk)가 나오게 된다. 이를 다시 정리하면 다음과 같다.

  

• 결국 k번째 성분의 혼합 계수는 데이터 포인트들을 설명하기 위해 취한 responsibility를 평균한 값이 된다.

• 이렇게 얻은 평균, 분산, 혼합 계수는 닫힌 형태의 해를 제공하지 못하는데, γ(z_nk)들이 복잡한 방식으로 종속되어 있기 때문이다.

  

EM 알고리즘 적용

• EM 알고리즘은 반복적인 방법을 이용하여 값을 추정하는데, GMM에서는 다음과 같이 처리한다.
  • (a)와 같이 random한 값으로 평균, 분산을 초기화 한다.
  • E 단계
    • 현재 값을 사용하여 사후 확률 z를 추정한다. -> (b)
  • M 단계
    • E 단계에서 계산한 값을 이용하여 MLE를 통해 평균, 분산, 혼합 계수의 값을 다시 추정한다. -> (c)
  • 반복
    • 수렴 조건이 만족할 때까지 E, M을 반복 (d) , (e) , (f)에 해당한다.
• EM 알고리즘이 수렴을 달성하기 위해 필요로 하는 반복 횟수가 K-means 알고리즘에 비해 훨씬 많다.
  • 따라서 K-means 알고리즘을 먼저 수행해서 적합한 초기값을 찾아내고, EM 알고리즘을 적용하는 것이 일반적이다.
• K-means와 동일하게 특이점 문제가 발생하지 않도록 조심해야 한다.
• 여러 개의 지역적 최댓값이 있으므로 EM 알고리즘은 이들 중 가장 큰 값을 찾는 것을 보장하지 못한다.

문제:

직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 가장 적은 수의 나무를 심고 싶다.

편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.

예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다. 심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.

입력:

첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다. (3<=N<=100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 100,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르다.

출력:

모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.

풀이방법:

N개의 최대공약수를 구하는 문제라고 생각하였다. 처음에 가로수가 심어져 있는 위치를 받았을 때, 각 가로수 사이의 간격을 측정해서 배열에 담도록 하였다. 이들을 최대한 균일하게 자르기 위해서는 이 수들의 최대공약수를 구해야 한다고 생각했다. 따라서 temp라는 배열에 복사를 하고 while문을 통해서 N개 수 최대공약수 문제를 풀었다.

마지막으로는 이렇게 구한 최대공약수를 통해 각 간격마다 나누어 주어서 심어야 할 가로수의 개수를 구했다.

문제링크:

https://www.acmicpc.net/problem/2485

문제:

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1<=N<=20, |S|<=1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력:

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

풀이방법:

알고리즘 분류가 브루트 포스로 되어 있었기 때문에 가능한 모든 경우의 수를 만들고자 하였다. 따라서 itertools의 combinations을 사용하였다. itertools.combinations( iterable, n)과 같이 사용하며 iterable한 객체로 반환을 한다. 따라서 이를 반복문으로 넣고 합했을 때 s가 되는 경우에 answer를 하나씩 올렸다.

문제링크:

https://www.acmicpc.net/problem/1182

아래 모든 내용들은 Christopher Bishop의 pattern recognition and machine learning에서 더 자세히 볼 수 있습니다.

4.2 확률적 생성 모델

• 앞서 설명했던 용어들을 다시 한 번 정리하고 넘어간다.

  • 사후 확률 (posterior) : p(C_k|x)

    • 임의의 데이터 x가 주어졌을 때 이 데이터가 특정 클래스에 속할 확률

  • 클래스-조건부 밀도(class-conditional density) : p(x|C_k)

    • 특정 클래스에서 입력된 하나의 데이터 x가 발현될 확률

  • 가능도 함수 p(X|C_k)

    • 주어진 샘플 데이터가 실제 발현될 확률값을 주로 사용하며, 로그를 불이는게 일반적이다.

• 생성적 접근법을 사용해서 클래스가 2 개인 경우를 고려해본다. 그러면 C₁에 대한 사후 확률을 다음과 같이 적을 수 있다.

  

• σ(a)는 로지스틱 시그모이드 함수로서 다음과 같이 정의된다.

  

• 시그모이드 함수는 다음과 같이 그려진다.

  

• 시그모이드 함수는 다음과 같은 대칭성을 만족한다.

  

• 시그모이드는 0과 1 사이의 값으로 수렴을 하므로, 확률 값으로 고려를 해도 되고, 모든 점에서 연속이기 때문에 미분 가능해 수학적 전개에도 매우 편리하다.

• 로지스틱 시그모이드의 역(inverse)은 다음과 같다.

  

• 이를 로짓이라고 부른다.

• K > 2인 경우에도 식을 확장할 수 있다.

  • 이를 일반 선형 모델이라고 부른다.

    

  • a_k는 다음과 같다

    

  • 이를 정규화된 지수 함수라 하며, 다중 클래스 분류에 사용되는 식이 된다. 이를 softmax function이라고도 한다.

    • 평활화된 버전의 최댓값 함수에 해당한다.

4.2.1 연속적인 입력값(Continuous inputs)

• 클래스별 조건부 밀도가 가우시안이라고 가정하자.

  • 모든 클래스들이 같은 공분산 행렬을 공유한다고 가정하자.

  

• 이를 class가 2 개인 경우에 대해 고려해보자.

  

• 위 식은 σ(a)에 정의되어 있었다.

  

• 위와 같은 내용을 얻을 수 있다.

• x에 대한 2차 term이 모두 사라지면서 직선 식을 얻게 되었다.

  • 공분산 행렬을 공유한다는 가정으로 인해

• 같은 분산을 가지는 두 개의 가우시안 분포가 만나는 지점은 당연히 직선의 형태일 것이다.

  

• 왼쪽 그림은 2-class에서의 확률 밀도를 표현한 것이다.

  • 공분산이 동일하므로 모양이 같고, 따라서 경계면은 직선일 것이다.

• 이제 이를 K 클래스 문제로 확장하면 어떻게 될까?

  

• 계산을 간단히 하기 위해 공분산이 동일하다고 가정했지만 다르면 어떻게 될까?

  • 경계면을 구하는 식에서 이차항이 남게 되어 경계면이 곡선이 될 수 있다.

4.2.2 최대 가능도 해

• 클래스 조건부 밀도의 매개변수적 함수 형태를 명시하고 나면 최대 가능도 방법을 이용해서 매개변수들의 값과 사전 클래스 확률을 구할 수 있다.

  • 이를 위해 관측값 x와 그에 대한 데이터 집합이 필요하다.

• 두 개의 클래스가 있는 경우를 고려해보자.

  • 각각의 클래스들은 가우시안 클래스 조건부 밀도를 가지며, 공분산 행렬은 공유한다.

• t_n=1인 경우 C₁로, t_n=0인 경우 C₂로 분류한다.

• 따라서 가능도 함수는 다음과 같다.

  

• π 구하기

  • 로그 가능도 함수를 π에 대해 미분하여 관련된 항목만 모으면 된다.

    

• 여기서 N₁은 C₁에 속하는 샘플의 수이고, N₂은 C₂에 속하는 샘플의 수이다.

• π는 정확히 C₁에 속하는 샘플의 비율을 의미하게 된다.

• μ 구하기

  • 마찬가지로 로그 가능도 함수를 각각의 μ 값으로 미분하여 값을 구한다.

    

• 이 식을 0으로 놓고 μ₁, μ₂에 대해 풀면 다음을 얻을 수 있다.

  

• Σ 구하기

  • 역시 로그 가능도 함수를 미분하여 값을 구한다.

    

• 여기서 S는 다음과 같다.

  

4.2.3 이산 특징

• 입력 값이 연속적이지 않고 Discrete이라고 가정한다.

• 입력 데이터가 D차원이라면 각 class별로 얻을 수 있는 확률 분포의 실제 x의 Discrete 범위는 2^D개이다.

  • 이 중 독립 변수는 2^D-1이다. (합산 제약 조건 때문)

• 나이브 베이즈 가정을 사용했고 각 class C_k에 대해 조건부일 때 독립적으로 취급한다. 따라서 다음과 같다.

  

• 이 식을 4.63에 대입한다.

  

• 이는 다시 입력 변수 x_i에 대해 선형 함수다.

• 2-class에서는 시그모이드를 도입하면 동일할 것이다.

4.2.4 지수족

• 지금까지 사후확률의 경우 항상 sigmoid, softmax를 이용해서 모델링을 할 수 있었다.

  • 이를 더 일반화 시켜보자.

• 클래스 조건부 밀도가 지수족 분포를 따른다면 가능하다.

  • 지수족 분포를 따를 경우의 확률 분포는 다음의 형태로 적을 수 있다.

    

• 이 중 u(x) =x인 부분 집합들만 고려한다. 여기에 척도 매개변수 s를 도입해서 제한된 형태의 지수족 분포 클래스 조건부 밀도를 구할 수 있다.

• 각각의 클래스들의 각자의 매개변수 벡터를 가지지만, 척도 매개변수 s는 공유한다고 가정한다.

• 2-class에서 사용한 a_k에 대입하여 전개해본다.

  

• K-class에도 비슷하게 나오며 모두 선형 식임을 알 수 있다.

4.3 확률적 판별 모델

• 2-class 문제에 대해서는 사후 확률을 시그모이드 함수로 표현하고, k-class 문제에 대해서는 softmax 함수로 제동되는 것을 확인하였다.

• 다른 방식을 생각해본다

  • 선형 모델의 함수 형태를 명시적으로 사용하고, 최대 가능도 방법을 적용해 직접 구한다.

  • 이를 위해 iterative reweighted least squares, IRLS라고 한다.

• 앞에서 설명했던 간접적으로 매개변수를 찾는 방식은 생성적 모델의 예시이다.

• 이번 절에서는 판별적 훈련의 예시를 살펴볼 것이며, 적응 매개변수의 숫자가 더 적으며, 더 나은 예측 성능을 보일 수도 있다.

4.3.1 고정된 기저 함수

• 지금까지는 원 입력 벡터 x에 대해 직접적으로 적용되는 분류 모델에 대해 고려했다.

• 이제는 비선형 기저 함수를 이용하여 입력 값을 변환하는 형태를 사용한다.

  

• 위의 그림은 비선형 기저 함수를 이용하여 변환된 데이터를 선형 판별하는 것을 묘사하고 있다.

  • 왼쪽 그림은 최초 입력에 대한 공간을 나타내며 2개의 클래스로 구성되어 있음을 알 수 있다.

  • 오른쪽은 입력 데이터가 변환된 뒤, 선형 판별식에 의해 클래스가 구별되고 있음을 보여준다.

  • 왼쪽에서의 검은 원은 오른쪽에서는 선형으로 바뀐 것을 알 수 있다.

• ϕ₀(x)=1를 추가해서 w₀가 bias 역할을 수행하도록 한다.

• 실제의 여러 문제들에서는 클래스 조건 밀도들 사이에 상당한 중첩이 있다.

  • 각각의 값이 0과 1이 아닌 경우가 발생한다.

  • 하지만 ϕ(x)는 이러한 중첩 현상을 제거해주진 못한다.

    • 그렇지만 적절한 비선형성을 선택한다면 사후 확률을 모델링하는 과정이 쉬워지게 된다.

4.3.2 로지스틱 회귀

• 2-class에서 일반화된 선형 모델에 대해 알아보도록 하자. 분류에 대한 사후 확률 값은 로지스틱 회귀로 기술되는 것을 확인했다. 식은 다음과 같다.

  

• 여기서 σ 는 로지스틱 시그모이드라고 부른다.

• 기저 함수 ϕ 가 M차원이면 M개의 조절 가능한 매개변수를 가게 된다.

  • 최대 가능도 방법을 이용하여 가우시안 클래스 조건부 밀도를 근사했다면 평균값에 대해서는 2M개, 공분산 행렬에 대해서는 M(M+1)/2개의 매개변수를 가지게 되었을 것이다.

  • 사전 분포까지 고려한다면 M(M+5)/2+1 개의 파라미터가 필요하게 된다.

  • 따라서 M이 클 경우 로지스틱 회귀 모델을 직접 다루는 것이 더 유리할 수 있다.

• 최대 가능도 방법을 통해서 로지스틱 회귀 모델의 매개변수를 구할 수 있다.

  • 이를 위해서는 로지스틱 시그모이드의 미분값을 구해야 하고, 자세한 증명은 생략하도록 한다.

    

• 가능도 함수를 다음과 같이 적어보자.

  

  • n=1,2,...,N에 대해 t_n={0,1}이고, ϕ_n=ϕ(x_n)이다.

  • 가능도 함수의 음의 로그값을 취하여 오류 함수를 정의한다.

    

  • 이러한 형태를 cross entropy error function이라고 한다.

• 이를 w에 대하여 오류 함수의 기울기를 계산하면 다음과 같다.

  

  • 로그 가능도 함수의 기울기를 위한 간단한 형태의 식이 된다.

• 원한다면 한 번에 하나씩 데이터를 추가하여 순차적인 알고리즘을 만들 수 있다.

• 선형적으로 분리 가능한 데이터 집합에 대해 최대 가능도 방법을 사용하면 심각한 과적합 문제를 겪을 수 있다.

4.3.3. IRLS(Iterative reweighted least squares)

• 가우시안 노이즈 모델을 선정하여 식을 모델링했고, 이 식은 닫힌 형태이므로 최적의 해를 구할 수 있다.

  • w에 대해 이차 종속성을 가지고 있었기 때문

• 하지만 로지스틱 회귀 모델의 경우에는 sigmoid 함수의 비선형성으로 인해 해가 닫힌 형태가 아니다.

  • convex 형태이므로 유일한 최솟값을 가지고 있다.

  • Newton-Raphson 방식으로 쉽게 최소화가 가능하다.

    

• 선형 회귀 모델과 제곱합 오류 함수에 대해 Newton-Raphson 방법을 적용해본다.

  

• 여기에 그래디언트와 헤시안을 적용하도록 한다.

  

• Newton-Raphson 업데이트 식은 다음과 같다.

  

• 이 결과값은 표준 최소 제곱 해에 해당하고, 오류 함수는 이차식이며, 한 단계만에 정확한 해를 구할 수 있다.

• 이제 이 업데이트를 cross-entropy 오차함수에 적용해 본다.

  

• 여기서 R은 N x N인 대각 행렬이다.

• 헤시안이 더 이상 상수가 아니며, 가중 행렬 R을 통해서 w에 종속성을 가지고 있음을 알 수 있다.

• y_n이 0과 1 사이의 수 라는 사실로 부터 H의 속성을 이해할 수 있다.

  • 임의의 벡터 u에 대해 u^THu > 0 을 만족한다.

  • 헤시안 행렬은 양의 정부호 행렬이고, w에 대한 볼록 함수이다.

• 로지스틱 회귀 모델에 대한 Newton-Raphson 업데이트는 다음과 같다.

  

  • 여기서 z는 다음을 원소로 가지는 N차원 벡터다.

    

• R이 상수가 아니고, 파라미터 w에 영향을 받는 요소이므로 이를 반복 업데이트 방식으로 풀어야 한다.

  • 따라서 IRLS라고 부른다.

• 이렇게 가중치가 부여된 최소 제곱 문제는 가중치 대각 행렬 R을 분산으로 생각할 수 있다. 로지스틱 회귀 모델에서 t의 평균과 분산은 다음과 같기 때문이다.

  

• IRLS는 변수 a = w^T ϕ에 대해 선형 문제를 가진다.

  

4.3.4 다중 클래스 로지스틱 회귀

• 다중 클래스 분류 문제를 다루는 생성적 모델에서는 선형 함수인 softmax가 사용한다고 이야기했다.

  

• 클래스 조건부 분포와 사전 분포를 따로 구하기 위해 MLE나 베이지안 정리를 사용해서 사후 확률을 찾았다.

  • 이를 바탕으로 간접적으로 매개변수 w_k를 구했던 것이다.

  • w_k를 직접 구하기 위해 y_k에 대한 미분값이 필요하다.

    

  • 여기서 I_kj는 단위 행렬이다.

• 가능도 함수에 대해 알아 본다. one hot encoding을 사용해서 표현하도록 한다.

  

  • 여기서 y_nk=y_k( ϕ_n)이고, T는 N x K인 행렬이다.

  • 음의 로그값을 취하면 다음과 같이 된다.

    

  • 이를 cross-entropy라고 부른다.

• 매개변수 벡터 w_j에 대해서 오류 함수의 기울기를 취해 본다.

  

• 선형 모델에 제곱합 오류 함수를 사용하였을 경우와 로지스틱 회귀 모델에 교차 엔트로피 오류 함수를 사용하였을 경우에 기울기 함수의 형태가 같다는 것을 확인할 수 있다.

4.3.5 프로빗 회귀

• 지금까지 클래스 조건 분포가 지수족으로 표현 가능하며 사후 분포를 로지스틱 함수로서 표현할 수 있다는 것을 보았다.

• 그러나 단순한 형태의 사후 확률이 모든 종류의 클래스 조건부 밀도 분포에 대해 결과로 나오는 것은 아니다.

  • 가우시안 혼합 분포를 이용하면 불가능하다.

• 다른 종류의 판별적 확률 모델을 살펴보도록 한다.

  • 2개의 분류 문제를 가진 일반화된 선형 모델의 틀을 유지한다.

    

  • 여기서 a=w^T ϕ 이고, 함수 f는 활성 함수(activation function)가 된다.

• 노이즈 임계값 모델을 고려해서 연결 함수를 선택할 수 있다.

  • ϕ_n을 a_n=w^Tϕ_n으로 계산한 후, 다음에 따라 표적값을 설정한다.

    

  • 여기서 θ 는 확률 밀도 p( θ )에서 추출된다면 활성 함수는 다음과 같이 기술할 수 있다.

    

    

• 여기서 파란색 곡선은 p( θ )로 두 개의 가우시안 함수의 혼합으로 이루어진다.

• 이에 해당하는 누적 분포 함수 f(a)는 붉은색 곡선으로 그려져 있다.

• 파란색 곡선 상의 녹색 수직선에서의 값은 같은 지점에서의 붉은색 곡선의 기울기와 같다.

• 이제 p( θ )를 표준 정규 분포로 생각한다면 식을 다음과 같이 기술할 수 있다.

  

• 이 함수를 역프로빗 함수라고 부른다.

  • 시그모이드 함수의 모양과 비슷하게 생겼으므로 일반적인 가우시안 분포를 사용해도 이 모델은 그대로 유지된다.

  • 오차 함수는 다음과 같이 정의된다.

    

  • 이 함수는 보통 erf 함수 또는 에러 함수라고 부른다.

    • 머신 러닝 모델에서 사용중인 오류 함수와는 다른 것이다.

• 이 오차 함수는 역프로빗 함수와 다음과 같은 관계를 가진다.

  

• 역프로빗 활성화 함수를 바탕으로 한 일반화된 선형 모델을 프로빗 회귀라 한다.

• MLE 방법을 이용하여 프로빗 회귀의 매개변수를 구할 수 있다.

  • 로지스틱 회귀와 비슷한 경우가 많다.

• 실제 응용 사례에서 문제가 될 수 있는 것은 outlier이다.

  • 입력 벡터 x를 측정할 때, 오류가 발생하거나 표적 벡터 t를 잘못 라벨링했을 때, 이상값 문제가 발생한다.

  • 이러한 데이터는 분류기를 심각하게 왜곡할 수 있다.

  • 로지스틱 회귀 모델과 프로빗 회귀 모델은 서로 다른 반응을 보인다.

    • 로지스틱 모델은 x가 문한대로 감에 따라서 exp(-x)와 같이 감쇠되는 반면, 프로빗은 exp(-x²)와 같이 감쇠되므로 더 예민하게 반응한다.

• 하지만 두 모델 모두 데이터는 모두 정확하게 라벨링되어 있다고 가정한다.

4.3.6 정준 연결 함수

• 가우시안 노이즈 분포를 사용한 선형 회귀 모델에서 에러 함수는 음의 로그 가능도 함수를 사용한다.

  

• 여기서 매개변수 벡터 w에 대해 미분하면 오륫값에 특징 벡터를 곱한 형태를 띠게 된다.

• 이 결과가 타깃 변수의 조건부 분포가 지수족에 포함되는 경우에 일반적으로 얻을 수 있는 결과이다.

  • 이 경우의 활성화 함수를 정준 연결 함수(canonical link function)라 한다.

• 입력 벡터 x에 대해 지수족 함수 분포를 가정했지만 여기서는 타겟 값 t에 대해 가정한다.

  

• 일반화된 선형 모델은 y가 입력의 선형 결합을 비선형 함수에 넣은 결과로 표현되는 모델이라 정의된다.

  

  • 여기서 f()가 활성 함수이며, f^-1()가 연결 함수다.

• η 의 함수로 표현되는 이 모델의 로그 가능도 함수를 고려해보자.

  

• 모든 관측값들이 동일한 척도 매개변수를 공유한다고 가정한다.

  • s는 n에 대해 독립적이다.

• 모델 매개변수 w에 대해 미분하면 다음과 같다.

  

• 여기서 a_n=w^T ϕ _n이고, y_n=f(a_n)이다.

  

• f( ψ (y))=y 이고, 따라서 f'( ψ ) ψ '(y)=1이다.

• 또한 a=f^-1(y) 이므로 a = ϕ 이고, 결국 f'(a) ψ '(y)=1이 된다.

  

문제:

다솜이는 기타를 많이 가지고 있다. 그리고 각각의 기타는 모두 다른 시리얼 번호를 가지고 있다. 다솜이는 기타를 빨리 찾아서 빨리 사람들에게 연주해주기 위해서 기타를 시리얼 번호 순서대로 정렬하고자 한다.

모든 시리얼 번호는 알파벳 대문자(A-Z)와 숫자 (0-9)로 이루어져 있다.

시리얼 번호 A가 시리얼번호 B의 앞에 오는 경우는 다음과 같다.

    1. A와 B의 길이가 다르면, 짧은 것이 먼저 온다.

    2. 만약 서로 길이가 같다면 A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저 온다. (숫자인 것만 더한다.)

    3. 만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다.

시리얼이 주어졌을 때, 정렬해서 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 기타의 개수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어져 있다. 시리얼 번호는 중복되지 않는다.

출력:

첫째 줄부터 차례대로 N개의 줄에 한줄에 하나씩 시리얼 번호를 정렬한 결과를 출력한다.

풀이방법:

 python에서는 정렬에 대한 기능이 잘 구현되어 있기 때문에 조건에 맞게 key를 설정해주면 된다. 시리얼 번호 중 숫자의 합을 구해야 하는 조건도 있기 때문에 입력을 받을 때 전처리 작업으로 숫자의 합을 구해서 (시리얼번호, 숫자합)과 같은 형태로 값들을 저장한다.

 값들을 다 저장한 후에는 sort의 key를 이용해서 정렬하도록 한다. key=lambda x : (정렬조건...) 과 같은 방식으로 사용한다. 1번 조건은 길이이므로 len(x), 2번 조건은 숫자의 합이므로 x[1], 마지막으로는 사전순이므로 x[0]과 같이 조건을 넣어주도록 한다.

문제링크:

https://www.acmicpc.net/problem/1431

Youtube에 있는 David Silver의 Reinforcement Learning 강의를 보고 작성하였습니다.

5. Model Free Control

• Model Free : MDP에 대한 정보가 없는 경우, 즉 environment에 대한 정보를 가지고 있지 않다.
• Control : value function을 최적화 하는 것, 즉 최적의 정책을 찾는 것

Model Free Control에서는 다양한 예제들이 있으며, 주로 다음 특징을 가지는 문제들을 해결한다,

• MDP를 모르지만, 경험을 sampling 할 수 있다.
• MDP는 알지만, sample들을 제외하고는 사용하기에는 너무 크다.

On Policy & Off Policy

• On Policy learning
  • "Learn on the job"
  • 학습하는 policy와 행동하는 policy가 같은 경우
    • ex)Sarsa
• Off Policy learning
  • "Look over someone's shoulder"
  • 학습하는 policy와 행동하는 policy가 반드시 같지 않아도 된다.
    • ex)Q-learning

On-Policy Monte-Carlo Control

• Generalised Policy Iteration

  

  • 3장에서 배웠던 내용으로 최적의 정책을 찾는 문제를 해결하기 위한 일반적인 방법론이다.
    • 임의의 정책으로 시작하여 value function을 추정하는 단계를 거친다.
    • 추정한 value를 바탕으로 정책을 발전시킨다.
    • 다시 맨처음으로 돌아간다.
    • 이는 EM 알고리즘과 같은 형태를 가지고 있다.
      • 따라서 Policy evaluation을 E단계, Policy improvement를 M 단계라 지칭한다.

• 4장에서 value function을 estimate 하는 방법들에 대해서 배웠는데 이를 E 단계에 적용해보도록 한다.

  • 하지만 그대로 적용한다면 다음과 같은 3가지 문제가 발생하게 된다.
    1. Value funcion의 model-based
    2. Local optimum
    3. Inefficiency of policy evaluation

1. Model-based

MC로 E단계를 수행하게 된다면 state value function을 사용해야 한다. 하지만 value function을 사용하면 M단계를 진행할 때 문제가 발생하게 된다. MC를 사용했던 이유가 Model-Free이기 때문이지만 value function으로 policy를 improve하려면 MDP의 model을 알아야 한다.

즉 위와 같이 reward와 state transition probaility를 알아야 한다. 즉 Model-based이어야 한다는 것이다.

따라서 이를 해결하기 위해서 value function을 action value function으로 바꾸게 되면 Model-Free 성질을 만족할 수 있다.

• return이 아닌 agent가 episode마다 random하게 움직이며 얻은 reward들 그리고 state transition prob.를 통해서 action-value function을 계산할 수 있다.

2. Local optimum

그러면 이제 Policy evaluation에서 value function을 action value function으로 바꾼다면 On policy MC를 사용할 수 있는 것일까? 다음 예시를 살펴보도록 한다.

• 두 개의 문이 내 앞에 있다.

  • 처음 왼쪽 문을 열었고, reward 0을 받았다.

    • V(left) = 0

  • 두번째에는 오른쪽 문을 열었고, reward 1을 받았다.

    • V(right) = +1

  • 세번째에 오른쪽 문을 열었고, reward 3을 받았다.

    • V(right) = +2

  • 네번째에 오른쪽 문을 열었고, reward 2를 받았다.

    • V(right) = +2

  • 그러면 지금까지 상황을 보았을 때 어느 문을 여는 것이 최선의 선택일까?

    • 아마도 이 네가지 상황으로만 본다면 오른쪽 문을 여는 것이 최선의 선택으로 보인다. 하지만 다음에 왼쪽 문을 열었을 때 reward를 100을 받을 수도 있는 것이다. 즉 지금 탐험과 탐사 trade-off에 빠지게 된 상황이다.

  • exploration(탐험) : environment에서 더 많은 정보를 알아내고자 하는 방법으로, 모든 행동을 할 때 일정 확률로 다른 곳으로 이동한다.

  • exploitation(탐사) : 알고 있는 정보를 바탕으로 보상을 최대화하고자 하는 것이다.

즉 지금 greedy 하게 improve 하는 것은 탐사에 빠지게 되는 것이다. 따라서 탐험을 어느정도 보장함으로써 model을 모르는 상황에서 더 좋은 성능을 낼 수 있을 것이다.

따라서 policy를 최적화 할 때 다음과 같이 일정한 확률을 부여해서 정하도록 한다.

3. Inefficiency of policy evaluation

하지만 MC 방법의 경우에 모든 episode들을 다 마친 후에 evaluation을 하면 너무 오랜 시간이 걸린다는 단점이 존재하게 된다. 따라서 이를 줄이기 위해서 매 episode들이 끝난 후에 policy evaluation을 수행하는 것으로 바꾸도록 한다.

즉 최종적인 On-Policy Monte-Carlo Control은 다음과 같다.

On- Policy Temporal-Difference Learning

TD가 MC보다 적은 variance를 가지고 online으로 학습가능하며, Incomplete sequence라는 장점들을 가지고 있기 때문에 control 문제에 적용해볼 수 있다.

Prediction에서 TD는 다음과 같이 표현을 했었다.

MC와 같은 이유로 value function을 사용할 수 없으므로 해당되는 부분들을 action value function으로 수정하도록 하자. 따라서 S에서 A 행동을 하면 보상 R을 받고 S'이라는 상태로 이동한다. 이 상태 S'에서 A'이라는 임의의 행동을 할 때의 action value function 값이 필요한 것이므로 다음과 같이 표현할 수 있다.

따라서 이를 앞부터 철자를 따서 Sarsa라고 부른다. Policy evaluation 부분에 MC 대신에 sarsa를 적용하면 다음과 같다.

n-step Sarsa

Sarsa가 애초에 TD의 개념에서 나온 것이므로 TD(λ)와 마찬가지로 Sarsa(λ)로 사용할 수 있다.

• forward view Sarsa(λ)

  • MC와 TD의 절충안이 n-step인 것처럼, 여러 개의 n-step을 선택하여 이의 평균을 취하면 각 n-step의 장점을 모두 가질 수 있게 된다. 이 때, 단순히 산술평균을 사용하는 것이 아니라 λ라는 weight를 이용해서 가중 평균을 취하도록하고 이를 Forward-view라고 한다.

  • episode가 모두 끝나야 계산이 가능하다. 따라서 TD의 장점을 많이 잃게 된다.

    

• backward view sarsa(λ)

  • 이제는 다시 forward-view TD(λ)에서 time-step마다 update할 수 있는 방법을 알아본다. 여기서 eligibility trace라는 개념이 나오게 된다. 이는 과거에 방문했던 state 중에서 현재 얻게 되는 reward에 영향을 주는 state를 판단해, 현재 얻게 되는 reward를 해당 state에 나누는 것이다.

    

Off- Policy learning

자신의 policy가 아니라 다른 사람의 policy를 통해서 학습을 하는 것이다. 이는 다음과 같은 관점으로 인해 중요하다.

1. 다른 agent를 관찰하는 것으로부터 배운다.
   • 다른 사람의 policy를(행동을) 따라 하는 것이 아닌, 경험만을 받아 학습해서 새로운 행동을 한다.
2. On policy의 경우에는 경험을 통해 policy를 업데이트를 했다면 사용한 경험은 버린다. 하지만 off policy는 이를 버리지 않고 재사용한다.
3. 탐험적인 행동을 하면서 최적의 policy를 찾을 수 있다.
4. 한 policy를 따르면서 여러 개의 policy를 학습할 수 있다.

Importance Sampling

X는 확률분포 P상에서 sampling 되는 것이고, Q는 P와 다른 확률분포를 의미한다. f(X)는 모든 함수를 넣을 수 있다. (f(X)=x, f(X)=3x...) 따라서 P를 따를 때의 f(X)의 기댓값을 구하고 싶은 것이다. 그런데 이를 이용해서 Q를 사용했을 때의 기댓값을 구하고 싶은 것이다.

이는 확률 분포 P와 Q의 비율을 곱해서 얻을 수 있는 것이다. 이를 Monte-Carlo에 적용해보자.

• Importance Sampling for Off-Policy Monte-Carlo

  • Monte Carlo를 수행할 때, 지나온 모든 행동들에 대해서 비율을 곱해준다.

  • 하지만 µ가 0이면 되면 사용할 수 없고, variance가 엄청 크기 때문에 사실상 사용할 수 없다.

• Importance Sampling for Off-Policy TD

  • 따라서 MC의 단점을 보완하기 위해서 TD를 사용하도록 한다.

Q-learning

Importance learning을 하지 않으면서 off-policy를 사용하기 위한 방법이다. 다음 행동은 behavior policy로 고르고, 다음 state S'에서 action A'은 target policy를 통해서 선택하는 것이다. 즉 다음과 같이 q-function이 업데이트가 된다.

Off-policy control with Q-learning

Q-learning에서는 behavior policy와 target policy를 동시에 improve 할 수 있다. Q-learning에서는 behavior policy μ는 ε-greedy로 target policy π는 greedy하게 선택하도록 한다. 각각 수렴 속도가 느리고, local optima에 빠질 수 있다는 단점을 해결하기 위해 적용된 절충안이다.

따라서 이제 다음과 같이 Q-learning이 진행된다.

1. 현재 state S에서 behavior policy μ( ε-greedy)에 따라 action A를 선택한다.

2. q-function을 이용해서 다음 state S'에서의 action A'은 π(greedy)에 따라 선택한다.

   

3. Q-learning의 target은 다음과 같이 구한다.

4. 다음과 같이 최종 update를 수행한다.

   

문제:

독일 로또는 {1, 2, ... , 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k개의 수를 골라 집합 S를 만든 다음 그 수만을 가지고 번호를 선택하는 것이다.

예를 들어 , k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다.

{[1,2,3,5,8,13].[1,2,3,5,8,21].[1,2,3,5,8,34],[1,2,3,5,13,21], ... ,[3,5,8,13,21,34]}

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력:

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k(6<k<13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력:

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

풀이방법:

 경우의 수를 구하는 문제는 python의 itertools를 사용하면 쉽게 구할 수 있다. itertools.combinations( iterable, k )와 같은 방식으로 사용하면 iterable한 자료형에서 k를 골라 만들 수 있는 모든 경우의 수를 만들어 준다.

 이 경우의 수를 출력하기 위해 *c와 같이 사용을 하고 각 테스트 케이스 사이에는 빈 줄을 하나 출력해야 하므로 print()를 마지막에 넣어주었다.

문제링크:

https://www.acmicpc.net/problem/6603

아래 모든 내용들은 Christopher Bishop의 pattern recognition and machine learning에서 더 자세히 볼 수 있습니다.

4. 선형 분류 모델

• 지금까지는 회귀 문제에 대해서만 다루어 보았지만 이번엔 분류 문제에 대해서 다루어 보도록 한다.

• 분류는 입력 벡터 x를 받았을 때 대응되는 클래스에 속하도록 하는 작업이다.
  • 이 때 클래스는 K개로 C_k 로 표기한다.
  • 하나의 데이터는 하나의 클래스에만 속하며, 하나의 클래스는 다른 클래스를 포함하지 않는다.
  • 이렇게 나누어진 영역을 decision region이라고 부르며 나누는 경계면을 decision boundaries라고 부른다.

4.1 판별 함수

4.1.1 두 개의 클래스

• 선형 판별식의 가장 간단한 형태를 다음과 같다.

• 여기서 w는 가중치 벡터라 부르고, w₀은 bias라고 부른다. 회귀랑 동일하다.

• 보통 2개의 클래스를 분류하는 문제에서 y(x)>=0인 경우를 C1으로 분류하고, 아닌 경우를 C2로 분류한다.

  • 이 때 decision boundaries는 y(x)=0임을 알 수 있다.

• 이제 임의의 두 점 x_A, x_B가 이 경계면 위에 있다고 하자.

  • 이 때 y(x_A)=y(x_B)=0를 만족하고, w^T(x_A−x_B)=0다. 여기서 w는 결정 경계에 대해 수직임을 알 수 있다.

  • 결정 경계에서 식을 전개하면 다음의 식을 얻을 수 있다.

    

• 이제 D=2라고 할 때 그림을 살펴본다.

  

• 임의의 한 점 x에 대해 결정 경계면에 수직으로 내린 지점을 x_ㅗ라고 하자.

• 이 경우 다음과 같은 식이 성립한다.

  

• 3장에서와 비슷하게 x₀=1를 이용하자.

  

• 위와 같이 간단하게 적을 수 있다.

4.1.2 다중 클래스

• K > 2인 상황을 다중 클래스라고 부른다.

  • 이 문제를 2-class 문제를 여러 개 조합해서 해결할 수 있다.
  • K-1개의 2-class 분류기가 있으면 K개의 클래스를 분류 가능하다.

  

• 왼쪽 그림을 보면 3개의 클래스를 분류하기 위해 2개의 2-class 문제를 사용하였다. 하지만 녹색 영역과 같이 판정을 할 수 없는 부분이 생기게 된다.

• 또한 만약 K(K-1)/2 개의 분류기를 사용해서 분류를 한다면 오른쪽과 같다.

  • 이 경우에도 녹색 영역과 같은 애매한 부분이 생긴다.

• 이 문제를 해결하기 위해 다른 방법을 사용한다.

  

• j != k일 때, y_k(x)>y_j(x)를 만족하면 x를 클래스 C_k로 판별하자.

  • 그러면 두 클래스 간의 decision boundaries는 y_k(x)=y_j(x)에서 형성된다.

  • 이 때 식을 전개하면,

    

  • 2-class 문제에서 사용하던 것과 같다.

• 이러한 판별 함수의 결정 경계는 언제나 단일하게 연결되어 있으며 볼록 성질을 가진다.

  • 모두 하나의 선으로 연결되어 있고, 내부의 어느 각도 180도를 넘지 않는다는 것과 같다.

  • 이를 확인할 수 있다.

    

    • x_A,x_B는 같은 지역의 임의의 두 점이다. x는 두 점 사이에 위치한 임의의 한 점을 나타내고, λ 는 0과 1 사이의 값이다.

      

    • y_k(x_A)>y_j(x_A) 이고 y_k(x_B)>y_j(x_B)이므로 y_k(xˆ)>y_j(xˆ)가 된다. 즉 아래 그림과 같다.

      

4.1.3 분류를 위한 최소 제곱법

• 최소제곱법을 사용해서 분류 문제를 해결해보자.

  • 사실 그리 정확하진 않다.

• 판별식은 다음과 같이 정의하고 간단히 정리하는 것이 가능하다.

  

• n번째 행이 t_n^T인 행렬 T와 n번째 행이 x

  _n^T라 하면, 전체 샘플 데이터를 X

  로 정의할 수 있다.

• 최소제곱법을 다음과 같이 적는다.

  

  • Tr은 행렬의 trace를 의미하며, trace는 행렬의 대각성분 합을 의미한다.

  • W에 대해 미분하고 정리하면 다음과 같다.

    

  • X^† 는 pseudo-inverse 행렬이다.

• 모든 훈련 집합의 표적 벡터들이 식 4.18의 선형 제약 조건을 어떠한 a와 b 값에 대해서 만족한다면 x 값에 대한 모델 예측값이나 제약 조건 4.19를 만족한다.

  

  

• 원 핫 인코딩을 통해 얻은 예측값들은 어떤 x의 경우에든 y(x)의 원소들을 전부 합하면 1이 된다.

  • 하지만 (0,1) 범위 내 안이라는 조건은 없으므로 확률값이라고 할 수 없다.

• 문제는 최소 제곱법은 outlier에 대해 너무 민감한 성질을 보인다. 따라서 더 강건한 모델을 고를 필요가 있다.

  

  • 녹색선은 로지스틱 회귀 분석으로 얻은 경계선, 보라색 선은 최소 제곱법을 사용한 것이다.
  • 보라색선은 우측의 그림처럼 outlier가 존재할 때 잘 분류하지 못하는 것을 알 수 있다.

4.1.4 피셔의 선형 판별

• 2-class 문제로 접근을 한다.

• D차원의 입력 벡터 x를 일차원에 투영한다고 해보자. 식은 다음과 같다.

  

• 이 식은 임의의 한 벡터를 한 차원의 벡터 위의 한 점(스칼라 값)으로 변환해준다.

• y에 임계값을 추가해 클래스를 분류하도록 한다.

• 높은 차원을 낮은 차원으로 줄였기 때문에 정보 손실은 당연하다.

  • 그렇기 때문에 정보 손실을 적게 하도록 해야 한다.

• w에 투영되었을 경우에 클래스 간의 분리 정도를 측정할 수 있는 가장 쉬운 방법은 투영된 클래스의 평균들이 얼마나 분리되어 있는가를 보는 것이다.

  

• 각 클래스의 평균을 나타내는 벡터를 표기할 수 있다.

• 이 값을 가지고 두 클래스간의 거리가 최대화되도록 하는 식을 전개한다.

• 1차원의 벡터로 투영된 후의 값은 다음과 같다.

  

• w를 찾아야 하는데, w 값만 무한정 커지면 값이 커지므로 단위 벡터로 고정을 한다.

• 이 식에 라그랑주 승수법을 적용해서 최소값을 구하면 w는 (m₂-m₁)에 비례한다.

• 왼쪽이 지금까지 한 방법인데 상당히 중복되는 것을 볼 수 있다. 이는 클래스 분포가 심한 비대각 공분산을 가지고 있기에 생긴다.

• 피셔의 제안은 투영된 클래스 평균 사이의 분리 정도를 크게 하는 동시에 각 클래스 내의 분산을 작게 하는 함수를 최대화함으로써 클래스 간의 중복을 최소화하는 것이다.

• 따라서 분산도를 정의한다.

  

• 여기서 y_n=w^Tx_n이다. 이 식은 투영 후 점들의 분산도를 의미한다.

  

• 최종 피셔 판별식은 위와 같으며, 정리하면 다음과 같은 식을 얻게 된다.

  

  • S_B는 클래스 간 공분산 행렬을 의미하고, S_W는 클래스 내 공분산 행렬을 의미한다.

    

  • J(w)를 w에 미분하면 최종적으로 위와 같은 식을 얻게 된다.

4.1.5 최소 제곱법과의 관계

• 에러 함수를 정의해본다.

  

• E는 w₀와 w에 대해 각각 미분하고 그 값을 0으로 설정하면 다음의 식을 얻게 된다.

  

• t_n은 다음과 같다.

  

  • N₁,N₂은 각 클래스에 속한 샘플 수를 의미하고 N은 전체 샘플 수를 의미한다.
  • C₁ = N/N₁, C₂=N₂

• m은 전체 데이터 집합의 평균이다.

  

• 4.32식에 x_n을 곱하고 전개하면 다음과 같다.

  

• 최종적으로 다음과 같으면 피셔 판별식과 동일하다.

  

4.1.6 다중 클래스에 대한 피셔 판별식

• 이제 K의 값이 2보다 큰 경우 피셔 판별식을 적용해보자.

  • 단 K<D임을 가정하자.

• D차원을 더 낮은 차원으로 변환하는 식을 아래와 같이 기술한다.

  

• W의 컬럼 개수는 D'로 정의한다. 당연히 D'의 값은 D보다 작다.

• 클래스 내 공분산 행렬

  • 앞서 살펴본 S_W를 K개의 클래스 버젼으로 확장한다.

  • N_k는 클래스 C_k에 속한 샘플의 수 이다.

    

• 클래스 간 공분산 행렬

  • 클래스 사이의 분산이 아닌 전체 데이터에 대한 공분산 행렬을 정의한다.

  • N은 전체 샘플 합계 : N=sum to k N_k

  • m은 전체 평균

    

  • 이 때 클래스 간 분산과 클래스 내 분산으로 나눌 수 있다.

  • 즉, S_T로 부터 S_W를 제외한 나머지를 S _B라고 정의한다.

    

  • 이 공분산 행렬들은 x 공간상에서 정의되었다. 행렬들을 투영된 D'차원의 y 공간상에서 정의해보자.

    

  • 에러 함수 만들 때, 여러 가지 선택지가 있지만 Fukunaga의 방법을 선택한다.

    

  • 투영 행렬 W에 대한 명시적인 함수로 다음과 같이 다시 적는다.

    

    • 이 기준을 최대화 하는 것은 어렵지 않지만 노력이 필요해서 Fukunaga에 설명되어 있다고 한다.

4.1.7 퍼셉트론 알고리즘

• 2-class에 대해 간단하게 알아보자.

  

• 활성 함수로 가장 간단한 형태인 계단형 함수를 쓴다.

  

• 여기서 ϕ ₀(x) = 1 이다. 표적값은 0,1 이 아닌 +1, -1로 정의해서 사용한다.

• 퍼셉트론에서 매개변수 w를 구하기 위한 알고리즘도 오류 함수를 최소화하는 방식이다.

  • 오분류된 패턴의 총 숫자를 오류 함수로 고를 수 있지만 사용하지 않는다.

    • 학습 알고리즘이 복잡해진다.
    • 오류 함수가 w에 대해 조각별 상수 함수다. w에 대한 변화가 결정 경계를 데이터 포인트들 중 하나를 건너 이동하게 하는 곳에서 불연속성이 발생한다.
      • 따라서 이 경우에 함수의 기울기를 통해서 w를 변경시키는 방법을 사용할 수 없다.

  • 따라서 퍼셉트론 기준이라는 오류 함수를 사용한다.

    

• 클래스 C₁에 대해서는 w^T ϕ (x_n) > 0이 되고, C₂는 w^T ϕ (x_n) < 0 을 만족하는 w를 찾고자 한다.

• 에러를 최소화 하는 방향으로 식을 전개해야 하므로 기울기 방법으로 w를 만들 수 있다.

  

  • η : 파라미터 학습 비율
  • τ : 알고리즘 스텝 인덱스

  

• 퍼셉트론의 동작 방식을 잘 설명하고 있는 그림이다.

  • 녹색 점이 오분류된 점인데 그에 따라 빨간색 방향만큼 보정이 된다.
  • 보정을 하고 난 뒤 다시 오분류된 점을 찾아 보정을 하는 작업을 계속해서 거치면 결정 경계가 완성된다.

• 아래 식을 통해 업데이트를 진행하면 에러가 점점 줄어든다는 것을 알 수 있다.

  

• 퍼셉트론 수렴 법칙(Perceptron convergence theorem)

  • 정확한 해를 가지고 있기만 한다면 퍼셉트론 학습 알고리즘은 정확한 해를 유한한 단계 안에 확실히 구할 수 있다.
    • 훈련 집합이 선형적으로 분리가 가능해야 한다.
  • 하지만 수렴을 위해 필요한 단계의 수가 매우 많을 수 있다.
    • 분리가 불가능한 문제인지, 단순히 수렴하는 데 오랜 시간이 걸리는 문제인지 구별이 불가능

• 퍼셉트론은 출력 값이 확률 값이 아니다.

• 중요한 제약 중 하나는 고정된 기저 함수의 선형 결합을 기반으로 한다.