畳み込みの仕組み | Convolution

Summary

このビデオでは、数のリストや関数の組み合わせ方として、畳み込みという少し話題に上がることの少ない方法に焦点を当てています。畳み込みは画像処理や確率分布、微分方程式の解析など、多様な分野で応用される重要な概念です。具体的な例を通して、畳み込みの基本的な考え方や計算方法、さらには高速フーリエ変換（FFT）を利用した効率的な計算アプローチまでを解説しています。視聴者は、畳み込みがどのようにして多式の掛け算や確率分布の足し合わせ、画像処理におけるぼかし効果などに応用されるのかを学びます。また、この概念がなぜ数学やコンピュータサイエンスで広く利用されるのかについての理解も深められるでしょう。

Takeaways

• 😀 2つのリストや関数を組み合わせて新しいリストや関数を作る方法を考える
• 😊 ダイスを投げて出目のペアの確率を求める問題では畳み込みの考え方が使える
• 🧐 畳み込みは2つのリストの各要素を組み合わせて新しいリストを作る操作
• 😯 FFTを使うと畳み込みを高速に計算できる(計算量がN^2からNlogNに)
• 😲 畳み込みは画像処理や確率など様々な分野で現れる汎用的な操作
• 🤔 多項式の掛け算をするときにも畳み込みの考え方を使える
• 🤯 FFTで2つの大きな数の掛け算も高速にできる可能性がある
• 😀 小学生が習う大きな数の掛け算も各桁での畳み込みといえる
• 👍 適切に選んだ入力の繰り返しパターンを使うと計算が楽になる
• 💡 畳み込みの定義から逆方向の高速アルゴリズムまで数学的に導出できる

Q & A

畳み込みとは数学的にどのように定義されているのでしょうか?

純粋な数学の文脈では、2つの関数や数列の畳み込みは、一方の関数や数列を反転させた上で、移動平均的に掛け合わせ足し合わせていく操作として定義されます。コンピュータ上の実装では反転することなく計算していることもありますが、この定義が自然に導出される背景があります。

なぜ画像処理で畳み込みがよく使われるのでしょうか?

画像をフィルタリングする際に、画像の各ピクセルの周囲の値を考慮することが多く、このとき窓関数的な小さな配列を画像と畳み込みを取る操作が発生します。ぼかしやエッジ検出など、様々な画像処理効果を畳み込みで実現できます。

畳み込みを高速に計算するアルゴリズムとは何でしょうか?

畳み込みを直接計算すると計算量が二乗オーダーとなりますが、フーリエ変換を利用することで線形オーダーのアルゴリズムを構築できます。これが高速フーリエ変換(FFT)です。畳み込み定理に基づいて導出されます。

畳み込みはなぜニューラルネットに現れるのでしょうか?

畳み込みは、画像認識などの分野で有効なニューラルネットワークの構造の一つです。そこではカーネルがニューラルネットが学習によって最適化されるため、特定のタスクに適したフィルタリング効果を持たせる事ができます。

2つの多項式を掛け算することと畳み込みにはどのような関係がありますか?

2つの多項式を掛け算することは、それぞれの係数の畳み込みと同値です。つまり、多項式の係数を配列として表現すれば、配列同士の畳み込み演算を行うことができます。これに基づいて畳み込みの効率的な計算法が構築されています。

移動平均との関係はどのようなものでしょうか?

1を足して1となる短い配列と長い配列の畳み込みを取れば、その出力は元の長い配列の滑らかなバージョン、つまり移動平均となります。画像処理でのぼかしもこの仕組みを利用しています。

確率分布の足し算と畳み込みにはどのような関係がありますか?

2つの確率変数の確率分布関数を足し算することは、その確率質量関数同士の畳み込みを取ることと等価です。ダイスなどの例で、各出目の確率を配列にしておき、畳み込みを取れば、和の確率分布が得られます。

畳み込みの長さはなぜ元の2つの長さより大きくなるのでしょうか?

純粋に数学的な操作としては、移動平均的な窓関数を動かすイメージの畳み込みではなく、あくまで2つの関数の合成演算と捉えられます。その性質上、出力は入力より大きくなることが起こり得ます。具体的な計算機上の実装では切り取るなどの操作が入ります。

畳み込みを計算する効率的なアルゴリズムの概要を教えてください。

