절5.6확률행렬¶ 고유 링크

목표

확률행렬의 예와 차분방정식에의 응용을 배웁니다.
Google의 PageRank 알고리즘을 이해합니다.
계산 절차: 양의 확률행렬의 정상상태를 구합니다.
그림: 양의 확률행렬의 동역학입니다.
정리: 페론–프로베니우스 정리입니다.
용어: 차분방정식, (양의) 확률행렬, 정상상태, 중요도 행렬, Google 행렬.

이 절에서는 고윳값의 흔한 응용 중 하나인 차분방정식, 특히 마르코프 연쇄의 연구를 다룹니다. 이러한 유형의 차분방정식을 나타내는 확률행렬을 소개하고, 확률행렬의 가장 유명한 예인 Google 행렬을 자세히 다룹니다.

소절5.6.1차분방정식

임의의 시각에서의 상태를 수의 목록으로 기술할 수 있는 시스템을 연구한다고 가정합시다. 예를 들어 나이가 각각 $0,1,$ 세와 $2$ 세인 토끼의 수, 또는 애틀랜타에 있는 각 Red Box 키오스크에 있는 Prognosis Negative의 사본 수가 그러합니다. 각 경우에 시각 $t$ 에서의 상태를 벡터 $v_t$ 로 나타낼 수 있습니다. $t$ 는 이산적인 시간의 양을 나타낸다고 가정합니다. 다시 말해 $v_t$ 는 “ $t$ 일째” 또는 “ $t$ 년째”의 상태입니다. 또한 시각 $t+1$ 에서의 상태가 시각 $t$ 에서의 상태와 선형적으로 관련되어 있다고 가정합시다. 즉, 어떤 행렬 $A$ 에 대해 $v_{t+1}=Av_t$ 입니다. 이 소절에서 다룰 상황이 바로 이것입니다.

정의

차분방정식은 $n\times n$ 행렬 $A$ 와 $\R^n$ 의 벡터 $v_0,v_1,v_2,\ldots$ 에 대하여

$\begin{equation*} v_{t+1} = Av_t \end{equation*}$

꼴로 나타나는 방정식입니다.

다시 말해:

$v_t$ 는 “시각 $t$ 에서의 상태이고,”
$v_{t+1}$ 은 “시각 $t+1$ 에서의 상태이며,”
$v_{t+1}=Av_t$ 는 $A$ 가 “상태 변화 행렬”임을 뜻합니다.

$\begin{equation*} v_t = Av_{t-1} = A^2v_{t-2} = \cdots = A^tv_0, \end{equation*}$

이라는 점에 유의하십시오. 이로부터 차분방정식의 장기적 거동이 고윳값 문제임을 짐작할 수 있습니다.

이 소절과 다음 소절에서는 다음 예를 사용합니다. 이 절을 이해하는 것은 곧 이 예를 이해하는 것입니다.

예제

Red Box는 애틀랜타 곳곳에 영화를 대여할 수 있는 키오스크를 두고 있습니다. 대여한 영화는 다른 어느 키오스크에든 반납할 수 있습니다. 간단히 하기 위해 애틀랜타에 키오스크가 세 곳 있고, 모든 고객이 다음 날 영화를 반납한다고 가정합시다. $v_t$ 를 키오스크 $1,2,$ 및 $3$ 에 있는 Prognosis Negative의 사본 수를 각각 성분 $x_t,y_t,z_t$ 로 갖는 벡터라고 합시다. $A$ 를 $i,j$ -성분이 키오스크 $j$ 에서 Prognosis Negative를 대여한 고객이 이를 키오스크 $i$ 에 반납할 확률인 행렬이라고 합시다. 예를 들어 행렬

$\begin{equation*} A = \mat{.3 .4 .5; .3 .4 \color{seq-red}.3; \color{seq-green}.4 .2 .2} \end{equation*}$

은 키오스크 3에서 대여한 고객이 영화를 키오스크 2에 반납할 확률이 $\color{seq-red}30\%$ 이고, 키오스크 $1$ 에서 대여된 영화가 키오스크 $3$ 에 반납될 확률이 $\color{seq-green}40\%$ 임을 나타냅니다. 예를 들어 행렬 $A$ 의 둘째 행은 다음을 말해 줍니다.

