アルゴリズムとデータ構造

数学 機械学習技術 人工知能技術 グラフデータアルゴリズム デジタルトランスフォーメーション プログラミング技術 本ブログのナビ

アルゴリズムとデータ構造

アルゴリズムとデータ構造は、コンピューターサイエンスの基本的な概念であり、密接に関連している。

アルゴリズムは、入力を取り込み、それを何らかの手順で処理し、最終的に出力を返すプロセスを表すもので、コンピューターサイエンスや数学、物理学、経済学、心理学など、多くの分野で利用されている重要な手法となる。またアルゴリズムは、ある問題を解決する手順や方法を明確に定めた手続きともいうこともできる。

アルゴリズムは数学と密接に関連している。数学は、抽象的な問題を形式化し、具体的な問題に変換することができるが、この数学を用いることで、問題を形式化してアルゴリズムに落とし込むことが可能となる。これは具体的には、離散数学での集合論や論理学を用いた、探索アルゴリズムの設計などになる。

このような数学的アプローチは、アルゴリズムの開発だけでなく、アルゴリズムの評価にも用いられる。アルゴリズムの評価は、正しさ、効率性、汎用性などの観点から行われ、正しいアルゴリズムは、すべての入力に対して正しい出力を返す必要があり、効率的なアルゴリズムは、処理時間や必要なリソースの量が少なく、速く処理でき、汎用的なアルゴリズムは、異なる入力に対しても同じ手順で処理できるように設計されている。これらの評価はすべて数学的表現を持って行われている。

具体的なアルゴリズムとしては、ソート、検索、パターン認識、データーベース、誤り訂正、暗号化のような基本的なアルゴリズムの他にマルコフ連鎖モンテカルロ法のようなシミュレーションアルゴリズムもある。以下にそれらのいくつかの例を挙げる。

• バブルソートアルゴリズム: バブルソートアルゴリズムは、数値の配列を昇順または降順に並び替えるために使用される。このアルゴリズムは、隣接する2つの要素を比較し、必要に応じて交換を繰り返すことで、配列全体をソートする。

• ダイクストラの最短経路アルゴリズム: ダイクストラの最短経路アルゴリズムは、グラフの最短経路問題を解決するために使用される。このアルゴリズムは、始点から各ノードへの最短距離を計算し、最短距離が確定したノードから次のノードを選択していくことで、全てのノードへの最短経路を見つける。

• クイックソートアルゴリズム: クイックソートアルゴリズムは、バブルソートと同様に配列をソートするために使用される。このアルゴリズムは、配列を分割し、部分配列ごとにピボットと呼ばれる要素を選択し、ピボットの左側と右側にそれぞれ小さい値と大きい値を移動させることで、配列全体をソートする。

• 線形探索アルゴリズム: 線形探索アルゴリズムは、配列やリストなどのデータ構造から、指定された要素を検索するために使用される。このアルゴリズムは、配列の最初から順番に要素を比較していき、指定された要素が見つかるまで続ける。

データ構造は、データを効率的に格納、検索、操作するための方法を指す。プログラミングでは、データを効率的に操作するために、適切なデータ構造を選択することが重要となる。データ構造には、以下のような種類がある。

• 配列(Array): 同じ種類のデータを連続的に格納するためのデータ構造。要素へのアクセスが高速ではあるが、要素の追加や削除にコストがかかる。

• リスト(List): データの順序を維持しながら要素を追加や削除できるデータ構造。要素へのアクセスには時間がかかる。

• スタック(Stack):  LIFO(Last In, First Out)の動作で要素の追加や削除ができるデータ構造。高速なスタックのトップからの要素へのアクセスが可能となる。

• キュー(Queue):  FIFO(First In, First Out)の動作で要素の追加や削除ができるデータ構造。高速なキューの先頭からの要素へのアクセスが可能となる。

• ツリー(Tree):  階層的なデータ構造で、ルートノードから複数の子ノードを持つことができる構造を持つ。データの挿入や検索が高速となる。

• グラフ(Graph):  ノードとエッジで構成されたデータ構造で、複雑な関係を表現することができる。グラフの探索や最短経路探索には様々なアルゴリズムが存在する。

データ構造を効率的に操作するためには、適切なアルゴリズムを使用する必要がある。例えば、配列内の要素を検索する場合、線形探索アルゴリズムよりも、二分探索アルゴリズムの方が効率的となる。また、グラフ内の最短経路を見つける場合、ダイクストラの最短経路アルゴリズムやベルマン・フォードのアルゴリズムなど、さまざまなアルゴリズムが存在する。

このようにある特定のデータ構造には、それを扱う特定のアルゴリズムがあり、データ構造が異なると同じ問題を解決するためのアルゴリズムも異なる場合もある。

