KI 2014: Advances in Artificial Intelligence論文集より

前回はKI2013について述べた。今回は2014年9月22日〜26日にドイツのシュトゥットガルトで開催された。第37回ドイツ人工知能会議（KI 2014）について述べる。

この会議は、人工知能のあらゆる分野の学術研究者や企業研究者が集まり、知的システム技術の理論と応用に関する最新情報と研究成果を交換するドイツで最も重要なフォーラムとなる。

KI 2014では、Wolfram Burgard (ドイツ、フライブルク大学)による、モバイルロボットナビゲーションのためのプロバビリステクニックの概要の説明と、Hans van Ditmarsch氏（LORIA Nancy、フランス）による、動的認識論理学と人工知能についての講演、oby Walsh (NICTA and UNSW Sydney, Australia) による、Allocation in Practice についての基調講演が行われた

また第8回ワークショップ「Emotion and Computing – Current Research and Future Impact」、第28回ワークショップ「Planen/Scheduling und Kon- figurieren/Entwerfen (PuK) 」、高階認知と計算に関するワークショップが行われ、さら、確率的プログラミング（Angelika Kimmig, KU Leuven） と人間計算（Fran ̧ Bry, LMU Munich）のチュートリアルが行われた。

その他の主な項目としては、Cognitive Modeling、Computer Vision、Constraint Satisfaction, Search, and Optimization、Knowledge Representation and Reasoning、Machine Learning and Data Mining、Planning and Schedulingに関する報告が行われている。

以下に詳細を示す。

数列の誘導は、知能検査に含まれる典型的な課題である。これは、規則的なパターンを検出し、それを一般化する能力を測定するもので、一般的な知能に重要であると考えられている。数問題の解決には、いくつかの計算機によるアプローチがある。特殊な目的のアルゴリズムの他に、E-generalizationや人工ニューラルネットワーク（ANN）に対して、汎用の学習アルゴリズムの数列予測への適用性が示された。本発表では、解析的帰納法プログラミングシステムIgor2の数列問題への適用可能性を示す。Igor2の実証的な比較により、ANNとE-generalizationの評価に用いたテスト系列において、Igor2が同等の性能を持つことが示された。Holzmanら(1982, 1983)による数列問題の認知分析結果に基づき、Holzmanが認知的複雑さの原因として特定した異なる次元で複雑さを変化させた数列問題群をIgor2に提示し、詳細なケーススタディを実施した。その結果、Igor2の演奏時間はほとんどの次元で認知所見に対応することがわかった。

アルゴリズムデバッグは、知的チュータリングシステム(ITS)における効果的な診断手法の一つである。専門家の問題解決を論理プログラムとして記述したものが与えられると、そのプログラムの漸増的実行中の振る舞いを、観測された学習者の振る舞いと比較する。このとき、プログラムの位置から学習者のエラーが検出される。ITSのフィードバックエンジンは、学習者がエラーを修正できるように、問題のプログラム節を生成することができる。しかし、エラー情報がプログラムの位置に限定されているため、フィードバックエンジンは、現在の問題解決のステップで何が問題なのかという観点からしか改善策を提示することができない。学習者の行動全体の階層的な文脈にアクセスできないため、ステップを実行する理由と方法を説明したり、学習者のこれまでのパフォーマンスをまとめたり、学習者がこれから行う問題解決に備えるための足場となる支援を行うことは困難です。このような足場作りは学習に役立つのに、残念なことです。この問題を解決するために、我々はメタ解釈の手法を拡張し、プログラマ注釈のアプローチで補完する。エキスパートプログラムは、コードブロックを説明するコメントのように、プログラムの背後にある論理を説明する用語で強化される。メタインタプリタは、プログラムの実行経路におけるすべての注釈を収集し、プログラムの証明木に関連する部分の記録を保持するように拡張される。我々は、Prologベースのタスク定義、実行、および監視の観点から、洗練されたチュートリアルのインタラクションを定義するフレームワークを得ることができます。

人間レベルの人工知能（HAI）は、様々な意味で特別な研究対象であることは確かです。そもそも知能の本質が完全には明らかにされていないこと、知能の付与に必要かつ十分な、人間のパフォーマンスとの類似性以外の一般的に合意された基準がないこと（そしてこの基準でさえ、多くの解釈の可能性がある）、HAIを適切に調査する方法とHAIシステムの実装の最初のステップの後に進む方法に関する明確さが欠けていること、などです。このノートでは、Psychometric Artificial Intelligence [1]のアプローチがHAIの科学的アプローチの基礎となりうる（そしてなりえない）方法を評価します。

