머신 러닝

몬테카를로 방법 빈도주의에 바탕한 방법. 특정 값의 근사치를 구하기 위해 난수를 이용해 확률적으로 구한다. 일종의 시뮬레이션으로 이해할 수도 있다. 계산하려는 목표가 해석불가능한 함 수거나 구하기가 극히 어려울 때 사용한다. 마르코프체인 정확히는 ‘마르코프 성질을 가진 이산 확률과정’, 줄여서 ‘이산시간 확률과정’. 시간에 따른 계의 상태변화를 나타내는데 관찰 시간이 이산적이어서 이산시간이다. 미래(𝜏 + 1)의 상태는 현재(𝜏)에만 의존하고 과거(𝜏 − 1)에는 의존하지 않아야 한다. 조건부 확률 이 ‘과거상태와 독립’이라고 표현하기도 한다. 깁스샘플링 결합확률분포로부터 일련의 표본을 생성하는 알고리즘. 메트로폴리스 헤이스팅스의 특별한 예. 제안분포 원 분포를 근사해내기 위해 샘플링 과정에서 필요한 분포. 원 분포를 최대한 타이트 하게 포함하도록 설정되며, 다루기 쉬운 분포(예-가우시안)를 고른다. 샘플링 방법에 따라 사용하는 승인률이 다르고 해당 승인률에 따라 원 분포를 추정해낸다. 메트로폴리스 알고리즘 메트로폴리스-헤이스팅스 알고리즘. 직접 표본을 얻기 어려운 확률분포로부터 표본의 수열을 생성해내는 데 사용하는 알고리즘. 표집법의 하나. 고윳값, 고유벡터 행렬 𝐴, 상수 𝜆 , 벡터 𝑣가 𝐴𝑣 = 𝜆𝑣관계를 만족하면, 𝜆를 고윳값, 𝑣를 고유벡터라 한 다.

