機械学習/AI

クイックソート徹底解説-アルゴリズムの仕組みから厳密な性能分析まで

ソートアルゴリズムの世界には、マージソート、ヒープソートなど、数多くの強力な候補が存在します。これらのアルゴリズムは、最悪の場合でも $\Theta(n \lg n)$ という優れた性能保証を持っています。一方で、今回解説するクイックソートは、最悪のシナリオでは $\Theta(n^2)$ という、単純なバブルソートなどと同レベルの非常に遅い実行時間となってしまいます。それにもかかわらず、クイックソートはC言語の標準ライブラリ qsort のような多くの場面で採用され、「実用上最も高速なソートア ...

2分探索木（BST）を完全解説｜探索・挿入・削除・計算量・中間順巡回まで

2分探索木（Binary Search Tree；BST）は、動的に変化する要素集合に対して、探索・最小値・最大値・前後要素の取得•挿入•削除といった操作を、木の高さ $h$ に比例する時間で実現する基本データ構造です。本章では、BST の定義（2分探索木条件）から始め、中間順木巡回（inorder）による昇順出力、SEARCH／MINIMUM／MAXIMUM／SUCCESSOR／PREDECESSOR の各クエリー、さらに INSERT／DELETE の実装までを、擬似コードとともに ...

乱択アルゴリズム徹底解説：計算量を劇的に改善する「ランダム性」の力

皆さんは「ランダム」という言葉を聞いて、どんなイメージを持つでしょうか？おそらく、サイコロを振る、ルーレットが回る、宝くじを引く、といった予測不能な出来事を思い浮かべるかもしれません。ゲームやギャンブルの世界では、この予測不能性が面白さを生み出す要素となっています。実は、コンピューターのアルゴリズムの世界でも、「ランダム性」は非常に強力なツールとなり得ます。通常、アルゴリズムはどんな入力に対しても正しい答えを効率的に出すように設計されます。しかし、時には「意地悪な入力」が存在し、特定のアルゴリズムの効率 ...

Transformer完全攻略ロードマップ：基礎から応用までを徹底解説

近年、自然言語処理や画像認識などさまざまな分野で活躍している「Transformer」。その革新的な構造が、深層学習の常識を大きく変えています。しかし、Attentionをはじめとする各要素を正しく理解しないと、実装や応用でつまずくことも多いのではないでしょうか。本記事では、Transformerを体系的に学ぶために押さえておきたいポイントを4つの記事に分けて、最適な順番で解説した「ロードマップ」をご紹介します。まずはTransformerの全体像を把握し、続けてAttention機構やPosition ...

アルゴリズムの設計：マージソート(Merge-sort)で学ぶ分割統治法の計算量解析

アルゴリズムの設計とは、与えられた問題を解決するための手続き・手順を考案し、それを正しく効率的に実行できるように組み立てる作業のことです。具体的には、入力（問題のデータ）と出力（結果）との間に、どのようなステップを踏めば解が得られるかを体系的に示し、それを計算機（あるいは人間）が順序通りに実行できるように定義することを指します。アルゴリズムの「性能」を評価するためには、以下のような観点が重要です。正しさ：アルゴリズムが意図したとおりに動作し、正しい結果を返すかどうか。実行時間：アルゴリズムを動かした ...

アルゴリズムの解析：RAMモデルと挿入ソートで学ぶ計算量の基本

「アルゴリズム」という言葉は、一言でいえば「何らかの問題を解決するための、手順や処理のしかたの明確な規則」を指す。たとえば「ある数列の中から目的の数を探し出す」「複数のデータを並び替える（ソートする）」「複雑な数値計算を行う」「パズルを解く手順を機械的に表す」といった事柄はすべてアルゴリズムの一例となる。アルゴリズムには必ず、入力（処理の対象となるデータ、問題設定）出力（得られる結果）明確かつ有限回のステップによる手順が存在する。たとえば「レシピ」や「数学の定理の証明における一連のステップ」も、 ...

情報幾何におけるアフィン接続について

皆さん、こんにちは！今日は情報幾何という分野に出てくる「アフィン接続」という考え方を、できるだけ丁寧に解説していきます。まずは、身近な例から考えてみましょう。例えば、地球儀のような曲面の上に、アリがチョークで線を引くことを想像してみてください。アリにとっての「まっすぐな線」って、どういうものでしょうか？地球儀の上では、普通の定規で引いたような線は「まっすぐ」ではありませんよね。実は、この「まっすぐ」という考え方が、アフィン接続と深く関わっているんです。ベクトル空間と多様体：舞台設定 ...

オートエンコーダー（AutoEncoder）を徹底解説：なぜ対数尤度ではなくELBOが目的関数となるのか【VAE】