本論文は、教育現場における認知的類推エンジンの有用な応用例を紹介する一連の関連記事[1,2]の最終章をなすものである。本論文は、小学校1年生の子供たちに100までの自然数における乗算ベースの関係を教えるためのツールであるNumber Highriseの簡単な分析と詳細な形式モデル（ヒューリスティック駆動型理論投影計算アナロジーのフレームワークに基づく）を提供し、完全に実行された追加例によって以前の研究を補完する。

これまでのところ、ほとんどの認知モデリングアプローチは、「平均的なユーザー」の行動をモデリングし、予測することに集中している。ユーザーのパフォーマンスは、ワーキングメモリ、計画の深さ、検索戦略など、ユーザーによって異なる心理的要因に大きく依存する。そこで、我々は複数のAI手法を組み合わせて、ユーザープロファイルを自動的に特定する手法を提案する。提案手法は、各ユーザに心理的要因によって制御される認知エージェントのセットを割り当てる。最後に、PSPACE完全計画問題Rush-Hourに関する予備的なユーザデータを用いて、本手法をケーススタディで評価する。

本論文では、超教師なし学習と半教師あり学習を組み合わせることで、ユーザとのインタラクションをほとんど必要とせず、与えられた環境において適応的に物体を学習することができるシステムを提案する。本アプローチの主な考え方は、クラスタリング手法を用いることで、ユーザーとの対話から必要なラベルクエリの数を減らすことができると同時に、学習に有用なデータを選択する可能性を提供することである。標準的な手法とは対照的に、我々は実際の環境からのデータのみを用いて分類器を訓練し、クラスタリングがそのデータに関連性があるという十分な証拠を与える場合にのみ、分類器を訓練する。本手法を室内環境における物体検出の問題に適用し、学習前に関心領域検出器を用いる。実験では、我々の適応的SSL手法が、屋内オフィスデータセットにおいて、標準的な非適応的教師ありアプローチよりも優れた性能を発揮することを示す。

意味的なシーンセグメンテーションでは、画像の各ピクセルにカテゴリーラベルを割り当てる。この作業は、構造化光センサーが提供する奥行き情報を取り込むことで容易になる。しかし、深度情報はRGB画像チャンネルとは全く異なる性質を持っている。本論文では、深度情報を会話型ニューラルネットワークに与えるための新しい方法を提案する。この目的のために、我々は深度チャンネルにHOD（Histogram of Oriented Depth）記述子の簡略版を適用する。我々は、困難なNYU Depth V2データセットでネットワークを評価し、我々の方法を用いれば、高いフレームレートで競争力のある性能に到達できることを示す。

我々は、道路ネットワークにおけるエネルギー効率の良い、迅速な経路を計算する問題の新しいバリエーションを紹介する。従来の経路計画アプローチとは対照的に、我々は省エネのために経路のバリエーションを利用するだけでなく、省エネを達成するために経路に沿った走行速度のバリエーションも許容する。本アプローチは、固定経路に沿った最適な速度に関する単純かつ基本的な洞察と、制約付き最短経路問題への還元に基づいている

多くのアプリケーションは、最新のCDCL SATソルバで取り組むことができます。しかし、最近のCDCLソルバーのほとんどは、単純だが非常に高速に計算できる決定ヒューリスティックで探索を誘導しています。CDCLソルバーとは対照的に、先読み処理に基づくSATソルバーは、決定と局所推論に多くの時間を費やします。本論文では、CDCLアルゴリズムに、局所ルックアヘッド、全単位UIP学習、オンザフライプロービングという3つの軽量な追加技術を提案し、単位伝播と節学習だけでは見つけにくい単位節を探索できるようにするものである。これらの技術による推論ステップの追加により、結果として、元のアルゴリズムでは解けないSAT式を解くことができるようになる。

実世界の多くの問題は、充足可能性テスト(SAT)によって解決されている。しかし、SATソルバはバグを記録しているため、ある式が充足不可能であるという回答が正しくないことがある。認証アルゴリズムは、SATソルバーの信頼性を向上させるための魅力的なアプローチである。満足できない式に対しては、満足できないことの証明を作成しなければならない。本論文では、最新のSATソルバーの成功に不可欠な、様々な式の簡略化技術に対する証明書を紹介する。

本論文では、Bailleuxらが[21]で定式化した、単位伝搬による一般化弧整合性を維持する、疑似ブール制約からCNFへの、よりコンパクトなエンコーディングの存在に関する未解決問題の答えを出す。他のエンコーディングとは対照的に、我々のアプローチは抽象的な方法で定義され、具体的なインスタンス化を提示する。その結果、一般化された円弧一貫性を維持する以前最もよく知られていたエンコーディングによって生成された句の空間複雑度がO(n3 log(n)log(wmax)) であるのに対し、 O(n2 log2(n) log(wmax)) 句となった。