まず入力の数列それぞれに対して高速フーリエ変換(FFT)で周波数空間に変換します。これらを係数のようにしてから成分ごとに掛け合わせます。最後に逆フーリエ変換して時間空間に戻せば、畳み込みが得られます。これにより計算量が二乗オーダーから線形オーダーに改善されます。

小学校で整数の掛け算を習うアルゴリズムと畳み込みにはどのような関係がありますか?

小学校で習う整数の桁ごとの掛け算と桁ごとの足し算をする計算は、各桁での畳み込み演算を行っていると見る事ができます。これに基づいて大きな整数に対しても線形オーダーで実行可能な掛け算アルゴリズムが理論的に存在する事が分かります。

Outlines

00:00

😊 畳み込みの基本的な概念と確率への適用

2つの数のリストや関数を組み合わせて新しいものを作る方法として、単純な足し算や掛け算に加えて「畳み込み」がある。これは画像処理や確率分布の組み合わせなどに広く用いられる。2つのダイスの出目の確率分布を組み合わせる例で畳み込みの概念を説明。

05:03

😃 畳み込みによる新しい数のリストの生成

畳み込みは2つの数のリストから新しいリストを生成する操作でもある。移動平均の計算などに利用できる。画像処理の例として、画像と特定のカーネル(値のグリッド)の畳み込みにより、ぼかしやエッジ検出などの効果が得られる。

10:05

🤔 カーネルの選択による畳み込みの多機能性

畳み込みで用いるカーネルの値を変えることで、多様な画像処理を実現できる。Gaussianカーネルでは画像がぼけた印象に、エッジ検出のカーネルではエッジが際立つ。ニューラルネットで最適なカーネルを学習することも可能。

15:05

📈 多項式の掛け算と畳み込みの関係性

2つの多項式の掛け算は、それぞれの係数を畳み込みすることと同じ。これは多項式を展開して項を集める過程と一致する。計算量的に畳み込みの方が大変だが、FFTを用いれば高速にできる。

20:06

😆 FFTによる畳み込みの高速化

FFT(高速フーリエ変換)を用いると、畳み込みをNlogNの計算量で実行でき、劇的に高速化される。これにより、多項式の掛け算や確率分布の組み合わせなど、実用的な大規模な畳み込みが可能になる。

Keywords

💡畳み込み

畳み込みは、2つの関数や数列を組み合わせて新しい関数や数列を作る数学的操作です。このビデオでは、確率分布の足し算や画像処理の例を通して、畳み込みの概念と定義が説明されています。

💡確率分布

確率分布とは、確率変数がとりうる値ごとに、その発生確率が定められている関数です。このビデオでは、サイコロの出目による確率分布同士の畳み込みが、新しい確率分布を作る例として出てきます。

💡画像処理

画像処理とは、コンピューターを使ってデジタル画像に様々な処理を施す技術です。このビデオで画像のぼかしなど、画像処理の効果がカーネルと呼ばれる小さい配列と元の画像の畳み込みによって実現している例が紹介されています。

💡カーネル

カーネルとは、画像処理や畳み込みニューラルネットワークにおいて、画像や他のデータに滑らかに重ね合わせて処理を行うための小さな配列(関数)のことです。このビデオでは、カーネルの違いによって、ぼかしやエッジ検出など、異なる画像処理を行えることが説明されています。

💡FFT(高速フーリエ変換)

FFT(高速フーリエ変換)は、デジタル信号処理において、信号の周波数スペクトルを高速に得るためのアルゴリズムです。このビデオでは、FFTを使うことで、計算量の大きな畳み込みを効率的に実行できることが説明されています。

💡掛け算

このビデオでは、2つの関数の掛け算がそれぞれの係数の畳み込みと等価であることが説明されています。さらに、FFTを使えば、大きな多項式の掛け算を効率的に計算できることも示されています。

💡移動平均

移動平均は、時系列データにおいて、その時点を中心とした近傍のデータの平均値を求めていく手法です。このビデオでは、移動平均が長いデータと短い平均化用のデータの畳み込みとして表現できる例が出てきます。

💡線形方程式

このビデオでは、畳み込みが分からない関数の値の断片的な情報から、その関数を表す(線形の)方程式を解くことに相当することが説明されています。

💡ぼかし

ぼかしは、画像処理における基本的な技法の一つです。このビデオでは、ガウス分布のカーネルを使ったぼかし処理が、画像とカーネルの畳み込みとして表現されている例が紹介されています。

💡エッジ検出

