NTTドコモR&Dの技術ブログです。

1=1+(1-1)の話

※この記事は同日投稿の"One Equals One Plus One Minus One"を翻訳したものです。

NTTドコモ R&D Advent Calendar 2022 の15日目の記事です。

1=1

私は DOCOMO Innovations, Inc. の Senior Research Engineer としてモバイル通信ネットワークの最適化に携わっています。ネットワーク最適化を考える上で,複雑な計算に頭を悩ませることがよくあります。ネットワークは相互に接続された多くのシステムで構成される複雑なシステムですが,単純なものから理解することで複雑なものの理解につながります。例えば次の数式はとても当たり前のものですが,意外と役に立つことがあります。

 \displaystyle
    1 = 1 + (1 - 1).

本記事では,この単純な式がいくつかの数学の基礎となっており,通信ネットワーク(特に信号処理)を考える上でも役に立つことを紹介していきます。

タピオカミルクティー

「3人の息子と17頭のラクダ」という古い有名な話がありますが,それを少し言い換えてみましょう。17杯のタピオカミルクティーがオフィスに届けられ,3つの部署が専有面積に応じて分配することになりました。A部の面積はオフィスの半分を,B部の面積はオフィスの1/3を,C部の面積はオフィスの1/9を,それぞれ占めているので,17杯の中から,A部は 8.5 杯,B部は 5 \frac{2}{3} 杯,C部は 1 \frac{8}{9} 杯になります。

さて,A部は8.5杯を受け取りました。つまり,コップは9杯あって,うち8杯は完全なタピオカミルクティーで,最後の1杯だけはコップの半分だけタピオカミルクティーが注がれています。この最後の1杯には肝心のタピオカが入っていません。もとの完全なタピオカミルクティーから半分を別のコップに注ぎ分けた際に,タピオカが流れて出てこなかったようです。タピオカの有無で揉め事になる前に人事部が自身で個別に買っていたタピオカミルクティー1杯を提供しました。すると初めから合計18杯が存在していたことになるのでもう一度,専有面積で分配し直してみましょう。A部は9杯,B部は6杯,C部は2杯と分けられます。 9+6+2=17 なので人事部は自身が提供した1杯を持ち帰ることができます。

人事部は揉め事を解決するために1を足して1を引きました ( 17 = 17 + (1 - 1) )。平等性を保ちながら計算が簡単になりました。タピオカが偏ることもないですね。

二次方程式

以下はより抽象的な話になります。

 \displaystyle
    x = x+(y-y).

タピオカミルクティーの分配の次は,数学の真髄に迫る問題になります。次の式において, a,b,c を定数として, x を解きます。

 \displaystyle
    ax^{2} + bx + c = 0.

もし「ああ,簡単だ,二次方程式の解を使おう。覚えてるぞ」

 \displaystyle
    x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a},

と考えるなら, x = x+(y-y) を使うことも考えてみましょう。でも,どうやって使いますか? はじめに,係数  a を式  ax^{2} + bx + c = 0 から取り出します。次に, x=x+(y-y) より, \frac{b^{2}}{4a^{2}} を足して引きます。すなわち,

 \displaystyle
\begin{split}
    a x^2 + bx + c & = a \left[ x^2 + \frac{b}{a}x + \frac{c}{a} \right] \\
    & = a \left[ x^2 +\frac{b}{a} x + \frac{b^2}{4a^2} - \frac{b^2}{4a^2} + \frac{c}{a} \right] \\ 
    & = a \left[ \left( x + \frac{b}{2a} \right)^2 - \frac{b^2}{4a^2} + \frac{c}{a} \right] = 0
\end{split}

次に,式を変形して左辺に x だけ残します。

 \displaystyle
    \begin{split}
        \left( x+ \frac{b}{2a} \right) ^2 & = \frac{b^2 - 4ac}{4a^2} \\
        x + \frac{b}{2a} & = \frac{\pm \sqrt{b^2-4ac}}{2a} \\ 
        x & = \frac{-b \pm \sqrt{b^2-4ac}}{2a} 
    \end{split}

関数の関数

同じ要素の足し算・引き算から,掛け算・割り算に話を進めましょう。

 \displaystyle
    x = x * \frac{y}{y}.

二次方程式の次は,合成関数の導関数について考えてみましょう。合成関数とは,ある関数の出力が別の関数の入力になっているもの,つまり関数の関数です。合成関数の導関数は次のように得られます。

 \displaystyle
    \begin{split}
        (f \circ g)'(x) & = \lim_{\epsilon \rightarrow 0} \frac{f(g(x)) - f(g(\epsilon))}{x-\epsilon}
    \end{split}

 x = x* \frac{y}{y} を使ってこれを解いてみましょう。 g(x)-g(\epsilon) を掛けて割り,ふたつの要素の積に分けます。

 \displaystyle
    \begin{split}
        (f \circ g)'(x) & = \lim_{\epsilon \rightarrow 0} \frac{f(g(x)) - f(g(\epsilon))}{x-\epsilon} \frac{g(x)-g(\epsilon)}{g(x)-g(\epsilon)} \\
        & = \lim_{\epsilon \rightarrow 0} \frac{f(g(x)) - f(g(\epsilon))}{g(x)-g(\epsilon)} \frac{g(x)-g(\epsilon)}{x-\epsilon} \\ 
        & = \lim_{\epsilon \rightarrow 0} \frac{f(g(x)) - f(g(\epsilon))}{g(x)-g(\epsilon)} \lim_{\epsilon \rightarrow 0} \frac{g(x)-g(\epsilon)}{x-\epsilon} \\
        & = f'(g(x)) \cdot g'(x)
    \end{split}