키오스크 $2$ 에 반납되는 영화의 수는 (평균적으로) 다음과 같습니다:

$\begin{equation*} \begin{split} 30\% \amp\text{ of the movies from kiosk } 1 \\ 40\% \amp\text{ of the movies from kiosk } 2 \\ 30\% \amp\text{ of the movies from kiosk } 3 \\ \end{split} \end{equation*}$

이를 세 행 모두에 적용하면 다음과 같습니다.

$\begin{equation*} A\vec{x_t y_t z_t} = \vec{.3x_t+.4y_t+.5z_t .3x_t+.4y_t+.3z_t .4x_t+.2y_t+.2z_t}. \end{equation*}$

따라서 $Av_t$ 는 다음 날 각 키오스크에 있는 영화의 수를 나타냅니다.

$\begin{equation*} Av_t = v_{t+1}. \end{equation*}$

이 시스템은 차분방정식으로 모델링됩니다.

차분방정식에 대해 던져야 할 중요한 질문은 그 장기적 거동이 어떠한가 하는 것입니다. 100일 후에는 각 키오스크에 몇 편의 영화가 있겠습니까? 다음 소절에서는 특정한 유형의 차분방정식에 대해 이 질문에 답하겠습니다.

예제(토끼 개체군)

소절5.6.2확률행렬과 정상상태

이 소절에서는 Red Box 예제처럼 확률을 나타내는 차분방정식을 다룹니다. 이러한 시스템을 마르코프 연쇄라고 합니다. 이 절에서 가장 중요한 결과는 마르코프 연쇄의 장기적 거동을 설명하는 페론–프로베니우스 정리입니다.

정의

정사각행렬 $A$ 의 모든 성분이 음이 아니고 각 열의 성분의 합이 $1$ 이면 $A$ 를 확률행렬이라고 합니다.

행렬의 모든 성분이 양수이면 그 행렬을 양행렬이라고 합니다.

양의 확률행렬은 모든 성분이 양수인 확률행렬입니다. 특히 0인 성분은 하나도 없습니다. 예를 들어, 아래의 첫 번째 행렬은 양의 확률행렬이지만 두 번째 행렬은 그렇지 않습니다.

$\begin{equation*} \mat{.3 .4 .5; .3 .4 .3; .4 .2 .2} \qquad \mat{1 0 0; 0 1 0; 0 0 1}. \end{equation*}$

참고

예제

Red Box 예제를 이어서 살펴보면, 행렬

$\begin{equation*} A = \mat{.3 .4 .5; .3 .4 .3; .4 .2 .2} \end{equation*}$

는 양의 확률행렬입니다. 각 열의 합이 $1$ 이라는 사실은 특정 키오스크에서 대여된 모든 영화가 어떤 키오스크로든 반드시 반납되어야 함을 의미합니다(모든 고객은 다음 날 영화를 반납한다는 점을 기억하십시오). 예를 들어, 첫 번째 열은 다음을 말해 줍니다.

키오스크 $1$ 에서 대여된 영화 중

$\begin{equation*} \begin{split} 30\% \amp\text{ will be returned to kiosk } 1 \\ 30\% \amp\text{ will be returned to kiosk } 2 \\ 40\% \amp\text{ will be returned to kiosk } 3. \\ \end{split} \end{equation*}$

모든 영화가 세 키오스크 중 한 곳으로 반납되므로 그 합은 $100\%$ 입니다.

행렬 $A$ 는 하루에서 다음 날로의 상태 변화를 나타냅니다.

$\begin{equation*} \vec{x_{t+1} y_{t+1} z_{t+1}} = A\vec{x_t y_t z_t} = \vec{.3x_t+.4y_t+.5z_t .3x_t+.4y_t+.3z_t .4x_t+.2y_t+.2z_t}. \end{equation*}$

$v_{t+1}$ 의 성분을 모두 더하면

$\begin{equation*} \begin{split} \amp(.3x_t+.4y_t+.5z_t)+ (.3x_t+.4y_t+.3z_t)+ (.4x_t+.2y_t+.2z_t) \\ \amp\qquad=(.3+.3+.4)x_t + (.4+.4+.2)y_t + (.5+.3+.2)z_t \\ \amp\qquad= x_t + y_t + z_t. \end{split} \end{equation*}$