さらに、アルゴリズムの選択によって、データ構造の効率性が大きく変わることがある。例えば、リストの途中に要素を挿入する場合、配列よりもリストの方が効率的であり、リスト内の要素をランダムにアクセスする場合は、配列の方が効率的となる。

アルゴリズムは、コンピュータープログラミングにおいて特に重要であり、多くのプログラムは、特定の問題を解決するために設計されたアルゴリズムを実行することで動作する。プログラミングにおいて、アルゴリズムを設計することは、コンピュータープログラムの設計の中で最も基本的で重要なステップの一つとなる。

またアルゴリズムは関数であり、また一定の順序に連結された操作の連鎖である。更に、一定の順序に連結された操作の連鎖とはプログラミングそのものでもあり、数学の世界とプログラミングの世界をつなぐものでもある。アルゴリズムの世界に現れるデータ構造や解析手法は、様々な言語の使いこなしや、機械学習/人工知能技術のための基礎となる。

本ブログでは以下に様々なアルゴリズムの理論と実装について述べる。

基本的なアルゴリズム

• アルゴリズムイントロダクション

本書は，計算機科学の基礎分野で世界的に著名な4人の専門家がMITでの教育用に著した計算機アルゴリズム論の包括的テキストであり，その第3版．前版までで既にアルゴリズムとデータ構造に関する世界標準教科書としての地位を確立しているが，より良い教科書を目指して再び全面的な記述の見直しがなされ，それを基に新たな章や節の追加なども含めて，大幅な改訂がなされている．
単にアルゴリズムをわかりやすく解説するだけでなく，最終的なアルゴリズム設計に至るまでに，どのような概念が必要で，それがどのように解析に裏打ちされているのかを科学的に詳述している．
さらに各節末には練習問題（全957題）が，また章末にも多様なレベルの問題が多数配置されており（全158題），学部や大学院の講義用教科書として，また技術系専門家のハンドブックあるいはアルゴリズム大事典としても活用できる

• 探索アルゴリズムの概要と各種アルゴリズムおよび実装

探索アルゴリズム（Search Algorithm）とは、問題の空間内で目標を見つけるために使用される計算手法の一群を指す。これらのアルゴリズムは、情報検索、組み合わせ最適化、ゲームプレイ、ルートプランニングなど、さまざまな領域で幅広く応用されている。ここでは、この探索アルゴリズムに関して様々なアルゴリズムと応用事例および具体的な実装について述べている。

• 自己適応型探索アルゴリズムの概要と適用事例および実装例について

自己適応型探索アルゴリズム（Self-Adaptive Search Algorithm）は、進化計算や最適化の文脈で使われるアルゴリズムの一群で、アルゴリズム内のパラメータや戦略が問題に適応的に調整される特徴を持つものとなる。これらのアルゴリズムは、問題の性質や環境の変化に適応し、最適解を効率的に見つけるために設計されている。ここではこの自己適応型探索アルゴリズムに関して様々なアルゴリズムおよび実装例について述べている。

• 多目的探索アルゴリズムの概要と適用事例および実装例について

多目的探索アルゴリズム（Multi-Objective Optimization Algorithm）は、複数の目的関数を同時に最適化するためのアルゴリズムとなる。多目的最適化は、1つの最適解を求めるのではなく、複数の最適解の中からバランスの取れた解（パレート最適解セット）を見つけることを目的としており、このような問題は、実世界の多くの複雑なシステムや意思決定問題に適用されている。ここではこの多目的探索アルゴリズムの概要とアルゴリズム及び実装例について述べている。

• 探索的ランキングの概要とアルゴリズム及び実装例

探索的ランキング（Exploratory Ranking）は、情報検索や推薦システムなどの順位付けタスクにおいて、ユーザーが関心を持つ可能性の高いアイテムを特定するための手法となる。この手法は、ユーザーが与えたフィードバックに基づいて、順位付けされたアイテムの中からユーザーが最も関心を持つアイテムを見つけることを目的としている。

• Maximum Marginal Relevance (MMR)の概要とアルゴリズム及び実装例について

Maximum Marginal Relevance（MMR）は、情報検索や情報フィルタリングのためのランキング手法の1つで、情報検索システムがユーザーに提供する文書のランキングを最適化することを目的としたものとなる。MMRは、複数の文書の中からユーザーの関心に関連する文書を選択するための方法として開発された。この手法では、各文書の関連性と多様性の両方を考慮してランキングを行い、具体的には、文書の関連性が高いが他の選択肢との類似性が低い文書を選択することを重視したものとなる。

• ミニマックス法の概要とアルゴリズム及び実装例について

ミニマックス法は、ゲーム理論や人工知能の分野で広く使用される探索アルゴリズムの一種であり、完全情報ゲーム（両プレイヤーが全ての情報を知っているゲーム）において最適な手を選択するために使用されるものとなる。代表的なゲームとしては、チェスや将棋、オセロ、囲碁などがある。

