f:id:s_yuka:20200820132703j:plain

こんにちは． Sansan DSOC 研究開発部の黒木です．今年の春に新卒社員として入社しました．専門は統計解析で，特に時系列データやネットワークデータの分析を行ってきました．最近では，タイピングゲーム「寿司打」のやりすぎで左手中指の第2関節が少し痛みます．

こちらの連載では，自分の勉強・復習も兼ねて，古典的な手法からより発展的な話題まで，ネットワークデータにまつわる統計解析を紹介していこうと思います．ネットワークとは，主体となるノード，それらのつながりであるエッジから構成される対象で，webページの巨大な集合であるWWW (World Wide Web) やSNSにおける人のつながり，交通網，食物連鎖のネットワークなど，その例は多岐に渡ります．近年の機械学習やデータサイエンスの盛り上がりとともに，このようなネットワークデータからも有益な知見を得たいという欲求が高まっています．そんな気が個人的にしています．

初回は，無作為抽出を前提とした平均値や総計値の推定からはじめ，基本的な標本調査，そのネットワークデータへの適用を整理します．

標本調査

そもそも標本調査とはなんでしょうか．標本調査とは，関心のあるなんらかの量について，対象の全体（母集団）を調べるのではなくその一部のみを取り上げ，推測することで済ませてしまうことです．

ここで少しだけ用語を整理します．標本調査において対象となる集団全体を母集団 (population)，興味のある母集団の特徴を母数 (parameter)，抽出された母集団の一部を標本 (sample)，標本から算出された母数の推計量を推定量 (estimator) と呼びます．

調査対象を母集団の一部に絞ってなお妥当な推測を行うことができるのであれば，時間や費用面を大きく節約できることになります．また，テレビの視聴率調査のように，その全貌を観測することがそもそも現実的でない場合もあります．たとえば国会議員の投票で開票が終わるよりも早く「当確」が出るのも，この標本調査を利用しているからです．しかし一方で，母数を直接計算するのとは異なり，標本から算出される推定量は誤差を伴います．

そこで，用いている推定アルゴリズムがどのような「誤差」を伴うのか，標本の抽出は適切に行われているのかを評価することが非常に重要になってきます．また，どのような抽出設計やアルゴリズムが「良い性質」をもっているのか，洞察を与えることは統計学の重要な役割の一つです．

統計的推測の初歩

着目する母数をある量の総計値と平均値の2つに絞り，少し一般的に上記の話題を整理します．データを要約する際はまずこの2つの量に着目することが非常に多いでしょう．

いま，大きさ $N$ の集合 $\mathcal{U} = \{1,\dots,N\}$ があるとします．また，それぞれの要素 $i \in \mathcal{U}$ が持つ興味ある量の値を $y_i$ とします．たとえば， $i$ を一人の日本人， $y _ i$ をその人の年収などとする場合です．

母集団 $\mathcal{U}$ の量 $y$ について合計をとった値 $\mathcal{Y} = \sum _ {i\in \mathcal{U}} y _ i$ は総計値 (population total)， $\mu = \mathcal{Y} / N$ は平均値 (population mean) と呼ばれます．

全数調査が難しい場合や，何らかの結果として観察されたデータのみがある場合には， $\mathcal{U}$ は得られておらず，そのサンプル $S = \{i_1, \dots, i_n\}$ のみがあることになります．得られた $S$ から平均 $\mu$ を推定することはよくあるタスクですが，その推定量としては $\bar{y} = \frac{1}{n}\sum _ {i\in S} y _ i$ が用いられることが多いと思います．

$S$ が $\mathcal{U}$ から等確率かつランダムに抽出されるという特殊な場合には，この推定量は不偏推定量となります．また，この特殊な抽出を単純無作為抽出 (simple random sampling) といいます．つまり， $\rm{E}(\bar{y}) = \mu$ になるということです．しかし，単純無作為抽出は簡単に行えるものでしょうか．そうでないことは想像に易いでしょう．たとえば国勢調査では，住宅所有者よりホームレスの人々を見つけ出すのに苦労します．

Horvitz-Thompson推定量

では，単純無作為抽出が行えない場合，どのように総計値や平均値を推定すれば良いでしょうか．本節で紹介するHorvitz-Thompson推定量を用いれば，そうでない標本抽出においてもこれらを偏りなく推定することができます．

準備のため，母集団 $\mathcal{U}$ のある要素 $i$ が抽出されるときに $Z _ i = 1$ ，抽出されないとき $Z _ i = 0$ となるような確率変数 $Z _ i$ を考えます．さらに，要素 $i$ が抽出される確率（一次の包含確率）は ${\rm P}(Z _ i = 1) = \pi _ i$ ，要素 $i, j$ が共に抽出される確率（二次の包含確率）は ${\rm P}(Z _ i = 1, Z _ j = 1) = \pi _ {i, j}$ と表します．ここで，確率変数 $Z$ はベルヌーイ分布に従うため，その期待値や分散，共分散は次のようになります．いずれも定義通りに計算しただけのものです．

