마르코프 연쇄(Markov chain)

이 개념 위에 세워진 것

이 개념을 언급하는 페이지

• 행렬의 곱

  … 확률을 모은 표를 전이 행렬이라 합니다. 이 행렬을 n번 곱하면 n단계 뒤의 확률이 나오고, 이런 과정이마르코프 연쇄입니다. 변수가 여러 개인 함수는 한 점 근처에서 행렬 하나로 근사됩니다. 그 행렬을 ⟦야코비 …

• 고유벡터와 고유값

  … 큰 고유값이 황금비 φ ≈ 1.618이라서, 이웃한 두 항의 비는 φ에 다가갑니다. 상태가 유한 개인마르코프 연쇄를 오래 돌리면, 모든 상태가 서로 오갈 수 있고 일정한 주기로 맴돌지 않는 한, 확률 분포가 한 단계 더 …

• 대각화와 행렬 거듭제곱

  … ≈ −0.618이고, 앞의 것이 압도하니 이웃한 두 항의 비 F_{n+1}/F_n 은 φ에 다가갑니다.마르코프 연쇄를 오래 돌렸을 때 확률 분포가 한 분포로 다가간다면, 그 분포는 한 단계를 더 가도 바뀌지 않으니, 전이 …

• 조건부 확률

  … 0.4인 것처럼, "지금 상태만 알면 다음 상태의 확률이 정해진다"는 조건부 확률을 사슬처럼 이어 간 것이마르코프 연쇄입니다. 이런 조건부 확률들을 '지금 상태'를 행, '다음 상태'를 열로 하는 표로 모으면 행렬이 …

• 무작위 행보

  … 보였습니다. 과거의 경로와 상관없이 지금 위치만이 다음 위치의 확률을 정하는 이런 과정을 일반화한 것이마르코프 연쇄입니다. 양 끝에 벽이 있으면 어느 쪽 벽에 먼저 닿는지가 문제가 됩니다. 이것이 도박꾼의 파산입니다. …

• 도박꾼의 파산

  … 걸립니다. 이어지는 곳. 가진 돈을 상태로 보면 다음 판의 돈은 지금 돈에만 달려 있으니 이 과정은마르코프 연쇄이고, 0과 N은 한 번 들어가면 다시 나오지 않는 흡수 상태 입니다. "각 값이 양옆의 평균"이라는 …

• 가우스 소거법

  … 어디서든 쓸 수 있어서, 소수 p 로 나눈 나머지의 세계(모듈러 연산)에서도 그대로 통합니다.마르코프 연쇄의 정상 분포, 곧 한 걸음 더 가도 각 상태에 있을 확률이 바뀌지 않는 분포도 연립방정식을 소거해 …

• 혼돈

  … 공간을 칸으로 나누고 칸에서 칸으로 옮겨 가는 비율을 재면, 계를 다음 칸이 지금 칸에만 달린 확률 과정인마르코프 연쇄로 근사할 수 있습니다. 기상 예보는 초기값을 조금씩 흔든 예보 수십 개를 함께 돌리고(앙상블), 그 …

• 그래프

  … 동형입니다(A를 A로, B와 C를 서로 바꾸어 보내면 됩니다). 이어지는 곳. 변에 방향과 확률을 붙이면마르코프 연쇄의 상태 그림(점은 상태, 화살표 위의 수는 그 상태로 옮겨 갈 확률)이 되고, 그 위를 떠도는 산책자가 …

• 페이지랭크

  … 부릅니다. 다음 위치가 지금 위치에만 달려 있으니 이것은 링크 그래프 위의 무작위 행보, 곧마르코프 연쇄입니다. 오래 걸은 뒤 산책자가 각 페이지에 있을 확률이 그 페이지의 페이지랭크입니다. d가 1보다 …

• 편집 거리

  … 여러 단계로 나뉜 최적화 문제에 두루 쓰입니다. 상태는 보이지 않고 상태가 내놓는 관측값만 보이는마르코프 연쇄에서 관측값들을 가장 그럴듯하게 만든 상태열을 찾는 비터비 알고리즘(은닉 마르코프 모델)도 같은 …

• 유한 오토마톤

  … 번 훑으면 반드시 멈추므로, 튜링 기계와 달리 정지 문제가 생기지 않습니다. 전이마다 확률을 붙이면마르코프 연쇄가 되고, 상태는 숨어 있고 상태가 내놓는 기호만 보이면 은닉 마르코프 모델이 됩니다. 1943년 …

