1 0 0 0 OA 大規模知識基盤形成のための次世代半構造マイニング技術の展開
本研究では,実世界と情報世界が融合した巨大な情報空間から有用な知識を効率よくとりだすための大規模半構造マイニング技術の確立を目指す.とくに,大規模規模知識基盤形成システムのための基礎技術として,超高速半構造マイニングエンジンと,時空間情報を用いた半構造マイニング技術の研究開発,周辺技術として,確率的情報スキーマの導入と,知識連係技術と知識索引技術の研究開発を行った.開発した技術の実装と最適化によりプロトタイプシステムの構築を行った.
1 0 0 0 平面巡回セールスマン問題の高速な近似アルゴリズム
- 著者
- 久保 典弘 村本 勝洋 下薗真一
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)
- 巻号頁・発行日
- vol.2000, no.84, pp.49-56, 2000-09-21
平面上に与えられた点をすべてを通過し最初の点に戻ってくる最も短い巡回路を求める問題の,非常に高速なアルゴリズムについて述べる.本アルゴリズムは非常に単純なアルゴリズムなので実装が簡単である.また,n個の点が与えられたときにO(n log n)時間,O(n)領域で計算を行う.アルゴリズムは,平面を分割し,点をソートして分割領域内の順路を求め,各領域内の順路をつなぎ合わせる構成をとる.ランダムに点が分布するときは確率的に定数近似アルゴリズムである.このアルゴリズムをKarpの分割アルゴリズム,Lin-Kernighanの局所探索,Aroraの近似スキームなどと比較した結果,実行時間は最も速く精度は同じかより良いという結果が得られた.We present a quite simple, fast and practical algorithm to find a short cyclic tour that visits a set of points distributed on the plane. The algorithm runs in O(n log n) time with O(n) space, and is simple enough to easily implement on resource restricted machines. It constructs a tour essentially by axis-sorts of the points and takes a kind of the 'fixed dissection strategy.' We show that the algorithm is a 'probabilistic' constant-ratio approximation algorithm for uniform random distributions. We made computational comparisons of our algorithm, Karp's partitioning, Lin-Kernighan local search, Arora's PTAS, etc. The results indicate that in running time our algorithm overwhelms existing ones, and the average approximation ratio is better or competitive.
我々が開発したCSDF構造刈り込みの手法は、脳機能の本質に迫るとされる冗長削減原理の一形態と考える。本基盤研究では、この手法を洗練・改良した上で以下のような応用を行い、当初の目標は概ね達成されたものと考える。(A)アナロジー類推プロセッサアナロジーは認知科学、心理学、科学史、AIなどで研究されてきた。アナロジー類推を行う我々のニューロプロセッサは比較的シンプルで、そこでは抽象化内部モデルおよび具体⇔抽象の結合がCSDFの働きで自律生成されるという独自のものである。内部モデルへの引き込み等が起こることで、複合アナロジーや追加アナロジーの学習パラダイムにおいても有効であることが確認された。(B)独立成分分析(ICA)ICAもしくはBSSとは、混合された複数未知信号を分離抽出するという新IT技術である。我々の方法は、情報理論に基づいた従来法とは根本的に異なる。センサー信号を入力するオートエンコーダに恒等写像学習を行わせ、同時に、デコーダ部にCSDFを施す。すると、CSDFに抗して生き残った隠れ素子が源信号を再生する。また、デコーダ行列は混合行列を再生するので、デコーダ部は外部世界(源信号-センサ)の内部モデルとなる。従来法と比べて適応性・ロバスト性に富むことが特長で、音声や画像の実データを使った実験においてもある程度の成功を収めた。