• アルファベータ剪定の概要とアルゴリズム及び実装例について

アルファベータ剪定（Alpha-beta pruning）は、人工知能やコンピュータ・ゲームの分野で使用される探索アルゴリズムの一種であり、特に、”ミニマックス法の概要とアルゴリズム及び実装例“で述べているミニマックス法などの木探索アルゴリズムと組み合わせて使用されることが一般的なアプローチとなる。このアルゴリズムは、ゲームの木構造を探索する際に、不要な探索を削減して効率的に解を見つけるために用いられ、具体的には、ゲームの可能な手の組み合わせを木構造で表現し、その探索中に不要な手を削除することで、計算時間を短縮している。

• モンテカルロ木探索の概要とアルゴリズム及び実装例について

モンテカルロ木探索（Monte Carlo Tree Search、MCTS）は、決定木探索の一種であり、ゲームの状態空間を探索し、最適な行動を見つけるための確率的手法となり、特にゲームや意思決定問題において効果的なアプローチとなる。

• UCT (Upper Confidence Bounds for Trees)の概要とアルゴリズム及び実装例について

UCT（Upper Confidence Bounds for Trees）は、モンテカルロ木探索（MCTS）の選択フェーズにおいて使用されるアルゴリズムであり、探索中の各ノードの探索価値をバランス良く評価することを目的としているものとなる。UCTは、探索と利用のバランスを取ることが重要となる。つまり、探索中のノードが多く訪問されるほど、そのノードの価値を高く見積もるようになるが、同時に未探索のノードにも適切な探索の機会を与える。

• Information Set Monte Carlo Tree Search (ISMCTS)の概要とアルゴリズム及び実装例について

Information Set Monte Carlo Tree Search（ISMCTS）は、不完全情報ゲーム（例：ポーカー）や情報を隠すゲーム（例：囲碁、将棋）などのゲームで使用されるMonte Carlo Tree Search（MCTS）の変種であり、MCTSを適用してゲーム木を探索する際に、情報セットと呼ばれるゲームの状態のグループを扱うことが特徴の手法となる。

• Nested Monte Carlo Search (NMC)の概要とアルゴリズム及び実装例について

Nested Monte Carlo Search（NMC）は、モンテカルロ木探索（MCTS）の一種であり、探索空間を効率的に探索するための手法となる。NMCは、複数のレベルの探索を組み合わせることで、高い探索効率を実現している。

• Rapid Action Value Estimation (RAVE)の概要とアルゴリズム及び実装例について

Rapid Action Value Estimation（RAVE）は、”モンテカルロ木探索の概要とアルゴリズム及び実装例について“で述べているモンテカルロ木探索（MCTS）の拡張として開発された、ゲーム木探索の手法の一つとなる。RAVEは、ゲーム木探索中に選択された手の価値を推定するために使用され、通常のMCTSでは、モデルが不完全な場合や探索が進むにつれて、探索された手の統計情報を用いて手の価値を推定するのに対して、RAVEはこれを改善し、より迅速に適切な手を見つけることを目指したものとなる。

• ランキングアルゴリズムの概要と実装例について

ランキングアルゴリズムは、与えられたアイテムの集合を、ユーザーにとって最も関連性の高い順に並べ替えるための手法であり、検索エンジン、オンラインショッピング、推薦システムなど、さまざまな分野で広く使用されているものとなる。ここでは、一般的なランキングアルゴリズムの概要について述べる。

• ランダムフォレストランキングの概要とアルゴリズム及び実装例

ランダムフォレスト（Random Forest）は、機械学習の分野で非常に人気のあるアンサンブル学習法(複数の機械学習モデルを組み合わせることで、個々のモデルよりも優れた性能を得る手法)の一つであり、複数の決定木（Decision Tree）を組み合わせて、より強力なモデルを構築するアプローチとなる。ランダムフォレストを利用して特徴量のランキングを行う際、さまざまなバリエーションが存在している。

• 多様性促進ランキングの概要とアルゴリズム及び実装例

多様性促進ランキング（Diversity-Promoting Ranking）は、情報検索や推薦システムなどで重要な役割を果たす手法の一つであり、この手法は、ユーザーが情報検索結果や推薦されるアイテムのリストをより多様でバランスの取れたものにすることを目的としたものとなる。通常、ランキングの目的は、ユーザーの関心に合ったものを上位に表示するが、このときに同じような内容や特徴を持つアイテムが上位に複数表示されることがある。例えば、商品の推薦システムであれば、似たような商品や同じカテゴリの商品が上位に並ぶことがよくある。しかし、これらのアイテムが類似しているため、ユーザーの興味を十分にカバーすることができず、情報の偏りや選択肢の制約をもたらす可能性があり、このような問題に対処するために、多様性促進ランキングが使用されている。

