ジニ係数と有効カタログサイズの関係

推薦システムの評価指標

推薦システムの評価には様々な指標が用いられます。代表的なものは以下の記事にまとめられています。
レコメンドつれづれ　～第3回 レコメンド精度の評価方法を学ぶ～

PrecisionやRecall、nDCGといった評価指標は教師データに基づいて推薦の精度を測るものですが、推薦システムが提供するコンテンツにどれくらい多様性があるかというのも重要な指標となります。
この「多様性」を測る指標として、2015年にNetflixが有効カタログサイズ（Effective Catalog Size: ECS）というものが提案しています。
The Netflix Recommender System: Algorithms, Business Value, and Innovation
ECSは以下の記事で紹介されています。
大量のコンテンツをラインアップする際の有効カタログサイズ

本の論文において、ECSが示す多様性が低い状態とはある1つのコンテンツに閲覧が集中している状態であり、多様性が高い状態とは全てのコンテンツが同じだけ閲覧されている状態である、と説明されています。
これをコンテンツ間の「格差」と捉え直すと、統計学において所得格差を表す指標として知られるジニ係数と似ていると感じました。
本記事ではECSとジニ係数の関係を調べてわかったことをまとめます。

先に結論

ECSとジニ係数は以下の関係にあることがわかりました。

$$\mathrm{Gini} = 1 - \frac{\mathrm{ECS}}{N}$$

ただし、

• $\mathrm{ECS}$：有効カタログサイズ
• $\mathrm{Gini}$：ジニ係数
• $N$：アイテムの総数

を表します。

問題設定

ECSとジニ係数は同じ文脈で出てくる指標ではないので、ここでは推薦システムに合わせて考えることにします。

推薦候補となるアイテムの集合があり、一定期間内にそれぞれのアイテムが推薦される回数を集計します。推薦システムによって多少異なりますが、アイテムごとに推薦回数の偏りが発生し、人気アイテムほどたくさんのユーザーに推薦されると考えられます。ECSは「多様性指標」なので、推薦システムが提示するアイテムの多様性をECSで定量化することを考えます。一方、ジニ係数は「格差指標」なので、アイテムごとの推薦回数の格差をジニ係数で定量化することを考えます。

また、記号を以下のように定義します。

• $c_i$：アイテム$i$の推薦回数
• $r_i$：推薦回数の小さい順に並べたときのアイテム$i$のランク
• $\hat{r}_i$：推薦回数の大きい順に並べたときのアイテム$i$のランク
• $N$：アイテムの総数

以下この問題設定に沿って式をいじっていきます。

有効カタログサイズ（ECS）

ECSは多様性を測る指標であり、値の範囲は1からアイテムの総数$N$、値が大きいほど多様性が高い状態であることを表します。論文の中で、ECSは確率質量関数$\boldsymbol{p}$を重みとして考慮した重み付け平均をスケーリングしたものと説明されています。

$$\tag*{(1)} \mathrm{ECS}(\boldsymbol{p}) = 2 \left( \sum_{i=1}^{N} p_i i \right) - 1$$

Equation (1) simply computes the average of the video index under the p.m.f. p, and rescales it to lie in the appropriate range.

ここで、アイテムは推薦回数の多い順に並べられていて、$p_i$は全体に対する$i$番目のアイテムの推薦回数の割合を表しています。この式を先ほど定義した記号で書き直すと、以下のように表せます。

$$\begin{aligned} \mathrm{ECS} &= 2 \left( \sum_i^N p_i \hat{r}_i \right) - 1 \\ &= 2 \left( \sum_i^N \frac{c_i}{\sum_j^N c_j} \hat{r}_i \right) - 1 \\ &= \frac{2 \sum_i^N (c_i \hat{r}_i) - \sum_j^N c_j}{\sum_j^N c_j} \\ &= \frac{2 \sum_i^N \left\{ c_i (\hat{r}_i - \frac{1}{2}) \right\}}{\sum_i^N c_i} \end{aligned}$$