확률적 모델은 모집단의 정확한 분포를 알수 없는 경우가 대부분이므로 샘플링해서 근사합니다. 샘플링을 무한히 할 수는 없으므로 이 방법으로는 ‘매우 정확한’ 분포를 알 수 없겠지만, 우리가 원하는 만큼의 정확도로 근사할 수만 있으면 되겠지요. 모집 단에서 랜덤하게 아무렇게나 여러개 추출해도 대충의 분포 모양을 짐작할 수 있습니다. 하지만 어느 정도 샘플링을 해야 ‘어느정도 정확하게’ 할 수 있을까요. 얼마나 정확하게를 말하는 것일까요. 좀 더 구체적으로 이야기 하자면, 샘플링의 목표는 어떤 함수의 특정 분포에 대한 기댓값을 구하는 문제입 니다. Bishop Fig 11.1 위 그림을 보시면, 확률분포 p(z)에 대한 f(z)의 기댓값(∫ 𝑓(𝑧)𝑝(𝑧)𝑑𝑧)를 구하는 것이 목표입니다. 그런데 f(z)의 값이 큰 쪽에서 p(z)가 값이 작고, f(z)가 작은 쪽에서 p(z)가 큰 영역이 존재함을 알 수 있습니다. 그러면 f(z)p(z)를 적분한 값이 p(z)가 작은 지역에 의해 더 좌지우지될 가능성이 크다고 볼 수도 있습니다(p(z)가 큰 지역에서는 f(z)가 작기 때문). 그러면 f(z)p(z)를 정확하게 근사할 수 없겠지 요. 더 많은, 혹은 더 정확한 샘플링이 필요할 것입니다. 그리고 이와 반대로, 샘플링은 임의의 형태의 분포를 생성하는 데도 사용될 수 있습니다. 좀 더 정 확히 말하면 우리가 생성하고자 하는 분포를 ‘충분히 대표해낼 수 있는’ 집단의 생성입니다. 이때 데 이터포인트를 생성해 내는것도 샘플링이라고합니다. 본질적으로 이 두 활동은 동일한데, 아예 모르는 분포로부터 ‘대표성 있는’ 작은 집단을 추출하는 것이나, 우리가 이미 알고있는 분포로부터 집단을 생 성해 내는 것이나 결국 샘플링 과정은 동일하기 때문입니다. 그러면, uniform distribution으로부터 우리가 원하는 분포의 샘플집단을 골라내는 방법에 대해 이야 기해보겠습니다.(이것은 위에 말한 샘플링의 두가지 과정 중 두번째에 가깝습니다) 일단, 0~1 사이의 균등한 분포의 난수가 주어졌다고 가정하고, 이때 위의 p(z)와 같은 분포를 얻 어내도록 하겠습니다. 일단 누적분포 h(y)를 다음 그림과 같이 그려보겠습니다. Bishop. Fig. 11.2 ∫ 𝑝(𝑦)𝑑𝑦 ௬ ି∞ = ℎ(𝑦)이고 ℎ(𝑦)를 𝑧라 하면, ℎ ିଵ(𝑧) = 𝑦로 쓸 수 있습니다. 즉 우리가 쓰려는 분포에 대해 부정적분을 취하고 그 역함수를 구하면, 우리가 원하는 샘플 y를 얻을 수 있습니다. 하지만 이렇게 p(z)를 부정적분해서 h(z)를 얻을 수 있는 경우가 극히 드묾으로 주 로 표집법을 씁니다. <거부표집법> p(z)로부터 직접 샘플링하는것은 어렵지만 정규화계수를 모르는 상태의 𝑝̂(𝑧)는 계산 가능하다고 가 정합시다. 종종 이것은 사실입니다. 즉, p(z) = ଵ ୞౦ 𝑝̂(𝑧)에서 Z_p를 알기 어렵다는 이야기입니다. 일단 제안분포(우리가 가정하는 분포)를 두고 샘플링을 시행합니다. 그러면 승인(acceptance) 확 률은 다음과 같습니다. Bishop. Fig. 11.4 이때 모든 z에 대해 kq(z) >= 𝑝̂(z)가 성립하는, 가능한 한 작은 k를 찾아야 합니다. 일단 여기까지만 해도 성공이긴 하지만, 제안분포가 위의 그림과 같이 우리가 얻어내고자 하 는 분포와 모양이 많이 다르면 어떻게 할까요. 그때 쓸 수 있는 방법중 하나로 적응적 거부표집이 있습니다. 포괄함수 를 그때그때(구간별로) 만들어 쓰는 것을 뜻합니다. 오른쪽 그림을 참고하세요.(Bishop. Fig. 11.6) 거부표집법은 고차원공간에서 쓸 수 없는 단점이 있습니다. 차원수가 증가함에 따라 승인률이 기 하급수적으로 감소하기 때문입니다. <중요도 표집법> 중요도 표집법은 위에 우리가 그림 11.1에서 본것과 같은 문제를, 구간을 나누어 해결하겠다는 아 이디어 입니다. 즉, 아래 그림에서 q(z)로부터 적당히 데이터 포인트를 추출하고, 그 항을 적절히 가 중해서 합하겠다는 아이디어 입니다. ∑f(z) p(z) q(z) 𝑞(𝑧)𝑑𝑧 ≈ 1 𝐿෍ 𝑝൫𝑧 (௟)൯ 𝑞(𝑧 (௟)) 𝑓൫𝑧 (௟)൯ 표집분포가 원 분포에 얼마나 근접하느냐가 중요하고, p(z)가 변동이 너무 심하면 소수의 가중치가 너무 큰 값을 가지게 되고 결과적으로 우리가 뽑은 샘플중에 유효한 샘플의 수가 너무 적게 됩니다. 따라서 p(z)가 중요한 구간에서는 q(z)도 커야 합니다. 이 변형으로 SIR이라는 것이 있습니다. sampling importance resampling인데 과정은 다음과 같습 니다. 1. q(z)로부터 L개의 표본을 추출 2. 중요도 표집에 따라 각각의 가중치 결정 3. 앞의 L개로부터 resampling. 이때 가중치는 2에서 결정한 가중치를 사용 우선 몬테카를로방법에 대해 알아보겠습니다. 좋은 예제로 원주율 계산이 있습니다. 일단 정사각형 안에 사분원을 그립니다. 그리고 그 안에 격자점을 찍습니다. 그 다음 원의 내부에 찍 힌 점의 수와 밖에 찍힌 점의 수를 세어서 그 비율로 원주율을 계산합니다. 이 방법은 표본공간차원이 고차원일때도 사용이 가능합니다. 다음으로 마르코프연쇄에 대해 알아보겠습니다. 마르코프연쇄는 쉽게 말하면 ‘다음상태가 바로 이전 상태에만 의존하는 것’을 말합니다. 식으로 나타내면 다음과 같습니다. 이 확률을 전이확률이라고 합니다. 모든 m에 대해 전이확률이 동일하면 동질적(homogeneous)이라고 합니다. 연쇄에서 각 단계가 분포를 변화시키지 않으면 그 분포를 마르코프 연쇄에 대해 불변이라고 합니 다.(invariant. stationary하다고도 합니다) 마르코프 연쇄를 사용해서 주어진 분포로부터 샘플링을 하려면 해당분포가 연쇄에 대해 불변이어야 하고, 무한히 반복해도 어떤 확률분포로 수렴해야 합니다. 이 수렴하는 분포를 평형분포라고 하고, 시작 분포가 어떤 분포이든 평형분포에 도달하는 성질을 에르고딕성이라고 합니다. 이 마르코프 연쇄를 사용해서 샘플링하는 방법중 대표적인 것이 메트로폴리스 헤이스팅스 알고리즘 입니다. 메트로폴리스와 메트로폴리스 헤이스팅스에 관해 녹화강의에 더 자세히 설명했으므로 참고 바 랍니다. <기브스 표집법> 메트로폴리스 헤이스팅스의 특수케이스입니다. 변수들 중 하나의 값을 나머지 변수들에 대한 해당변 수의 조건부분포에서 추출한 값으로 바꾼 것입니다. 예를 들어 세개의 변수들에 대한 분포 p(z1,z2,z3) 로부터 z1을 빼고, 남은 z2, z3만 조건부로 넣고 z1을 새로 샘플링해서 replace하는 것입니다. 이것을 z2, z3에 대해서도 반복하고 다시 z1에 대해서도 반복할 수 있습니다. 기브스 표집법이 세부균형을 만족한다는 점을 강의시간에 증명했으므로 참고 바랍니다. <조각표집법> 메트로폴리스 알고리즘의 경우 각 단계 크기가 크면 높은 거부율때문에 비효율적입니다. 반대로 크 기가 작으면 임의보행행동으로 비상관화가 느립니다. 그래서 분포의 성질을 보고 단계 크기를 맞추는 방식이 가능한데 그것이 조각표집법입니다. 차원수 감소의 가장 대표적인 선형방법이 주성분분석(Principal Component Analysis)입니다. 데이터 를 subspace에 투영해서 차원감소를 시도하는 아이디어 입니다. 이때 데이터의 분산을 최대화 하는 방 향으로 투영이 이루어집니다. 평균투영비용(데이터포인트와 투영체간 평균제곱거리)을 최소화 하는 방향 으로 투영할수도 있는데 이 두가지는 사실 같은 것입니다. 이 둘이 같음을 보이겠습니다. 일단 최대분산방향을 구해보겠습니다. 1차원에 투영한다고 할때, 투영되는 1차원 공간의 방향을 D차원 벡터 u_1으로 정의하겠습니다. 방 향만 중요하므로 u_1은 단위벡터이고, 각각의 데이터포인트는 𝑢ଵ ்𝑥௡으로 투영됩니다.(내적) 투영된 데이터의 분산은 공분산행렬 S가 일 때, 으 로 주어집니다. 이 값을 최대화하는 것이 목표입니다. 라그랑주 승수법으로 해결하며, 구체적인 과정을 녹화강의에 담았습니다. 참고 바랍니다. 설명 도중에 고유벡터와 고윳값에 대한 설명도 포함되어 있습니다. 기초적인 개념이고 중요한 것이 므로 강의가 부족하면 다른 것들이라도 찾아보면서 알아두시기 바랍니다. 요약하면, 데이터집합의 평균과 공분산행렬을 계산하고, 공분산행렬의 가장 큰 M개의 고윳값에 해당 하는 M개의 고유벡터를 찾는 과정입니다.