エッジ検出は、画像処理において、画像中のコントラストの大きな変化を検出することです。このビデオでは、適切なカーネルを使うことで、畳み込みによってエッジ検出が実現できることが示されています。

Highlights

数のリストや関数の組み合わせの分脈では全く新しいものです

確率で最も単純な例の1つで皆さんも人生のどこかで考えたことがあるでしょう2つのダイスを投げて異なる目の輪が出る確率

この過程が畳み込みの基本的な考え方の1つになります

これは至るところに出てきます画像処理にはいつも出てくるし確率の角となる部分に関係していたり微分方程式を解くのによく使われたり

コードまで踏み込んでいて興味のある方は概要欄からご覧ください

全体としてこの過程では左から右に進むにつれピクセルの値の変化を検出しますなのである意味画像の縦の線を検出していくことになります

2つの関数を掛け算することはごとの操作になりますがまずそれぞれの関数が多公式だとして係数を取ってきてそれからこの2つの係数のリストの畳み込みを計算するのと同じことになります

FFTコボルを使うと同じものを別の方法で計算してたった均4.3mm秒で計算できましたなので3桁違いの改善ですね

こんな感じのペアの掛け算の表を作って斜めに足していったそれぞれが出力に対応しています

小学校で習った普通の方法ですねこれがそれぞれの桁の畳み込みになっていることを説明してみましょう

つまりnの2乗のオーダではなくNLNで済むような方法です

畳み込みは基本的にただの掛け算よりずっと複雑に感じられることです

裏口から忍び込むように畳み込みをするんですね

ある数学の操作や概念が一見無関係な領域にたくさん出てくると面白いということのとても良い例だと思います

Transcripts

2つの数のリストあるいは2つの異なる

関数を与えられたとしましょうこれらの

リストを組み合わせて新しい数のリストを

作ったり2つの関数を組み合わせて新しい

関数を作ったりする方法をできる限り

たくさん考えてみてください1つ単純な

やり方は1つ1つの項を足し合わせること

ですよ

ね同様に関数についても対応する出力を

全部足し合わせることができますそして

同様に2つのリストを項ごとに掛け算する

こともできてこれも関数でもすることが

できできますねしかしこれら2つと同じ

くらい基本的でなのにずっと話されること

の少ない組み合わせ方があるんです

畳み込みです2つの例とは違ってこれは

単に数にできる操作に由来するものでは

ありません数のリストや関数の組み合わせ

の分脈では全く新しいもの

ですしかしこれは至るところに出てきます

画像処理にはいつも出てくるし確率の角と

なる部分に関係していたり微分方程式を

解くのによく使われたりそれからこの名前

でなくとも見たことがある多式の掛け算で

も出てきます資格化して説明する

チャンネルでは特に良いトピックですねと

いうのも公式的な定義を文脈なしに

いきなり見せられるとちょっと怖い感じが

しますからしかし時間をかけてこれが何を

言っているのかを紐解きそしてその前に

なぜこんなものが欲しいのか

モチベーションを得ることにしましょう

とっても美しい操作ですからねそしてこの

内容の資格化から学ぶことも多い

でしょう2つの関数の畳み込みでは様々な

資格化の方法が考えられますがそのうち1

つからはなぜ正規分布が確率でその役割を

果たすのかについて発見があるかもしれ

ません関数の形とかに関連してるのですが

ちょっと先走ってますね今回の動画では

まず理3的な場合に注目して特に意外で

とてもかこいこの計算のアルゴリズムの話

をしそれから次のパートで連続的な場合に

ついて話したいと思い

[音楽]

ます今回とても画像処理の話から始めたい

のですががというのも資格的で1番面白い

ですからねただやや扱いにくさがあって

畳み込みの代表にしづらいので代わりに

確率からお話ししたいと思います特に最も

単純な例の1つで皆さんも人生のどこかで

考えたことがあるでしょう2つのダイスを

投げて異なる目の輪が出る確率を考えると

いうことをしたいと思いますはい皆さんは

こうおっしゃるでしょう余裕だね2つの

ダイスにはそれぞれ6つの異なる出目が

あり全部で36の異なる結果のペアが得

られますそしてこれを全部見てくとある輪

になるペアがいくつあるか数えられますね

このように行子上にペアを並べると嬉しい

ことに同じ輪になるペアは斜めに揃って

見えます

ねなのである輪がどれだけ出やすいかは