• ランクSVMの概要とアルゴリズム及び実装例

ランクSVM（Ranking Support Vector Machine）は、順位付けタスクに適用される機械学習アルゴリズムの一種であり、特に情報検索や推薦システムなどの順位付け問題に使用されるものとなる。関連する論文としては”Optimizing Search Engines using Clickthrough Data“、”Ranking Support Vector Machine with Kernel Approximation“等がある。

• Diversified Top-k Retrieval (DTkR)の概要とアルゴリズム及び実装例について

Diversified Top-k Retrieval（DTkR）は、情報検索やランキングのタスクにおいて、多様性を持った上位k件の検索結果を取得するための手法であり、単純なTop-kの結果ではなく、異なる観点や多様性を持った検索結果を得ることを目指すものとなる。一般的なTop-kの検索では、単純にスコアが高い上位k件を取得することが目的だが、類似したものが上位に並びがちであり、多様性に欠ける。一方で、DTkRは、検索結果をより多様かつ異なるものにすることを目指し、単純なTop-kの検索結果では得られない多様性を持った情報検索を行うことができる。

• Submodular Diversificationの概要とアルゴリズム及び実装例について

Submodular Diversificationは、情報検索やランキングのタスクにおいて、多様性を持った上位k件の選択を行うための手法の一つであり、この手法は、選択されたアイテム間の相互作用を考慮し、多様性を最大化しつつ効率的に上位k件を選択することを目指すものとなる。Submodular Diversificationの基盤となるのが、”劣モジュラ最適化と機械学習“でも述べているSubmodular 関数で、これは、集合関数 \( f: 2^V \rightarrow \mathbb{R} \) で、以下の性質を持つ関数となる。

• Cluster-based Diversificationの概要とアルゴリズム及び実装例

Cluster-based Diversificationは、アイテムのクラスタリングを利用して推薦システムに多様性を導入する手法となる。この手法では、類似したアイテムを同じクラスタにグループ化し、異なるクラスタからアイテムを選択することで多様性を実現している。

• ニューラルランキングモデルの概要とアルゴリズム及び実装例

ニューラルランキングモデルは、検索エンジンや推薦システムなどで利用される機械学習モデルの一種であり、主な目的は、与えられたクエリやユーザーの情報に基づいて、最適な順位でアイテム（例えばウェブページや商品など）を並び替えるものとなる。一般的な検索エンジンの場合、ユーザーが検索したクエリに最も関連性の高いウェブページを最初に表示することが重要で、これを実現するために、検索エンジンは多くの要因を考慮してウェブページのランキングを決定している。これには、キーワードの一致度、ページの信頼性、ユーザーの過去のクリック履歴などが含まれる。

• パーソナライズドランキングの概要とアルゴリズム及び実装例

パーソナライズドランキングは、ユーザーごとに最適な順位でアイテムを提供するランキングの手法で、一般的なランキングシステムでは、全ユーザーに対して同じ順位でアイテムを提示するが、パーソナライズドランキングは、ユーザーの個別の嗜好や行動を考慮して、そのユーザーにとって最適な順位でアイテムをランク付けするものとなる。パーソナライズドランキングの目的は、ユーザーが興味を持つ可能性の高いアイテムを上位に表示することで、ユーザーエンゲージメントを向上させるユーザーエンゲージメントの向上、ユーザーの購買、クリック、その他のアクションを増やし、コンバージョン率を向上させるコンバージョン率の増加、ユーザーが求める情報や商品を素早く見つけられることで、ユーザー満足度を高めるユーザー満足度の向上などになる。

• Beam Searchの概要とアルゴリズム及び実装例について

Beam Search（ビームサーチ）は、主に組み合わせ最適化問題や意味のある解を見つける問題に適用される探索アルゴリズムとなる。Beam Searchは、広い探索空間を効率的に探索するための手法で、通常はツリー構造を持つ解空間において探索され、主に機械翻訳、音声認識、自然言語処理などの領域で使用されている。

• ランダムウォークの概要とアルゴリズム及び実装例

ランダムウォーク（Random Walk）は、グラフ理論や確率論で用いられる基本的な概念で、グラフ上のランダムな移動パターンを表現し、グラフ内の構造や特性を理解するのに役立つ手法となる。

• 機械学習におけるメッセージパッシングの概要とアルゴリズム及び実装例

機械学習におけるメッセージパッシングは、グラフ構造を持つデータや問題に対する効果的なアプローチで、特に、グラフニューラルネットワーク（Graph Neural Networks, GNN）などの手法で広く使用されている手法となる。

• メタヒューリスティクスの数理　読書メモ