これはいわゆる連鎖律 *1です。連鎖律はニューラルネットワークの訓練アルゴリズムであるbackpropagationや最適解を見つける勾配降下法などに用いられています。

量子化誤差

これまでの話では,ある値を追加したり削除したりしてきました。ではランダムな値を追加しても良い結果が得られるのでしょうか? もちろん可能です。ディザリング (Dithering) とは意図的にランダムな値を式に加える便利な手法です。まずは概要を説明して理解を深めてから,ディザリングによって得られた結果をいくつか紹介します。

量子化の中でディザリングを使ってみましょう。量子化とはアナログ信号(例:人間の声)をデジタル信号(例:スマホの音声メモ)に変換する際に発生します。スマホで電話をかけると声が相手に届く前に量子化されています。大まかに言えば,量子化とは荒くグループに分類することです。1から10の間で任意の数を選んで,これを1から10の間の偶数に量子化すると,1以下の量子化誤差が発生します(例:1を2に量子化すると誤差1が発生)。次にこの概念を別のものに喩えてみましょう。

お気に入りのカフェが突然メニューの種類を半分にしてしまいました。この場合,メニューを量子化したと言えるでしょう。お気に入りの紅茶はメニューから消えましたが,似たような風味の紅茶がいくつかメニューに並んでいます。あなたが好きだった紅茶と注文した紅茶の違いが量子化ノイズです。

ディザリングには減算ディザリング(乱数の加算と減算をする)と非減算ディザリング(乱数を加算するが減算しない)があります。理論的には減算ディザリングは非常に有効ですが,実際にはシステム制約上,非減算ディザリングの方が適用しやすいです。

例えば,減算ディザリングを使えば,量子化ノイズはどのような入力に対しても統計的に独立であることを示すことができます。ちなみに,入力に応じてノイズを加えるのは,ヘッドホンのノイズキャンセリング機能の仕組みです(つまり外界の音の逆の音をノイズとして加えます)。カフェのメニューが減った例で説明すると,カフェに何度も通って,お気に入りの紅茶に一番近い味の紅茶をランダムに選ぶと,お気に入りの紅茶がひとつもなくても,長い目で見ればあたかもお気に入りの紅茶を楽しんでいるように錯覚することができるのです。似たような紅茶の味をランダムに選ぶことがディザリングであり,お気に入りの紅茶の本来の味がすると錯覚することがディザリングの効果です。声を量子化すると誤差が生じますが,通話相手が聞く分にはディザリングによって平均的には誤差なくきちんと声が伝わったという認識を得ることができます。

実際には,紅茶の選択からディザリング効果を引き算することはできません。また,実際には,減算ディザリングは,非常に単純なケース*2以外では実装が困難です。より高度な数学については,こちらこちらで詳しく説明しています。今回は,非減算ディザリングに着目して,ディザリングの威力を見ていきたいと思います。

画像への適用例

非減算ディザリングとはランダムに要素を追加することであり,量子化の際に使用します。図1のような画像を考えてみましょう。一番左の画像はメキシコのどこかで筆者が撮影した背の高い植物のカラー画像です。この画像の各ピクセルを白と黒のどちらかに量子化していきます。左から2番目の画像は,原画像の色の強さに応じて,画素を2値(黒か白)のどちらかに決定することで量子化していますが,画質の多くが失われています(例えば,鳥の絵の空は真っ白になりました)。左から3番目の画像は,Floyd-Steinberg ディザリング と呼ばれるもので,量子化による出力値を決める際に,直前の出力値決定で生じた誤差を元にしてノイズとして付与します(例えば,鳥の絵の空の一部は量子化後も残っています)。基本的にノイズは画像そのものから発生します。連続してピクセルが白になると,次のピクセルは黒になる可能性が高くなります(ただし保証はありません)。4枚目(一番右)の画像は,画像全体に任意のパターンでノイズを繰り返しかける Ordered ディザリング で量子化を行います。画像の多くの部分で網目のような4x4のパターンを確認することができますが,これはパターン内の各点が異なるノイズ値を持つためです。画像を注意深く見ると,4x4のサイズで繰り返しのパターンが見えてきます。

2つのディザリングの違いをよりよく理解するために,図2は図1の鳥の絵の箇所を拡大したものです。今度は,量子化によって画像の一部が失われることになります。色彩豊かな原画像から単調な白黒画像になってしまうのです。しかし,ノイズを加えることでより見やすく原画に近い画像を作成することができます。

図1:左から順に,原画像,2値化画像,Floyd–Steinberg ディザリングによる2値化画像,Ordered ディザリングによる2値化画像

図2:左から順に,鳥の絵の箇所を拡大した原画像,2値化画像,Floyd–Steinberg ディザリングによる2値化画像,Ordered ディザリングによる2値化画像

まとめ

ある値を追加してから削除することで有益な結果が得られる事例を紹介しました。量子化する際にも工夫して値を追加することで視覚的に美しい結果を得ることができました。数学を知ることは道具としての使い方を知ることです。その道具の最もシンプルな部分をよく理解すれば,どの道具を使えばよいか自然と分かるようになります。

著者:David Ramirez,翻訳:井上 義隆

*1:賢明な読者のみなさんは,ゼロによる除算を処理するために,1つの隠れたステップがあることに気づくでしょう。

*2:デジタル・アナログ変換器のダイナミックレンジを知ることで,減算ディザリングの実用化における技術的な課題を理解することができます。