$\displaystyle \begin{align} &{\rm E}(Z _ i) = \pi _ i ,\\ &{\rm V}(Z _ i) = \pi _ i (1 - \pi _ i), \\ &{\rm Cov}(Z _ i, Z _ j) =\pi _ {i,j} - \pi _ i \pi _ j. \end{align} \tag{1}$

それでは本題です．次式で示されるHorvitz-Thompson推定量は総計値の不偏推定量になることが知られています．

$\displaystyle \hat{\mathcal{Y}} _ {HT} \equiv \sum_{i=1}^n \frac{y _ i}{\pi _ i}.\tag{2}$

また，これに対応する平均値の推定量は $\pi _ {HT} = \frac{1}{n}\hat{\mathcal{Y}}$ です．式より，各要素が抽出される確率の逆数 $\frac{1}{\pi _ i}$ で， $y _ i$ を加重平均する形になっています．

Horvitz-Thompson推定量が不偏推定量であることは，次の式変形から明らかです．

$\begin{align} {\rm E}\left(\hat{\mathcal{Y}} _ {HT}\right) &= {\rm E}\left( \sum_{i=1}^n \frac{y _ i}{\pi _ i}\right)\\ &= {\rm E}\left(\sum _ {i\in\mathcal{U}} \frac{y _ i}{\pi _ i}Z _ i\right)\\ &= \sum _ {i\in\mathcal{U}} \frac{y _ i}{\pi _ i}{\rm E}\left(Z _ i\right) \\ &= \mathcal{Y}. \end{align} \tag{3}$

また，Horvitz-Thompson推定量はその分散も明らかにされており，同様に $Z _ i$ と式(1)を考えて次式のようになります．

$\displaystyle {\rm V}(\hat{\mathcal{Y}} _ {HT}) = \sum _ {i,j=1} ^ {N}\frac{\pi _ {i,j} - \pi _ i \pi _ j}{\pi _ i \pi _ j}y _ iy _ j. \tag{4}$

つまり，各要素が抽出される確率さえ分かっていれば不偏推定を行うことができるだけでなく，推定量のばらつきも評価できるというわけです．

ネットワークデータ

ネットワークという構造を持つデータにおいても，「人気者で露出も多い人」が観測されやすかったり，「有名人どうしの親密な繋がり」が広く知れ渡るように，より観測されやすいノード・エッジが存在することは頻繁にあるでしょう．ネットワークデータでも慎重に標本調査を行う必要がありそうです．

ここでは，準備としてネットワークの表現を用意します．

興味の対象であるネットワーク全体を $G=(V, E)$ とし，その主体であるノードの集合を $V = \{1,\dots,N _ v\}$ ，とします．また，ノード $u, v$ 間のつながりであるエッジを $e _ {u,v}$ とするとき，エッジの集合を $E = \{e _ {u,v} | u, v \in V\}$ とします．ノードの数とエッジの数はそれぞれ $N _ v = |V|, N _ e = |E|$ と表すことにします．また，ネットワークは無向であり，多重エッジや自己ループはないものとします．

一般に $G = (V, E)$ の全貌は観測し得ず，その一部のみが観測されます． $G' = (V', E')$ が $G$ の部分グラフ (subgraph) であるとは， $V'\subseteq V$ かつ $E'\subseteq E$ ということです．また，もう一つ大切な概念に誘導部分グラフがあります．誘導部分グラフとは，ノードの部分集合と，その間に張られるエッジにより構成されるグラフのことで， $V'\subseteq V$ であり $E' = \{e _ {u,v} \in E| u,v \in V'\}$ と表されます．

Horvitz-Thompson推定量のネットワークへの適用

ネットワークデータに対しては，平均次数や密度，クラスター係数などのように，その構造に由来する様々な特徴量を算出することができます．しかし，大規模なネットワークは通常全貌を観測できないため，標本調査を利用して妥当な推定，特に不偏推定を行いたいと考えるのが自然です．さらに，ネットワークは構造をもつため，先ほどのような単純無作為抽出を考えることは難しくなります．つまり，こういった量に対してもHorvitz-Thompson推定量のような推定量を適用したいのです．

実は，母集団 $\mathcal{U}$ と，その構成要素 $i$ がもつ量の $y _ i$ をうまく考えることにより，様々なネットワークの特徴量を総計値 (total) の形で表現することができます．それに加えて包含確率 $\pi _ i$ さえ分かれば（もしくは妥当な仮定をおければ），Horvitz-Thompson推定量を得ることができる，というわけです．