• 정규 표현식

  … 거리⟧가 작은 문자열을 찾는 문제입니다. 정규 표현식과 짝을 이루는 오토마톤의 화살표에 확률을 붙이면마르코프 연쇄가 되고, 상태를 숨기면 은닉 마르코프 모델이 됩니다.

• 정보 엔트로피

  … 한 변수가 다른 변수에 대해 알려 주는 양, 곧 상호 정보량입니다. 다음 상태가 지금 상태에 달린마르코프 연쇄에서는 한 걸음당 엔트로피(엔트로피율)를 정의할 수 있습니다. 평균과 분산이 정해진 연속분포 가운데 …

• n-그램 언어 모델

  … 이 문제를 피합니다. 바로 앞 n−1개를 한 덩어리 '지금 상태'로 보면, 다음 상태가 지금 상태에만 달린마르코프 연쇄의 가정을 그대로 가져온 것이고, 확률은 말뭉치에서 n개짜리 묶음을 세어 나누는 것으로 어림합니다. n = …

• 은닉 마르코프 모델

  … 그날 먹은 아이스크림 개수(1–3개)만 적혀 있습니다. 날씨는 오늘 날씨에 따라 내일 날씨가 정해지는마르코프 연쇄를 따르고, 더운 날에는 아이스크림을 많이, 추운 날에는 적게 먹는 경향이 있습니다. 이처럼 상태(날씨)는 …

• 원천 부호화 정리

  … 하나하나의 길이로 하한을 따지는 길을 열었습니다. 이어지는 곳. 기호가 앞 기호에 기대는 원천, 예컨대마르코프 연쇄에서는 엔트로피 대신 엔트로피율이 한계가 됩니다. 엔트로피율은 기호 n개의 결합 엔트로피를 n으로 …

• 렘펠–지브 압축

  … 뜻입니다. 상태가 유한 개이고 전이 확률이 고정되어 있으며 어느 상태에서든 모든 상태로 갈 수 있는마르코프 연쇄(정상 분포에서 출발한 것)가 그런 예입니다. 분포를 모르고도 원천 부호화 정리의 한계에 닿으니 …

• 결합 엔트로피와 조건부 엔트로피

  … 를 이미 한데 정리해 두었습니다. 이어지는 곳. 오늘이 내일을 정하는 규칙이 이 그림처럼 이어지는 과정이마르코프 연쇄이고, 정상 분포(이 그림에서는 기후)에서 출발했다면 한 걸음마다 새로 생기는 불확실성 H(X n+1 |X …

• 상호 정보량

  … 지우는 값을 치러야 합니다. X \to Y \to Z 처럼 다음 것이 바로 앞의 것에만 기대는 사슬이 곧마르코프 연쇄라서, 데이터 처리 부등식은 마르코프 연쇄에 대한 정리이기도 합니다.

• 쿨백–라이블러 발산

  … 보상으로 강화 학습하는 추론 모델의 GRPO도 출발 모델에서 멀어지지 않도록 같은 KL 벌점을 둡니다.마르코프 연쇄에서는 현재 분포와 정상 분포(오래 돌리면 다다라 더는 바뀌지 않는 분포) 사이의 KL 발산이 한 걸음마다 …

• 최대 엔트로피 원리

  … 아니며, 정보를 지우는 데 드는 열을 따지는 맥스웰의 악마와 란다우어 원리가 두 세계를 잇습니다.마르코프 연쇄를 오래 돌리면 정상 분포에 대한 KL 발산이 줄어들고, 볼츠만 분포를 정상 분포로 삼는 연쇄를 만들어 …

• 산술 부호화

  … 한계는 엔트로피율, 곧 앞의 글자들을 다 알 때 다음 글자에 남는 불확실성(조건부 엔트로피)이며,마르코프 연쇄가 가장 단순한 예입니다. 되살릴 때 조금 달라져도 되는 손실 압축의 한계는 율–왜곡 이론이 다루고, …

• 고정점

  … 연산은 할인율 γ가 1보다 작으면 축약이라, 되풀이하면 하나뿐인 고정점, 곧 참 가치로 수렴합니다.마르코프 연쇄의 정상 분포와 고윳값이 1인 고유벡터도 고정점입니다. 1950년 미국의 수학자 존 내시는, 모든 …

• 르베그 적분과 측도

  … 결과이고(모스크바 수학 학파, 니콜라이 루진), 측도 위에서 세운 확률은 중심극한정리와마르코프 연쇄의 바탕이 되었습니다. 두 분포를 옮기는 비용으로 거리를 재는 최적 수송도 측도의 언어로 적힙니다. …

• 동역학계

  … 결정론적인 계에 확률이 들어오는 문이 되었습니다. 상태 하나 대신 상태의 분포를 한 걸음씩 옮기면마르코프 연쇄가 되고, 복소평면의 반복 z \mapsto z^2 + c 가 c마다 어떤 궤도를 낳는지 한 장에 모은 …

• 통계학

  … 브래들리 에프런이 내놓은 붓스트랩(표본에서 다시 표본을 뽑아 흩어짐을 재는 방법)이 또 하나입니다.마르코프 연쇄로 복잡한 사후 분포(자료를 본 뒤의 믿음)에서 표본을 뽑는 계산도 가능해졌습니다. 덕분에 18세기 …

• 확률변수

  … 약 95%). 그의 제자 안드레이 마르코프와 알렉산드르 랴푸노프는 서로 기대는 확률변수들의 열(마르코프 연쇄)과 중심극한정리의 일반적인 증명으로 이 길을 넓혔습니다. 이어지는 곳. 확률변수 여러 개를 더하면 …