単にこの斜めに沿ってペアがいくつあるか

数えれば分かりますねはいよくできました

という感じですがしかし同じ問題を資格化

する他の方法を思いつきますかある輪を

持つ異なるペア全部を資格化する方法です

もしかしたら皆さんの1人が手を上げて

あるよと言うかもしれませんこれらの出目

を2列で並べて2つ目をひっくり返すん

ですねこうすると輪が7になる異なるペア

全てが縦に揃いますねそして下の列を1番

左までずらすと足して2になるペアがただ

1つ現れますここから右に1つ分ずらすと

足して3になる異なるペアが2つ現れます

ねそして一般にひっくり返した後下の列を

何個分ずらしたかによってある輪になる

ペアが全部分かるということになります

そしてこれだけだとあんまり面白くない

ですねただこれらのカテゴリにそれぞれ

いくつペアがあるか数えているだけです

からこれはそれぞれの出目が出る確率が

同様に確からしいという暗黙の過程に

基づいていますがもしこれが一様でないと

したらどうでしょう変なダイスの青い方は

それぞれの出目が出る確率が決まっていて

赤の方も別の数のリストがあったらどう

でしょうこの場合例えば2が出る確率を

知りたかったら青の台数の1が出る確率と

赤の台数の1が出る確率を掛け算します

そして3が出る確率についてはありえる2

つの異なるペアについて再び対応する確率

を掛け合わせてそれからその積を

足し合わせ

ます同様に4が出る確率は3つの異なる

デメのペアについて掛け算をして結果を

足し合わせますそしてこの上の確率をA1

A2A3という風に名付けて下をB1b2

B3という風にし

ましょう一般にこの2つの異なる数の列を

取って2つ目をひっくり返して異なる数分

ざらしてペアの掛け算を足し合わせていく

この過程が畳み込みの基本的な考え方の1

つになり

[音楽]

ますさてもう少し正確に説明すると今この

過程で2から12までの輪それぞれを見る

確率を計算しましたこれをするには値のの

リストの1つ目Aともう1つのリストBを

混ぜていました言い換えるとこれら2つの

畳み込みで新たな数のリストを得られると

言えます新たな11個の値からなる数の

リストでそれぞれの値はペアの席を

足し合わせたような見た目をしています

もし先ほどの例がを好きなら同じ操作を

まず全てのペアの席の表を作ってそれから

斜めに足し合わせていくと考えることも

できますこれも2つの数のリストを

混ぜ合わせて新たな11の数のリストを

作る方法になっていますねただ視点が

異なるだけで窓をスライドさせるのと同じ

操作ですちょっと書き方も見てみましょう

小さなアステリスクで表されるAとBの

畳み込みは新たなリストになっています

そのN番目の要素は添字のペアIとJに

ついてその輪がNに等しいものを全て

足し合わせたものになっています少し

分かりづらかったかもしれませんが例えば

もしNが6なら計算するペアは1と52と

43と34と25と1ということになり

ます足して6になる全てのペアですねただ

ただ正直どう書いても良くてこの過程の

書き表し方よりも資格的な要素の方が重要

でしょうここで練習のためにとても単純な

例題を考えましょう123と456という

2つのリストの畳み込みを考えてみ

ましょう先ほどのように2つのリストの

うち2つ目をひっくり返して1番左まで

ずらして始めましょうこうすると1と4が

揃うのでこれを掛け算すると出力の最初の

要素が得られますね下のリストを1つ右に

ずらすと揃うペアをは15と24になり

ますこれらをかけて足すと13が得られ

ます出力の次の数ですねもう1つずらして

1下6+25+3-4を計算すると28に

なりますえさらにもう1つずらして2下6

+3下5で27を得て最後に3下6で18

になりますねもし良かったらお好きな

プログラミング言語とライブラリーを持っ

てきて計算していただけると結果が確かめ

られると思います123と456の

畳み込みを取ると実際これが得られる結果

になっていますねこれが自然でちょうど

欲しい操作になっている例2つの確率分布

を足す場合を見てきましたもう1つよく

ある例が移動平均です長い数のリストが

あってもう1つ全部足すと1になる短い数

のリストがあるとしましょうここでは

1/5の値が5つある小さなリストがあり

ますねそしてこの窓をスライドさせる

畳み込みのプロセスを行うとどうなるか見

てみ

[音楽]

ましょう小さなリストが大きなリストと

完全に重なった時畳み込みの各項には