概念パターンに対する概念記述の照合は、Classicシステムでの応用を動機として、約20年前に記述論理（DL）の新しい推論タスクとして導入された。DLであるELでは、TBoxを用いないマッチングがNP完全であることが2000年に示された。本論文では、一般的なTBox（一般概念包含の有限集合、GCI）を用いたELのマッチングがNPであることを、非決定論的ルールを用いて、与えられたマッチング問題を多項式数のルール適用により解決された形に変換するゴール指向のマッチングアルゴリズムを紹介することにより、示します。また、一般的なTBoxに対するマッチング問題の扱いやすい変形をいくつか検討します。

過去10年間で、自動交渉は分散型人工知能の中心的な関心事に発展してきた。これは、経済学、電子商取引、政治・社会科学など様々な分野での幅広い応用の可能性があるためである。現実的な自動化交渉は、多問題、不完全情報、連続時間環境という複雑性を持つため、厳しい課題があり、近年、この課題に対応する多くの交渉戦略が提案されている。従来、このような戦略の性能は、各エージェントが他のすべての参加エージェントと「グローバル」に相互作用（交渉）するゲーム理論的な設定で評価されてきた。しかし、この伝統的な評価は、参加エージェント間の「局所的」相互作用によって特徴付けられる交渉設定、すなわち、多数の参加エージェントのそれぞれが、他のすべてのエージェントではなく、その局所的な隣人とのみ交渉する設定には適していない。本論文では、このような局所的な設定を扱うためのアプローチを提示する。従来のグローバルな視点から出発し、交渉の局所性（したがって、エージェントに関する空間的情報）を考慮するという新しい方法で交渉を分析する。このような異なるシナリオにおいて、経験的ゲーム理論と空間進化ゲーム理論の両方を用いて、最先端の交渉エージェント間の二国間交渉結果をどのように解釈できるかを示している。

可能性回答集合プログラミングは、標準的なASPの枠組みを拡張したもので、ASPプログラムのルールに確実性の度合いを付けることができるようにしたものである。このようなPASPプログラムのためのセマンティクスがいくつか発表されているが、それぞれが特定の長所と短所を持っている。本研究では、Gebserら(2009)によって導入された解の概念である、いわゆるiota-answer setを用いて、奇数サイクルや自動ブロック化規則を持つ標準的なASPプログラムの解を求める新しいセマンティクスを提案する。これは、与えられたASPプログラムのうち、解答集合が存在する最大部分集合を考慮することで実現される。我々の研究の主なアイデアは、ι-semanticsをポッシビリスティックなフレームワークに統合し、確実性の程度を回答集合に含まれる原子だけでなく、回答集合自体にも割り当てるというものである。我々のアプローチは、より満足のいく解を与え、他のアプローチで生じる直感に反する例を回避することができる。我々のアプローチを既存のものと比較し、既存のツールで解を計算できるように、標準的なASPフレームワークへの翻訳を提示する。

記述論理(DL)の文脈では、具象領域は、概念と事実を具象的な値とその間の予測値でモデル化することを可能にする。一般的なTBoxを持つDL ALCにおける推論では、具体的領域は非可述性を引き起こす可能性がある。具体的な領域に対するある種の制限の下では、決定可能性を回復することができる。一般に、具体的領域述語はクリスプであり、これはいくつかのアプリケーションにとって制限となる。本論文では、一般的なTBoxに対して、ファジィ具象領域と組み合わせたクリスプALCを研究し、決定可能性の条件を考案し、タブローに基づく推論アルゴリズムを与える。

本論文は、新しい問い合わせ言語フレームワークSTARQLの書き換え可能性、すなわちTBoxからオントロジーレベルの問い合わせへのコンパイル可能性、および展開可能性、すなわちオントロジーレベルの問い合わせからデータソースレベルの問い合わせへの変換可能性について議論することにより、”Ontology Based Data Access(ODBA)と生成系AIとGNN“で述べているオントロジーに基づくデータアクセス（OBDA）の時間化およびストリーム化の最近の取り組みに貢献するものである。STARQLの特徴は、一般的なストリームウィンドウとABoxシーケンシング戦略であり、これにより、接続クエリのユニオン（UCQs）のようなよく知られたクエリー言語をDL-LiteのようなTBox言語と組み合わせて接続し、その上でソート付き一階論理による時間推論を行うことが可能である。本論文では、DL-Liteオントロジー上のUCQを埋め込むSTARQLクエリが、CQLのようなバックエンドの再合理化ストリームクエリ言語に書き換えられ展開される安全性について論じる。これらの成果により、産業用モニタリングなどの産業関連アプリケーション分野における記述論理技術の採用が決定的に促進される。