ジニ係数

ジニ係数は「格差」を測る指標であり、値の範囲は0から1、値が大きいほど格差が大きい状態であることを表します。wikipediaによると、

ジニ係数は、ローレンツ曲線と均等分配線によって囲まれる領域の面積と均等分配線より下の領域の面積の比として定義される。

$$\mathrm{Gini} = \frac{A}{A+B} = 2A = 1 - 2B$$

このようにジニ係数は面積$B$つまりローレンツ曲線下の面積を用いて表すことができます。（面積$A,B$の定義はwikiの図を参照してください。）この面積$B$を台形積分で求めてみます。ローレンツ曲線は、今回の問題設定ではアイテムを推薦回数の小さい順に並べて、横軸にアイテムの累積比、縦軸に推薦回数の累積比をプロットしたものです。そのため、あるアイテム$i$のローレンツ曲線上の点の座標は推薦回数$c_i$や小さい順でのランク$r_i$を用いて以下のように表せます。

$$(x,y) = (\frac{r_i}{N}, \frac{\sum_{r_j \leq r_i} c_j}{\sum_j^N c_j})$$

よって、このアイテムを表す点と、1つ上のランクのアイテムを表す点とで構成される1つの台形の面積は以下のように表せます。

$$\frac{1}{2} \frac{1}{N} \left( \frac{\sum_{r_j < r_i} c_j + \sum_{r_j \leq r_i} c_j}{\sum_j^N c_j} \right)$$

全アイテムについてこの台形の面積の総和を取れば面積$B$となります。

$$\begin{aligned} B &= \sum_i^N \frac{1}{2} \frac{1}{N} \left( \frac{\sum_{r_j < r_i} c_j + \sum_{r_j \leq r_i} c_j}{\sum_j^N c_j} \right) \\ &= \frac{\frac{1}{2} \sum_i^N \left( \sum_{r_j < r_i} c_j + \sum_{r_j \leq r_i} c_j \right)}{N \sum_j^N c_j} \\ &= \frac{\frac{1}{2} \sum_i^N \left[ c_i \{2(N-r_i) + 1\} \right]}{N \sum_i^N c_i} \end{aligned}$$

最後の式変形では、分子の$i$に関する総和の中でランク$r_i$のアイテムが$2(N-r_i)-1$回足されることを利用しています。2つのランク$r_i,\hat{r}_i$には$r_i+\hat{r}_i = N+1$という関係があることから、さらに以下のように変形できます。

$$B = \frac{\sum_i^N \left\{ c_i (\hat{r}_i - \frac{1}{2}) \right\}}{N \sum_i^N c_i}$$

よって、ジニ係数は以下のように表せます。

$$\begin{aligned} \mathrm{Gini} &= 1 - 2B \\ &= 1 - \frac{2 \sum_i^N \left\{ c_i (\hat{r}_i - \frac{1}{2}) \right\}}{N \sum_i^N c_i} \end{aligned}$$

結論（再掲）

ECSの式とジニ係数の式と見比べてみると、共通の項があってそれを介してECSとジニ係数は以下の関係にあることがわかります。

$$\mathrm{Gini} = 1 - \frac{\mathrm{ECS}}{N}$$

それぞれが取りうる値の範囲と意味

ECSが表す「推薦システムの多様性」とジニ係数が表す「アイテム間の格差」の対応関係をまとめると以下の通りです。

	多様性が低い 完全な不平等		多様性が高い 完全な平等
ECS	$1$	↔︎	$N$
ジニ係数	$1 - \frac{1}{N}$	↔︎	$0$

ただし・・・

ジニ係数の計算時に数値積分で近似的に値を求めており、その上で有効カタログサイズと上記のような関係が成り立ちます。
ローレンツ曲線下の面積を別の方法で求めれば、上記の関係から少しズレると思われます。