이를 얻습니다. 이는 예상대로 세 키오스크에 있는 Prognosis Negative의 총 개수가 날마다 변하지 않음을 의미합니다.

벡터 $v_t$ 와 $v_{t+1}$ 의 성분의 합이 같다는 사실은 확률행렬의 각 열의 합이 $1$ 이라는 사실에서 비롯됩니다.

$A$ 를 확률행렬, $v_t$ 를 벡터라 하고, $v_{t+1} = Av_t$ 라고 합시다. 그러면 $v_t$ 의 성분의 합은 $v_{t+1}$ 의 성분의 합과 같습니다.

차분방정식의 장기적 거동을 계산하는 것은 결국 고윳값 문제가 됩니다. 확률행렬의 고윳값은 매우 특별한 성질을 가집니다.

사실

$A$ 를 확률행렬이라고 합시다. 그러면 다음이 성립합니다.

$1$ 은 $A.$ 의 고윳값입니다.
$\lambda$ 가 $A$ 의 (실수 또는 복소수) 고윳값이면 $|\lambda|\leq 1.$ 입니다.

증명

실제로 양의 확률행렬 $A$ 에 대해서는, $\lambda\neq 1$ 가 $A$ 의 (실수 또는 복소수) 고윳값이면 $|\lambda|\lt 1.$ 임을 보일 수 있습니다. 확률행렬의 $1$ -고유공간은 매우 중요합니다.

정의

확률행렬 $A$ 의 정상상태란 고윳값 $1$ 에 대응하는 고유벡터 $w$ 중에서 성분이 모두 양수이고 그 합이 $1$ 인 것을 말합니다.

페론–프로베니우스 정리는 확률행렬로 표현되는 차분방정식의 장기적 거동을 설명합니다. 이 정리의 증명은 이 책의 범위를 벗어납니다.

페론–프로베니우스 정리

$A$ 가 양의 확률행렬이라고 합시다. 그러면 $A$ 는 유일한 정상상태 벡터 $w$ 를 가지며, 이 벡터는 $1$ -고유공간을 생성합니다.

또한 성분의 합이 어떤 수 $c$ 인 임의의 벡터 $v_0$ 에 대하여, $t$ 가 커짐에 따라 반복값

$\begin{equation*} v_1 = Av_0,\; v_2 = Av_1,\; \ldots,\; v_t = Av_{t-1},\; \ldots \end{equation*}$

는 $cw$ 에 가까워집니다.

해석: 페론–프로베니우스 정리는 다음을 주장합니다.

양의 확률행렬의 $1$ -고유공간은 직선입니다.
$1$ -고유공간은 성분이 모두 양수인 벡터를 포함합니다.
모든 벡터는 $A$ 를 반복해서 곱하면 $1$ -고유공간에 가까워집니다.

정상상태 벡터 $w$ 는 백분율의 벡터로 생각해야 합니다. 예를 들어 오늘 영화들이 이 백분율에 따라 분포되어 있다면, $Aw=w$ 이므로 내일도 같은 분포를 가질 것입니다. 그리고 영화의 처음 분포가 어떻든 장기적인 분포는 항상 정상상태 벡터가 됩니다.

$v_0$ 의 성분의 합 $c$ 는 모형화하는 계에 있는 대상의 총수입니다. 총수는 변하지 않으므로 계의 장기적 상태는 $cw$ 에 가까워져야 합니다. 이 상태는 $1$ -고유공간에 포함되므로 $w$ 의 배수이며, $cw$ 의 성분의 합은 $c$ 입니다.

계산 절차 1: 정상상태 벡터 구하기

$A$ 가 양의 확률행렬이라고 합시다. 다음은 $A.$ 의 정상상태 벡터를 구하는 방법입니다.

$(A-I_n)v = 0$ 을 풀어 고윳값 $1$ 에 대한 $A$ 의 고유벡터 $v$ 를 아무것이나 하나 찾으십시오.
$v$ 를 $v$ 의 성분의 합으로 나누어 성분의 합이 $1.$ 인 벡터 $w$ 를 얻으십시오.
이 벡터의 성분은 자동으로 양수가 됩니다. 이 벡터가 유일한 정상상태 벡터입니다.