どんな意味があるでしょう

かそれぞれの計算では大きなリストの

データを取ってきてそれぞれに1/5を

かけて足していますつまりこの小さな窓の

中でデータの平均を取っていることになり

ます全体としてこの過程で元のデータを

滑らかにしたようなバージョンが得られ

ますこれは少し調整して異なる数のリスト

を使うこともできます値が足して1になる

限り移動平均として解釈できるでしょう

ここで示した例ではこの移動平均は中央の

値により重みがあるようになっていてこれ

でもまたデータの滑らかなバージョンを得

られ

ますこれの2次元バージョンをすると画像

をぼかす面白いアルゴリズムが得られます

ここでお見せするアニメーションは元の

英語版の中の人がMITのジュリアラボと

の講義用に作ったものを改変したもので

画像処理についての単元も含まれています

そちらではもう少しコードまで踏み込んで

いて興味のある方は概要欄からご覧

くださいぼかしの例に戻るとここでは3下

3の値のグリッドがあってこれが元の画像

の上を滑っていきズームインするとこれら

の値それぞれは1/9になっていますね

そして毎回の計算で何をしているかと言う

とこれらの値をちょうど重なっている

ピクセルと掛け算してるんですねもちろん

コンピューターの中では色も赤緑青の3つ

の値のベクトルとして考えますからこれら

の値を全て1/9倍して足し合わせるとと

それぞれの色についての平均の値が出て右

の画像で対応するピクセルはこれを集めた

ものになっていますこれを画像の全ての

ピクセルについて行うとそれぞれの

ピクセルがある意味周りに染み出すような

形で元の画像をぼかしたバージョンが得

られ

ます言い換えると右の画像は元の画像と

小さな値のグリッドの畳み込みだと言え

ますより厳密にはこの値のグリッドを

180°回転させたバージョンの畳み込み

だと言うべきですね対象なので関係ない

ですが純粋な数学の分脈から導かれる

畳み込みの定義は2つ目の配列を

ひっくり返すことと関連していたことを

思い出し

ましょうこれを少し調整して異なる値の

グリッドを使うともっと綺麗なぼかしの

効果を得ることができますここでは5下5

のグリッドを使っていますが先ほどと大き

さだけでなく値も異なっていますズーム

インすると真ん中の値が端より大きくなっ

ていますねこれはガウス分布として知ら

れるベルカーブから持ってきた値

ですこうするとこれらの値全てを対応する

ピクセルと掛け合わせた時端よりも中心の

ピクセルに集中することになり

ます先ほどと同様に右側で対応する

ピクセルはこの輪になっていますこれを

全てのピクセルについて行うとレンズの

焦点をずらした時により近いようなぼかし

の効果が得られ

ますこのアイデアでできることは決して

ぼかしだけではありません例えばこの

グリッドを見てみましょう左にせの値が右

に負の値があってそれぞれ青と赤に色付け

されてい

ます少し時間を取って処理後の画像が

どんな感じになるか予想してみて

ください今回は画像をカラーではなく

モノクロで考えたいと思いますなので

それぞれのピクセルは3つでなく1つの値

で表されますそして今度の畳み込みでは負

の値も考えられますね例えばこの点で

ズームインするとグリッドの左半分は値が

0で表される黒いピクセルに完全に重なっ

ています一方右の負の値の3マスは値が1

で表される白いピクセルに重なっています

なのでそれぞれ掛け算して足し合わせると

計算結果はとても小さい負の値になります

ね右の画像は負の値を赤正の値を青で

色付けしていますもう1つ注目したいのは

全部同じ色の部分では値が0になってい

ますグリッドの中の値のが0ですからね

これは先ほどまでのグリッドの中の辺りの

輪が1で移動平均つまりぼかしとして解釈

できたレートは大きく異なります全体とし

てこの過程は左から右に進むにつれ

ピクセルの値の変化を検出しますなので

ある意味画像の縦の線を検出していくこと

になり

ますそして同様にグリッドを回転させて上

から下に値が変わるようにすると今度は横

の線を検出するようになりますパイ

クリーチャーの目が悪魔的な感じになって

しまいまし

[音楽]

たこの小さなグリッドはカーネルと呼ばれ

ますここで美しいのは異なるカーネルを

選ぶだけで異なる画像処理の効果が得

られるところですよねぼかし境界検出だけ

でなくシャープにすることもできます

畳み込みニューラルネットワークを聞いた

