この記事は博報堂テクノロジーズアドベントカレンダー17日目の記事です。
はじめに
博報堂テクノロジーズの坂井です。
普段はメディア効果の予測や最適化のツールを開発していて、日々数学の力を借りながら開発業務をしています。
私がこの仕事をしていてワクワクするのが、高度な数学の概念と広告の実務が交差する瞬間です。
本稿ではその一例として、複数の広告メニューを横断した広告の接触回数の分布を、フーリエ変換を用いることで効率的に計算できるテクニックを紹介します。
問題設定
広告の実務では、「世の中の生活者に何回ずつ広告が当たったか」を広告接触回数分布（フリークエンシー分布とも）として評価します。フリークエンシー分布がわかれば、そのキャンペーンがどのくらい幅広く生活者にリーチしたのか、あるいは一部の生活者に偏って接触が集中してしているのかを把握できます。
単一の広告メニューであれば、それぞれのメニューごとにフリークエンシー分布を計測することは比較的容易です。
一方で複数の広告メニューを同時に出稿したとき、複数のメニューを横断して全体としてのフリークエンシー分布を計測することは一般的には難しく、推定に頼るケースが多いです。
数学的には、複数の確率分布 $P(X_1), P(X_2), \ldots, P( X_M)$ が与えられたときに、それらの和 $X_{\rm total}=X_1 + X_2 + \cdots + X_M$ の分布 $P(X_{\rm total})$ を求める問題に帰着します。
ここでは簡単のため、広告メニュー間の接触は独立とみなせると仮定します。
ナイーブな解法とその問題点
独立を仮定してよければ、2媒体 ( $M=2$ ) であれば、次の和で簡単に求められます。
$$
P(X_{\rm total}=k) = \sum_{i+j=k} P(X_1=i) P(X_2=j)
$$
しかし媒体数 $M$ を増やすと、計算量は指数的に増えてしまいます。
$$
P(X_{\rm total}=k) = \sum_{i_1 + i_2 + \cdots + i_M = k} P(X_1=i_1),P(X_2=i_2) \cdots P(X_M=i_M)
$$
ナイーブな計算では、接触回数の合計が $k$ になるような各メニューの接触回数の組み合わせの数え上げをしています。このため $\mathcal{O}(K^M)$ の計算量になってしまいます（$K$ を各媒体の最大接触回数とする）。
フーリエ変換で「急がば回れ」
ここで数学の出番です。
上記で挙げた計算は、関数の「畳み込み和」という計算の一種です。
畳み込み和には、フーリエ変換を使った効率的な計算が知られています。
確率変数 $X$ の確率関数のフーリエ変換を $\varphi_X(\omega) = \mathbb{E}[e^{i\omega X}]$ と定義します（これを特性関数ともいいます）。
フーリエ変換の基礎的な性質として、「畳み込み和のフーリエ変換は、フーリエ変換したものの積に一致する」という定理があります。
$$
\varphi_{X_{\rm total}}(\omega) = \prod_{m=1}^{M} \varphi_{X_m}(\omega)
$$
そして、フーリエ変換したものを逆変換すれば元の関数に戻せます。
つまり、畳み込みという数え上げが必要な計算を直接行わず、一度フーリエ変換して掛け算し、最後に逆変換しても、同じ結果を得られるというわけです。離散分布の場合は高速フーリエ変換 (FFT) を使うことで $\mathcal{O}(M K \log K)$ にまで計算量を落とすことができます。まさに「急がば回れ」ですね。
実際の数値例
簡単な数値例を示します。
PX1 = [0.5, 0.3, 0.2] # 0回, 1回, 2回接触の確率分布
PX2 = [0.4, 0.6, 0.0]
↓ これらを一度フーリエ変換します。
FFT(PX1) = [1.0+0.0j, 0.712-0.412j, 0.3-0.3j, 0.287-0.012j, 0.4+0.0j]
FFT(PX2) = [1.0+0.0j, 0.824-0.424j, 0.4-0.6j, -0.024-0.424j, -0.2+0.0j]
↓ 要素ごとに掛け算します。
FFT(PX_total) = [1.0+0.0j, 0.412-0.641j, -0.06-0.3j, -0.012-0.121j, -0.08+0.0j]
↓ 最後に逆フーリエ変換します。
IFFT(FFT(PX_total)) = [0.2 0.42 0.26 0.12 0. ] # ナイーブに計算したのと同じ結果
$j$ は虚数単位を表します。
途中で実数ではなく複素数が出てくるなど、なかなか難解ですが、最終的には得たい確率分布を得られるのはなんとも不思議な感じがしますね。
計算時間の比較
実際の計算時間も比べてみました。
Pythonのプログラムで上記の処理を実装しています。
ナイーブな計算（青）では指数的に計算時間が増え、広告メニュー数が14で6秒以上の計算時間になります。このままの推移ですと、広告メニュー数が20を超えると現実的な時間では計算が難しくなるでしょう。
一方でフーリエ変換を使った計算（オレンジ）では、広告メニュー数が14でも0.0008秒程度で計算でき、その差は歴然です。計算時間は線形に増えるので、広告メニュー数が100でも1000でも、一瞬で計算できるでしょう。
最後に
今回は、フーリエ変換という数学の概念を使って、広告の実務で必要となるフリークエンシー分布の計算を効率化する事例を紹介しました。
フーリエ変換も、畳み込みについての定理も、それ自体は大学の数学の授業で習うような基礎的な内容ではありますが、こうした理論と実務とがふとつながる瞬間がこの仕事の醍醐味だと感じています。