オートエンコーダーの基本概念オートエンコーダー( Autoencoder )は、入力データをコンパクトな表現（潜在表現）へと圧縮し、その後、圧縮した情報から元のデータを復元することを学習するニューラルネットワークの一種です。具体的には、ある入力ベクトル $$ \mathbf{x} \in \mathbb{R}^D $$ を与えると、オートエンコーダーはまずエンコーダ(Encoder)によって $\mathbf{x}$ を低次元の潜在表現 \(\mathbf{z} \in ...

TransformerのAttentionの線形化による計算量削減【Linear Transformer】

TransformerとはGPTなど広く使われるAIモデルで、もともとは自然言語処理の機械翻訳の分野において提案されたEncoderとDecoderからなる深層学習モデルです。こちらの記事ではTransformerやMulti-Head Attentionに関する詳しい解説をしています。ぜひご覧ください。 Transformerは「Attention機構」を用いることで、入力系列中の遠距離にある各単語間の関連性を捉えることができます。このような特性を実現させるのが「Scaled Dot-Product ...

【最適輸送】シンクホーンアルゴリズム

最適輸送問題とシンクホーンアルゴリズム最適輸送問題とは、物理学や経済学などの分野で長い歴史を持つ数理的な問題です。この問題は、ある場所に存在する物資を別の場所に運ぶ際の最適な方法を探求します。具体的には、物資を運ぶためのコストを最小化する方法を見つけることを目的としています。この記事でも定式化していますが、最適輸送は重み付き点群を輸送コストをもとに比較するツールです。点群Aと点群Bの違い、距離を求めるものです。これの定式化は以下です。しかしこれにはいくつか短所があります。中でも、問 ...

ワッサースタイン(Wasserstein)距離とは？距離の公理を満たすことの証明まで

GANなどの生成モデルで使われるようになりたびたび聞くことも増えたワッサースタイン(Wasserstein)距離というものを解説します。ワッサースタイン距離というのは一言でいうと、確率分布間を測る距離の一つです。この記事では離散確率分布に対するワッサースタイン距離の定義とそれが距離の公理を満たすことを証明します。最適輸送問題とは最適輸送問題は、物理学や経済学などの分野で長い歴史を持つ数理的な問題です。この問題は、ある場所に存在する物資を別の場所に運ぶ際の最適な方法を探求します。具体的 ...

サポートベクターマシン（SVM）徹底解説！マージン最大化とカーネル法、双対問題とは

この記事ではできうる限り厳密にサポートベクターマシンの理論について解説を行っていく。この記事を読めばSVMのおおよそすべてが分かる。注意としては実装の仕方やコードなどの解説は一切行わない。理論的な部分に関しての解説をとことん行う。サポートベクターマシン(SVM)とはサポートベクターマシン(SVM)とは、サポートベクトルマシンとも呼ばれ、分類問題でよく用いられる有名な機械学習の手法の一つである。分類問題とは、入力されたデータを複数の特定のカテゴリーに分ける問題である。た ...

サポートベクターマシン(SVM)の最適化

この記事ではサポートベクターマシン(SVM)の最適化問題について特化して詳しく解説していく。 SVMのマージン最大化などの基本的な理論についてはこちらの記事を参考にしてほしい。むしろ順番としてはこちらの記事を読んでからこの記事を読んだほうが理解が深まると思う。 SVMの基本原理 SVMの基本的な目的は、データを分類する最適な超平面を見つけることである。この超平面は、異なるクラスに属するデータポイントを最も効果的に分離する。SVMでは、次の二つの主要な概念が用いられる。マージン最大化: SV ...

Positional Encoding徹底解説：Sinusoidal（絶対位置）から相対位置エンコーディング

Transformerで使われているPositional EncodingであるSinusoidal Positional Encodingについて徹底的に解説してさらに、そこから相対位置エンコーディングへの橋渡しをこの記事では行う。なるべく直感的に、なぜこのような手法がとられるのか、なぜうまくいくのか、現時点での僕ができうる限り解説する。この記事を読めばInput Embeddingがどういう気持ちで何をやっているのかがわかることと思う。必要な前提知識は三角関数だけである。（線形代 ...

Multi-Head AttentionとScaled Dot-Product Attentionの全て：Transformerの核心を徹底解説

この記事では、Transformerの中心的な役割を果たすMulti-Head Attentionについて解説する。 Transformerのほかの機構の詳細な解説はせず、完全にMulti-Head Attention特化の解説となるので、ほかの機構や全体観を掴みたい方はこちらの記事をご一読いただきたい。この記事はまずはScaled Dot-Product AttentionというMulti-Head Attentionの中で使われている核心部分についてこれでもかと詳しく解説したのちに、本 ...

1 2 3 Next »