위의 계산 절차는 손으로 계산하기에 적합하지만, $A$ 가 확률행렬이라는 사실을 활용하지는 않습니다. 실제로는 다음과 같이 컴퓨터로 정상상태 벡터를 계산하는 것이 일반적으로 더 빠릅니다.

계산 절차 2: 컴퓨터로 정상상태 벡터 근사하기

$A$ 가 양의 확률행렬이라고 합시다. 다음은 컴퓨터로 $A$ 의 정상상태 벡터를 근사하는 방법입니다.

성분의 합이 $1$ 인 벡터 $v_0$ 를 아무것이나 하나 고르십시오(예: 표준 좌표 벡터).
$v_1 = Av_0,\,v_2 = Av_1,\,v_3=Av_2,\,$ 등을 계산하십시오.
이 벡터들은 정상상태 벡터 $w$ 로 수렴합니다.

예제( $2\times 2$ 확률행렬)

예제

Red Box 예제에 이어, 페론–프로베니우스 정리를 명시적으로 확인해 볼 수 있습니다. 행렬

$\begin{equation*} A = \mat{.3 .4 .5; .3 .4 .3; .4 .2 .2} \end{equation*}$

의 특성다항식은 다음과 같습니다.

$\begin{equation*} f(\lambda) = -\lambda^3 + 0.12\lambda - 0.02 = -(\lambda-1)(\lambda+0.2)(\lambda-0.1). \end{equation*}$

$1$ 이 다른 고윳값들보다 절댓값이 엄격하게 크며, 대수적(따라서 기하적) 중복도가 $1$ 임에 주목하십시오. 고윳값 $1,-0.2,0.1$ 에 대한 고유벡터를 계산하면 각각 다음과 같습니다.

$\begin{equation*} u_1 = \vec{7 6 5} \qquad u_2 = \vec{-1 0 1} \qquad u_3 = \vec{1 -3 2}. \end{equation*}$

고유벡터 $u_1$ 은 반드시 양의 성분을 가지며, 정상상태 벡터는 다음과 같습니다.

$\begin{equation*} w = \frac 1{7+6+5}u_1 = \frac 1{18}\vec{7 6 5}. \end{equation*}$

고유벡터 $u_1,u_2,u_3$ 은 $\R^3$ 의 기저 $\cB$ 를 이룹니다. $\R^3$ 의 임의의 벡터 $x = a_1u_1+a_2u_2+a_3u_3$ 에 대해 다음이 성립합니다.

$\begin{equation*} \begin{split} Ax \amp= A(a_1u_1+a_2u_2+a_3u_3) \\ \amp= a_1Au_1 + a_2Au_2 + a_3Au_3 \\ \amp= a_1u_1 - 0.2a_2u_2 + 0.1a_3u_3. \end{split} \end{equation*}$

이런 식으로 $A$ 를 반복해서 곱하면, $t\to\infty$ 일 때 다음을 얻습니다.

$\begin{equation*} A^tx = a_1u_1 - (0.2)^ta_2u_2 + (0.1)^ta_3u_3 \;\To\; a_1u_1 \end{equation*}$

이는 페론–프로베니우스 정리가 보장하는 대로, $A^tx$ 가 고윳값이 $1$ 인 고유벡터인 $a_1u_1$ 에 가까워짐을 보여 줍니다.

위의 계산은 애틀랜타 Red Box 키오스크에 있는 Prognosis Negative의 사본 수에 대해 무엇을 말해 줍니까? 키오스크들이 처음에 이 영화의 사본 100개를 가지고 있으며, 키오스크 1에 $30$ 개, 키오스크 $2$ 에 $50$ 개, 키오스크 $3$ 에 $20$ 개가 있다고 가정합시다. 이 상태를 나타내는 벡터를 $v_0 = (30,50,20)$ 이라고 합시다. 그러면 다음 날에는 키오스크에 $v_1 = Av_0$ 만큼의 영화가 있고, 그다음 날에는 $v_2 = Av_1$ 만큼의 영화가 있는 식으로 계속됩니다. $v_t = (x_t,y_t,z_t).$ 라고 둡시다.