ことがあるかもしれませんそちらでは

データを元にどんなカーネルが良いかを

見つけますこれはニューラルネットワーク

が何を検出したいかによって決められます

ねもう1つ力の長さについても触れた方が

良いかもしれません例えば移動平均のよう

な例では両方の窓が完全に重なっている

部分の甲だけを考えたいですよねあるいは

画像処理の例では出力が元の画像と同じ

サイズになっていて欲しいですよねただ

純粋な数学の操作としての畳み込みは基本

的に元の2つのリストより長いリストを

作ります少なくとも一方が長さ1の場合を

除きますなのでコンピューターの特定の

領域では一部を切り抜くことになり

ます

さらにもう1つコンピューターに関連して

話しておく価値があるのがこの計算の前に

カーネルをひっくり返すのはよくかなり変

だとか別にいらないと感じられるかもしれ

ませんしかし繰り返しになりますがこれは

純粋な数学の文脈に由来するもので確率の

例で見たようにとっても自然なことなん

ですそしてちょっともう1つプログラマー

も気にすべき純粋な数学の例をお見せし

たいと思いますこれは畳み込みをずっと

早く計算するアルゴリズムにもつがってい

ますからねPythonで2つの異なる

比較的大きな配列を作りたいと思います

それぞれ10万のランダムな要素を持って

いますここでナパというライブラリーの

実行時間を見てみ

ましょうこの場合何回か繰り返し計算して

平均を取っているようでこの

コンピューターでは平均4.87秒という

ことになりました対象的に栽培

ライブラリーの別の関数FFTコボルを

使うと同じものを別の方法で計算して

たった均4.3mm秒で計算できましたな

ので3桁違いの改善ですねこれは名前が

違っても両方同じ畳み込みを計算してい

ますただ片方がずっと賢い方法で計算し

てるんです

ね確率の例を思い出しましょう畳み込みの

別の考え方としてペアの席の表を作って

斜めに足し合わせるという話をしまし

たこれはもちろん確率に限った話ではあり

ません数のリスト2つの畳み込みはいつで

もこのように考えることができますこんな

感じのペアの掛け算の表を作って斜めに

足していったそれぞれが出力に対応してい

ますこれが特に自然な見方になっているの

が2つの多式を掛け算する時です例えば

ここにある表をちょっと書き換えて上の数

を

12X3x2乗そしてもう1つの方を

45x6x2にしてみましょうさてこれら

全てのペアの席をを作ることにどんな意味

があるでしょう

かこれは2つの多式の席を完全に展開して

いるのと同じことになりますねそして斜め

に足し算をしていくのは同じ時数の項を

集めることに対応しています多項式を展開

して整理するのが畳み込みと全く同じ

プロセスになっているのはそれ自体

すっきりしていると思うんですが実はここ

から結構すごいことができるんです

ちょっと考えてみてください2つの異なる

関数を掛け算することはこれはごとの操作

になりますがまずそれぞれの関数が多公式

だとして係数を取ってきてそれからこの2

つの係数のリストの畳み込みを計算するの

と同じことになります面白いのは畳み込み

は基本的にただの掛け算よりずっと複雑に

感じられること

ですこれは単に概念的に難しいというだけ

でなく計算的にもペアの掛け算をするより

も畳み込みをする方がより多くのステップ

がかかり

ます例えば2つのとても大きい多式を考え

ましょうそれぞれ係数が100個あります

そしてこの席を全部展開すると100下

100のペアの席の表を埋めることになり

ますから1万の異なる席を計算することに

なりますそれから斜めに値を集めて足して

いくのはさらに大体1万くらいの計算を

用し

ます言い換えるとこのアルゴリズムの

オーダーはN2乗ですつまりサイズがnの

2つのリストについて必要な計算の量はn

の2乗に比例して増えていきます一方で2

つの多式を出力の点で考えたら例えばいく

つかの点での値を集めてきたらこれらを

掛け算するのはサンプルの数の回数だけの

計算で済みますそして多式の係数を求める

には有限のサンプルだけあれば大丈夫です

ね例えば2つの出力があればある一次関数

を特定できますね3つの出力があれば2次

関数を特定することができて一般にNコの

出力があればNコの係数を持つ多式を特定

することができ

ます線形方程式の言葉で言い換えてみ

ましょうある係数の分からない多式があっ

たとしますこの例ではこれが計算しようと

