著者

有村 博紀 宇野 毅明 湊 真一 平田 耕一 伊藤 公人 下薗 真一 喜田 拓也

出版者

北海道大学

雑誌

基盤研究(A)

巻号頁・発行日

2012-04-01

---

本研究では,実世界と情報世界が融合した巨大な情報空間から有用な知識を効率よくとりだすための大規模半構造マイニング技術の確立を目指す.とくに,大規模規模知識基盤形成システムのための基礎技術として,超高速半構造マイニングエンジンと,時空間情報を用いた半構造マイニング技術の研究開発,周辺技術として,確率的情報スキーマの導入と,知識連係技術と知識索引技術の研究開発を行った.開発した技術の実装と最適化によりプロトタイプシステムの構築を行った.

著者

奥乃 博 湊 真一

出版者

情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.36, no.8, pp.1789-1799, 1995-08-15

被引用文献数

2 1

---

BDD(二分決定グラフ)はブール関数のコンパクトな表現方法である。我々は、BDDを使用して組合せ問題の複数の解を同時に表現したり、ATMSといった多重文脈型真偽維特システムの機能拡張をする方法を検討してきた。与えられた問題記述あるいは制約条件からBDDを構築する過程は制約充足問題の解法とみなすことができる。本稿では、2種類のBDD、算術諭理式が使用できる通常のBDDと組合せ集合が使用できるZBDD(Zero?Suppressed BDD)を取り上げ、それらを用いた割約充足問題の解法を検討する。制約充足問題のデータと制約条件のコーディング方法を提案し、N?Queens問題や魔方陣の問題などの具体的な問題を取り上げ、2種類のBDDによる解法を評価する。さらに、BDDによる解法を、制約充足問題での一貫性アルゴリズムやATMSと比較し、評価を行う。BDDでは、一旦適用された制約条件が以降ずっと成立するという単調一貫性維持が成立する、一方、ZBDDでは、組合せ集合演算の性質から、制約条件が適周する対象によって制限される。しかし、この結果ZDDDでは段階的解法が容易となる。

著者

金田 悠作 吉澤 真吾 湊 真一 有村 博紀 宮永 喜一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. VLD, VLSI設計技術 (ISSN:09135685)

巻号頁・発行日

vol.109, no.393, pp.131-136, 2010-01-19

---

本稿では,重要なデータストリーム処理問題の一つである正規表現パターン照合に対して,ビット並列型パターン照合手法に基づいた高速なハードウェア指向アルゴリズムを提案する.並列ビット分配と呼ぶ新しいビット並列手法を用いて,文字と,連接,和,Kleeneプラスから構成させる非消去的正規表現のクラスに対して,O(mdlogb+m|Σ|)前処理時間とO(mdlogb/w+m|Σ|/w)領域を用いて,O(mdlogb/w)領域の高速なアルゴリズムを与える.ここで,nは入力長を表わし,mとd,bは,それぞれ,パターンの長さと,深さ,最大戻り幅を,wは計算機のワード長,|Σ|はアルファベットの要素数を表わす.さらに,このアルゴリズムを用いて,回路の再構成を伴わずにパターンの変更を可能なハードウェア実装のアーキテクチャをしめす.

著者

西野 正彬 安田 宜仁 湊 真一 永田 昌明

出版者

人工知能学会

雑誌

人工知能学会全国大会論文集 (ISSN:13479881)

巻号頁・発行日

vol.27, 2013

---

本稿ではPersonalized PageRank (PPR) を高速に計算する方法について述べる.PPRを計算するためには隣接行列を対象とする行列の乗算を繰り返し実行する必要があるが,グラフが大規模になると乗算にかかる計算コストが膨大になる.提案手法は隣接行列をゼロサプレス型二分決定グラフ (ZDD) を用いて圧縮した形で表現し,行列の乗算に必要な演算回数を削減することによって高速化を実現する.

著者

河原 吉伸 津田 宏治 鷲尾 隆 武田 朗子 湊 真一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. IBISML, 情報論的学習理論と機械学習 (ISSN:09135685)

巻号頁・発行日

vol.110, no.476, pp.63-68, 2011-03-21

参考文献数

14

---

特徴選択は,所与の特徴(パラメータや属性,関数などの集合)の中から問題解決に有効なその一部を取り出すタスクであり,機械学習や統計科学,データマイニングなどにおける最も重要な課題の一つである.この問題は近年,解釈性や計算効率の有用性から,疎な解を誘導しやすいノルムを用いた正則化損失関数最小化の枠組みで議論される場合が多い.損失関数の多くは集合関数として見た場合,劣モジュラ性を有するため,本稿では,特徴選択を劣モジュラ関数最適化として定式化する.これは,最も疎な解を誘導しやすいl_0ノルムを用いた正則化損失関数最小化を直接扱っている事に相当する.著者らは,2分決定図(Binary Decision Diagram; BDD)を用いた解空間の表現,及び,特徴を選択する評価関数の劣モジュラ性を用いた効率的な探索により,厳密解を含む最適性の高い解を列挙する方法を提案する.さらに,提案手法の有用性に関する検証例を示す.

著者

鮑 若愚 白井 康之 湊 真一

出版者

人工知能学会

雑誌

人工知能学会全国大会論文集 (ISSN:13479881)

巻号頁・発行日

vol.26, 2012

---

インターネットの普及により、ネット上での評価情報(口コミ、レビューなど)は消費者の消費行動に大きく影響を及ぼすようになっている。しかし、消費者への正確な評価情報の推薦、評価の正当性など、未だに多くの課題が存在している。こうした背景に基づき、本研究では評価情報中のコメント文に着目し、消費者、提供者、評価者に対して、それぞれの立場や目的に応じた評価情報の有効的な利用について提案する。

著者

櫻井 祐子 横尾 真 湊 真一

出版者

九州大学

雑誌

基盤研究(C)

巻号頁・発行日

2011-04-28

---

効率的な提携を形成すること(提携構造形成問題)は,人工知能やマルチエージェントシステムの研究領域において,重要な研究分野となっている.本研究課題では,多分岐ゼロサプレス型BDD~(MTZDD)を応用し,(1) あらゆる特性関数を記述可能,(2) 既存の表現法よりも指数的に簡略化可能な場合が存在,(3) コアに関する問題をMTZDDのノード数の多項式時間で求解可能,(4) 提携構造形成問題は混合整数計画法を用いることで,既存アルゴリズムよりも高速に解を求めることが求解可能といった性質を持つ簡略記述法の提案などを行った.これらの研究成果は,国際会議 PRIMA2011で優秀論文賞を受賞した.

著者

湊 真一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. AI, 人工知能と知識処理 (ISSN:09135685)

巻号頁・発行日

vol.107, no.78, pp.27-32, 2007-05-31

---

二分決定グラフ(BDD)は,大規模論理関数を主記憶上に効率よく表現するデータ構造であり,1990年頃より,車にVLSI設計自動化の分野で盛んに研究開発されてきた.近年,このBDDが,データマイニング・知識発見の分野においても活用できることがわかってきた.特に,ゼロサプレス型BDD(ZBDD)と呼ばれるタイプのBDDは,疎な組合せ集合を効率よく扱うことができるため,現実に扱われる多くのデータベースの解析処理に適している.本稿では,ZBDDを用いた頻出アイテム集合マイニングの技法や,様々なクエリを集合演算として処理する渾繹データベースへの応用,アイテム集合に関する独立成分や対称成分を高速に抽出するアルゴリズム等,BDDを用いたデータマイニング・知識発見技術に関する最近の話題について述べる.