メタヒューリスティクスとは、難度の高い最適化問題を解くための経験的手法（ヒューリスティクス）を有機的に結合させたものであり、最近では、実務的な問題を楽に解くためのフレームワークとして、実務家の間でよく用いられる最適化アルゴリズムとなっている。実際問題を解くとき、ある程度のプログラミングの腕と、メタヒューリスティクスの選択眼と、設計のコツさえつかんでいれば、比較的短時間でロバスト（頑強）な解法を設計できる。

• メタヒューリスティックと応用 読書メモ

本書は新たな最適化手法である「メタヒューリスティクス」のアルゴリズムと応用事例を体系的にまとめたものである。アルゴリズム編では、Memeticアルゴリズム、人工免疫システム、アントコロニー最適化手法、Particle Swarm Optimizationなどの最新の手法を幅広く網羅しており、応用編では、スケジューリング問題、配送計画問題、構造最適設計への応用などを幅広く取り上げている。ハンドブック的な利用も可能であり、システム工学・情報工学に携わる学生・技術者・研究者必携の書である。

• 動的計画法の概要と適用事例とpythonによる実装例

動的計画法(Dynamic Programming)は、最適化問題を解くための数学的手法の一つであり、特に重複する部分問題を持つような問題に適用される手法を指す。動的計画法は、一度計算した結果を保存して再利用することで、指数的な計算量を劇的に減らすことができるため、効率的な解法を提供する。ここでは、この動的計画法に対して、様々なアルゴリズムとpythonによる具体的な実装方法について述べている。

• 動的計画法のアルゴリズムとデータ構造

ある計算式に対して、一度計算した結果をメモに記録しておき、同じ計算を繰り返し行うという無駄を避けつつ、それを再利用することにより効率化を測ることは、プログラミングやアルゴリズムの設計を行う絵腕有効なアプローチとなる。その手法の一つが動的計画法となる。

• 検索エンジンのマッチングアルゴリズム 検索エンジンでの文字列のマッチング

検索エンジンの文字列マッチングアルゴリズム(n-gram、メタワードインデクシング等)の紹介

• 検索エンジンのページランクアルゴリズム

検索エンジンのアルゴリズムのうち、googleを飛躍的に発展させた検索順位を決定するページランクアルゴリズムについて。

• Exponential Smoothingの概要とアルゴリズム及び実装例について

指数平滑法（Exponential Smoothing）は、時系列データの予測やデータの平滑化に使用される統計的手法の一つであり、特に、過去の観測値を基に未来の値を予測するために使用されるものとなる。指数平滑法は、シンプルながら効果的な方法であり、時間に対する重み付けを行い、過去のデータに対する影響を調整することができる手法となる。

• LLE (Locally Linear Embedding)について

LLE（Locally Linear Embedding）は、高次元データを低次元に埋め込む非線形次元削減アルゴリズムの一つであり、データが局所的に線形であると仮定し、データの局所的な構造を保持しながら次元を削減するものとなる。これは、主にクラスタリング、データの可視化、特徴抽出などのタスクに使用されている。

• 多次元尺度構成法（MDS, Multidimensional Scaling）について

多次元尺度構成法（MDS）は、多変量データを可視化するための統計的手法の一つであり、データ間の距離または類似性を保持しながら、データポイントを低次元空間（通常は2次元または3次元）に配置する方法を提供するものとなる。この手法は、高次元データを理解しやすい低次元プロットに変換するために使用され、データの特徴やクラスタリングを可視化するのに役立つ。

• t-SNE (t-distributed Stochastic Neighbor Embedding)について

t-SNEは、高次元データを低次元に埋め込む非線形次元削減アルゴリズムの一つであり、t-SNEは主にデータの可視化やクラスタリングなどのタスクに使用され、特に高次元データの非線形構造を保持する能力が強みな手法となる。t-SNEの主なアイデアは、高次元データの類似性を低次元空間に反映させることとなる。

• UMAP (Uniform Manifold Approximation and Projection)について

UMAPは、高次元データの非線形次元削減手法であり、データの構造を保持しながら低次元に埋め込むことを目的としたもので、”t-SNE(t-distributed Stochastic Neighbor Embedding)について“で述べているt-SNEと同様に可視化やクラスタリングに使用されるが、いくつかの点で異なるアプローチを採用している手法となる。

• パターン認織アルゴリズム 最近傍、決定木、ニューラルネット

基本的なパターン認織のアルゴリズムとして、最近傍法、決定木、ニューラルネットワークについて紹介する

• データベースのアルゴリズム(1) データベースの一貫性

データベースが他の情報保存方法と違う最大のポイントとして、データベース内の情報が予め定義された構造を持っている事となる。またもう一つの特徴として「一貫性」がある。