している席だったとしましょうそしてこの

多式にいろんな入力0123とかを入れて

いったらどうなるかだけお伝えしたとし

ます十分な数これを伝えてつまり分から

ないの数と同じだけの方程式があればあと

たまたまこれがラッキーなことに線形方程

式系だとしたらこれで係数を求めることが

できるはずですなのでざっくり

アルゴリズムの大枠を話すと2つの数の

リストの畳み込みを計算する時これを多項

式の係数のように扱って十分たくさんの点

でこれらの多式を評価して部屋の掛け算を

してそれから軽を解いて係数を求めます

裏口から忍び込むように畳み込みをするん

ですねそして皆さんの中ににはこう思う人

もいるかもしれませ

んバカなプランだとというのも1つの多式

についてサンプルを計算するだけでまずn

の2乗のオーダーの計算が必要でまた線形

方程式系を解くのも最初から畳み込みを

するくらい計算的に難しいんじゃないかと

そして確かに掛け算と畳み込みの関係が

あるけれど難しいところは全部この視点の

移動じゃないかというかもしれませ

んでもトリックがあるんですね皆さんの中

で営変換やFFTをご存知の方は予想が

つくかもしれませんもしご存知でない方は

これから言うことは少々トピかもしれませ

んただ数学の道筋でこれが予想外になら

ないようなたどり方もあると知って

いただけると良いでしょうまアイディアは

ここで選択の自由があることです適当な

入力例えば0123みたいなものの代わり

に特別に選んだ複素数で多式を評価するん

ですね特に単位円上で均等に並んだ1の

累乗コを使いますこうするとより楽な経営

が得られ

ます要は類似していくと繰り返しの

パターンを持つような数を選ぶことで作ら

れる系に同じ数が何度も繰り返して異なる

項に登場するようにするわけですそして

この繰り返しを賢く使うと計算でずっと楽

をすることができるんです

ねこの出力の集合には特別な名前がついて

いて係数の利3風リエ変換と呼ばれます

これらのトピックについてもジュリア

MITの講義がありますので是非ご覧

くださいそれから高速風流変換について

リーブルというチャンネルがとってもいい

動画を出しているので見てみてください

あとベリタcumというチャンネルでも

FFTのとても良い動画が上がっています

この高速なアルゴリズムこそが今私たちに

とって重要なところですそしてこの

繰り返しのおかげで係数からこれらの出力

を出す方法があるんですねN2乗の

オーダーの代わりにN下logNでより

大きなリストになるとずっとずっと早い

計算をすることができるようになります

そして重要なことにFFTは片道だけじゃ

ないんですね出力から係数に行くことも

できますというわけでアルゴリズムの全体

像をもう1度見てみましょうか2つの長い

数のリストがあって畳み込みを計算したい

時まずそれぞれの高速風流変換を計算し

ますこれらを他行式の係数のように扱って

特別な点の集合で評価したようなものとし

て考えると良い

でしょうそれから得られた2つの結果を

計算してこのペアの席は早く計算できます

ねそれから逆高速振り変換をして探して

いった畳み込みを裏口から計算できるわけ

ですしかし今度はNlogNの横断の計算

で済みますこれは結構すごいと思います

この畳み込みが出てくるかなり具体的な

文脈他方式の掛け算は畳み込みが出てくる

他の全ての物事に関わるアルゴリズムに

つながっています確率分布を足したり

大きな画像を処理したり何でもですある

数学の操作や概念が一見無関係な領域に

たくさん出てくると面白いということの

とても良い例だと思い

ますちょっとした宿題が欲しい方はこんな

面白いことを考えてみましょう2つの

異なる数を掛け算する時小学校でみんな

習った普通の方法ですねこれがそれぞれの

桁の畳み込みになっていることを説明して

みましょうま繰り上がりのようにおまけの

ステップもついていますが基本的には

畳み込みですそして高速なアルゴリズムが

あるということは2つの非常に大きな整数

を掛け算すると

これを小学校で学んだやり方よりも早く

計算する方法があるということになります

つまりnの2乗のオーダではなくNLNで

済むような方法ですそもそも不可能に感じ

られますよねま実際役に立つ前にこの2つ

の数が馬鹿げた大きさにならないといけ

ないんですがでもそういったアルゴリズム

が存在するのは結構面白いと思います

畳み込みシリーズの次回は確率分布に注目

して連続な場合を見ていきたいと思い

ます

[音楽]