$\begin{equation*} \begin{array}{c|c|c|c} t & x_t & y_t & z_t \\\hline 0 & 30.000000 & 50.000000 & 20.000000 \\ 1 & 39.000000 & 35.000000 & 26.000000 \\ 2 & 38.700000 & 33.500000 & 27.800000 \\ 3 & 38.910000 & 33.350000 & 27.740000 \\ 4 & 38.883000 & 33.335000 & 27.782000 \\ 5 & 38.889900 & 33.333500 & 27.776600 \\ 6 & 38.888670 & 33.333350 & 27.777980 \\ 7 & 38.888931 & 33.333335 & 27.777734 \\ 8 & 38.888880 & 33.333333 & 27.777786 \\ 9 & 38.888891 & 33.333333 & 27.777776 \\ 10& 38.888889 & 33.333333 & 27.777778 \\ \end{array} \end{equation*}$

(물론 영화의 수가 분수인 것은 말이 되지 않습니다. 여기서는 수렴을 보여 주기 위해 소수를 포함했습니다.) 정상상태 벡터는 결국 영화들이 다음 비율

$\begin{equation*} w = \frac 1{18}\vec{7 6 5} = \vec{38.888888\% 33.333333\% 27.777778\%}, \end{equation*}$

에 따라 키오스크에 분포하게 된다는 것을 말해 주며, 이는 위의 표와 일치합니다. 더욱이 이 분포는 키오스크에 있는 영화의 처음 분포와 무관합니다.

이제 행렬 $A$ 의 동역학(즉, $A$ 를 반복하여 곱하는 것)을 시각화해 봅시다. 이 행렬은 대각화 가능합니다. 다음

$\begin{equation*} C = \mat{7 -1 1; 6 0 -3; 5 1 2} \qquad D = \mat{1 0 0 ; 0 -.2 0; 0 0 .1}. \end{equation*}$

에 대해 $A=CDC\inv$ 입니다. 행렬 $D$ 는 $x$ 좌표는 그대로 두고, $y$ 좌표는 $-1/5$ 만큼, $z$ 좌표는 $1/10$ 만큼 배율을 조정합니다. $D$ 를 반복하여 곱하면 $y$ 좌표와 $z$ 좌표가 매우 작아지므로, $D$ 는 “모든 벡터를 $x$ 축으로 빨아들입니다.”

행렬 $A$ 는 $D$ 와 같은 일을 하지만, $C$ 의 열 $u_1,u_2,u_3$ 이 정의하는 좌표계를 기준으로 합니다. 이는 $A$ 가 벡터 성분의 합을 바꾸지 않으면서 “모든 벡터를 $1$ -고유공간으로 빨아들인다”는 뜻입니다.

그림18확률행렬 $A$ 의 동역학. “multiply”를 클릭하면 색칠된 점들에 왼쪽에서는 $D$ 를, 오른쪽에서는 $A$ 를 곱합니다. 양쪽 모두에서 모든 벡터가 “ $1$ -고유공간으로 빨려 들어간다”(초록색 선)는 점에 주목하십시오. (오른쪽과 왼쪽에서 벡터의 크기가 대략 같도록 $C$ 의 배율을 $1/4$ 만큼 조정했습니다. “multiply”를 누를 때 일어나는 “점프”는 $-.2$ -고유공간의 부호 반전이며, 이는 애니메이션으로 표시되지 않습니다.)

양의 확률행렬의 그림은 대각화 가능 여부와 관계없이 항상 같습니다: 벡터 성분의 합을 바꾸지 않으면서 모든 벡터가 “직선인 $1$ -고유공간으로 빨려 들어갑니다.” 이것이 페론–프로베니우스 정리의 기하학적 내용입니다.

소절5.6.3Google’의 PageRank 알고리즘

1990년대의 인터넷 검색은 매우 비효율적이었습니다. Yahoo나 AltaVista는 페이지에서 검색어를 찾아본 뒤, 그 단어가 가장 많이 나오는 결과를 단순히 나열했습니다. 놀랄 것도 없이, 더 수상한 웹사이트들은 자기 페이지에 “Alanis Morissette”라는 단어를 백만 번 넣어 두면, 불안에 찬 십대가 Napster에서 Jagged Little Pill을 찾으려 할 때마다 맨 먼저 나타날 수 있다는 것을 곧 알게 되었습니다.