たとえばネットワークの平均次数を推定したい場合，ノードを $i$ の持つ繋がりの数（次数）を $d _ i$ を用いて $\mathcal{U} = V, y _ i = d _ i$ とすれば良いですし，ネットワーク内に存在するつながりの総量を求めたければ $\mathcal{U} = E, y _ i = 1$ とすれば良いことになります．つまり，このような表現を用いれば，Horvitz-Thompson推定量をはじめとした推定量により，観測された部分グラフからも全体の総計値が推定できることになるわけです．

ネットワークデータのサンプリング

ここからの抽出は，すべて非復元であるとします（そのため， $n < N$ となります）．復元の有無にかかわらず，不偏推定量の不偏性は保たれますが，非復元の場合その分散は小さくなります．これは，標本 $S$ の要素が全て異なるように強制され，より効率的に使用されるためです．

Horvitz-Thompson推定量を適用するには，ノードやエッジの包含確率 $\pi _ i$ などが所与でなくてはなりません．また，ネットワークは構造をもつため，単純無作為抽出を考えるのは難しいのでした．そこで本節では，母集団のネットワーク（母ネットワーク）からどのように部分グラフを抽出するのか，最も単純な2つの抽出方法を紹介します．ノード単位の単純無作為標本から部分グラフを構成するinduced samplingと，エッジ単位の単純無作為標本から部分グラフを構成するincident samplingです．

Induced sampling

まずは，ネットワークのノードを無作為抽出し，そこから得られる誘導グラフを観察することを考えます．

$V = \{1, \dots, N _ v\}$ からの大きさ $n$ の無作為標本を $V' = \{i _ 1, \dots, i _ n\}$ とします．

次に， $\{i, j\} \in E$ であるすべての頂点ペア $i, j \in V'$ についてエッジが観測され， $E'$ を得ます．

induced samplingでははじめにノードが無作為抽出され，ついでノード間の関係が観測されるため，FacebookなどのSNSにおける交友ネットワークの構築などもこの一例と考えることができるかもしれません．

induced sampling のもとでは，ノードの包含確率は全て等しく，次のようになります．

$\displaystyle \pi _ i = \frac{n}{N _ v}.\tag{5}$

また，あるエッジ $e _ {i, j}$ が観測されるためにはノード $i, j$ がともに抽出される必要があります．そのため，あるエッジが抽出される確率あらゆるノードペアの組み合わせを考え，その包含確率もすべて等しく次のようになります．

$\displaystyle \pi_{i, j} = \frac{n(n-1)}{N _ v(N _ v-1)}.\tag{6}$

しかしここで， $N _ v$ は未知であることに注意が必要です．Facebookの場合は，世界の総人口とできるかもしれません．他にも，社内ネットワークについて調査する場合などは，社員名簿を参照することで解決されるかもしれません．

ネットワークの大きさの推定についても，このシリーズでいずれ扱いたいと思います．

Incident sampling

続いて，はじめにエッジが無作為に $n$ 個抽出されるincident samplingを考えます．

エッジは等確率で抽出されるため，包含確率は当然 $\pi _ {i, j} = n / N _ e$ となります．

一方でノードの包含確率はより複雑なものになります．

$\displaystyle \begin{align} \pi _ i &= {\rm P}(ノードiが抽出される確率) \\ &= 1 - {\rm P}(ノードiに接続するエッジが抽出されない確率) \\ &= \begin{cases} 1 - \frac{\left(\begin{array}{c}N _ e - d _ i\\ n \end{array}\right )}{\left(\begin{array}{c}N _ e\\ n \end{array}\right )} & {\text if } n\leq N _ e - d _ i\\ 1 & {\text if } n\geq N _ e - d _ i \end{cases}. \end{align} \tag{7}$

この包含確率を計算するためには，エッジ数 $N _ e$ だけでなく，各ノードの次数 $d _ i$ に関しても知っている必要があります．

たとえば社内SNS（slackなど）のメッセージについて調査するとき，ある社員が送受信したダイレクトメッセージだけでなく，社内で行われたダイレクトメッセージの総数について知る必要があります．

まとめ

今回は，標本調査の初歩の初歩と，ネットワークの標本抽出について紹介しました．特に連載の初回ということもあり，できるだけ簡単な出だしになるように心がけました．ネットワークのように構造をもったデータ（他には時系列データや地理データなど）に対する統計解析は非常に複雑で難しいものになりますが，順を追って整理できればと思っております．次回以降は，もう少し発展的なネットワークの標本抽出について紹介したり，今回は既知であるとしていた $N _ v$ についての推定に触れたいと思います．よろしくお願いします．

buildersbox.corp-sansan.com