我々は、大規模知識ベースにおける不整合性測定の問題を、ストリームベースの不整合性測定、すなわち、知識ベースを全体として考慮することができず、ストリーム内で処理する不整合性測定法を検討することによって調査する。そのために、まず、ストリーミングのケースに適用するのに適した新しい一貫性測定法を提示し、次に、新しい一貫性測定法と既存のいくつかの一貫性測定法に対するストリームベースの近似を提示する。大規模な知識ベースにおけるこれらの不整合性測定の動作について、実行時間、精度、スケーラビリティの観点から広範な実証分析を行った。その結果、新しい不整合性測定の近似とコンテンション不整合性測定の近似の2つについて、大規模な不整合性測定が可能であることがわかった。

定性的空間・時間推論における中心的な概念は、定性的制約論理であり、空間・時間知識を表現し推論するための特定のパラダイムを捉えるものである。この概念は、長い間研究コミュニティで非公式に使用されてきたが、2004年にLigozatとRenzによって特別な種類の関係代数として正式に定義され、バイナリ制約についての推論の特別なタイプを強調した。この概念は限定的であることが知られているが、このコミュニティで広く使われている。本論文では、この概念を再検討し、代替的なアプローチと対比させ、一般的な特性を分析する。我々の結果は、定性的制約論理の概念が狭すぎ、かつ一般的すぎることを示している。それは、異なるアプローチを許さないが、その設定はすでに任意の難しい問題を可能にする。

文脈を認識するシステムの設計指針として、文脈の取得と解釈に関する情報を利用者に提供することが挙げられる。この論文では、わかりやすさを提供するための既存のアプローチを紹介し、共通の欠点を明らかにする。コンテキストレベルから始まる説明は、ユーザーがシステムが動作しない理由を見つけ、理解するのを助けるには不十分である。本論文では、ユーザが故障の原因を突き止めるのを助ける手段として、コンテキスト認識システムのためのデバッガビリティを導入する。これを達成するために、我々は説明的デバッグから情報交換のアプローチを採用する。さらに、デバッガビリティの未解決の問題について議論し、可能な解決策を提供する。

本論文では、インデックスに基づくワークフロー類似性関数に向けた最初のステップを提示する。ワークフローの類似性に関する古典的なアプローチは、ワークフローのペアワイズ比較を実行する。したがって、本論文で紹介するワークフロー類似性関数は、インデックス上で比較が実行されるため、計算を高速化することができる。

人工ニューラルネットワークは、適用段階では高速ですが、学習段階では非常に低速です。一方、ニューラルネットワークを用いた最新のアプローチとして、例えば音素からなる信号データから画像を分類するハイブリッドニューラルネットワークプレイト（HNNP）アプローチのように、画像年齢分類タスクにおいて非常に効率的なものがあります。我々は、HNNPの中で最も計算コストの高い畳み込みニューラルネットワークを、先行する局所特徴抽出器とより単純で高速なニューラルネットワークに置き換えることで、音素認識のためのHNNPを高速化することを提案する。そこで、本論文では、この問題に対して適切な特徴抽出器を提案し、その結果得られる計算コストと分類性能を調査・比較する。実験の結果，提案した特徴抽出器のうち最適なものをより小さなニューラルネットワークと組み合わせたHNNPは，より複雑な畳み込みニューラルネットワークを用いたHNNPよりも2倍以上速く，なおかつ良好な分類性能を示すことが分かった．

現代のデータマイニングのアプリケーションで発生するビッグデータ問題を解決するためには、柔軟なモデルと、高速に収束し、データポイント数と特徴数の両方において効率的な並列化が可能な最適化アルゴリズムを組み合わせた包括的なアプローチが必要である。

本論文では、基底展開の原理に基づく加法モデルのフィッティングアルゴリズムを紹介する。基礎となる正規方程式を解く古典的なバックフィットアルゴリズムは、固有のデータ依存性のために適切に並列化することができず、特定の状況下では限られた誤差の減少につながる。その代わりに、この問題の特殊なブロック構造に適合するように修正されたBiCGStab法を提案する。この新しい方法は、優れた収束速度と有望な並列スケーラビリティを実証している。

本手法の収束特性について議論し、一連のベンチマーク問題を用いてその収束性とスケーラビリティをさらに調査する。