Larry Page와 Sergey Brin은 페이지를 중요도에 따라 랭크를 매기는 방법을 고안했습니다. 그들은 이 알고리즘을 바탕으로 Google을 설립했습니다. 대략적인 작동 방식은 다음과 같습니다.

각 웹 페이지에는 중요도, 즉 랭크가 연관되어 있습니다. 이것은 양수입니다. 이 랭크는 다음 규칙에 따라 결정됩니다.

중요도 규칙

페이지 $P$ 가 다른 $n$ 개의 페이지 $Q_1,Q_2,\ldots,Q_n$ 에 링크하면, 각 페이지 $Q_i$ 는 $P$ ’의 중요도의 $\frac 1n$ 을 물려받습니다.

실제로 이것은 다음을 의미합니다:

매우 중요한 페이지가 여러분의 페이지에 링크하면(그리고 그 페이지가 수많은 다른 페이지에도 함께 링크하지 않는다면), 여러분의 페이지는 중요한 페이지로 간주됩니다.
수많은 중요하지 않은 페이지가 여러분의 페이지에 링크하더라도, 여러분의 페이지는 여전히 중요합니다.
알려지지 않은 페이지 하나만 여러분의 페이지에 링크한다면, 여러분의 페이지는 중요하지 않습니다.

또 다른 방법으로, 무작위 서퍼 해석이 있습니다. “무작위 서퍼”는 하루 종일 컴퓨터 앞에 앉아 무작위로 링크를 클릭할 뿐입니다. 그가 가장 많은 시간을 보내는 페이지가 가장 중요한 페이지여야 합니다. 따라서 중요한(순위가 높은) 페이지는 무작위 서퍼가 가장 자주 도달하게 되는 페이지입니다. 이 척도는 랭크와 동치인 것으로 밝혀집니다.

중요도 행렬

페이지가 $n$ 개인 인터넷을 생각해 봅시다. 중요도 행렬은 $i,j$ -성분이 페이지 $j$ 가 페이지 $i.$ 에 전달하는 중요도인 $n\times n$ 행렬 $A$ 입니다.

모든 페이지에 링크가 있다고 가정하면 중요도 행렬은 확률행렬임을 관찰하십시오. 페이지 $i$ 에 링크가 $m$ 개 있으면, $i$ 번째 열에는 수 $1/m$ 이 $m$ 번 나타나고 나머지 성분은 0입니다.

예제

페이지가 네 개뿐인 다음 인터넷을 생각해 봅시다. 링크는 화살표로 표시되어 있습니다.

$\begin{tikzpicture} \matrix[matrix of nodes, nodes={draw, circle, thick, anchor=center, font=\large}, row sep={3cm,between origins}, column sep={5cm,between origins}] (pages) { |[seq1] (A)| A \& |[seq2] (B)| B \\ |[seq3] (C)| C \& |[seq4] (D)| D \\ }; \begin{scope}[->, shorten=2pt, every node/.style={midway, auto, thin border}, every to/.style={bend left=10}] \draw[seq1] (A) to node {${\frac 13}$} (B); \draw[seq1] (A) to node {${\frac 13}$} (C); \draw[seq1] (A) to node[near start] {${\frac 13}$} (D); \draw[seq2] (B) to node[near end] {${\frac 12}$} (C); \draw[seq2] (B) to node {${\frac 12}$} (D); \draw[seq3] (C) to node {${1}$} (A); \draw[seq4] (D) to node[near end] {${\frac 12}$} (A); \draw[seq4] (D) to node {${\frac 12}$} (C); \end{scope} \end{tikzpicture}$

중요도 규칙을 시행하면 다음과 같습니다:

페이지 $\color{seq1}A$ 에는 링크가 $3$ 있으므로, 자신의 중요도의 $\frac 13$ 을 페이지 $B,C,D$ 에 각각 전달합니다.
페이지 $\color{seq2}B$ 에는 링크가 $2$ 있으므로, 자신의 중요도의 $\frac 12$ 을 페이지 $C,D$ 에 각각 전달합니다.
페이지 $\color{seq3}C$ 에는 링크가 하나 있으므로, 자신의 중요도 전부를 페이지 $A$ 에 전달합니다.
페이지 $\color{seq4}D$ 에는 링크가 $2$ 있으므로, 자신의 중요도의 $\frac 12$ 을 페이지 $A,C$ 에 각각 전달합니다.