• 기계 학습

  … 회귀⟧와 주성분 분석에 있습니다. 확률 모형으로 배우는 쪽은 최대가능도법, 베이즈 정리,마르코프 연쇄, 은닉 마르코프 모델이고, 언어를 배우는 모형은 n-그램과 단어 임베딩에서 토큰화, …

• 확률적 경사 하강법과 Adam

  … 방법⟧의 한 예이고, 학습률이 일정할 때 바닥 근처에서 맴도는 θ는 한 걸음이 지금 자리에만 달린마르코프 연쇄를 이룹니다. 학습 데이터의 손실을 끝까지 줄이면 과적합이 생길 수 있어 검증 오차를 보며 멈추거나 …

• 순환 신경망과 LSTM

  … 2014년 조경현과 동료들의 GRU는 게이트를 둘로 줄인 더 단순한 변형입니다. 확률 모형과 견주면.마르코프 연쇄의 분포도 전이 행렬을 거듭 곱하며 나아갑니다. 고유값 1이 하나뿐이고 나머지 고유값의 절댓값이 모두 …

• 강화 학습

  … 칸에서 오른쪽을 고르면 출구에 도착할 확률이 0.8입니다. 다음 상태가 지금 상태와 행동에만 달려 있으니마르코프 연쇄에 선택을 더한 것입니다. 목표는 받을 보상의 합 r_0 + \gamma r_1 + \gamma^2 r_2 …

• 확산 모델

  … 100개입니다. 점 하나는 원점으로 끌리는 무작위 걸음을 하고, 다음 위치가 지금 위치에만 달려 있으니마르코프 연쇄입니다. 당기는 비율 \sqrt{1-\beta_k} 는 분산이 1인 분포가 한 걸음 뒤에도 분산 1이 …

• 언어 모델과 다음 토큰 예측

  … 확률을 어떻게 계산하느냐에서 들어옵니다. n-그램은 바로 앞 n − 1개 토큰만 본다고 가정하고(마르코프 연쇄의 가정), 순환 신경망은 지금까지의 글을 고정된 크기의 벡터 하나에 요약하며, 트랜스포머는 정해진 …

• 모나드

  … b마다 P(b) × P(c | b)를 더하기', 곧 전확률 공식입니다(조건부 확률). 상태가 유한한마르코프 연쇄에서는 이 풀칠이 전이 행렬의 곱이고, 결합법칙은 여러 걸음의 전이 확률을 어디서 끊어 계산해도 같다는 …

• 상태 공간 모형과 선형 순환

  … 돌며 줄어드는지는 극형식과 오일러 공식이 설명하고, 같은 수학이 순환 신경망의 기울기 소실과마르코프 연쇄가 처음을 잊는 빠르기에도 나옵니다. 되풀이를 풀어 쓴 합성곱은 합성곱 신경망의 필터를 시간 축으로 …

• 모노이드 범주와 끈 그림

  … 가운데 하나이고, 켜진 램프는 하루 사이에 0.3의 확률로 나갑니다. 각각을 열이 오늘, 행이 내일인마르코프 연쇄의 전이 행렬로 적으면 F = \begin{pmatrix}0.9 & 0.2\\ 0.1 & …

• 라플라시안과 그래프 라플라시안

  … 0인 함수여서 도박꾼의 파산과 전기 회로가 같은 문제가 되고, 그래프 위의 확률이 퍼지는마르코프 연쇄와 페이지랭크도 같은 뼈대를 씁니다. 사진을 흐리게 하는 것도, 경계를 찾는 것도, 확산 모델이 …

이 페이지가 가리키는 개념