構造とは文字通り、データが整理された例えばテーブルのような形であらわされていることであり、一貫性とはデータベースに含まれている情報がデータの出し入れが行われても矛盾を起こさないことを表す。ここではこれらの特徴を実現する為に3つのアルゴリズムが述べられている。一つは「ログ先行書き込み」、もう一つが「2段階コミット」、そして最後が「リレーショナルデータベース」となる。

• データベースのアルゴリズム(2) リレーショナルデータベース

データベースは構造を持ったデータであり、最もシンプルなものは表の構造を持ったものになる。表の構造はは一つではなく複数に分割した方が効率的な場合がある。

このようにシンプルな構造にすることで、コンピューターのメモリを節約できると共に、データを変更する際にも繰り返された情報(授業情報)すべてを一つ一つ変更せずにまとめて変更できるという利点が生じる。

ここで分割された二つの表で共通して利用するデータ(上記の例だと授業番号)はキーと呼ばれる。データベースはこのキーを使ってデータを塊として捉えて高速にアクセスすることができ、この塊のことをコンピューター科学では「B木」と呼ぶ。

• データ圧縮アルゴリズム(1) ロスなし圧縮

圧縮技術には大きく分けて「ロスなし圧縮」と「ロスあり圧縮」の二つの技術がある。「ロスなし圧縮」は圧縮されても元のデータを完全に再現できるため本来であればこれ一つあればよいが、圧縮率がそれほどよくできないと言う課題を持つ為、「ロスあり圧縮」が利用されている。

「ロスなし圧縮」の基本原理は、データが反復している部分を見つけてそれを省略することにある。

• データ圧縮アルゴリズム(2) ロスあり圧縮

画像情報(JPEG)等に用いられるデータ圧縮のアルゴリズムについての紹介。

• 決定不能性の証明 計算できない問題について

ここではコンピューター(のアルゴリズム)でできないものは何かについて述べられている。ここで言われているアルゴリズムは自動車を完璧に運転したり、学生の成績を見事に評価したりする難しい問題のことではなく、本質的に「計算できない問題」についてとなる。

説明の題材として、ソフトウェアのバグ、クラッシュを検出するチェックツールについて上げている。結論から言うと、どのプログラムツールでもすべてのクラッシュを起こしそうな場所を見つける事が不可能な事は証明できるというものになる。

• 誤り訂正符号アルゴリズム

コンピューターの行う3つの仕事について定義されている。一つが計算を実行すること、二つ目がデータを保存する事で、三つ目がデータを伝送することだ。ソフトウェア的な観点からはデータを保存する機能はデータベース技術に代表され、データを伝送する機能はインターネットを始めとするウェブ技術に代表される。

データの伝送と保存を考えた時に、最も重要なことはそのデータを「完全に正確に」保存/あるいは伝送することにある。それに対してメモリや通信等のハードウェアには必ずノイズや誤動作が付きまとい100%の動作は保証してくれない。その為ソフトウェア的な工夫で「完全に正確に」を担保してやる必要があり、それらを実現する技術の一つが「誤り訂正技術」になる。

「完全に正確に」なデータの保存/伝送手法は、データの冗長度をあげることになる。たとえば「5123」という数字を「five one two three」という形で伝送すると、前者の場合は1文字エラーが生じても元のデータが完全失われてしまうが、後者の場合は例えば「five」の一文字が代わり「fave」となったとしても、前後の情報で「five」に修正できる可能性が高い。

• デジタル署名アルゴリズム

デジタル署名の「署名」は読めるけれど誰にもコピーできないものと定義される。これは誰でもコピーできる「デジタル」とは全く逆の概念となる。このパラドックスに解を提供するものがデジタル署名となる。

デジタル署名はそもそも何のために使われるかと言うと、通常の手紙のように自分が誰かに送るものに署名するのではなく、誰れかから署名されたものが送られてきた時に、コンピューターがチェックするために存在している。

ここで署名に必要な要件として、(1)署名の原本を保管している所は信頼のおける場所であること、(2)署名は第三者には簡単に偽造されないことの2つが挙げられる。

• 公開鍵暗号法アルゴリズム

一番シンプルな暗号の手法は「共有する秘密を持つ」ことから始まる。あるデータを特定の人にだけ送る時、その人とだけ共有している秘密の数字があるとする。(例:322)その時データとして8を送る時、それを加えたものを相手に送り(322+8=400)相手が、送られた数字から共有する番号を引き算すれば良い。

これを更に実用的にするには、共有する数字が簡単に分からないもの、たとえばもっと長い数字を送れば良い。(例3桁の数字を秘密の数字にすると999通りあるが、この程度だとコンピューターは簡単にすべての組み合わせを試すことができる)一般的な暗号アルゴリズムでは送られたデータの30%を計算した桁数が鍵となるので、128ビットの暗号だと38桁で1兆の一兆倍の1兆倍より大きな数字となる。これを現在のコンピューターで計算すると10億年単位の時間がかかるので、安全な方式だと判断できる。

