nomuyu

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

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

皆さんはWordPressでブログ記事を書くとき、どのように執筆していますか？ 私は普段から慣れているMarkdownで下書きをして、最後にWordPressのエディタに貼り付けることが多いです。 でも、この作業、地味に面倒じゃないですか？ Markdownのままでは正しく表示されない（太字や見出しなど） 特に、技術ブログで必須の数式の変換がうまくいかない... いちいち手動でHTMLタグに修正するのが大変！ そんな悩みを解決するために、Markdownで書いた文章をWordPress記法に一発で変換する ...

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

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

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

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

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

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

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

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

  あるところに、これから合コンする予定の男子A,B,Cの３人がいました。 彼らは仲が良く、合コンで狙う女子が被って喧嘩にならないように事前にとある約束をしました。なぜならば合コン中に男子同士で喧嘩するのはみっともないからです。   ある程度場が進んだら、自分の箸を狙っている女子に向け、男子にだけその人が狙っている女の子がわかるようにしました。   そして、その時がやってきました。相対する女子はX,Y,Zの三人 C君はXちゃんに揃えた箸を向けました。 B君は決めかねたのか、Y ...

二部グラフ \(G=(V, U, E)\) が森であるならぱ、 \(|E| \leq|V|+|U|-1\) という不等式が成り立つ理由を説明 します。ここで、森とは閉路を含まないグラフを指します。   まず、基本的なグラフ理論の概念について確認しましょう。   グラフ理論の確認 1. 木と森の定義: ・木: 閉路を持たない連結なグラフ。 ・森: 閉路を持たないグラフ（つまり、複数の木の集合）。 2. 二部グラフ: ・グラフ \(G=(V, U, E)\) が二部グラフである場合、頂点集 ...

テンソル場を理解するのに必要な知識は、 双対空間（双対基底） テンソル です。 ささっと復習してテンソル場の定義、性質をこの記事で理解します。   この線形空間\(V\)とその双対空間\(V^*\)をそれぞれ\(s\)個、\(r\)個ずつ直積してできるベクトル空間を\((r,s)\)型テンソル空間と呼びます。       テンソル場 多様体\(M\)の各点にテンソルを割り当てたテンソル場というものを考えましょう。 ３つ以上のテンソル場のテンソル積も同様です。 &nb ...

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