> [!abstract] 概要(ACM Comput. Surv. abstract の日本語訳) > アルゴリズムに関する研究は近年、劇的に増加している。計算機科学の様々な下位分野が、異なる目的と基準にしたがってアルゴリズムを研究している。この分野の多元性は、隣接する下位分野へまだ移転されていない様々な方法論的進展をもたらしてきた。より良い知識交換のための中心的な障壁は、これらの下位分野の視点を統合する共通の方法論的枠組みが欠けていることにある。本論文の目的は、アルゴリズムエンジニアリングのためのそのような研究枠組みを構築することである。我々の枠組みは、科学哲学で議論される3つの領域——存在論(ontology)・認識論(epistemology)・方法論(methodology)——の上に築かれる。この枠組みは、計算機科学の様々な領域におけるアルゴリズムに関するあらゆる貢献に関連する、様々な妥当性の懸念を特定し議論するのに役立つ。 ## 論文情報 - タイトル: Methodology of Algorithm Engineering - 著者: [[Jan Mendling]]([[Humboldt University of Berlin|Humboldt-Universität zu Berlin]]・[[Vienna University of Economics and Business]]・[[Weizenbaum Institute]]、責任著者)・[[Henrik Leopold]]([[Kühne Logistics University]]・[[Hasso Plattner Institute]], [[University of Potsdam]])・[[Henning Meyerhenke]]([[Karlsruhe Institute of Technology]])・[[Benoît Depaire]]([[Hasselt University]]) - 媒体: *ACM Computing Surveys*, Vol. 58, No. 4, Article 94, 38 pages - 発表年: 2025年10月(受理: 2025-09-15、改訂: 2025-08-06、初回投稿: 2023-10-30) - DOI: [10.1145/3769071](https://doi.org/10.1145/3769071) ## 概要 計算機科学の様々な下位分野(VLDB・NeurIPS・ESA・VIS等)がそれぞれ異なる評価基準・作法でアルゴリズムを研究しており、方法論的な知見が分野横断的に共有されていない現状に対して、科学哲学の存在論・認識論・方法論という3領域を土台に、アルゴリズムエンジニアリング全体を貫く統一的な研究枠組みを構築した論文である。既存の議論を統合した枠組みそのものが本論文の主要な貢献であり、個々の新規実験結果は提示しない。 ## 問題設定 計算機科学における「アルゴリズム」を扱う研究は、VLDB(性能評価と形式的正しさを重視)・VIS(ユーザースタディを重視)のように分野ごとに評価要件が大きく異なる。この多元性(pluralism)が方法論的進展の分野間移転を妨げており、この論文は「異なる要件を統合できる共通の科学的枠組みは存在するか」という問いに答えることを目指す(Source: 本文 §1)。 ## 提案手法 ### 存在論(ontology)——4つの実体と3つの関係 Staples (2014) のエンジニアリング存在論モデルに基づき、アルゴリズムエンジニアリングの実践に関わる4つの存在論的実体を定義する(Source: 本文 §2)。 - **Real-World Problem(現実世界の問題)**: 具体的で、動的な状況・複雑なシステムに紐づき、しばしば境界が曖昧な「厄介な問題(mess)」(Ackoff 1979)である。 - **Algorithmic Task(アルゴリズムタスク)**: 現実世界の問題を**抽象化(Abstracts)**した、入力・処理・目標に関する前提条件を明示する概念化。アルゴリズムタスク・アルゴリズム問題・計算問題・単に「問題」とも呼ばれる(Aho et al. 1974)。 - **Algorithm Design(アルゴリズム設計)**: タスクを**満足(Satisfies)**する設計。設計原理(divide-and-conquer等)と設計決定からなり、性能保証を伴いうる。 - **Algorithm Implementation(アルゴリズム実装)**: 設計を**具体化(Instantiates)**した実装。実装決定を伴い、実データ上での実行が出力と経験的性能を生成する。 **Figure 1: 存在論的視点のフレームワーク** ![[_attachments/Methodology-of-Algorithm-Engineering/fig01-ontological-framework.png]] (Figure 1. Real-World Problem→Algorithmic Task→Algorithm Design→Algorithm Implementationの4段の連鎖を、Abstracts・Satisfies・Instantiatesの3つの関係でつなぐ。Source: 本文 Fig. 1, p.94:3。) タスクが完全に形式仕様化できる場合(ソート等)はアルゴリズムが自動的に出力を決定できるが、意味論を完全specifyできない自然言語処理のような「fuzzy task」ではユーザーとの対話的技法が必要になる(Source: 本文 §2.2)。設計の説明方法には擬似コード・フローチャート(図式表現は認知的有効性で擬似コードより理解容易とされる、Scanlan 1989)・数式による形式仕様の3水準があり、それぞれ実装への近さが異なる(Source: 本文 §2.3)。 ### 認識論(epistemology)——Popperの三世界論の適用 Popper (1979) の三世界論(World 1: 物理的実体・World 2: 主観的心的状態・World 3: 客観的知識)を援用し、存在論的フレームワークを拡張する(Source: 本文 §3、Naur 1985・Staples 2014の先行適用を踏襲)。 **Figure 2: 認識論的視点のフレームワーク** ![[_attachments/Methodology-of-Algorithm-Engineering/fig02-epistemological-framework.png]] (Figure 2. Real-World ProblemとAlgorithm ImplementationはWorld 1に、abstract/design/implementateの3つの行為はWorld 2に、Algorithmic Task・Algorithm Design・Body of KnowledgeはWorld 3に位置づけられる。Body of Knowledgeは Knowledge of Tasks・Knowledge about Tasks・Knowledge of Design・Knowledge about Design の4つに分節化される。Source: 本文 Fig. 2, p.94:7。) タスク・設計それぞれについて「knowledge of」(それが何であるか)と「knowledge about」(その性質について何が分かっているか)を区別する。knowledge about designはさらに4類型に分けられる(Source: 本文 §3.5、Santner et al. 2003の実験計画論に基づく)。 - **性能知識(performance knowledge)**: 設計がタスク要件をどの程度満たすか。満足の問い(does it satisfy?)と程度の問い(to which extent?)に分かれる。 - **感度知識(sensitivity knowledge)**: 内部設計決定(パラメータ設定)の変化に対する性能の頑健性。 - **不確実性知識(uncertainty knowledge)**: タスク前提の変化(問題インスタンス間の分散)に対する性能の変動。 - **説明的知識(explanatory knowledge)**: タスク前提と設計決定がどのように相互作用して性能に影響するかのメカニズム。設定の比較評価(機能の有無等)によって確立される。 ### 方法論(methodology)——知識拡張の4カテゴリと9つの妥当性概念 知識拡張を4カテゴリ(タスクの新規/改善知識・設計の新規/改善知識・タスク/設計についての形式的知識・タスク/設計についての経験的知識)に分類し、それぞれに対応する研究手法(帰納的手法・設計手法・形式的手法・経験的手法)を提示する(Source: 本文 §4)。 **Figure 3: 方法論的視点のフレームワーク** ![[_attachments/Methodology-of-Algorithm-Engineering/fig03-methodological-framework.png]] (Figure 3. Body of Knowledge内部でKnowledge of Tasks/Designs・Formal/Empirical Knowledge about Tasks/Designsが相互に関係し、それぞれの遷移に対応する妥当性概念(Ecological/Design/Implementation/External/Logical/Justification/Internal/Construct/Conclusion Validity)が矢印に付記される。Source: 本文 Fig. 3, p.94:14。) 設計手法として、演繹(既存タスク・設計・設計原理からの特殊化。例: Ganapathi and Chowdhury 2022のbubble sortへのdivide-and-conquer適用)・帰納(数学的帰納法の類推、Manber 1988。個別インスタンスからの一般化)・アブダクション(異常からの診断的発見。例: process miningのα-algorithmの拡張系譜)・類推/メタファー(自然科学現象からの借用。simulated annealing・particle swarm optimization等)の4種を区別する(Source: 本文 §4.2)。 経験的知識生成のプロセスは、(1) 仮説の開発 → (2) 研究デザインの導出(探索的・相関的・実験的の3種、Wohlin et al. 2012) → (3) 計測用実装の構築 → (4) 評価データの選定(公開/非公開 × 実世界/人工生成の2軸) → (5) 計測と計装 → (6) 結論の導出、という6段階として整理される(Source: 本文 §4.4)。 **9つの妥当性概念(Table 1、要約転記)** | 妥当性概念 | 説明 | 対応する存在論的実体 | |---|---|---| | 生態学的妥当性(Ecological validity) | アルゴリズムタスクや設定が現実世界の状況・問題文脈をどの程度反映しているか | Algorithmic task | | 設計妥当性(Design validity) | アルゴリズム設計の内部構造と論理が首尾一貫し、正当化され、説明可能である度合い | Algorithm design | | 実装妥当性(Implementation validity) | アルゴリズム実装が意図した設計を忠実に具体化し、期待通りに振る舞う度合い | Algorithm implementation | | 外的妥当性(External validity) | 結果が関心対象のデータセット群にわたって一般化する度合い | Empirical results | | 正当化妥当性(Justification validity) | 仮説や定理が演繹的論証によって説得的に支持されている度合い | Theorems, hypotheses | | 論理的妥当性(Logical validity) | 証明で使われる三段論法が真理を保存する度合い | Proofs | | 内的妥当性(Internal validity) | 観察された効果が交絡要因ではなく処理に帰属できる度合い | Research design | | 構成概念妥当性(Construct validity) | ある構成概念の測度が意図した性質を正確に測っている度合い | Measurement | | 結論妥当性(Conclusion validity) | 結果が仮説化された関連を実際に明らかにしていると合理的にみなせる度合い | Empirical results | (Table 1. Validity Concerns in Algorithm Engineering. Source: 本文 Table 1, p.94:15。) ## 新規性 既存の議論(Staples 2014の工学存在論、Popperの三世界論、Cook et al. 2002・Wohlin et al. 2012・Larsen et al. 2020等の個別の妥当性概念)を初めて**アルゴリズムエンジニアリング専用の統一枠組み**に統合した点が新規性である。個々の要素(存在論モデル・三世界論・妥当性概念)はいずれも既存文献からの借用だが、これらを1本の存在論的連鎖(タスク→設計→実装)に体系的に対応づけ、VLDB・NeurIPS・VIS等の分野横断で共通言語として使える形に仕上げた点、および9つの妥当性概念がどの実体・どの知識類型に対応するかを明示的に整理した点(§5.3の対応表)にオリジナリティがある(Source: 本文 §1, §5)。 ## 実験設定 本論文は理論的枠組み構築を目的とするサーベイ/概念論文であり、新規の実験は行わない。枠組みの各要素を、既存文献からの30件以上のExample(例2.1〜4.29)によって例証する構成をとる。例示に使われる主な既存研究にはVaswani et al. 2017(Attention Is All You Need)・Kriegel et al. 2017(k-meansやDBScan実装の性能差研究)・Russakovsky et al. 2015(ImageNet)・Bodlaender et al. 2015(treewidthパラメータ化計算量)などが含まれる(Source: 本文 §2-4)。 ## 実験結果 該当なし(理論枠組み論文のため、定量評価は行われない)。 ## 考察 ### §5の実践的示唆(存在論的明晰さ・認識論的精密さ・方法論的妥当性) 論文の§5は、研究者が自身の論文を執筆する際に自問すべき具体的な問いを3つの表(Table 2〜4)に整理する。これらは本論文の理論的貢献(§2〜4)を実践的なチェックリストへ変換したものである(Source: 本文 §5)。 **Table 2: 存在論的明晰さについての問い** | 存在論的明晰さ(タスク) | | |---|---| | タスクは何か、現実世界の問題とどう関係するか | | | 入力データ・アルゴリズム処理・望ましい出力に関してどんな前提が置かれているか | | | どの性能要件が関連するか | | | タスクはどの程度完全に形式仕様化できるか。タスクが曖昧な場合ユーザーはどう関与するか | | | **存在論的明晰さ(設計)** | | | アルゴリズムはどう動作するか、どの設計原理に基づいて設計されているか | | | どの前提に基づいてどの設計決定がなされたか | | | どんな考慮に基づいてパラメータ値が設定されたか | | | 該当する場合、どんな実装決定がなされたか | | | 実装はどんな結果を与えるか | | (Table 2. Questions on Ontological Clarity. Source: 本文 Table 2, p.94:27。) **Table 3: 認識論的精密さについての問い** | 認識論的精密さ(タスク) | | |---|---| | なぜタスクは形式的・準形式的・非形式的等で記述されるのか | | | このタスクについてどんな先行研究が発表されているか | | | このタスクの何が知識として発表されているか | | | このタスクについてどんな新規・改善された知識が提示されるか | | | このタスクについてどんな形式的知識(定理を含む)が発表されているか | | | このタスクについてどんな新規・改善された定理が提示されるか | | | このタスクについてどんな経験的知識(仮説を含む)が発表されているか | | | このタスクについてどんな新規・改善された仮説が提示されるか | | | **認識論的精密さ(設計)** | | | 特定の設計について何が知識として発表されているか | | | その設計についてどんな新規・改善された知識が提示されるか | | | なぜ設計は擬似コード・フローチャート・形式仕様等で記述されるのか | | | その設計についてどんな形式的知識(定理を含む)が発表されているか | | | その設計についてどんな新規・改善された定理が提示されるか | | | その設計についてどんな経験的知識(仮説を含む)が発表されているか | | | その設計についてどんな新規・改善された仮説が提示されるか | | | 定理・仮説は性能・感度・不確実性・説明的知識のいずれと、どの因果要因に関係するか | | (Table 3. Questions on Epistemological Precision. Source: 本文 Table 3, p.94:28。) **Table 4: 方法論的妥当性についての問い** | 方法論的妥当性(タスク) | | |---|---| | タスクの知識を生成するのにどんな手法が使われたか | | | 生態学的妥当性に関連する脅威があれば、どう緩和されたか | | | 研究知見はどの程度現実世界の問題に一般化できるか | | | **方法論的妥当性(設計)** | | | 設計の知識を生成するのにどんな手法が使われたか | | | なぜ演繹・帰納・アブダクション・類推等の手法が使われたか | | | 問題空間と設計空間の共進化はどう展開したか | | | 設計妥当性に関連する脅威があれば、どう緩和されたか | | | アルゴリズムの内部構造はどの程度一貫し透明で説明可能か | | | 効率性はどの漸近的関数クラスに関係するか | | | 正しさ・完全性・停止性についてどんな形式的保証ができるか | | | 論理的妥当性に関連する懸念があれば、どう対処されたか | | | 効率性と有効性のトレードオフは何か | | | 定理・補題を証明するのにどんな証明戦略が使われるか | | | なぜ仮説は演繹的あるいは帰納的に、あるいは他の方法で開発されたか | | | 正当化妥当性に関連する脅威があれば、どう緩和されたか | | | 仮説には理論的正当化があるか、それとも他の根拠があるか | | | なぜ探索的・相関的・実験的な研究デザインが使われたか | | | 内的妥当性に関連する脅威があれば、どう緩和されたか | | | 潜在的な交絡要因は何で、どう制御されたか | | | どの実装方法が選ばれ、なぜか | | | 実装はどうテストされたか | | | 実装妥当性に関連する脅威があれば、どう緩和されたか | | | どの評価データが選ばれ、なぜか | | | なぜベンチマークデータか私的データか、実世界データか人工データが使われたか | | | 外的妥当性に関連する脅威があれば、どう緩和されたか | | | 特徴量の範囲は理解され現実的か | | | 関連要因はどう解きほぐされ分離されるか | | | 過学習はどう回避されるか | | | どのように適切な測度が選定・構築されるか | | | 構成概念妥当性に関連する脅威があれば、どう緩和されたか | | | 測度は意図した構成概念の妥当かつ信頼できる操作化であるか | | | 有効性は客観的なゴールドスタンダードで測られるか、人間のアノテーションから得たゴールドスタンダードか、ゴールドスタンダード不在の人間の判断か | | | 予期しない結果はどう説明できるか | | | 設計の見直しか知識の見直しかの論拠は何か | | | 結論妥当性に関連する脅威があれば、どう緩和されたか | | | 統計的検定の前提は満たされているか | | | 外れ値・異常なデータ点から何を学べるか | | | 結果は確立された標準に照らして再現可能か | | | データと研究ソフトウェアはFAIR原則に基づき共有されているか | | (Table 4. Questions on Methodological Validity. Source: 本文 Table 4, p.94:29。) - **9つの妥当性概念とその適用の4原則**(Source: 本文 §5.3): (1) どの妥当性概念が関連するかは貢献の存在論的焦点(タスク/設計/実装)に依存する。(2) 貢献が言及する知識類型(of/about、形式的/経験的)によって関連する妥当性概念が変わる。(3) 妥当性への対応戦略には強度の階層があり、最弱は「限界の記述による透明性確保」、より強いのは「追加分析」、最強は「研究デザインの段階で妥当性懸念を予期し操作チェック等で対処する」。(4) すべての妥当性概念を完璧に満たす貢献は存在せず、特に内的妥当性と外的妥当性はトレードオフの関係にあることが多い。 - **倫理的考察**(Source: 本文 §5.4): フレームワークの3視点それぞれに倫理的論点が現れる。存在論的視点では現実世界の問題・タスク自体の倫理性(deepfake生成タスクの是非等)、認識論的視点では設計の倫理的含意についての知識(道徳的ジレンマの文化差)、方法論的視点では評価データのバイアス(Kshetri 2021のクラウドソーシングラベリングの公正性問題を含む)が論点となる。 - **知識のof/about区別の重要性**(Source: 本文 §3.5): 新しいアルゴリズムを提案する論文は「knowledge of design」に焦点を当てるが、多くの場合そのアルゴリズムがタスク要件をどの程度満たすかを示す評価パートを含んでおり、これは実質的に「knowledge about design」の提供でもある。逆にサーベイ論文やベンチマーク研究は新規アルゴリズムを提案せず「knowledge about design」のみを提供する。この区別が曖昧なまま論文が書かれると、読者は貢献の性質を正確に評価できない。 ## 強み / 弱点・課題 **強み** - 科学哲学の確立した概念(存在論・認識論・方法論、Popperの三世界論)を借用することで、分野固有のjargonに依存しない普遍的な語彙を提供している。 - Table 2〜4(§5)に、著者が論文執筆時に自問すべき具体的な問いのチェックリストとして整理されており、実務的に使いやすい。 - 30件以上の多様な既存研究(グラフ理論からTransformer、process miningまで)を例に用いており、フレームワークが特定の下位分野に偏っていないことを示している。 **弱点・課題**(著者自身は明示的な限界節を設けていないが、本文の記述から読み取れる論点) - 枠組み自体の実証的検証(例えば、実際にこの枠組みを著者陣以外の研究者に適用してもらい、論文の質やレビューにどう影響したかを測る実験)は行われていない。 - 内的妥当性と外的妥当性のトレードオフについて言及するが(§5.3)、アルゴリズムエンジニアリング特有の解決策(他分野の複数研究デザイン統合戦略、Roe and Just 2009を援用するに留まる)は十分に展開されていない。 - 創造性・セレンディピティが設計手法の重要な源泉であることを認めつつ(§4.2)、それらは体系的手法の「白地」として位置づけられるにとどまり、フレームワーク自体はこの領域を扱わない。