• データソートについて バブルソート、クイックソート、マージソート、選択ソート、ヒープソート

データのソート(並べ替え)はアルゴリズムの基本となる。ソートのアルゴリズムとしては以下に示すようなものがある。

隣接する値同士を比較し入れ替える作業を繰り返す「バブルソート」、ピポットと呼ばれる基準値を定めて、データ群を基準値以上と基準値未満の2つのグループに分ける作業を繰り返すことで要素の入れ替えを行う「クイックソート」、データを最小の単位(単一要素)まで分解し、最小の単位からソート、マージ(併合)を繰り返して要素を並び替える「マージソート」。

一番目以降の要素から最小値を見つけて一番目の要素と交換し、二番目以降の要素から最小値を見つけて二番目の要素と交換する作業を続けて要素を並び替える「選択ソート」、前から2個要素を取り出し、順番が逆なら並び替え、次に3個目を取り出し、　2個までの中の適切な場所に挿入する作業を続けて要素を並び替える「挿入ソート」。

「ヒープソート」は、元のデータを以下に示すような順序木に一旦変換し、変換した順序木の「子と親」を比較していき、親が子より小さければ親と子を交換するという手続きを全てのノードの組み合わせについて行うものとなる。

• その数式プログラミングできますか?

この本のテーマはプログラミングだが、ほとんどのプログラミング本と異なり、アルゴリズムやコードに加えて、数学証明や、古代から現代までの数学上の発見に関する歴史的経緯が含まれている。

もう少し具体的に言うと、テーマはジェネリックプログラミング(generic programming)となる。ジェネリックプログラミングは1980年台に登場したプログラミングの手法であり、1990年代にC++のTL(Standard Template Library)が開発された。ここで、ジェネリックプログラミングとは、アルゴリズムとデータ構造を設計することに焦点を合わせ、効率を低下させることなく、それらを最も一般的な環境で動作させるためのプログラミング手法となる。

• Pythonで学ぶアルゴリズムの教科書

本書では以下の目次に示すようにPythonプログラミングの基本とベーシックなアルゴリズムの構築について述べられている。

内容としては、まずpyhtpnの基本的な知識とベクトル、配列、スタック、キュー、リスト、木、グラフ等の基本的なデータ構造のpythonでの扱い、線形探索、2分木、木探索等の探索アルゴリズム、選択ソート、バブルソート、挿入ソート、クイックソート、マージソート、ヒープソート等のソートアルゴリズム、ハッシュとユークリッドの互助法、文字列探索、最短経路問題等の具体的なアルゴリズム、最後にアルゴリズムの見える化等によるアルゴリズムの理解について述べている。

• Clojureを用いたシンプルな推薦アルゴリズムの実装

推薦システムは、あるアイテムに対するユーザーの好みや嗜好を予測しようとする情報システムとなる。推薦システムは、ユーザーに有用な情報を提供することを目的とした情報フィルタリングシステムでとなる。推薦システムは、ユーザーの行動履歴を利用したり、他のユーザーが気に入ったものを推薦したりする。この2つのアプローチが、推薦システムで用いられる2種類のアルゴリズム（コンテンツベースフィルタリングと協調フィルタリング）の基礎となっている。

機械学習における数学

数学とはwikiによると「数学とは、一般に形式科学に分類され、自然科学とははっきり区別される。方法論の如何によらず最終的には、数学としての成果というものは自然科学のように実験や観察によるものではない。」とある。

形式科学とは、記号システムで記述される抽象的構造であり、これは数学はものの構造(モデル)を何らかの記号を用いて抽象化し、その抽象化したモデルを使って推論を行うことで結果を導き出すものとなる。

数学を用いることで、機械学習等に用いられアルゴリズムを厳格に誤りなく記述することができる。また人工知能で用いられる推論機能も数学の形式科学的な厳格さに依っている。この厳格さは自然言語のような非常にあいまいな記号システムとは対極なものとなる。

本ブログでは、 以下のページにて、以下示すような数学的観点からの人工知能、機械学習等のコンピューターでの利用を念頭においてそれらに必要だと思われる項目についてまとめていく。

最適化の数学

• はじめての最適化　読書メモ

本書は具体的に理解できるよう、図形的説明を多用しながら分かりやすく詳説する。問題と解法の直感的理解を促し、具体的な問題を解けるようになることを目標とする。本文を簡潔に述べるように努めて、追加説明や他に言及したいことなどを側注とした。各章末には練習問題を配し巻末に全ての問題の解答を付けている。はじめて最適化問題を学ぶ初学者には、数学的復習から入っていくので、大変理解しやすく学べる好書である。

確率的最適化

