畳み込みの仕組み | Convolution
Summary
TLDRこのビデオでは、数のリストや関数の組み合わせ方として、畳み込みという少し話題に上がることの少ない方法に焦点を当てています。畳み込みは画像処理や確率分布、微分方程式の解析など、多様な分野で応用される重要な概念です。具体的な例を通して、畳み込みの基本的な考え方や計算方法、さらには高速フーリエ変換(FFT)を利用した効率的な計算アプローチまでを解説しています。視聴者は、畳み込みがどのようにして多式の掛け算や確率分布の足し合わせ、画像処理におけるぼかし効果などに応用されるのかを学びます。また、この概念がなぜ数学やコンピュータサイエンスで広く利用されるのかについての理解も深められるでしょう。
Takeaways
- 😀 2つのリストや関数を組み合わせて新しいリストや関数を作る方法を考える
- 😊 ダイスを投げて出目のペアの確率を求める問題では畳み込みの考え方が使える
- 🧐 畳み込みは2つのリストの各要素を組み合わせて新しいリストを作る操作
- 😯 FFTを使うと畳み込みを高速に計算できる(計算量がN^2からNlogNに)
- 😲 畳み込みは画像処理や確率など様々な分野で現れる汎用的な操作
- 🤔 多項式の掛け算をするときにも畳み込みの考え方を使える
- 🤯 FFTで2つの大きな数の掛け算も高速にできる可能性がある
- 😀 小学生が習う大きな数の掛け算も各桁での畳み込みといえる
- 👍 適切に選んだ入力の繰り返しパターンを使うと計算が楽になる
- 💡 畳み込みの定義から逆方向の高速アルゴリズムまで数学的に導出できる
Q & A
畳み込みとは数学的にどのように定義されているのでしょうか?
-純粋な数学の文脈では、2つの関数や数列の畳み込みは、一方の関数や数列を反転させた上で、移動平均的に掛け合わせ足し合わせていく操作として定義されます。コンピュータ上の実装では反転することなく計算していることもありますが、この定義が自然に導出される背景があります。
なぜ画像処理で畳み込みがよく使われるのでしょうか?
-画像をフィルタリングする際に、画像の各ピクセルの周囲の値を考慮することが多く、このとき窓関数的な小さな配列を画像と畳み込みを取る操作が発生します。ぼかしやエッジ検出など、様々な画像処理効果を畳み込みで実現できます。
畳み込みを高速に計算するアルゴリズムとは何でしょうか?
-畳み込みを直接計算すると計算量が二乗オーダーとなりますが、フーリエ変換を利用することで線形オーダーのアルゴリズムを構築できます。これが高速フーリエ変換(FFT)です。畳み込み定理に基づいて導出されます。
畳み込みはなぜニューラルネットに現れるのでしょうか?
-畳み込みは、画像認識などの分野で有効なニューラルネットワークの構造の一つです。そこではカーネルがニューラルネットが学習によって最適化されるため、特定のタスクに適したフィルタリング効果を持たせる事ができます。
2つの多項式を掛け算することと畳み込みにはどのような関係がありますか?
-2つの多項式を掛け算することは、それぞれの係数の畳み込みと同値です。つまり、多項式の係数を配列として表現すれば、配列同士の畳み込み演算を行うことができます。これに基づいて畳み込みの効率的な計算法が構築されています。
移動平均との関係はどのようなものでしょうか?
-1を足して1となる短い配列と長い配列の畳み込みを取れば、その出力は元の長い配列の滑らかなバージョン、つまり移動平均となります。画像処理でのぼかしもこの仕組みを利用しています。
確率分布の足し算と畳み込みにはどのような関係がありますか?
-2つの確率変数の確率分布関数を足し算することは、その確率質量関数同士の畳み込みを取ることと等価です。ダイスなどの例で、各出目の確率を配列にしておき、畳み込みを取れば、和の確率分布が得られます。
畳み込みの長さはなぜ元の2つの長さより大きくなるのでしょうか?
-純粋に数学的な操作としては、移動平均的な窓関数を動かすイメージの畳み込みではなく、あくまで2つの関数の合成演算と捉えられます。その性質上、出力は入力より大きくなることが起こり得ます。具体的な計算機上の実装では切り取るなどの操作が入ります。
畳み込みを計算する効率的なアルゴリズムの概要を教えてください。
-まず入力の数列それぞれに対して高速フーリエ変換(FFT)で周波数空間に変換します。これらを係数のようにしてから成分ごとに掛け合わせます。最後に逆フーリエ変換して時間空間に戻せば、畳み込みが得られます。これにより計算量が二乗オーダーから線形オーダーに改善されます。
小学校で整数の掛け算を習うアルゴリズムと畳み込みにはどのような関係がありますか?
-小学校で習う整数の桁ごとの掛け算と桁ごとの足し算をする計算は、各桁での畳み込み演算を行っていると見る事ができます。これに基づいて大きな整数に対しても線形オーダーで実行可能な掛け算アルゴリズムが理論的に存在する事が分かります。
Outlines
😊 畳み込みの基本的な概念と確率への適用
2つの数のリストや関数を組み合わせて新しいものを作る方法として、単純な足し算や掛け算に加えて「畳み込み」がある。これは画像処理や確率分布の組み合わせなどに広く用いられる。2つのダイスの出目の確率分布を組み合わせる例で畳み込みの概念を説明。
😃 畳み込みによる新しい数のリストの生成
畳み込みは2つの数のリストから新しいリストを生成する操作でもある。移動平均の計算などに利用できる。画像処理の例として、画像と特定のカーネル(値のグリッド)の畳み込みにより、ぼかしやエッジ検出などの効果が得られる。
🤔 カーネルの選択による畳み込みの多機能性
畳み込みで用いるカーネルの値を変えることで、多様な画像処理を実現できる。Gaussianカーネルでは画像がぼけた印象に、エッジ検出のカーネルではエッジが際立つ。ニューラルネットで最適なカーネルを学習することも可能。
📈 多項式の掛け算と畳み込みの関係性
2つの多項式の掛け算は、それぞれの係数を畳み込みすることと同じ。これは多項式を展開して項を集める過程と一致する。計算量的に畳み込みの方が大変だが、FFTを用いれば高速にできる。
😆 FFTによる畳み込みの高速化
FFT(高速フーリエ変換)を用いると、畳み込みをNlogNの計算量で実行でき、劇的に高速化される。これにより、多項式の掛け算や確率分布の組み合わせなど、実用的な大規模な畳み込みが可能になる。
Mindmap
Keywords
💡畳み込み
💡確率分布
💡画像処理
💡カーネル
💡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つ
の数が馬鹿げた大きさにならないといけ
ないんですがでもそういったアルゴリズム
が存在するのは結構面白いと思います
畳み込みシリーズの次回は確率分布に注目
して連続な場合を見ていきたいと思い
ます
[音楽]
تصفح المزيد من مقاطع الفيديو ذات الصلة
But what is a convolution?
京都大学 数学・数理科学5研究拠点合同市民講演会「源氏香はクラスタリング~ベル数とその周辺~」間野修平(情報・システム研究機構 統計数理研究所 数理・推論研究系 教授)2021年11月6日
MongoDB Schema Design | Embedding or Referencing? MongoDB Tutorials
Using Images in Next.js (next/image examples)
【大学数学】線形代数入門①(概観&ベクトル)【線形代数】
PythonでPDFファイルを操作しよう!業務自動化・効率化で使える!!〜初心者向け〜 pypdf・reportlab
5.0 / 5 (0 votes)