進化戦略(ES)を用いた実パラメータのブラックボックス最適化は、適合度関数やその特性が明示的に与えられていない場合によく適用されます。また、適合度や実現可能性の評価にはコストがかかる可能性がある。この問題を解決するために、過去に様々な代理モデルによるアプローチが提案されてきた。我々のこれまでの研究では、既に評価済みの個体で学習させた局所的な実現可能性代理モデルが提案されてきた。この最適化プロセスとの緊密な相互依存関係は、共分散行列適応ES (CMA- ES) のようなメタヒューリスティックを適用した場合に、複雑な副作用を引き起こすことになる。本論文の目的は、新しいタイプの制約代理モデルを提案することである。このモデルは、制約境界の推定に多段階の能動学習の概念を用い、段階に依存した精度を実現するものである。制約境界の基礎となる線形モデルは、各ステージにおいて二値探索により推定される。最適化過程では、制約関数の呼び出しを節約するために、事前選択スキームが採用される。この代理モデルは、単純な適応型(1 + 1)-ESと、制約付き最適化のための複雑な(1 + 1)-CMA-ESで評価される。線形制約付きテストベッドにおける両ESの結果は有望である。

近年、風力発電の短期予測において、統計的手法が大きな成果を上げている。本論文では、ターゲットとなるタービンの周囲を特定の半径で分割し、タービンを事前に選択する方法を示す。小さな問題インスタンスは、様々な回帰技術を用いた異なる入力セットの厳密な比較を可能にし、適切な特徴を見つけるための”進化的アルゴリズムの概要とアルゴリズム及び実装例について“でも述べている進化的アルゴリズムの適用を動機付ける。この最適化問題は、対象となるタービンや予測手法に強く依存しながらも、解くのが難しいことが判明した。

高度なAIプランニングアルゴリズムが存在するにもかかわらず、多くの統合された大規模プロジェクトではプランニングが使用されていません。その理由の一つは、シンタックス・ハイライティング・可視化などのエンジニアリングツールによるサポートが欠けているためと思われる。我々は、pddlのドメインと問題を効率的に作成するためのモジュラーツールボックスであるmyPddlを提案する。myPddlを評価するために、既存のpddl用知識工学ツールと比較し、pddlの初心者のための有用性を実験的に評価する。

この論文では、コンテナの積載で自然に発生するパッキング問題に注目する。3次元等方性オブジェクトの集合とコンテナが与えられたとき、タスクは、パッキングによって無駄にされるスペースを最小化する、ID、位置、および方向からなる入力オブジェクトのパッキングシーケンスを見つけることである。決定問題の代わりに、パッキング最適化問題に注目し、パッキングの総高さを最小化する。この手法は、シングルエージェントゲームや、最近では複雑な巡回セールスマン問題や車両経路問題の解決に有効であることが示されているランダム化探索手法である。実装は非常に単純であり、数学的プログラムによる分岐・境界探索や局所探索のアプローチとは概念的に異なる。しかし、2次元および3次元のパッキング問題を解いた結果は、有望である。

一般に領域非依存的な計画は、広範なタスクに適用可能である。現実的な問題の様々な側面を記述できる形式が多く存在する．しかし，表現力を高めると計画時間が長くなったり，政策の質が低下したりするため，どれを使うかは明らかでない場合が多い．ハードな保証は必要ないという前提のもとで、ユーザは複数のアプローチの中から選択を迫られることになる。一般的なモデルとして、我々は”マルコフ決定過程(MDP)の概要とアルゴリズム及び実装例について“で述べているマルコフ決定過程(MDP)の形式による確率的な記述を用いている。我々は、古典的計画法への抽象化変換と、完全観測可能な非決定論的計画法を定義する。我々の目標は、異なるMDP計画領域において、最先端のシステムがどのように機能するかを洞察することである。

自律的なエージェントは、環境であるビアセンサーやアクチュエーターと相互作用する。センサが高価であるという観察に動機づけられ、本論文では、部分的に観測可能な非決定論的環境において、エージェントがうまく計画し行動するために必要なセンサの量を最小化する問題に取り組んでいる。具体的には、観測変数の空間において、計画を見つけるために観測するのに十分な状態変数の包含最小集合を返す単純な貪欲なトップダウンアルゴリズムを提示する。我々は、以前の反復から計画を再利用し、変数間の関数的依存性を利用することで、ある変数の値を他の変数の値から推測できるようにし、アルゴリズムを拡張する。多くのベンチマーク問題に対する実験的評価により、実行時間、センサ数、計画の品質に関して有望な結果が得られた。

次回はKI2015について述べる。