インターネット、センサ技術およびコンピューターの発達により、さまざまな種類のデータが大量に手に入る現在、大量のデータから意味ある情報を取り出すための機械学習技術が注目され、大きく発展している。多種多様なデータが取得可能になったことで様々な問題が解けるようになった一方で、データサイズの肥大化による計算量増大の問題が生じている。

機械学習技術をフル活用するには大量データの学習をなるべく効率よく行う必要がある。確率的最適化は大量データの大規模学習問題を解くための強力な手法であり、現在の機械学習における基本的構成要素となっている。ここでは機械学習における確率的最適化の諸手法について述べる。

本ブログでは 以下のページにて、この確率的最適化について述べる。

統計的学習理論

本コンテンツの目的は、機械学習アルゴリズムの統計的性質に関する理論を理解することにある。そのために主に(a)一様大数の法則、(b)普遍カーネル、(c)判別適合損失の3つについて述べている。国内外の著作では(a)について多くの記述がある。Foundation of Machine Learning(Mohri, MIT Press)では、ラデマッハ複雑度を主軸にして(a)についての見通しの良い理論を展開している。一方、(b)(c)を体系的に解説した著作はほとんどない。

本ブログでは 以下のページにて、この統計的学習理論の詳細について述べる。

機械学習のための連続最適化

高度に情報化した現代社会において、データから有用な知見を得ることは、科学的に重要な発見を行い、産業・経済社会を促進する上で、極めて重要な課題となっている。今日、データは大規模化、高次元化、多様化の一途を辿っている。このようなデータを適切に扱うための基盤技術として、近年、機械学習と呼ばれる分野が勃興し、急速に発展している。統計学やデータサイエンスなど、データを扱う従来の学問分野では、主に統計的推論を適切に行うためのモデリング技術が発展してきた。

一方機械学習では、効率的な計算手法の開発により重点が置かれている点に特徴があるといえる。ビッグデータ時代を背景にして、機械学習の分野で開発された様々な手法が社会に大きなインパクトをあたえつつある。

本ブログでは 以下のページにて、この機械学習アルゴリズムを構成する上で欠かすことのできない計算手法である連続最適化の方法について述べる。

グラフアルゴリズム

グラフはものや状態といった対象同士の結びつきを表すための表現方法となる。多くの問題をグラフの問題に帰着することができるため、グラフに関するアルゴリズムが多く提案されている。

本ブログでは 以下のページにてこのグラフデータの基本的なアルゴリズムである探索アルゴリズム、最短経路アルゴリズム、最小全域木アルゴリズム、データフローアルゴリズム、強連結成分分解をベースとしたDAG、SAT、LCA、決定木等のさまざまなアルゴリズムとグラフ構造をベースとした知識データ処理、ベイズ処理等の応用について述べている。

マルコフ連鎖モンテカルロ法

MCMCは「マルコフ連鎖モンテカルロ法」(Markov Chain Monte Carlo Method)の略で、多変量の確率分布からサンプルを抽出する(乱数を発生する)ためのアルゴリズムの一つとなる。

MCMCは単なる計算法であり、タスクを解くためには、MCMCで解ける様に問題を整理する作業(統計モデリング)が必要となる。算数の文章題で、加減乗算の計算そのものより「何を計算するか」が肝心なのと同様なものとなる。

最小二乗法で曲線をあてはめたり、最尤法で確率分布のパラメータを推定するのに必要なものは「行列の分解」や「最適化」となる。それらは目的が「一つの決まった曲線や数字」(点推定値)を直接求めるものである為で、それに対してベイズ統計では「答」はまず「事後分布」という「分布」の形で与えられる。そこで、分布からのサンプルを生成するMCMCとの相性が抜群となる。点推定値や誤差、予測区間など、最終的に必要な情報はMCMCで生成した多数のサンプルから求める。

MCMCと最適化の違いは、MCMCがずっと動き続けてサンプリングを生成するのに対して、最適化はどこか(うまくいくときには本当の最適解、うまくいかないときは曲初回)で止まる。実際には、MCMCも最適化に近い動きをすることもあるが、その場合でも最適解のまわりでいつまでも「ごにょごにょ」と動いて、ベイズの意味での誤差を表現する。MCMCの「収束」とは、分布の収束なので、ある一点二位ってそこで止まると言う意味ではない。

MCMCは確率分布を扱う汎用の手法で、統計物理や頻度論的な統計学でも使われる。逆にベイズ統計では、ラプラス近似、カルマンフィルタ、逐次モンテカルロ法、変分ベイズ法などいろいろな計算法が使われていて、MCMCはその中の一つとなる。

本ブログでは 以下のページにて、このマルコフ連鎖モンテカルロ法での基本的な理論と具体的なアルゴリズムと実装コード等について述べている。