행렬로 표현하면, $v = (a,b,c,d)$ 가 페이지 $A,B,C,D$ 의 랭크 $a,b,c,d$ 를 담은 벡터일 때 다음이 성립합니다.

$\begin{equation*} \def\r{\color{seq1}}\def\b{\color{seq2}}\def\g{\color{seq3}}\def\p{\color{seq4}} \mat{ \r0 \b0 \g1 \p\frac 12; \r\frac 13 \b0 \g0 \p0; \r\frac 13 \b\frac 12 \g0 \p\frac 12; \r\frac 13 \b\frac 12 \g0 \p0} \vec{a b c d} = \spalignsysdelims()\syseq{ \. \+ \. \+ c + \frac 12d; \frac 13a; \frac 13a + \frac 12b \+ \. + \frac 12d; \frac 13a + \frac 12b} = \vec{a b c d}. \end{equation*}$

왼쪽의 행렬이 중요도 행렬이며, 마지막 등식은 중요도 규칙을 나타냅니다.

위의 예는 핵심 관찰을 보여 줍니다.

핵심 관찰

랭크 벡터는 고윳값이 $1$ 인 중요도 행렬의 고유벡터입니다.

핵심 관찰에 비추어, 우리는 페론–프로베니우스 정리를 사용하여 랭크 벡터를 구하고자 합니다. 안타깝게도 중요도 행렬이 항상 양의 확률행렬인 것은 아닙니다.

예제(링크가 없는 페이지)

예제(연결되지 않은 인터넷)

다음은 Page와 Brin’s의 해결책입니다. 먼저 각 영 열을 $1/n$ s로 이루어진 열로 바꾸어 중요도 행렬을 수정합니다. 여기서 $n$ 은 페이지의 수입니다:

$\begin{equation*} A = \mat{0 0 0; 0 0 0; 1 1 0} \sptxt{becomes} A' = \mat{0 0 1/3; 0 0 1/3; 1 1 1/3}. \end{equation*}$

수정된 중요도 행렬 $A'$ 는 항상 확률행렬입니다.

이제 $(0,1)$ 에 속하는 수 $p$ 를 하나 고르는데, 이를 감쇠 인자라고 부릅니다. (전형적인 값은 $p=0.15$ 입니다.)

Google 행렬

$A$ 를 $n$ 개의 페이지로 이루어진 인터넷의 중요도 행렬이라 하고, $A'$ 를 수정된 중요도 행렬이라 합시다. Google 행렬은 다음 행렬입니다.

$\begin{equation*} M = (1-p)\cdot A' + p\cdot B \sptxt{where} B = \frac 1n\mat{1 1 \cdots, 1; 1 1 \cdots, 1; \vdots, \vdots, \ddots, \vdots; 1 1 \cdots, 1}. \end{equation*}$

무작위 서퍼 해석에서 이 행렬 $M$ 이 말하는 바는 다음과 같습니다: 확률 $p$ 로 서퍼는 완전히 무작위인 페이지로 이동합니다. 그렇지 않으면 현재 페이지에 있는 무작위 링크를 클릭하는데, 현재 페이지에 링크가 없는 경우에는 어느 쪽이든 완전히 무작위인 페이지로 이동합니다.

독자는 다음의 중요한 사실을 확인할 수 있습니다.

사실

Google 행렬은 양의 확률행렬입니다.

모든 페이지의 랭크의 합이 $1$ 이 되어야 한다고 정하면, 다음을 얻습니다.

250억 달러짜리 고유벡터

PageRank 벡터는 Google 행렬의 정상상태입니다.

페론–프로베니우스 정리에 의해 이것은 존재하며 양의 성분을 가집니다. 어려운 부분은 이것을 계산하는 것입니다. 실제로 Google 행렬은 엄청나게 많은 행을 가지고 있습니다.

예제

번역에 대한 의견이나 오류 제보(GitHub 계정 필요)

목표

정의

예제