05 2016/06 07
29303101020304
05060708091011
12 131415161718
19202122232425
26272829300102
Click セミナー

過去のセミナー

開催日2016年6月13日(月曜日)
発表者和佐州洋
タイトル非巡回な部分グラフの列挙について
開催日2016年5月31日(火曜日)
発表者荒井ひろみ
タイトルリバース・エンジニアリングによるプライバシ評価
開催日2016年5月23日(月曜日)
発表者竹内聖悟
タイトルBDD/ZDD を用いた近似計算について
開催日2016年5月17日(火曜日)
発表者Mathias Soeken
タイトルAncilla-free reversible logic synthesis using symbolic methods
開催日2016年2月22日(月曜日)
発表者岡本 吉央
タイトルネットワーク型交渉ゲームの安定化アルゴリズム
開催日2016年2月16日(火曜日)
発表者森永聡、中村祐一
タイトル「企業における情報科学技術の基礎研究と応用」 ‐機械学習、ハードウェアプラットフォームの例で‐
開催日2016年1月28日(木曜日)
発表者鷲尾 隆
タイトル機械学習による先端センシングデバイスの実現
開催日2016年1月19日(火曜日)
発表者Hei Chan
タイトルIdentifying Causal Effects in Linear SEMs
開催日2015年12月25日(金曜日)
発表者白井康之
タイトルビッグデータ分析とプロモーション戦略・戦術展開への応用
開催日2015年12月7日(月曜日)
発表者幸若完壮
タイトルソーシャルネットワークにおけるコアコミュニティ発見に関する研究
開催日2015年12月3日(木曜日)
発表者繁富(栗林)香織
タイトル細胞折紙技術 — 細胞が折り紙を折る? 最適な折り図はあるか? —
開催日2015年11月30日(月曜日)
発表者中島祐人
タイトルLyndon 文字列の世界と連定理
開催日2015年10月23日(金曜日)
発表者Endre Boros
タイトルGenerating Bodies, Simplices, and Vertices of Polyhedrao
開催日2015年10月23日(金曜日)
発表者津田宏治
タイトルガウシアンプロセスとベイズ最適化
開催日2015年10月20日(火曜日)
発表者林克彦
タイトル木オートマトン・トランスデューサによる自然言語処理
開催日2015年9月29日(火曜日)
発表者木村 圭吾
タイトル高速テンソル分解法 -高速テンソル分解,オンラインテンソル分解-
開催日2015年9月3日(木曜日)
発表者難波 博之
タイトルパーマネントを用いた最短点素パスの計算
発表者丸茂直貴
タイトル離散DC計画問題に対する連続緩和
発表者坂上晋作
タイトル2本の2次制約付き非凸2次計画問題に対する多項式時間アルゴリズム
開催日2015年9月2日(水曜日)
発表者伝住周平
タイトルZDDの簡潔表現に関する進展と最近の話題について
発表者岩政勇仁
タイトルk-劣モジュラ緩和について
開催日2015年8月31日(月曜日)
発表者石井 利昌
タイトル連結度要求を持つネットワーク構成問題とその一般化について
開催日2015年8月19日(水曜日)
発表者川原純
タイトル複数終端ZDDを用いた連結成分重み比順の連結成分分割列挙
開催日2015年7月10日(金曜日)
発表者澤田 宏
タイトル多次元複合データ分析技術
開催日2015年7月7日(火曜日)
発表者伊藤公人
タイトルCombining Population Genetics of Pathogens and Epidemiology of Infectious Diseases
開催日2015年5月15日(金曜日)
発表者David Avis
タイトルPolynomial size matching polytopes
開催日2015年5月12日(火曜日)
発表者井上武
タイトルホスト名グラフと暗号化通信の推定
開催日2015年4月27日(月曜日)
発表者新屋良磨
タイトル正規表現入門~星の高さを求めて~
開催日2015年2月6日(金曜日)
発表者Matias Korman
タイトルExtremal distances in Polygonal Domains
開催日2015年1月30日(金曜日)
発表者David Avis
タイトルA portable parallel implementation of the lrs vertex enumeration code
開催日2015年1月16日(金曜日)
発表者中原 啓貴
タイトル電波望遠鏡におけるデジタル分光器と決定グラフを用いた設計法について
開催日2014年12月25日(木曜日)
発表者阿部正佳
タイトルリバースエンジニアリングにおける BDD/ADD の二つの適用事例
開催日2014年12月19日(金曜日)
発表者牧野和久
タイトル単調論理関数の双対化問題について
発表者宇野毅明
タイトルコーヒーよりドーナッツ
開催日2014年12月5日(金曜日)
発表者竹内聖悟,倉井龍太郎
タイトルSDD (Sentential Decision Diagram) の概要と SDD Package の利用方法について
開催日2014年11月14日(金曜日)
発表者白井康之
タイトル購買選好度減衰曲線を用いた選択多様性解析とその応用 (北海道大学集中講義「大規模離散計算科学特論」)
開催日2014年10月30日(木曜日)
発表者鷲尾 隆
タイトルMass based estimation of data distribution and dissimilarity (北海道大学集中講義「大規模離散計算科学特論」)
開催日2014年10月24日(金曜日)
発表者津田宏治
タイトルマテリアルズ・インフォマティクスにおけるベイズ最適化 (北海道大学集中講義「大規模離散計算科学特論」)
開催日2014年10月3日(金曜日)
発表者田中功
タイトルマテリアルズ・インフォマティクスの現状と将来展望
開催日2014年9月3日(水曜日)
発表者鈴木大慈
タイトル確率的交互方向乗数法
開催日2014年8月25日(月曜日)
発表者Michael Lampis
タイトルParameterized Approximation Schemes using Graph Widths
開催日2014年8月19日(火曜日)
発表者笹木一義
タイトル日本科学未来館の展示開発・連携事業 2013~2014
開催日2014年8月5日(火曜日)
発表者比戸将平
タイトルJubatusから未来の分散インテリジェンスへ
開催日2014年7月15日(火曜日)
発表者Kitsuchart Pasupa
タイトルCan relevance of images be inferred from eye movements?
開催日2014年7月7日(月曜日)
発表者Leonardo Bartoloni
タイトルTime/space tradeoff on Discrete Optimization using approximated Binary Decision Diagrams
開催日2014年7月4日(金曜日)
発表者東條 弘
タイトルODSの取り組みについて
開催日2014年5月28日(水曜日)
発表者瀧澤重志
タイトル国際会議凱旋報告:ZDDとフロンティア法を用いた建築のフロアプラン列挙手法
開催日2014年5月7日(水曜日)
発表者長津尚英
タイトルNTT R&Dのグローバル活動とNTTビズリンク社のビジネスについて
開催日2014年4月30日(水曜日)
発表者永幡 裕
タイトルMarkov連鎖が持つ時間階層構造抽出に向けて (階層間をつなぐ理論の構築と、複雑な反応系の解析に向けて)
開催日2014年4月16日(水曜日)
発表者Valia Mitsou
タイトルComputational complexity of games and puzzles, and, in particular of the card game SET
開催日2014年4月11日(金曜日)
発表者花田 博幸
タイトルq-gram距離基準による類似文字列検索の高速化
開催日2014年2月26日(水曜日)
発表者井上 武
タイトルGraphillion update
発表者安田宜仁
タイトル部分木の列挙におけるGraphillionの利用事例
発表者中元政一
タイトルEkillionでのGraphillionの利用事例紹介
発表者安井 雄一郎
タイトル高性能計算機上でのグラフ最適化基盤の開発
開催日2014年1月24日(金曜日)
発表者岩下洋哲
タイトルプロパティ検証問題におけるBDDの実用化技術
開催日2014年1月17日(金曜日)
発表者戸田貴久
タイトル三分決定グラフを用いた論理関数の双対化について
開催日2014年1月10日(金曜日)
発表者Charles Jordan
タイトル大規模なExperimental Descriptive Complexityへ向かって
開催日2013年12月16日(月曜日)
発表者Phillippe Samer
タイトルA branch and cut algorithm for spanning trees under conflict constraints
開催日2013年12月10日(火曜日)
発表者安田宜仁
タイトル地理情報検索とそのサービス例
開催日2013年12月6日(金曜日)
発表者Nabila Abdessaied
タイトルUpper bounds for reversible circuits based on Young subgroups
開催日2013年12月3日(火曜日)
発表者数原良彦
タイトル検索サービスを支える技術
開催日2013年11月28日(木曜日)
発表者Will Archer Arentz
タイトルWhat is Rakuten Institute of Technology (RIT)?
開催日2013年11月8日(金曜日)
発表者白井康之
タイトル人気感度と多様性に基づく顧客のセグメント化とその応用(北海道大学集中講義「大規模離散計算科学特論」)
開催日2013年11月1日(金曜日)
発表者鷲尾 隆
タイトル確率的希少事象シミュレーションによる災害シナリオ解析(北海道大学集中講義「大規模離散計算科学特論」)
開催日2013年10月28日(月曜日)
発表者田部井靖生
タイトル巨大反復テキスト処理のための完備オンライン文法圧縮
開催日2013年10月25日(金曜日)
発表者津田宏治
タイトル生命科学におけるデータマイニング(北海道大学集中講義「大規模離散計算科学特論」)
開催日2013年10月8日(火曜日)
発表者Florian Lonsing
タイトルSearch-based QBF Solving: Basics, Recent Trends and Challenges
開催日2013年10月1日(火曜日)
発表者永幡裕
タイトル定常マルコフ連鎖から階層構造を抽出する際に生じる組み合わせ爆発
開催日2013年9月20日(金曜日)
発表者Rajeev Raman
タイトルEncodings for Range Selection and Top-k Queries
開催日2013年9月18日(水曜日)
発表者鈴木 真一朗
タイトルMuseum and the Web 2013 参加報告
開催日2013年9月12日(木曜日)
発表者櫻井 祐子
タイトル特性関数の簡潔記述法と提携構造形成問題
開催日2013年9月3日(火曜日)
発表者Novi Quadrianto
タイトルSimple and Efficient Bayesian Random Forest
開催日2013年8月29日(木曜日)
発表者Martina Seidl
タイトルRecent Advancements in QBF Solving
開催日2013年8月28日(水曜日)
発表者Zhiyong Peng
タイトルKey Management for Access Control in Trusted Cloud Storage
開催日2013年8月27日(火曜日)
発表者秋葉拓哉
タイトルPruned Landmark Labeling によるグラフ最短経路クエリ
開催日2013年8月26日(月曜日)
発表者Łukasz Kaiser
タイトルExperimental Descriptive Complexity and Machine Learning
開催日2013年8月8日(木曜日)
発表者中原啓貴
タイトル多値決定グラフに基づくパケット分類器に関して
開催日2013年8月1日(木曜日)
発表者伊藤健洋
タイトルグラフ構造を用いた配電融通アルゴリズムの研究
開催日2013年7月16日(火曜日)
発表者永山忍
タイトルZDD を用いた正規表現マッチングについて
開催日2013年7月4日(木曜日)
発表者前原貴憲
タイトル大規模グラフに関する行列計算
開催日2013年7月2日(火曜日)
発表者Marco Cuturi
タイトルLightspeed Optimal Transportation Distances for Histograms
開催日2013年5月29日(水曜日)
発表者安田宜仁
タイトル制約をともなう動的計画法のZDDを用いた解法
開催日2013年5月9日(木曜日)
発表者Florian Horn
タイトルStochastic Games in Verification
開催日2013年4月24日(水曜日)
発表者Michael E. Houle
タイトルIntrinsic Dimensionality and Discriminability of Data
開催日2013年4月12日(金曜日)
発表者美添一樹
タイトル分散並列モンテカルロ木探索および囲碁への応用(中間報告)
開催日2013年3月26日(火曜日)
発表者杉本雅則
タイトル音響信号を用いたセンシング技術
発表者吉田 哲也
タイトルネットワークからのコミュニティ発見に関する取り組み
開催日2013年3月22日(金曜日)
発表者石畠 正和
タイトルProposionalized Probability Computation and Learning on Binary Decision Diagrams
開催日2013年3月21日(木曜日)
発表者Martin Müller
タイトルMove Quality in Monte Carlo Simulation: A Case Study using the Fuego Go Program
開催日2013年3月11日(月曜日)
発表者斎藤寿樹
タイトル区間グラフおよび関連クラスに対する部分表現拡張問題
開催日2013年3月9日(土曜日)
発表者岩下洋哲,中澤 吉男
タイトル最小完全ハッシュ関数を用いたグリッドグラフ上の効率的なパス数え上げ
開催日2013年1月31日(木曜日)
発表者宮川 晋
タイトル最新IP技術開発の現場から
開催日2013年1月28日(月曜日)
発表者Robert Wille and Mathias Soeken
タイトルSynthesis of Reversible Circuits using Decision Diagrams: Background,Recent Accomplishments, and Open Challenges
開催日2013年1月15日(火曜日)
発表者吉仲亮
タイトル近年の文脈自由文法のアルゴリズム的学習について
開催日2013年1月11日(金曜日)
発表者湊 真一
タイトル本プロジェクトの近況と今後の方向性について
開催日2012年12月12日(水曜日)
発表者遠藤敏夫
タイトルポストペタスケール時代のメモリ階層の深化に対応するソフトウェア技術
発表者佐藤仁
タイトルGPU MapReduceによる大規模グラフ処理
発表者安井雄一郎
タイトルメモリ階層構造を考慮した大規模グラフ処理の高速化
発表者藤澤克樹
タイトル大規模最適化問題に対するソフトウェア開発と高速&安定計算 --理論からスパコンまで--
開催日2012年12月6日(木曜日)
発表者笠原 正治
タイトルクラウド・コンピューティングにおけるタスク・スケジューリング問題と確率論的アプローチ
開催日2012年12月5日(水曜日)
発表者Rajeev Raman
タイトルDynamizing Succinct Tree Representations
発表者Roberto Grossi
タイトルEmpowering Succinct Data Structures for Strings and Sequences
開催日2012年11月22日(木曜日)
発表者Alexandre Termier
タイトルParaMiner: generic and parallel pattern mining scaling to real-world data
開催日2012年11月19日(月曜日)
発表者夫 紀恵
タイトルToric idealを用いた平面的periodicグラフ上最短路問題及びパラメトリック整数計画問題のための高速アルゴリズム
開催日2012年11月14日(水曜日)
発表者林浩平
タイトルテンソル分解による関係データ解析
開催日2012年11月12日(月曜日)
発表者S.R.K. Branavan
タイトルGrounding Linguistic Analysis in Control Applications
開催日2012年11月9日(金曜日)
発表者白井康之
タイトルSet-Similarity Joins (北海道大学集中講義「大規模離散計算科学特論」)
開催日2012年11月6日(火曜日)
発表者戸田貴久
タイトルOn Separating Convex Points with Lines
開催日2012年11月2日(金曜日)
発表者鷲尾 隆
タイトルGlobal Maximization of Submodular Function and Its application to Machine Learning(北海道大学集中講義「大規模離散計算科学特論」)
開催日2012年10月26日(金曜日)
発表者津田宏治
タイトル大量データの類似度検索技術(北海道大学集中講義「大規模離散計算科学特論」)
開催日2012年10月3日(水曜日)
発表者Lukasz Kaiser
タイトルLearning and Playing Board Games using Descriptive Complexity
開催日2012年9月14日(金曜日)
発表者鍋島 英知
タイトル高速 SAT ソルバーの原理
開催日2012年9月13日(木曜日)
発表者谷 誠一郎
タイトル匿名ネットワーク上の分散計算におけるメッセージ圧縮とその応用
開催日2012年9月12日(水曜日)
発表者Prof. Rusins Freivalds
タイトルUltrametric automata and Turing machines
開催日2012年9月7日(金曜日)
発表者堀山貴史
タイトル多面体の展開図の数え上げについて
開催日2012年8月10日(金曜日)
発表者山西芳裕
タイトル薬・標的タンパク質間相互作用ネットワーク予測のための機械学習法
開催日2012年8月3日(金曜日)
発表者相田 慎
タイトル福島復興プロジェクト「ふるさとめぐみラボ」
開催日2012年7月6日(金曜日)
発表者番原 睦則
タイトルSAT 技術を用いた組合せテストケース生成
開催日2012年6月8日(金曜日)
発表者瀧川一学
タイトル創薬・生命科学におけるデータマイニング
開催日2012年5月30日(水曜日)
発表者山室健
タイトルCompression and Searches with Modern Processors (Practice and Implementation)
開催日2012年5月30日(水曜日)
発表者鬼塚真
タイトル大規模データを対象とした分析処理の高速化に関する取り組み
開催日2012年5月24日(木曜日)
発表者竹内聖悟
タイトル第22回世界コンピュータ将棋選手権参加報告、及び、GPS 将棋のアルゴリズム
開催日2012年4月20日(金曜日)
発表者青木 洋士
タイトル文字列の集合を表すSeqBDDに関する種々の技法について
開催日2012年4月13日(金曜日)
発表者福田健介
タイトルインターネットバックボーントラフィックにおける異常検出
開催日2012年3月30日(金曜日)
発表者鈴木 真一朗
タイトルつながりをつくる -日本科学未来館の取り組み-
開催日2012年2月24日(金曜日)
発表者美添 一樹
タイトル超並列分散モンテカルロ木探索
開催日2012年2月20日(月曜日)
発表者石畠正和
タイトルBayesian networks and BDDs
開催日2012年2月10日(金曜日)
発表者Charles Jordan
タイトルDescriptive Programming
開催日2012年1月20日(金曜日)
発表者渋谷哲朗
タイトル統計モデルと大規模パタンマッチングアルゴリズム
開催日2011年12月26日(月曜日)
発表者戸田貴久
タイトル集合の2分割のなす分離族について
開催日2011年12月19日(月曜日)
発表者堀田 敬介
タイトル一票の格差の観点からの選挙区割と最適化
開催日2011年11月25日(金曜日)
発表者鷲尾 隆
タイトル関数モデル上の統計的因果推論研究の現状(連携講座集中講義)
開催日2011年11月24日(木曜日)
発表者白井康之
タイトル大規模実データを用いた解析事例の紹介(連携講座集中講義)
開催日2011年11月14日(月曜日)
発表者吉澤 真吾
タイトルアルゴリズムFPGA/LSIハードウェア実装の研究戦術
開催日2011年10月27日(木曜日)
発表者浅野哲夫
タイトル省メモリのための新たなアルゴリズム設計技法:制限された作業用メモリでアルゴリズムを如何に設計するか
開催日2011年10月14日(金曜日)
発表者津田宏治
タイトル複合ソート法による高速な全ペア類似度検索とその生物学データへの応用(連携講座集中講義)
開催日2011年10月12日(水曜日)
発表者富田 悦次
タイトル最大クリーク問題の多項式時間的可解性について
開催日2011年9月30日(金曜日)
発表者千葉 英史
タイトル液晶製造に関連した最適化問題としての定式化と効率的な解決法の提案
開催日2011年9月14日(水曜日)
発表者穴井 宏和
タイトルQEの計算アルゴリズムとその応用~数式処理による最適化
開催日2011年8月30日(火曜日)
発表者佐久間 淳
タイトル知識発見におけるデータ匿名化とプライバシ保護データマイニング
開催日2011年8月29日(月曜日)
発表者堀山 貴史
タイトル最小/最大の直径、幅および包囲長方形を持つ正多面体の展開図について
開催日2011年8月26日(金曜日)
発表者加藤直樹
タイトル最適避難計画の理論と応用
開催日2011年8月25日(木曜日)
発表者中原 啓貴
タイトル多分岐決定図に基くプロセッサとその応用
開催日2011年8月25日(木曜日)
発表者岸本章宏
タイトルDepth-First Proof-Number Search in the Presence of Repetitions
開催日2011年8月24日(水曜日)
発表者定兼 邦彦
タイトル簡潔データ構造
開催日2011年8月23日(火曜日)
発表者杉山将
タイトル確率密度比を用いた統計的機械学習の新しいアプローチ
開催日2011年8月23日(火曜日)
発表者伊藤大雄
タイトル定数時間アルゴリズムとその基本定理 --- 正則性補題と分割定理
開催日2011年8月9日(火曜日)
発表者宇野毅明
タイトル必ず2つ以上子供を持つ木の圧縮
開催日2011年7月29日(金曜日)
発表者竹内 聖悟
タイトルモンテカルロ木探索の将棋への応用とパラメータ調整
開催日2011年7月15日(金曜日)
発表者西野 正彬
タイトルZDDを用いた効率的な集合拡張の計算
開催日2011年7月8日(金曜日)
発表者松崎和賢
タイトルデータ匿名化の現状に関する一考察
開催日2011年7月1日(金曜日)
発表者湊 真一
タイトル米国CMU訪問および国際会議SAT2011の参加報告
開催日2011年6月17日(金曜日)
発表者岩下洋哲
タイトルZDD-Mate法(仮称)によるグラフのパス列挙
開催日2011年5月24日(火曜日)
発表者Prof. Neil Immerman
タイトル"P versus NP: Approaches, Rebuttals, and Does It Matter?"
開催日2011年5月20日(金曜日)
発表者川原 純
タイトルZDDを用いたパスの列挙と索引生成
開催日2011年4月21日(木曜日)
発表者湊 真一
タイトルπDD: 順列集合を演算処理する二分決定グラフについて
開催日2011年4月15日(金曜日)
発表者梅谷 俊治
タイトル大規模な集合被覆問題に対する数理計画法に基づく発見的解法
開催日2011年4月8日(金曜日)
発表者Michael Houle
タイトルIntrinsic Dimensionality and its Applications to Databases and Data Mining
開催日2011年3月23日(水曜日)
発表者湊 真一
タイトルBDD/ZDDパッケージ講習会(第二回)
開催日2011年3月22日(火曜日)
発表者湊 真一
タイトルBDD/ZDDパッケージ講習会(第一回)
開催日2011年3月7日(月曜日)
発表者 Dr. Benjamin Rossman
タイトルAverage-case complexity of detecting cliques
開催日2011年2月28日(月曜日)
発表者倉井龍太郎
タイトルWebサービス事業者の最新動向と株式会社はてなの研究開発事例
開催日2011年2月24日(木曜日)
発表者植野 剛
タイトル統計学習による強化学習の考察
開催日2011年2月7日(月曜日)
発表者Dr. Paula Brito
タイトルIntroduction to Symbolic Data Analysis (An interaction movement between statistics and data processing)
開催日2011年1月31日(月曜日)
発表者Dr. Mathias Soeken
タイトルFormal Verification of UML-based Specifications
開催日2011年1月28日(金曜日)
発表者岩下 洋哲
タイトルImproving Simulation Coverage of Metastability Effects in Clock Domain Crossing Verification
開催日2011年1月21日(金曜日)
発表者小寺正明
タイトルメタボローム技術で得られる代謝経路不明な多数の化合物の組み合わせから経路を予測する手法の開発
開催日2011年1月11日(火曜日)
発表者金沢 誠
タイトルA Chomsky-Sch\"{u}tzenberger-Weir Representation Theorem for Simple Context-Free Tree Grammars
開催日2011年1月7日(金曜日)
発表者伊藤公人
タイトルPrediction of amino acid substitutions on the hemagglutinin molecules of influenza A viruses
開催日2010年12月17日(金曜日)
発表者Guan-Cheng Li
タイトルMining Psychology from English News and Applications on Finance.
開催日2010年11月19日(金曜日)
発表者Prof. Kai Ming Ting
タイトルMulti-Dimensional Mass Estimation and Mass-based Clustering
開催日2010年11月15日(月曜日)
発表者Prof. Adnan Darwiche
タイトルEfficient Representations of Boolean Functions: The View from Knowledge Compilation
開催日2010年11月12日(金曜日)
発表者鈴木譲
タイトル連続データにも使えるMDL基準の一般化
開催日2010年11月5日(金曜日)
発表者吉仲 亮
タイトルSeq BDD と既存手法との比較について,
開催日2010年11月5日(金曜日)
発表者伝住周平
タイトルSeqBDD : Introduction to Sequence BDD
開催日2010年10月29日(金曜日)
発表者井上 武
タイトル通信ネットワークの構造分析について
開催日2010年10月22日(金曜日)
発表者湊 真一
タイトルBDD/ZDDを基盤とする種々の離散構造の演算処理と代数系(algebra) について
開催日2010年9月27日(月曜日)
発表者比戸将平
タイトルハッシュを用いた高速なグラフカーネルとZDD
発表者今道貴司
タイトル非線形最適化を用いた図形の充填問題の解法
発表者井手剛
タイトル経路のコストに関する回帰問題について
開催日2010年9月16日(木曜日)
発表者堀山 貴史
タイトル回転によるタイリングについて
開催日2010年9月2日(木曜日)
発表者Prof. Randy Goebel
タイトルChallenges for a theory of visualization: what is semantic symmetry?
開催日2010年8月26日(木曜日)
発表者田部井靖生
タイトルスケッチソート法による全点間類似度検索
開催日2010年8月23日(月曜日)
発表者柴田剛志
タイトルデータインテンシブな計算方法としての分散ワークフローに関する研究の紹介
開催日2010年8月20日(金曜日)
発表者山下茂
タイトル量子回路設計とは?
開催日2010年8月20日(金曜日)
発表者Byung-Soo Choi
タイトルTopological Quantum Computerのための量子回路設計問題
開催日2010年8月6日(金曜日)
発表者宇野 毅明
タイトル山登りは大変なので沢登りアルゴリズム
開催日2010年8月6日(金曜日)
発表者山本章博
タイトル分散データベースからの頻出飽和アイテム集合のプライバシー保護発見
開催日2010年8月4日(水曜日)
発表者上原 隆平
タイトルじゃばら折りの一般化とその複雑さの研究
開催日2010年8月3日(火曜日)
発表者山下茂
タイトルIntroduction to Grover Algorithm
開催日2010年8月3日(火曜日)
発表者Prof. Byung-Soo Choi
タイトルGrover Search and its Applications
開催日2010年7月23日(金曜日)
発表者喜田拓也
タイトル効率よいVF符号の設計
開催日2010年7月9日(金曜日)
発表者白井康之
タイトルデータ匿名化に関する検討事項
開催日2010年7月2日(金曜日)
発表者斎藤寿樹
タイトルProper Interval Graphのランダム生成と列挙
開催日2010年6月18日(金曜日)
発表者川原 純
タイトルオンラインユニットクラスタリング問題の競合比の改良
開催日2010年6月4日(金曜日)
発表者吉仲 亮
タイトルChomsky-Schützenberger-Type Characterization of Multiple Context-Free Languages
開催日2010年5月21日(金曜日)
発表者湊 真一
タイトル北大版BDD/ZDDパッケージの概要/北大ERATOオフィスのIT系インフラ構成の現状と今後の課題について
開催日2010年5月14日(金曜日)
発表者荒井迅
タイトル計算ホモロジー理論とその応用
    

詳細

閉じる
開催日2016年6月13日(月曜日)
開催場所VBL棟 301B
開催時間16時30分-17時30分 
発表者和佐州洋  
発表者の紹介国立情報学研究所 情報学プリンシプル研究系 特任研究員
タイトル非巡回な部分グラフの列挙について 
発表の概要部分グラフ列挙問題とは,グラフGとグラフクラスCが与えられた時に,Cに属するGの部分グラフを漏れなく重複なく列挙する問題である.これまでに,全域木やコーダルグラフなど,幾つかのグラフクラスに対して,最適な列挙アルゴリズムが開発されてきたものの,未解決な列挙問題が多いのも現状である.
本発表では,列挙アルゴリズムを構築する上での基礎的な知識を紹介するとともに,発表者が特に注目してきた非巡回なグラフクラスに対する列挙問題と,開発してきたアルゴリズムについて紹介する.また,列挙で使われる技法と,他分野とのつながりについても議論したい.
接続サイト神田ラボ
    
閉じる

詳細

閉じる
開催日2016年5月31日(火曜日)
開催場所VBL棟 301B
開催時間13時00分-14時00分 
発表者荒井ひろみ  
発表者の紹介東京大学
タイトルリバース・エンジニアリングによるプライバシ評価 
発表の概要個人情報や秘匿性の高いデータの利用に関する話題の一つに,データ開示におけるプライバシ保護がある.例えば個票の公開の際には明示的な識別子を消去する匿名化などの技術がある.統計量や学習器などの明示的に元のデータを含まないデータの場合は元のデータのプライバシが保護されていると考えられてきた.しかし近年,そのような抽象化されたデータから元のデータを推測する攻撃方法が提案されてきている.本講演では,講演者の研究であるゲノム検査結果からもとのゲノムを推測する攻撃や,Model Inversion Attack [1] を紹介し,リバース・エンジニアリングによるプライバシ評価の可能性について議論したい.

[1] Fredrikson, Matt, Somesh Jha, and Thomas Ristenpart. "Model Inversion Attacks that Exploit Confidence Information and Basic Countermeasures." Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. ACM, 2015.
接続サイト神田オフィス
    
閉じる

詳細

閉じる
開催日2016年5月23日(月曜日)
開催場所VBL棟 301B
開催時間14時30分-15時30分 
発表者竹内聖悟  
発表者の紹介東京大学大学院新領域創成科学研究科 特任研究員
タイトルBDD/ZDD を用いた近似計算について 
発表の概要二分決定グラフ (BDD) とゼロサプレス型二分決定グラフ (ZDD) はそれぞれブール関数と集合族を圧縮索引化して表すデータ構造である。これを利用した制約付きグラフの列挙索引化アルゴリズムであるフロンティア法など、BDD/ZDD を利用した研究が広く行われている。
大規模な問題やBDD/ZDD サイズが大きくなってしまう問題への対処として, 近似計算が考えられる。本発表では、BDD/ZDD を用いた近似計算の手法としてDecomposition やRelaxation/Restriction, Sampling を紹介し、発表者の取り組み・応用事例などを紹介する。
接続サイト神田ラボ
    
閉じる

詳細

閉じる
開催日2016年5月17日(火曜日)
開催場所VBL棟 301B
開催時間16時30分-17時30分 
発表者Mathias Soeken  
発表者の紹介Swiss Federal Institute of Technology in Lausanne (EPFL)
タイトルAncilla-free reversible logic synthesis using symbolic methods
 
発表の概要Due to the properties of reversibility, reversible circuit synthesis that is optimum in the number of lines is a difficult task. For an irreversible Boolean function it is coNP-hard to find an optimum embedding, i.e., a reversible function with the minimum number of additional lines. Synthesis algorithms exist that obtain from an optimum embedding ancilla-free reversible circuits which have as many circuit lines as variables in the reversible function. However, so far all implementations for such synthesis algorithms require exponential time and space since they operate on the truth table representation of the function. In the talk, alternative implementations of the algorithms based on decision diagrams and Boolean satisfiability are presented that allow to run the algorithm in less space and time for some functions. It is shown that high quality synthesis results for large circuits can be obtained using these implementations.
接続サイト神田ラボ
    
閉じる

詳細

閉じる
開催日2016年2月22日(月曜日)
開催場所北大工学系C302
開催時間15時30分-17時00分 
発表者岡本 吉央  
発表者の紹介電気通信大学 情報・通信工学専攻 情報数理工学コース 准教授
タイトルネットワーク型交渉ゲームの安定化アルゴリズム 
発表の概要ネットワーク型環境における交渉問題をゲーム理論的に研究する.そのような状況で安定解が存在すると常に言えるわけではないため,ネットワークに修正を加えて,安定解が存在するようにしたい.そのような修正は最小限に留めたいので,考える問題はグラフ上の組合せ最適化問題となる.過去の研究において,辺削除については,問題が NP 困難になることが示されていた.本研究では,その他の可能な変更,つまり,辺追加,点削除,点追加に関して,問題が多項式時間で解けることを証明する.また,重み付きバージョンにおいて,辺追加と点削除がともにNP 困難となることを証明する.伊藤健洋氏 (東北大),垣村尚徳氏 (東大),神山直之氏 (九大),小林佑輔氏 (筑波大) との共同研究に基づく.
    
閉じる

詳細

閉じる
開催日2016年2月16日(火曜日)
開催場所北大工学部C302 ERATOセミナ室
開催時間15時30分-17時00分 
発表者森永聡、中村祐一  
発表者の紹介日本電気株式会社
タイトル「企業における情報科学技術の基礎研究と応用」
‐機械学習、ハードウェアプラットフォームの例で‐ 
発表の概要企業における情報科学技術の基礎研究と応用について、機械学習とハードウェアプ
ラットフォームの二つの例で紹介する。
機械学習: 機械学習技術を活用して様々な問題を解決しようという試みが盛んに行
われているが、社会的に重要な用途で大規模に実用しようとする場合は、「高精度」
「ホワイトボックス性」「低コスト」の三つを同時に満足する必要ある。特に今回
は、大規模な予測システムを実用化するために開発した「異種混合学習技術」と、幾
つかの応用例を紹介する。
ハードウェアプラットフォーム: 半導体の進化により、この10年で計算機の速度は
約100倍高速化した。その結果、たとえば、ディープラーニングで利用される多層
ニューラルネットワークにおいて、10年前は2層が限界であったのがものが、20層近
いものが利用可能となっている。一方で、ムーアの法則の破たんにより、今後、これ
以上の計算機の速度は単純には進化しないと言われている。そこで提案されているの
が、各種アクセラレータを駆使したヘテロコンピューティングである。本講演では、
ヘテロコンピューティングの概念と企業における適用事例について解説を行う。
    
閉じる

詳細

閉じる
開催日2016年1月28日(木曜日)
開催場所北大工学部C302 ERATOセミナ室
開催時間15時30分-17時00分 
発表者鷲尾 隆  
発表者の紹介大阪大学 産業科学研究所
タイトル機械学習による先端センシングデバイスの実現 
発表の概要ナノセンサ、量子計測など先端デバイスの開発分野では、微細・微量な
対象を計測するためのデバイスが次々と開発されつつある。しかし、計
測対象が微小であるために熱雑音や量子揺らぎの影響を受ける。その
ため、実用的計測のためには、不確定な情報から高精度に対象状態を
推定する統計処理や機械学習の適用が必須である。本セミナーでは、
既存センサの組み合わせによる情報センシングシステムの実現に留ま
るのではなく、新たな先端センシングデバイスを実現する技術開発へ向
けた取り組みを紹介する。
    
閉じる

詳細

閉じる
開催日2016年1月19日(火曜日)
開催場所北大工学部C302 ERATOセミナ室
開催時間15時30分-17時00分 
発表者Hei Chan  
発表者の紹介
タイトルIdentifying Causal Effects in Linear SEMs
 
発表の概要In this talk, we discuss the problem of identifying causal effects in linear Structural Equation Models (SEMs). Given the causal diagram of the SEM, which is a directed acyclic graph (with bi-directed edges to represent confounders), we want to find the solution of a causal effect from the observed covariances. The two methods for solving this problem are algebraic methods, which attempts to solve the set of simultaneous equations based on Wright's method of path analysis, and graphical methods, which tests for certain conditions in the causal diagram based on Pearl's d-separation test. To unify the two sets of methods, we introduce the Instrumental Variable Function, which we show to correspond to both algebraic and graphical methods, and is useful in helping us to solve this problem in a variety of graphs.
    
閉じる

詳細

閉じる
開催日2015年12月25日(金曜日)
開催場所
開催時間15時30分-17時00分 
発表者白井康之  
発表者の紹介大東文化大学
タイトルビッグデータ分析とプロモーション戦略・戦術展開への応用 
発表の概要前年度データ解析コンペティションで実施した良品計画の分析
について,MUJIらしさに着目した解析手法ならびにこれらを応用した
分析結果を紹介する.また,本手法を適用したほかのアプリケーション,
また,共進化を応用した今後の展開の方向性について議論する.
    
閉じる

詳細

閉じる
開催日2015年12月7日(月曜日)
開催場所北大工学部C302 ERATOセミナ室
開催時間15時30分-17時00分 
発表者幸若完壮  
発表者の紹介北海道大学
タイトルソーシャルネットワークにおけるコアコミュニティ発見に関する研究 
発表の概要本発表では高密度な部分グラフ(コアコミュニティ)の新しいモデルについて発表する.
提案するモデルは従来では発見が難しかったコア/ペリフェリ構造を発見することができ, グラフ分割法の最適解を与える.
提案モデルをソーシャルネットワーク解析に用い有効性を検証する.
またその他の応用について最近の成果を発表する.
    
閉じる

詳細

閉じる
開催日2015年12月3日(木曜日)
開催場所北大工学部C302 ERATOセミナ室
開催時間10時30分-12時00分 
発表者繁富(栗林)香織  
発表者の紹介北海道大学大学院情報化学研究科 学術研究員
タイトル細胞折紙技術 — 細胞が折り紙を折る? 最適な折り図はあるか? — 
発表の概要私たちのからだは60兆個ほどの細胞でできています。その細胞を使い折り紙を折り、立体構造を作製するというのが、今回紹介する「細胞折紙」です。本講演では、「細胞折紙」技術のことを知っていただき、私たちが親しんでいる折り紙の技術が医療分野、特に再生医療分野に応用できることをぜひ知っていただけたらと思います。

これまでの細胞の立体構造の形成は、主に立体的な足場に細胞を撒くことで組織形成がなされてきました。しかしこの方法では、高密度の組織や,異種細胞が空間的に制御して配置することは難しいことでした。そこで、微細加工技術を利用して、細胞の足場となる微小プレートなどのマイクロ構造体を作製し、細胞を培養後にこれらプレートを折り畳むことで3次元構造を構築する方法を確立しました。折り畳む駆動力は、細胞自身の牽引力です。さまざまな形の細胞の3次元立体構造は、2次元平面の展開図を工夫することで、簡単に作製することができます。同じ立体形状でも異なる展開図がある場合では、細胞は自分の好みがあるか? 最適な折り図を求めることにより、より効率よく細胞の立体構造を作製できる技術に発展させたいと考えています
    
閉じる

詳細

閉じる
開催日2015年11月30日(月曜日)
開催場所北大工学部C302 ERATOセミナ室
開催時間15時30分-17時00分 
発表者中島祐人  
発表者の紹介九州大学
タイトルLyndon 文字列の世界と連定理 
発表の概要 文字列中の極大な周期的部分区間がその最小周期の2倍以上の長さを持つとき,その区間を連とよぶ.文字列に含まれる連の構造は文字列中の任意の連続した部分文字列の繰り返しを捉える重要な文字列の特徴である.長さ n の任意の文字列中に含まれる連の最大数 ρ(n) について,1999年に Kolpakov と Kucherov によって ρ(n) = O(n) であるという驚くべき性質が示されたと同時に ρ(n) < n であるという予想がなされ,連予想として知られることとなった.それ以来多くの研究者たちが,周期性補題を用いた解析により連予想の証明を試みたが解決には至らなかった.

 発表者らは予想から15年が経った2014年にこれまでのアプローチとは全く異なる方法で連予想を解決した.本研究でのアプローチは, Lyndon 文字列とよばれる文字列の辞書式順序に基づいた性質の利用である,連予想の解決には一見関係なさそうに思われる辞書式順序の性質を捉えた Lyndon 文字列を利用することで,連予想の解決だけではなく,これまでの上界の証明に比べ非常に簡潔な証明を可能にしている.本発表では,連定理の証明と15年来の問題を解決に導いた Lyndon 文字列の世界を紹介したいと思う.
    
閉じる

詳細

閉じる
開催日2015年10月23日(金曜日)
開催場所北大工学部C302 ERATOセミナ室
開催時間10時30分-12時00分 
発表者Endre Boros  
発表者の紹介Rutgers Univ.
タイトルGenerating Bodies, Simplices, and Vertices of Polyhedrao 
発表の概要Monotone generation problems are pervasive and are the underlying reason for the efficiency or inefficiency of many of the “large data” related tasks. Many of these problems have natural geometric representations, and lead to interesting and sometimes surprising connections. In this talk, we survey the complexities of generation problems and related geometric questions: given a finite set of points in an Euclidean space, what are the minimal subsets that contain a given point in their convex hull (simplices), in the interior of their convex hull (bodies), or the maximal counterparts of these. Analogously, given a set of linear inequalities, what are the minimal infeasible subsystems, or what are the maximal feasible subsystems? Both of these types of problems have close relations to the problem of generating the vertices of polyhedra represented as finite systems of linear inequalities, as well as to some problems on graphs and directed graphs. In this talk we survey these results and problems, their connections, and recall some open problems. (Based on joint research with K. Borys, K. Elbassioni, V. Gurvich and L. Khachiyan.)
    
閉じる

詳細

閉じる
開催日2015年10月23日(金曜日)
開催場所 北大工学部C302 ERATOセミナ室
開催時間15時30分-17時00分 
発表者津田宏治  
発表者の紹介東京大学大学院新領域創成科学研究科
タイトルガウシアンプロセスとベイズ最適化 
発表の概要本講義では、ベイズ推論の一手法であるガウシアンプロセスを紹介し、
それを用いた実験計画手法であるベイズ最適化を解説する。
応用例としては、材料科学データと、創薬関連データを取り扱う。
    
閉じる

詳細

閉じる
開催日2015年10月20日(火曜日)
開催場所北大工学部C302 ERATOセミナ室
開催時間15時30分-17時00分 
発表者林克彦  
発表者の紹介日本電信電話(株) NTT コミュニケーション科学基礎研究所
タイトル木オートマトン・トランスデューサによる自然言語処理 
発表の概要近年、自然言語処理分野では統計処理と木構造を扱う形式言語モデルの融合が進み、
機械翻訳や文短縮などのタスクに大きな進展をもたらした。特に、木構造を扱う形式
言語モデルとして木オートマトン・トランスデューサがその中心的な役割を果たしてきた。
この発表では正規木言語と呼ばれる木の集合を表すクラスに対応する正規木文法、
木オートマトン、木トランスデューサに関する定式化、及び、その主要な演算について
簡単に紹介し、機械翻訳をはじめとした自然言語処理タスクへの応用事例をいくつか
紹介する。
---
(時間があるようでしたら、最近取り組んでいる有限トランスデューサの研究に
ついても少し話をさせていただけたらと思っております。)
    
閉じる

詳細

閉じる
開催日2015年9月29日(火曜日)
開催場所北大工学部C302 ERATOセミナ室
開催時間15時30分-17時00分 
発表者木村 圭吾  
発表者の紹介
タイトル高速テンソル分解法 -高速テンソル分解,オンラインテンソル分解- 
発表の概要テンソル分解は,多次元データに対する圧縮や,可視化,特徴抽出などに扱われる手法であり,近年,推薦やウェブマイニング,時系列解析など様々な 分野で,研究されている手法である.
本発表では,いくつかの高速なテンソル分解法とオンラインテンソル分解法について,応用事例とともに紹介する.
なお、今回の内容(の一部)は、今年11月に開催される国際会議 IEEE ICDM2015
に採択され、発表する予定である。
    
閉じる

詳細

閉じる
開催日2015年9月3日(木曜日)
開催場所北大工学部C302 ERATOセミナ室
開催時間15時00分-16時00分 
発表者難波 博之  
発表者の紹介東京大学大学院 情報理工学系研究科 M2
タイトルパーマネントを用いた最短点素パスの計算 
発表の概要無向グラフとターミナルの集合Tが与えられたときに,始点,終点がTに属する|T|/2本の点素パスでパスの長さの和が最小であるものを求める問題を考える。ただし,特定のタイプの点素パスは受理しないという制約をつける。
問題の解法には行列のパーマネント計算を応用する。パーマネントの計算は一般には#P-hardであるが,mod 2^kでなら多項式時間で計算できることを利用する。
開催時間16時00分-17時00分 
発表者丸茂直貴  
発表者の紹介東京大学大学院 情報理工学系研究科 M2
タイトル離散DC計画問題に対する連続緩和 
発表の概要2つの凸拡張可能な離散関数の差を最小化する「離散DC計画問題」に対し,適切な連続緩和を考えることで整数性ギャップを回避できることを示す.また,それを用いたアルゴリズムを示し,数値実験で実用性を確認する.
開催時間17時00分-18時00分 
発表者坂上晋作  
発表者の紹介東京大学大学院 情報理工学系研究科 M2
タイトル2本の2次制約付き非凸2次計画問題に対する多項式時間アルゴリズム 
発表の概要2本の2次制約付き非凸2次計画問題(2QCQP)は最適化問題の一種であり,非線形計画問題に対するアルゴリズム(Celis-Dennis-Tapia法)などに利用される.2QCQPの解法としては,半正定値計画問題への緩和による解法などが研究されてきたが,一般に大域的最適解を求められる解法は確立されていなかった.そこで本研究では,2QCQPの大域的最適解を求める多項式時間アルゴリズムを提案する.提案手法は,岩田,中務,武田が示した2QCQPの特殊ケースに対する解法の一般化であり,大域的最適解の候補となる点(Karush-Kuhn-Tuker点)を,固有値計算を利用して列挙するという方針を用いる.
    
閉じる

詳細

閉じる
開催日2015年9月2日(水曜日)
開催場所北大工学部C302 ERATOセミナ室
開催時間15時00分-16時30分 
発表者伝住周平  
発表者の紹介東京大学大学院 情報理工学系研究科
タイトルZDDの簡潔表現に関する進展と最近の話題について
 
発表の概要ゼロサプレス型二分決定グラフ(ZDD)は組合せ集合を表現するデータ構造である.
ZDDは組合せ集合同士の演算もサポートしているが,大きなメモリ量を必要とするため簡潔データ構造を用いたDenseZDDが提案された.
ただし,DenseZDDはコンパクトではあるものの動的な演算による更新が難しいため,従来のZDDと併用するHybrid DenseZDDも同時に提案されていた.
しかし,そのHybrid手法は実装はされておらず,またZDDとDenseZDDが混在する状況下でのDenseZDDへの効率よい変換方法はわかっていなかった.
そこで本発表では,Hybrid DenseZDDに対する圧縮アルゴリズムとその計算量及び実験結果を解説する.
また,その他にも最近の話題について紹介する.
開催時間16時30分-17時30分 
発表者岩政勇仁  
発表者の紹介東京大学大学院 情報理工学系研究科 M2
タイトルk-劣モジュラ緩和について 
発表の概要k-劣モジュラ関数は,NP困難な問題の緩和問題からよく生じ,近似アルゴリズムやFPTアルゴリズムの設計に対して重要な役割を担っている.本発表では,与えられた関数がk-劣モジュラ緩和を持つ必要十分条件とその構成アルゴリズムを説明する.
    
閉じる

詳細

閉じる
開催日2015年8月31日(月曜日)
開催場所北大工学部C302 ERATOセミナ室
開催時間15時30分-17時00分 
発表者石井 利昌  
発表者の紹介北海道大学大学院経済学研究科
タイトル連結度要求を持つネットワーク構成問題とその一般化について 
発表の概要グラフ理論における連結度の概念は, 種々のネットワークの制御・設計におい
て,耐故障性に関する基本的な評価尺度として用いられる. 本セミナーでは,
連結度に関するネットワーク最適化問題の基礎をなす,連結度増大問題とその
関連問題を中心に歴史や最近の話題について紹介する.また,これらの問題に
対する劣モジュラ関数などを用いた一般化の研究についても紹介する.
    
閉じる

詳細

閉じる
開催日2015年8月19日(水曜日)
開催場所北大工学部C302 ERATOセミナ室
開催時間15時30分-17時00分 
発表者川原純  
発表者の紹介奈良先端科学技術大学院大学 情報科学研究科
タイトル複数終端ZDDを用いた連結成分重み比順の連結成分分割列挙 
発表の概要頂点重み付きグラフと定数kが与えられたとき、連結成分の重みの最大値と最小値の比
が最小となるように、グラフをk個の連結成分に分割する問題を考える。本講演では、
フロンティア法を用いて本問題の解集合をZDDとして表し、さらに、サブセッティング
法を用いて、指定した比より小さな解のみを抽出する手法について述べる。複数終端
ZDDを用いて、指定した比の昇順に解を出力する手法についても述べる。
    
閉じる

詳細

閉じる
開催日2015年7月10日(金曜日)
開催場所北大工学部C302 EATOセミナ室
開催時間15時30分-17時00分 
発表者澤田 宏  
発表者の紹介NTT サービスエボリューション研究所
タイトル多次元複合データ分析技術 
発表の概要多くの属性を持つ多次元データを分析し,データに内在する潜在構造(クラスタ)を抽出する技術について述べる.
もっともシンプルな2属性の関係は行列で表現され,特に非負値データを扱う場合は非負値行列因子分解(NMF: Nonnegative Matrix Factorization)として幅広く用いられている.
我々はNMFおよびそのテンソル拡張であるNTF: Nonnegative Tensor Factorizationをベースにしてより多い4属性以上を持つ多次元データを効率良く分析する技術を提案している.
本講演では,もっともシンプルなNMFの概要と応用例から始めて,属性の数を増やしていく際に発生する問題点を解決するアプローチについて述べる.
    
閉じる

詳細

閉じる
開催日2015年7月7日(火曜日)
開催場所北大工学部C302 ERATOセミナ室
開催時間15時30分-17時00分 
発表者伊藤公人  
発表者の紹介人獣共通感染症リサーチセンター教授
タイトルCombining Population Genetics of Pathogens and
Epidemiology of Infectious Diseases
 
発表の概要Through efforts combining mathematics, informatics, epidemiology, and biology, we are developing computational methods for the prediction and prevention of zoonotic outbreaks and epidemics. I this presentation, I will talk about following three topics:

1. Detecting changes in viral population size by population genetics

Early detection of ongoing outbreaks of influenza in non-natural host species is critical to control both avian and human influenza. Here, we propose the use of Tajima’s D as a tool to detect changes in viral population size. By analyzing 6,782 nucleotide sequences from 21 published research papers, we show that the mean values of Tajima’s D are different depending on the hosts and segments. The Tajima’s D values of internal influenza virus genes isolated from wild mallard samples are close to zero, meaning that the population of influenza A virus is stable. However, the Tajima’s D values from chicken and human samples are negative, which means the viral population is increasing. We anticipate this method can be applied to other pathogens to detect hidden outbreaks.

2. A large-scale analysis of interspecies transmission of zoonotic pathogens

We are developing a computational method that detects the transmission of pathogens between different host species. A total of 33,587 nucleotide sequences of the hemagglutinin and neuraminidase of avian and swine influenza viruses were downloaded from the internet. To clarify the interspecies transmission of influenza viruses between pigs and birds, we employed the reciprocal best BLAST hits algorithm. Those pairs sharing genes of 100% identity were regarded as the evidence of interspecies transmissions between avian and swine viruses. The method detected one hundred five possible interspecies transmissions between birds and pigs. Twelve results of them are consistent with the results from scientific papers that were published previously, suggesting that our method can correctly detect interspecies transmission. We anticipate that this method can be applied to detect the other zoonotic pathogens.

3. Predicting antigenic changes of influenza viruses through data assimilation

Human influenza A viruses undergo antigenic changes with gradual accumulation of amino acid substitutions on the hemagglutinin molecule. Antigenic mismatch between vaccine and epidemic strains often requires the replacement of influenza vaccine strains. To establish a practical method enabling us to predict the future direction of the viral evolution, we are developing a new prediction method based on a computational technique called data assimilation. Our aim here is to integrate actual observations of viral gene mutation into computer simulations, and infer current herd immunity and next mutations. To establish a practical method enabling us to predict amino acid substitutions on the hemagglutinin, we have constructed a mathematical model of viral population, infection, and host immunity. Based on the developed model, actual viral evolution observed in past 45 years was analyzed by particle filters. The timing when the dominant epidemic strains were replaced by other strains—as well as the future direction of the viral evolution—could be predicted by the method.
    
閉じる

詳細

閉じる
開催日2015年5月15日(金曜日)
開催場所北大工学部C302 ERATOセミナ室
開催時間15時30分-17時00分 
発表者David Avis  
発表者の紹介京都大学大学院情報学研究科通信情報システム専攻
タイトルPolynomial size matching polytopes 
発表の概要I will begin by giving an introduction to extension complexity including
the exponential lower bound results of Fiorini et. al for the travelling
salesman problem and of Rothvoss for the matching problem. This latter
result proves the striking result that Edmonds' matching polytope is not
the projection of any polynomially sized polytope.

I will then describe a perfect matching polytope that is different from
Edmonds' polytope and explain the notion of a weak extended
formulation(WEF). Then I will show that this new polytope has a WEF of
polynomial size. This implies that perfect matchings in graphs can be
solved in polynomial time by linear programming over the WEF. We have
built a compiler that inputs an algorithm in pseudocode and outputs a
corresponding WEF.
This is joint work with David Bremner, Hans Tiwary and Osamu Watanabe.
    
閉じる

詳細

閉じる
開催日2015年5月12日(火曜日)
開催場所
開催時間15時30分-17時00分 
発表者井上武  
発表者の紹介NTT未来ねっと研究所
タイトルホスト名グラフと暗号化通信の推定 
発表の概要インターネット上で提供されるサービスの大多数はHTTPによるWeb通信である.そして多くのWeb通信がHTTPSによって暗号化されるようになった.例えばYouTubeのビデオも暗号化された通信路で配信されている.HTTPSの普及に伴いトラヒックの計測・分析が難しくなる問題が生じる.すなわち暗号化により通信の宛先サーバのホスト名が不明となるため,ネットワークサービス提供者は自網の回線がユーザにどのように利用されているかを把握することが困難となった.この問題を解決するためにDNSクエリ・応答情報を用いてHTTPS通信のホスト名を推定するフレームワークであるSFMap(Service-Flowmap)を提案する.SFMapの主要なアイディアはCNAMEを経由したIPアドレスと複数ドメイン名の関係をグラフとして保持し,そのグラフを元に所与のサーバIPアドレス,クライアントIPアドレス情報から尤もらしいサーバのホスト名を推定することにある.2箇所の計測地点で収集した実トラヒックデータを用い,提案手法がこれまでの先行研究で提案された手法と比較してより高い精度を達成することを示す.
    
閉じる

詳細

閉じる
開催日2015年4月27日(月曜日)
開催場所北大工学部C302 ERATOセミナ室
開催時間15時30分-17時30分 
発表者新屋良磨  
発表者の紹介東京工業大学 首藤研究室
タイトル正規表現入門~星の高さを求めて~ 
発表の概要正規表現とはパターンマッチングのための記法であり,文字列検索の便利な道具として広く親しまれています.
この講演会では,正規表現の基礎から始め,「星の高さ」という性質に注目して正規表現の裏側に潜む数理構造に迫っていきます.
    
閉じる

詳細

閉じる
開催日2015年2月6日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時00分-17時00分 
発表者Matias Korman  
発表者の紹介Assistant Professor at NII (Network Algorithm Group of the ERATO Kawarabayashi Large Graph Project)
タイトルExtremal distances in Polygonal Domains 
発表の概要The geodesic distance between two points p,q in a polygonal domain P is defined as the path of shortest length connecting the two points that contained in P. This distance is a proper metric, and as such the usual concepts of diameter (i.e., points of P that are furthest away) and center (i.e., point whose distance to its furthest away point is minimized) naturally extend. Although the definition of these traits is very simple, finding efficient algorithms that can compute these values has proven to be difficult. In this talk, we discuss the difficulties that lie in designing algorithms for computing the center and diameter for both simple domains and in the presence of holes.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2015年1月30日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時00分-16時30分 
発表者David Avis  
発表者の紹介Department of Communications and Computer Engineering, School of Informatics, Kyoto University
タイトルA portable parallel implementation of the lrs vertex enumeration code 
発表の概要I will begin by describing the vertex enumeration problem and a method to solve it using reverse search with its implementation lrs. Then I will describe a parallel implementation of lrs that automatically exploits available hardware on multi-core computers and runs on a wide range of platforms.
The implementation makes use of a C++ wrapper that essentially uses the existing lrs code with only minor modifications. It makes use of the restart feature of reverse search that allows for independent subtree search and the fact that no communication is required between these searches. As such it can be readily adapted for use in other reverse search enumeration codes.
Joint work with Gary Roumanis (Microsoft)
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2015年1月16日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間16時00分-17時30分 
発表者中原 啓貴  
発表者の紹介愛媛大学情報工学科
タイトル電波望遠鏡におけるデジタル分光器と決定グラフを用いた設計法について 
発表の概要電波望遠鏡は天体から放射される電波を受信し,分光器を用いてスペクトル解析を行う装置であり,広帯域かつ高分解能なFFTを行っている.しかし,デジタル分光器を書換え可能なLSIであるFPGA(Filed Programmable Gate Array)で実現した場合,FFT回路の面積が大きく,特に乗算器が大量のLUT (Look-Up Table)を消費するため,LUT数の削減が求められている.一般的に,nビットの乗算器を考えるとき,ゲート数はO(2^n)である.従って,nを分解するとLUT数を削減できる.本セミナーでは,電波望遠鏡におけるデジタル分光器を紹介し,剰余数系(RNS: Residue Number System)に基づく決定グラフを用いたnを分解する回路設計法について述べる.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2014年12月25日(木曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時00分 
発表者阿部正佳  
発表者の紹介株式会社NTTデータ数理システム 知識工学部
タイトルリバースエンジニアリングにおける BDD/ADD の二つの適用事例 
発表の概要当該プロジェクトは COBOL、PL/I といったプログラム遺産を静的解析することで、プログラムの理解を助けるさまざまな情報を提供するのが目的である。弊社では静的解析系の出力である条件式(複数論理変数から有限列挙値への関数)を、人間にとって分かりやすい表現に変換する部分を担当している。第一の事例は条件式の Spine-ADD 表現である。これは ADD 表現をベースにある基準で定義された簡単な部分論理式(Spine)を 1 ノードに潰すことを繰り返して得られる表現である。第二の事例は条件式を通常のプログラミング言語と同様の if-then-else 形式で表し、さらに各論理式を SOP に限定するという制約下でのリテラル数最小な表現をBDD 及び組み合わせ最適化技術により求めるものである。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2014年12月19日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間14時00分-15時20分 
発表者牧野和久  
発表者の紹介京都大学数理解析研究所
タイトル単調論理関数の双対化問題について 
発表の概要単調論理関数の双対化問題とは,与えられた単調な論理和形から等価な論理積形を求める問題である.この双対化問題は,数理計画,人工知能,データベース,分散システム,学習理論など様々な分野に現れる数多くの重要かつ実用的な問題と(多項式時間還元の意味で)等価であることが知られている.現在までのところ,Fredman-Khachiyan による準多項式時間アルゴリズムが知られているが,20年以上もの間,多項式時間アルゴリズムが存在するかどうか未解決のままである.今回は,この双対化問題の歴史や最近の話題について紹介する.
接続サイト東京,大阪,九州(予定),京都大学(SV1)
開催時間15時20分-16時30分 
発表者宇野毅明  
発表者の紹介国立情報学研究所情報学プリンシプル研究系
タイトルコーヒーよりドーナッツ 
発表の概要良好なコミュニケーションによる活発な研究、創造的なコミュニティの育成、コミュニケーションを用いた研究や組織活動の進展などについて、宇野の体験談と総論をお話しします。意外や意外、いいコミュニケーションをするには意外なところにちょっとしたコツが必要だったりするようです。
接続サイト東京,大阪,九州(予定),京都大学(SV1)
    
閉じる

詳細

閉じる
開催日2014年12月5日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時00分 
発表者竹内聖悟,倉井龍太郎  
発表者の紹介JST ERATO
タイトルSDD (Sentential Decision Diagram) の概要と SDD Package の利用方法について 
発表の概要UCLA の Darwiche 教授らが 2011に IJCAI で提唱した,命題論理式に対する新しい表現形式 SDD (Sentential Decision Diagram) の概要,ならびに SDD Package ( http://reasoning.cs.ucla.edu/sdd/ )の利用方法について解説し,今後の方向性に関するディスカッションを行う.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2014年11月14日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時00分 
発表者白井康之  
発表者の紹介JST ERATO
タイトル購買選好度減衰曲線を用いた選択多様性解析とその応用 (北海道大学集中講義「大規模離散計算科学特論」) 
発表の概要平成25年度データ解析コンペティションで提供された購買履歴データを用いた分析結果とその後の展開について報告する.我々は,ユーザの購買選好度の変化を減衰曲線として表し,消費者の時系列的購買状況をモデル化するとともに,商品ロック状態に基づくクラス分類を行った.ロック状態の分布に基づき,商品や購買行動のパタン分類を行い,将来のユーザの行動予測を行うことができる.また,商品分類を消費者の視点からクラウドソーシングにより効果的に行う方法を検討しており,これらの結果を用いた分析についても報告する.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2014年10月30日(木曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時00分 
発表者鷲尾 隆  
発表者の紹介大阪大学 / JST ERATO
タイトルMass based estimation of data distribution and dissimilarity (北海道大学集中講義「大規模離散計算科学特論」) 
発表の概要データ空間上のランダム領域標本のアンサンブルによって、データ分布密度やデータの非類似度を評価する手法が発展して来ている。これらの手法は、標準的なノンパラメトリック推定に比べて、推定分散を小さくできる、データ分布の性質を反映した非類似度を評価できるなど、種々のメリットを有する。ここでは、これらの原理と機械学習タスクに適用した際のメリットについて述べる。
    
閉じる

詳細

閉じる
開催日2014年10月24日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時00分 
発表者津田宏治  
発表者の紹介東京大学 / JST ERATO
タイトルマテリアルズ・インフォマティクスにおけるベイズ最適化 (北海道大学集中講義「大規模離散計算科学特論」) 
発表の概要オバマ政権によるマテリアルゲノム計画の発足以降、機械学習などのデータサイエンス技術を、材料・物性科学に持ち込み、新たな材料設計を効率化する試みが世界的に活発になっている。講演者は、機械学習・データマイニングの専門家であり、材料科学に関する知識は乏しいが、2013年より、科研費新学術領域「ナノ構造情報のフロンティア開拓ー材料科学の新展開」に参画し、材料科学研究者との共同研究をスタートした。本講演では、マテリアルズ・インフォマティクスをめぐる内外の状況を述べた後、京都大学と共同で行った、二元材料の融点に関する研究に関して述べる。この研究では、地球科学において鉱山の発見などの目的で用いられてきた、クリギングというベイズ最適化法を用いて、最高融点材料の探索が大幅に効率化できることを示した(Seko et al., Physical Review B, 2014)。このような手法の有効性・将来性について、参加者の方々と議論を深めたいと考えている。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2014年10月3日(金曜日)
開催場所関西サテライトラボ
開催時間15時00分-17時00分 
発表者田中功  
発表者の紹介京都大学工学研究科・材料工学専攻 教授
タイトルマテリアルズ・インフォマティクスの現状と将来展望 
発表の概要実験,理論と鼎立する第3の科学として「計算科学」が材料研究に重要な位置を占めるようになったが,近年それら 3 本の柱を束ねる第4の科学として「データ科学」の重要性が認識されつつある.実験,理論,計算で得られた物質・材料に関する知識とデータを駆使して,統計学習により物質・材料の機能を制御する法則を探り「設計」を可能とする系統的アプローチを構築すること,それを通して具体的に新物質,新材料の「発見」を加速し,究極として材料特性を支配する法則を「発見」することを目指すものである.
この Materials Inforrnatics には様々なアプローチがあり,その一部だけを取り出すと,従来型のデータベース活用研究あるいは実験計画法と矮小して見られがちである.しかし,数学,物理学,化学,情報科学と材料科学が密接に連携することで,高度な実験・計算で獲得されるビッグデータを巧く処理し,それに基づいてデータ駆動型で新材料の発見や法則の発見に導く流れは,従来にない新しいものである. うまく成功すれば,材料研究に大きなインパクトを与えるであろう.わが国は, MaterialsInforrnatics 分野の初動において,米国や欧州に少し遅れを取っている懸念があるが,(1) 完験的な材料研究において世界を主導してきたこと,(2)学際的な連携に大きな盛り上がりが見られること,(3)放射光など大型施設や電子顕微鏡のような高度実験設備が整備されていること,(4)MatNaviを代表とするデータベースを持っていること,などを考えると,これから充分に世界の主導権を取った研究を行うことが可能と期待している. Materials Inforrnatics の研究テーマを例示すると以下のようになる.自分たちの研究は主にIとIIに関するものであるが,それ以外にも進捗を諸外国での状況を交えて,包括的にお話ししたい.

I. 第一原理計算データベースに基づいた新しい材料探索
II. 計算および実験データの機械学習による高機能データベースの構築とデータ駆動型発見
III. 材料のマルチスケールシミュレーションと最適化設計..
IV. コンビナトリアル実験と計算の連携による材料のハイスループットスクリーニング..
接続サイト札幌,東京
    
閉じる

詳細

閉じる
開催日2014年9月3日(水曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時00分-16時30分 
発表者鈴木大慈  
発表者の紹介東京工業大学大学院情報理工学研究科数理・計算科学専攻准教授
タイトル確率的交互方向乗数法 
発表の概要本講演では交互方向乗数法とよばれる最適化技法の確率的最適化手法を提案する.正則化項が複雑な構造をもつ構造的正則化学習問題を解く際に,交互方向乗数法は有用な手法である.交互方向乗数法は線形制約付き凸最適化問題を解くための汎用的な手法である.その汎用性より広く様々な問題に応用され,理論研究も近年になり急速に発展している.本講演では交互方向乗数法を変形したオンライン確率的最適化技法と,バッチデータに対する確率的双対座標降下法型の交互方向乗数法を提案する.どちらの方法も広い応用範囲を持ち,実装が容易である.また,提案手法の収束レートも示す.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2014年8月25日(月曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時30分 
発表者Michael Lampis  
発表者の紹介Research Institute for Mathematical Sciences, Kyoto University
タイトルParameterized Approximation Schemes using Graph Widths 
発表の概要A number of natural graph problems are known to be W-hard to solve exactly when parameterized by standard widths (treewidth or clique-width). At the same time, such problems are typically hard to approximate in polynomial time. In this talk we will present a natural randomized rounding technique that extends well-known ideas and can be used to obtain FPT approximation schemes for several such problems, evading both polynomial-time inapproximability and parameterized intractability bounds.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2014年8月19日(火曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間16時00分-17時00分 
発表者笹木一義  
発表者の紹介日本科学未来館
タイトル日本科学未来館の展示開発・連携事業 2013~2014 
発表の概要日本科学未来館では、「科学を伝える ~先端科学技術の情報発信と伝達手法の開発」という活動の柱のもとに、常設展、企画展、外部との連携事業などで、単なる展示更新に留まらない新しい試みを行っている。その中で、直近1年(2013年下期~2014年上期)にかけての最新の展示開発、連携事業を紹介する。
事例として、「トイレ」というタブー視されがちなテーマに焦点を当てた企画展「トイレ?行っトイレ!」、常設展に3種導入されたアンドロイド展示、数理モデルに挑んだメディアラボ13期展示「1たす1が2じゃない世界」、ロボット関連の長期にわたる館内での実証実験2種(ASIMO、UNI-CUB)などを取り上げる。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2014年8月5日(火曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間14時00分-15時30分 
発表者比戸将平  
発表者の紹介Preferred Infrastructure
タイトルJubatusから未来の分散インテリジェンスへ 
発表の概要Jubatusは弊社がNTTソフトウェアイノベーションセンタと共同開発し、3年前にOSS公開した分散オンライン機械学習基盤であるが、当初から大規模データの活用において機械学習の重要性が増す現状を見越して開発されていた。一方、最近M2M/IoTに再び注目が集まっているが、クラウドを中心とした現在の中央集権的なアーキテクチャでは解決できない問題の存在が明らかになりつつある。本セミナーではJubatusの基本について紹介したあと、今後出現する高度なアプリケーションと分散インテリジェンスを説明し、そこで鍵となるだろう技術について述べる。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2014年7月15日(火曜日)
開催場所北海道大学情報科学研究科棟 2F A22 講義室
開催時間15時30分-17時30分 
発表者Kitsuchart Pasupa  
発表者の紹介King Mongkut's Institute of Technology Landkrabang
タイトルCan relevance of images be inferred from eye movements? 
発表の概要Searching for images from a large collection is a difficult task for automated algorithms. Many current techniques rely on items which have been manually 'tagged' with descriptors. This situation is not ideal, as it is difficult to formulate the initial query, and navigate the large number of hits returned. In order to present relevant images to the user, many systems rely on an explicit feedback mechanism. A machine learning algorithm can be used to present a new set of relevant images to the user -- thus increasing hit rates. In this work, we use eye movements to assist a user when performing such a task, and ask this basic question: "Is it possible to replace or complement scarce explicit feedback with implicit feedback inferred from various sensors not specifically designed for the task?" In reasonably controlled setups, fairly simple eye movements‘features in conjunction with machine learning techniques are capable of judging the relevance of an image based on eye movements alone, without using any explicit feedback -- therefore potentially assisting the user in a task. We also combines image features together with implicit feedback from users' eye movements, using them to rank images in the database.
接続サイトなし
    
閉じる

詳細

閉じる
開催日2014年7月7日(月曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間13時00分-14時30分 
発表者Leonardo Bartoloni  
発表者の紹介University of Pisa
タイトルTime/space tradeoff on Discrete Optimization using approximated Binary Decision Diagrams 
発表の概要A wide range of discrete optimization problems can be solved using encoding the set of feasible solutions on a binary decision diagrams (BDD), with weights associated to arcs, and then performing a shortest path search on the BDD graph. In the worst case however the size of the BDD can be of exponential order in respect to the number of variables, making this method unsuitable for a lot of practical problems.
In this talk we will show how by merging or discarding nodes during the BDD construction it is possible to generate simpler diagrams which encode a superset or a subset of feasible solutions.
With those diagrams we can solve relaxed and restricted versions of the optimization problem using a limited memory space.
Finally we will show how these approximation can be used as branch elimination heuristics in a branch-and-bound search in order to solve the original optimization problem.
接続サイト東京,大阪,NTT×2
    
閉じる

詳細

閉じる
開催日2014年7月4日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間16時30分-18時00分 
発表者東條 弘  
発表者の紹介NTT 未来ねっと研究所
タイトルODSの取り組みについて 
発表の概要ODSとは音楽や舞台のライブ映像を、高品質で全国の映画館に配信し、映画館を映画用途ではなく、ライブ中継を視聴する形態(ODS:Other Digital Stuff/Online Digtal Source)であり、映画館のデジタル化の進展に伴い、ODSの配信先の数も増加傾向にある。本セミナーでは、ODSに関する動向ならびにNTTの取り組みについて紹介する。最後に4K/8Kに関するNTT研究所の取り組みと今後の課題・方向性について述べる。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2014年5月28日(水曜日)
開催場所ERATO大阪オフィス
開催時間15時30分-17時30分 
発表者瀧澤重志  
発表者の紹介大阪市立大学
タイトル国際会議凱旋報告:ZDDとフロンティア法を用いた建築のフロアプラン列挙手法 
発表の概要ERATO湊プロジェクトの関連研究として,2012年度に京大加藤直樹研で当時M2だった宮田祐次君が修士研究として標記研究を行い,ERATOシンポジウムで何度か報告させていただきました.去る2014年5月14-16日に,建築設計におけるコンピューター利用に関する国際会議 CAADRIA2014が京都工芸繊維大学で開催され,そこに本研究を纏めて論文を投稿し採択されました.会議には298件のアブストラクトが集まり,フルペーパー審査を含む2段階審査の結果,88件の論文が採択されました.最終日に各賞の発表があり,本研究がめでたくBest Paper Awardを受賞いたしました.関係者の方々に感謝いたします.そこで今回は少しお時間をいただいて,会議の様子,本研究の概要,今後の展望などに関して報告と議論をさせていただければと思います.
接続サイト札幌,東京
    
閉じる

詳細

閉じる
開催日2014年5月7日(水曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間16時00分-17時00分 
発表者長津尚英  
発表者の紹介NTTビズリンク株式会社
タイトルNTT R&Dのグローバル活動とNTTビズリンク社のビジネスについて 
発表の概要・NTT R&Dの概要紹介
・NTT R&Dのグローバル活動の紹介(主に欧州における活動を中心として)
・NTTビズリンクのTV会議サービスラインアップの紹介
・NTTビズリンクの新規ビジネス(ODS: Other Digital Stuff事業)の紹介
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2014年4月30日(水曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時30分 
発表者永幡 裕  
発表者の紹介北海道大学大学院生命科学院
タイトルMarkov連鎖が持つ時間階層構造抽出に向けて (階層間をつなぐ理論の構築と、複雑な反応系の解析に向けて)  
発表の概要本講演では、一次反応の化学反応ネットワークと等価なMarkov連鎖がもつ時間階層構造を抽出する手法について考察する。
Markov 連鎖はマスター方程式、反応速度論、統計テスト、統計分布生成、待ち行列理論、PageRank、画像解析、ゲーム理論、金融工学、バイオインフォマティクスとその数学的な扱いやすさと、より一般的なマルコフ過程の線形近似となっていることから汎く用いられている。
近年我々の研究分野では、前田理先生(北大理)が考案された反応経路自動探索手法群(総称してGRRM戦略と呼んでいる)によって、一次反応ネットワークを構成するための基礎データが計算機によって収集可能となり、またCrutchfieldらによって考案された計算力学によりタンパク質一分子の時系列から隠れマルコフモデルを抽出できるようになった。とくに後者では、計測時間幅を変えることによって得られるマルコフ連鎖の頂点数が変わることがわかっており、その数理的性質と解析手法が求められている。
本研究では、GRRM戦略を用いることによって得られた、クライゼン転移反応と関わる一次反応のネットワークから観測時間幅 tで抽出したマルコフ連鎖の t依存性について考察する。特に tを変化させることによって生じる時間階層性について、その数理的性質と発見手法(時間-階層的クラスタリング)について考察する。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2014年4月16日(水曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時30分 
発表者Valia Mitsou  
発表者の紹介Visiting researcher at Kyoto University / The Graduate Center, City University of New York
タイトルComputational complexity of games and puzzles, and, in particular of
the card game SET 
発表の概要In this talk, we will analyze the algorithmic properties of one and two-player games people enjoy playing, such as Sudoku or Chess. Questions asked about puzzles and games in this context are of the following type: can we design efficient computer programs that play optimally given any opponent (for a two-player game), or solve any instance of the puzzle in question?
We will first give an overview of the field describing how to attack this question and what is generally known for games and puzzles in this context. Alongside, we will give some required background.
Then, we will focus on the game of SET, a card game where the objective is to form sets of cards that match in a certain sense using cards from a special deck. We will analyse single- and multi-round variations of this game and establish interesting connections with other classical computational problems. We will prove algorithmic and hardness results inthe classical and the parameterized sense.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2014年4月11日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時30分 
発表者花田 博幸  
発表者の紹介北海道大学大学院情報科学研究科
タイトルq-gram距離基準による類似文字列検索の高速化 
発表の概要q-gram距離とは、二つの文字列の類似性を、含まれているq-gramの個数の差の総和で表すものである。例えば "ababba" と "babbba" の2-gram距離は、二つの文字列に含まれる "ab" の個数が1異なっており、"bb" の個数も1異なっていることから("aa" と "ba" は同数)、1 + 1 = 2と計算される。
q-gram距離の利用方法としては、編集距離の近似関数としての用途や、これをそのまま用いることによる文書やゲノム配列等の文字列データ分類などが考えられている。
q-gram距離は、二つの文字列x, yの間の距離計算そのものは、suffix treeを用いることでO(|x| + |y|)時間で計算できる(|・|は文字列長)。しかしながら類似部分文字列を検索する問題、すなわち「テキスト文字列tの部分文字列で、パターン文字列pとのq-gram距離がしきい値k以下であるものをすべて求める」問題は、従来のアルゴリズムでは最善でも平均・最悪時間計算量ともにO(|t|・log k + |p|)であった。
本研究では、qが十分大きくかつtが無作為に生成されるとしたとき、平均時間計算量をO(|t| + |p|)に改善し、かつ最悪時間計算量が従来と変わらないアルゴリズムを示す。この改善は、従来のアルゴリズムにおいて、大きさO(k)の探索木に対してO(|t|)回の挿入・削除が必要であったことに着目したもので、提案するアルゴリズムではこの挿入・削除が平均O(1)時間で可能になるよう、索引付きの連結リストを用いている。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2014年2月26日(水曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間10時30分-12時00分 
発表者井上 武  
発表者の紹介NTT
タイトルGraphillion update 
発表の概要昨年6月に Graphillion をリリースして以降の出来事について報告します.PyCon APAC での発表と衝撃的な質疑応答,電力配電網の検証手法への応用,漏れ聞こえてくるその他の利用事例などを紹介します.また,より多くの方々の役に立つには今後どうしていくべきかについても,ざっくばらんな議論ができればと思っています.なお,同日に開催される安田さんと中元さんのご講演でも,Graphillion の利用事例が紹介される予定です.
接続サイト東京,大阪,九州(予定)
開催時間13時30分-14時15分 
発表者安田宜仁  
発表者の紹介JST ERATO
タイトル部分木の列挙におけるGraphillionの利用事例 
発表の概要発表者は木の中のすべての部分木をZDDで表現することに取り組んでいる。このZDDの大きさは、適切な変数順序を固定した場合にはきつい見積りを証明により得ることが可能である。しかし、証明が得られていないような変数順序の場合に見積りを立てることは困難である。そこで、ZDDの大きさのあたりをつけるための道具としてGraphillionを手軽な電卓として利用している。本発表では上記の実際の利用例に加え、木のjumbled pattern matchingを解く例についても紹介する。
接続サイト東京,大阪,九州(予定)
開催時間14時15分-15時00分 
発表者中元政一  
発表者の紹介JST ERATO
タイトルEkillionでのGraphillionの利用事例紹介 
発表の概要関西サテライトラボで開発、公開しているEkillion(大都市近郊区間大回り経路探索:http://54.249.81.169:8080/eki)でのGraphillionの利用事例を紹介する。
接続サイト東京,大阪,九州(予定)
開催時間15時30分-17時30分 
発表者安井 雄一郎  
発表者の紹介中央大学 研究開発機構 専任研究員 / JST CREST
タイトル高性能計算機上でのグラフ最適化基盤の開発 
発表の概要近年, グラフアルゴリズムやグラフ解析は様々な分野で盛んに研究されている.本発表は, 計算機の特性を考慮して高性能を達成するための高速化手法や, それらを用いたグラフアルゴリズム実装の性能について説明を行う.我々の研究グループでは, 最新の Graph500 リストと Green Graph500 リストにおいて, それぞれ計算機1台で最高速,最高電力性能を達成している.なお, 本研究で用いた高速化手法は汎用的で, ZDD を用いた数え上げ問題や半正定値問題ソルバに対しても高い効果を確認している.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2014年1月24日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時30分 
発表者岩下洋哲  
発表者の紹介JST ERATO
タイトルプロパティ検証問題におけるBDDの実用化技術 
発表の概要前半では、実用的なBDD処理系の登場によって1990年代に急速に発展した記号モデル検査技術について、その歴史や背景とともに実用化研究の事例を紹介する。一般的な記号モデル検査では、プロパティ記述言語CTLの自然な解釈と一致した逆像計算が主に使われていた。これに対して本研究では、ハードウェアの実設計を検証対象とする場合には像計算に対して逆像計算のコストが大きいケースが多いことに着目し、記号モデル検査の基本演算を逆像計算から像計算に置き換えるForward Model Checking 手法を新しく提案した。さらに、グラフ表現したプロパティを深さ優先で処理することにより、バグ検出までの計算時間を大幅に短縮する検証アルゴリズムを提案した。後半では、フロンティア法をはじめとする現代の技術を広く実用化するための、新しいBDD/ZDD処理系の開発について議論したい。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2014年1月17日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時30分 
発表者戸田貴久  
発表者の紹介JST ERATO
タイトル三分決定グラフを用いた論理関数の双対化について 
発表の概要本発表では論理関数の双対化を扱う。単調な論理関数の双対化は、多くの研究者により取り組まれている研究課題であり、計算量の解析に関する理論研究だけでなく、近年はアルゴリズムの実際的な性能に焦点を当てた実証研究も盛んに行われるようになってきた。このような背景において、筆者は以前の研究において単調な論理関数の双対化を二分決定グラフと呼ばれる圧縮データ構造を用いて計算する方法を与え、この問題に対して圧縮に基づく計算法がとても効果があることを実験的に確認した。単調でない論理関数もまた重要であり、そのような論理関数を扱えることはより広い応用につながるので、本発表では、以前の方法を拡張し、一般の論理関数の双対化を計算する手法を与える。実験的な評価を通して本手法の特性について考察する。
接続サイト東京,大阪,京都大学,山梨大学,神戸大学,NII, 九州(予定)
    
閉じる

詳細

閉じる
開催日2014年1月10日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時30分 
発表者Charles Jordan  
発表者の紹介Graduate School of Information Science and Technology, Hokkaido University
タイトル大規模なExperimental Descriptive Complexityへ向かって 
発表の概要ある特定な性質を満たすプログラムや関数を見つけることは,プログラム合成、機械学習やAIにおいて一般的な課題だが,計算量理論でも同様の課題として,計算問題間の帰着や計算問題を解くための多項式時間プログラムの探索が挙げられる.
計算問題の記述計算量とは計算問題を形式言語で定義する際に必要充分な記述能力であり,計算量理論を形式論理の視点から研究する分野である.ここでは,記述計算量のexperimentalバージョンについて紹介する.
Experimental Descriptive Complexityに関する研究では,計算機を使って計算量理論における諸問題を定量的に理解するとともに,記述計算量のアイディアの他分野(AIやゲーム等)への応用が課題である.本講演では記述計算量の紹介を含め,上記のような応用について発表する.現在,発表者らが行っているスパコンを使用した大規模問題を用いた実験とその応用に関して報告する.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年12月16日(月曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時30分 
発表者Phillippe Samer  
発表者の紹介Laboratory for Algorithms, Graduate School of Information Science and Technology, Hokkaido University
タイトルA branch and cut algorithm for spanning trees under conflict constraints 
発表の概要Let $G(V,E)$ be a finite, undirected graph, and $C \subset E \times E$ a set of conflicting edge pairs. This talk overviews an approach for the exact solution of the NP-hard problem of determining a minimum spanning tree of $G$ including at most one of the edges from each pair in $C$.
In this work, we regard polyhedral representations of conflict-free edge subsets as stable sets in an auxiliary conflict graph $H(E,C)$. We present integer linear programming formulations including four classes of exponentially-many constraints: two of which correspond to classic polyhedral representations of spanning trees in $G$, and two for strengthening the intersection with relaxations of the polytope of stable sets in $H$ (with clique and odd-cycle inequalities).
We introduce and evaluate a preprocessing method and branch and cut algorithms. Encouraging results consistently improve those previously available in the literature. New feasibility and optimality certificates are provided, and stronger dual bounds are already obtained in the initial linear relaxation of the formulations, even for the hardest instances in the standard benchmark.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年12月10日(火曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間13時00分-14時30分 
発表者安田宜仁  
発表者の紹介JST ERATO
タイトル地理情報検索とそのサービス例 
発表の概要地理情報検索の実現例について述べる. 地理情報検索とは, 内容面での要求に加えて, 地理的側面からの要求を考慮するような文書検索技術であり,クエリとしてキーワードと地理範囲を受け付ける.特に, 本発表ではGPSタグ等の明示的な地理マーカーのないような, 自然文で書かれた文書を対象とした地理情報検索について述べる.
自然文中での地理的表現は, 「大阪府大阪市北区芝田1丁目4-14」のような正規の住所での記述さる場合よりも,「札幌」や「大岡山」といった多様な表現と範囲の粒度で記述される場合が多い.このような多様な表現と範囲をどのように考慮して地理情報検索を行うことが可能かについて, 実証実験での実例を題材に述べる.
また, 地理情報検索では「地理範囲」と「キーワード」という2種類のクエリを必要とするためユーザの負担が大きい.2種類の一方のみなら与えられるような漠然とした検索要求を持つユーザに対して,どうやって他方を提案することが可能かについての試みについての述べる.
接続サイト東京,大阪,九州(予定),埼玉大学,東海大学
    
閉じる

詳細

閉じる
開催日2013年12月6日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間16時00分-17時30分 
発表者Nabila Abdessaied  
発表者の紹介Institute of Computer Science, Group of Computer Architecture, University of Bremen, Germany
タイトルUpper bounds for reversible circuits based on Young subgroups 
発表の概要We call a logic function f : {0,1}^n -> {0,1}^n reversible if it is bijective, i.e. there exists a 1-to-1 mapping from the inputs to the outputs.
Synthesis is the problem of finding a sequence of reversible functions g1; g2; : : : ; gk such that f = g1*g2*...*gk where * denote a decomposition and each gi is from a gate set G.
G is called universal if such a sequence exists for all functions. Toffoli gates Tn are a universal gate set. We are interested in determining a tighter upper bounds on the number of Toffoli gates needed for synthesizing a reversible function. Both multiple controlled Toffoli gates and mixed polarity Toffoli gates have been considered for this purpose.
The calculation of the bounds is based on a synthesis approach based on Young subgroups that results in circuits using a more generalized gate library.
Starting from an upper bound for this library we derive new bounds which improve the existing one by around 77%.
接続サイト東京,大阪,岩手大学
    
閉じる

詳細

閉じる
開催日2013年12月3日(火曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間13時00分-14時30分 
発表者数原良彦  
発表者の紹介NTTサービスエボリューション研究所
タイトル検索サービスを支える技術 
発表の概要自社における地理情報検索技術の取り組みの紹介と,検索サービスの基盤となる全文検索エンジンの仕組みの解説を行う.地理情報検索はキーワードによる全文検索と,地理範囲による空間検索の2つの側面を持つ. このため,実用的な地理情報検索サービスを提供するためには,双方の機能を高スループットで実現する検索エンジンが欠かせない.本講演では, 全文検索エンジンの転置インデクスの索引構造に始まる基礎的な話題から,インデクス圧縮,分散インデクス,および地理検索のための空間インデクス等,高スループットな検索エンジンを支える技術を概観する.また,NTT研究所が行った実証実験を事例に,大規模データを扱う上での工夫や苦労話についても触れる.
接続サイト東京,大阪,九州,NII,東海大学
    
閉じる

詳細

閉じる
開催日2013年11月28日(木曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間16時45分-17時45分 
発表者Will Archer Arentz  
発表者の紹介Executive Scientist and Vice Director of Rakuten Institute of Technology
タイトルWhat is Rakuten Institute of Technology (RIT)? 
発表の概要An informal introduction Rakuten Institute of Technology - who and what we are, as well as some of the things we work on. Some examples of research and development within distributed systems, algorithms, web services, financial services and O2O will be given.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年11月8日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間16時00分-18時00分 
発表者白井康之  
発表者の紹介JST ERATO
タイトル人気感度と多様性に基づく顧客のセグメント化とその応用(北海道大学集中講義「大規模離散計算科学特論」) 
発表の概要日本オペレーションズ・リサーチ学会や日本データベース学会,日本マーケティング・サイエンス学会等が中心となって組織している経営科学系研究部会連合協議会では,毎年国内最大級のデータ解析コンペティションを開催している.昨年度は,フラッシュマーケティングのログデータ分析を対象としたコンペティションが行われ,我々の参加チームでは,エントロピーをユーザのクラスタリングのための指標として導入し,フリー一般部門の優秀賞を獲得することができた.本講演では,昨年度の参加チームによる成果の概要等にも触れ,我々が実施した分析内容や,その後追加で実施したアプローチ方法を紹介する.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年11月1日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間16時00分-18時00分 
発表者鷲尾 隆  
発表者の紹介大阪大学産業科学研究所 / JST ERATO
タイトル確率的希少事象シミュレーションによる災害シナリオ解析(北海道大学集中講義「大規模離散計算科学特論」) 
発表の概要東日本大震災などを契機として、非常に希少であるが大規模な災害に対して、適切な避難計画や災害教育を含めたソフト指向対策を行うことが強く要請されるようになった。しかし、そのような過去に経験のない非常に希少で大規模な災害について、適切な仮定の下でリスクや被害を想定することは難しく、それらのシミュレーションや確率評価は殆ど行われて来なかった。ここでは、そのような極めて希少で複雑な災害シナリオのシミュレーション導出とその確率評価に関する我々の最近の研究を紹介する。河川洪水災害に関する具体事例を通じて、過去の流域降雨データとレプリカ交換法と呼ばれるモンテカルロ法を組み合わせることで、非常に希少な事象シナリオや確率値を推定できることを示す。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年10月28日(月曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時30分 
発表者田部井靖生  
発表者の紹介JST さきがけ専任研究員
タイトル巨大反復テキスト処理のための完備オンライン文法圧縮 
発表の概要近年, テキスト中に類似する部分列を多く含むデータが増加している. これらのデータは反復テキスト(repetitive text)と呼ばれ, 例として個人ゲノム, バージョン管理ソフトにより管理された文章, リポジトリ中でのソースコードなどがある.特に, シーケンサー技術の発達により個人ゲノムは爆発的に蓄積されており,国際1,000ゲノムプロジェクトでは, 2,000人以上のゲノム配列が蓄積されている.このような背景のもと, 巨大反復テキストを効率的に処理するための技術開発が緊急の課題となっている. 文法圧縮とは, テキストを文法により一意に表現することによりテキストを圧縮する手法であり, 反復テキストに対して有効な圧縮法である. これまで多くの文法圧縮が提案されてきたが, 大規模テキストに対しては, 膨大な作業領域が必要で適応することが困難であった. そこで, 我々は巨大テキストにも適応可能な完備オンライン文法圧縮を提案した. 提案手法は, 文法構築と文法の簡潔表現を同時にオンラインで行なう. これにより, 少ない作業領域で巨大テキストを圧縮することができる. さらに, 文法の簡潔表現のサイズは, 文法を表現するための情報論的下限に漸近的に一致する. そして, テキスト処理として, 文法の簡潔表現による部分文字列復元もサポートする. 実反復テキストを用いた実験では, 反復テキストのための圧縮法であるLZendとの比較により提案手法の有効性を示す.
接続サイト東京,大阪,筑波大学,京都大学,大阪オフィス(中原)
    
閉じる

詳細

閉じる
開催日2013年10月25日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間16時00分-18時00分 
発表者津田宏治  
発表者の紹介産業技術総合研究所 / JST ERATO
タイトル生命科学におけるデータマイニング(北海道大学集中講義「大規模離散計算科学特論」) 
発表の概要パーソナルゲノム時代に入り、生命科学で扱うデータは増加の一途であり、解析に困難をきたすことも珍しくない。各個人のゲノム、エピゲノム、遺伝子発現、タンパク質発現、代謝物プロファイルなどが比較的安価で得られるようになり、Multi-omics解析も可能になってきている。このような大量データ解析において、よくある誤解は、解析に必要な計算量はデータの量に比例するというものである。単一の種類のデータを解析する場合には、それで概ね正しいのであるが、生命科学においては、異なる種類のデータ間の関連を明らかにする統合解析が主なタスクであるので、状況はもっと悪い。例えば、100万SNP、1万発現量、1万CNVの関連を明らかにしようとすると、100兆回の評価値計算が必要になる。データの増加そのものが問題なのではなく、多様なデータが引き起こす組合せ爆発こそが最も深刻な問題なのである。組合せ効果をデータから高速に発見するには、データマイニングの諸手法を用いればいいのだが、そのようなやり方は、生命科学の論文で広く採用されるには至っていない。この理由は、データマイニングで得られた結果に関して、統計的有意性が証明できないことにある。多くのジャーナルでは、主要な結果に関しては統計的に有意であることを求めており、特に、検証実験ができない疫学の分野では、その傾向が顕著である。データマイニングでは、非常に大きな数の仮説の中から、データに合う仮説を選び出すということを行うので、多重検定の問題をクリアするのが難しい。本講義では、この問題を解決するための手法について述べる。
接続サイト東京,京都大学,筑波大学
    
閉じる

詳細

閉じる
開催日2013年10月8日(火曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時30分 
発表者Florian Lonsing  
発表者の紹介Knowledge-Based Systems Group, Vienna University of Technology
タイトルSearch-based QBF Solving: Basics, Recent Trends and Challenges 
発表の概要The logic of quantified Boolean formulas (QBF) is an extension of propositional logic where the Boolean variables in a formula are existentially or universally quantified. The decision problem of QBF is PSPACE-complete, which allows to use QBF as a natural modelling language for PSPACE-complete problems from model checking and formal verification, for example. In this talk, we give an overview on search-based QBF solving which is based on recursive variable instantiation with backtracking. Search-based QBF solving is related to the DPLL algorithm for SAT which was published in its original form in 1962. The implementations of modern search-based QBF solvers, however, largely differ from the basic recursive approach. Typically, QBF solvers apply sophisticated rules to reduce the number of variables that must be assigned to solve a QBF. For example, the resolution rule for QBF allows solvers to deduce new clauses from a given QBF, which is called clause learning. The application of these rules in modern QBF solvers blurs the traditional picture of search-based QBF solving as a recursive algorithm. In addition to giving a broad overview, we report on recent trends and challenges in search-based QBF solving. Thereby, we focus on the implementation of our QBF solver DepQBF.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年10月1日(火曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時00分-17時00分 
発表者永幡裕  
発表者の紹介北海道大学大学院生命科学院
タイトル定常マルコフ連鎖から階層構造を抽出する際に生じる組み合わせ爆発 
発表の概要本講演では、定常マルコフ連鎖ネットワーク(又はより一般化して枝が重みを持つグラフ)の最小コンダクタンスカットと呼ばれるクラスタリングについて、その分子科学的意義を中心に話す。また時間があれば、関連してスペクトル理論から得られる諸定理(Heuristics、ランダムウォークのmixing、グラフの直径 等)、重み付きグラフでの最小コンダクタンスカットなども紹介する。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年9月20日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間16時00分-18時00分 
発表者Rajeev Raman  
発表者の紹介University of Leicester, UK
タイトルEncodings for Range Selection and Top-k Queries 
発表の概要We study the problem of encoding the positions the top-k elements of an array A[1..n] for a given parameter 1 \leq k \leq n. Specifically, for any i and j, we wish create a data structure that reports the positions of the largest k elements in A[i..j] in decreasing order, without accessing A at query time. This is a natural extension of the well-known encoding range-maxima query problem, where only the position of the maximum in A[i..j] is sought, and finds applications in document retrieval and ranking. We give (sometimes tight) upper and lower bounds for this problem and some variants thereof. (This work is joint with Roberto Grossi, John Iacono, Gonzalo Navarro, Rajeev Raman, Satti Srinivasa Rao and was presented at ESA 2013).
I will also talk about recent unpublished results for the encoding range selection problem, done jointly with a subset of the above co-authors.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年9月18日(水曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間11時00分-12時30分 
発表者鈴木 真一朗  
発表者の紹介日本科学未来館
タイトルMuseum and the Web 2013 参加報告 
発表の概要
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年9月12日(木曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間16時00分-17時30分 
発表者櫻井 祐子  
発表者の紹介九州大学大学院システム情報科学研究院 准教授
タイトル特性関数の簡潔記述法と提携構造形成問題 
発表の概要本セミナでは,協力ゲームにおける特性関数の簡潔表記法として,多分岐ゼロサプレス型BDD (MTZDD) と既存の特性関数簡潔記述法のSCG(Synergy Coalition Group) [Conitzer 06]を融合した表記法を紹介する.効率的な提携を形成することは,人工知能やマルチエージェントシステムの研究領域において,重要な研究分野となっている.エージェントらは提携することで,個人では成し得ないことが可能になったり,より効率的に物事を行うことが可能となる.協力ゲーム理論は,利己的に行動するエージェント間で提携を形成することのできる場合のエージェントの振る舞いに関する理論である.提案記述法は(1)あらゆる特性関数を記述可能,(2)SCG よりも指数的に簡略化可能な場合が存在,(3) コアの非空性判定,ある配分がコアに入っているかどうかの判定など,コアに関する問題をMTZDD のノード数の多項式時間で求解可能,(4) 提携構造形成問題は混合整数計画法を用いることで,既存アルゴリズムよりも高速に求解可能という性質を持つことを示す.本研究は,離散構造に関する研究とゲーム理論を融合した,新しい研究領域の創出にも貢献できると考える.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年9月3日(火曜日)
開催場所大阪オフィス
開催時間15時30分-17時30分 
発表者Novi Quadrianto  
発表者の紹介Newton Fellow, Cambridge Machine Learning Group, University of Cambridge
タイトルSimple and Efficient Bayesian Random Forest 
発表の概要Random forests are one of the most successful ensemble methods in machine learning with state-of-the-art performance in many application domains. It works by averaging several predictions of de-correlated trees. Training phase of each decision tree involves finding data features to recursively partition the data space, and fitting a predictive model within each partition. All decision tree learning algorithms which are used in practise select features based on either entropy, or the Gini impurity criteria. In this talk, I will show a conceptually radical yet simple and efficient approach to generate a random forest based on Bayesian statistics. (Joint work with Zoubin Ghahramani.)
接続サイト北大,東工大,九大
    
閉じる

詳細

閉じる
開催日2013年8月29日(木曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時00分-17時00分 
発表者Martina Seidl  
発表者の紹介Institute for Formal Models and Verification, Johannes Kepler University
タイトルRecent Advancements in QBF Solving 
発表の概要Quantified Boolean formulas (QBF) provide a powerful framework for efficiently encoding application problems located in PSPACE including problems from formal verification, artificial intelligence, etc. The language of QBF extends propositional logic by universal and existential quantifiers over the propositional variables. The interest in QBF is raised by the vision of using QBF solvers as effectively as SAT solvers are used for problems in NP providing general, highly tuned reasoning engines.
In this talk, state-of-the-art techniques are presented which contribute towards making QBF technology ready for practical applications. Therefore, well established solving techniques are reviewed first including the QBF version of the famous DPLL decision procedure with learning which is implemented in most state-of-the-art QBF solvers. On this basis, it is shown how novel techniques like preprocessing, dual propagation, and certificate extraction are integrated into the solving workflow and how they affect the solving performance.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年8月28日(水曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時00分-17時00分 
発表者Zhiyong Peng  
発表者の紹介Wuhan University
タイトルKey Management for Access Control in Trusted Cloud Storage  
発表の概要In trusted cloud storage (TCS), for protecting the privacy of the sensitive outsourced cloud data, data owners locally encrypt their data before outsourcing. Through the secure management of the data keys, the selective access of outsourced data can be enforced in TCS scenarios. However, in TCS with multiple data owners, it remains a challenge to reduce users’ security risk and costs of key management as much as possible. In this talk, we propose a novel key management scheme based on global logical hierarchical graph (GLHG) for key derivation, which is used to enforce correctly the global authorization policies of all users. Our solution can achieve high efficiency by delegating the management of GLHG structure to cloud and adopting proxy re-encryption (PRE) technology. Additionally, we state the update policies for supporting dynamic access control. Finally, we show the benefits of our solution by experimentally evaluating quantitative criterions of key management.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年8月27日(火曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時00分-17時00分 
発表者秋葉拓哉  
発表者の紹介東京大学 情報理工学系研究科
タイトルPruned Landmark Labeling によるグラフ最短経路クエリ 
発表の概要グラフ上の最短経路クエリを処理するアルゴリズム Pruned Landmark Labeling (PLL) とその種々の拡張について紹介する.グラフ上の 2 頂点間の最短経路は,幅優先探索や Dijkstra のアルゴリズムにより(ほぼ)線形時間で計算できるということが古くから知られている.しかし,対話的なシステムの中で大規模なグラフ上の多くの頂点対について最短経路を必要とするような状況などでは,それらは時間がかかりすぎる.そこで,グラフに対し予め前計算を行い前計算の結果を用いて最短経路を高速に応答するアルゴリズムが開発されてきており,PLL はその 1 つである.
PLL のアルゴリズムは驚くほどシンプルなものである.前計算は枝狩り幅優先探索を全頂点から行い,クエリの処理では 2 つの配列を走査するだけである.ただし,枝狩りのルールは巧妙かつ非自明で,構成中の未完成の前処理データにクエリを発行するという興味深い動作になっている.ソーシャルネットワークやウェブグラフ等の現実世界のグラフであれば,数億辺のグラフを数時間で前計算し,クエリに数マイクロ秒で答えることができる.近いクエリ時間を持つ既存の手法では,数時間で前処理ができる限界が数百万辺のグラフに留まっていたため,一気に 2桁のスケーラビリティ改善を達成したと言える.また,PLL が効率的である理由は,ハブの存在やコアフリンジ構造など実ネットワークに共通して知られる性質により説明することができる.
さらに,PLL は幅優先探索をベースとしたシンプルな手法であるが故に,関連する問題に向けた様々な拡張を考えることができる.今回は,到達可能性クエリ,交通ネットワーク上での最短経路クエリ,動的なネットワークへの対応,Top-k 最短経路クエリなどへの取り組みについて紹介する.
接続サイト東京,大阪,埼玉大学,中央大学
    
閉じる

詳細

閉じる
開催日2013年8月26日(月曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時30分 
発表者Łukasz Kaiser   
発表者の紹介 LIAFA in Paris
タイトルExperimental Descriptive Complexity and Machine Learning 
発表の概要Descriptive complexity studies the logical means necessary to define a function or set of interest. In addition to standard complexity questions (about the time, space, or communication needed) and circuit complexity issues (such as the circuit size or depth necessary), descriptive complexity studies structural properties of definitions, such as uniformity and locality. I will introduce these notions and show that they are closely related to recent developments in machine learning. In particular, I will show that an extension of first-order logic with bit and successor relations and the majority quantifier, which has been widely studied in descriptive complexity, corresponds to a class of convolutional neural networks that have recently been applied in many domains. I will discuss how this relationship can be used both in experimental descriptive complexity and to gain insights into machine learning algorithms.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年8月8日(木曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間15時00分-17時00分 
発表者中原啓貴  
発表者の紹介鹿児島大学大学院理工学研究科 助教
タイトル多値決定グラフに基づくパケット分類器に関して 
発表の概要パケット分類は, ルータやファイアウォールが持つ機能の一つである. パケットヘッダには, プロトコル番号, 送信元アドレス, 送信先アドレスやポート番号などの情報が含まれている. パケット分類器はこれらを参照し, ルールと呼ばれる予め登録されてたヘッダと一致した場合, 特定の動作を行う.パケット分類器は, セキュリティを改善するため用いられているファイアウォール, QoS等で用いられるアクセス制御リスト, IPマスカレード等で行われるパケットのフィルタリング, 及び加工で用いられるIPチェーン等様々な機器で用いられている.
インターネットの爆発的な普及によりトラフィックは増加し続けており, 現行のバックボーンルータの検索速度は100Gbpsに達している. 次世代規格400Gbpsの仕様が策定されつつあり, パケット分類器もルータ並の検索速度を持つ専用回路が必要である.
本講演ではパケット分類表を多値決定グラフの一種であるEdge-valued Multi-valued Decision Diagram (EVMDD(k))に基づくLUTカスケードで実現する手法について述べる.従来手法は二分決定グラフ(BDD: Binary Decision Diagram)に基づく回路の実装方法に主眼が置かれていた. 提案手法ではパケット分類表をコンパクトに表現でき, かつ実装に適するようにデータ構造を見直した点が独創的であり新規性があるといえる.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年8月1日(木曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間16時30分-18時00分 
発表者伊藤健洋  
発表者の紹介東北大学大学院情報科学研究科
タイトルグラフ構造を用いた配電融通アルゴリズムの研究 
発表の概要電力網の配電融通問題は,(多重)ナップザック問題にグラフ構造を導入したグラフ分割問題として定式化できる.本発表では,このグラフ分割問題に対して,発表者が現在までに得た計算困難性や近似困難性,グラフ構造を用いたアルゴリズムについて概観する.また,発表者の最近の研究課題から,所望の配電方法に遷移させるスイッチング手順に関する話題にも触れたい.
より具体的には,本発表では,次のようなグラフ分割問題を扱う.グラフの各点は,供給点もしくは需要点であるとし,それぞれ供給量と需要量が与えられているとする.各需要点は,高々1個の供給点からしか供給を受けられないとする.したがって,グラフから何本かの辺を取り除き(送電線のスイッチをオフにし),各連結成分には供給点が高々1個だけあるようにしたい.むろん,供給点を持つ各連結成分においては,その供給量はその連結成分にある需要量の合計以上でなければならない.このようなモデル化の下,発表者は,供給が受けられる需要量の合計を最大化する問題や,分割を遷移させる(スイッチング)問題などを,主にグラフ構造を利用して研究している.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年7月16日(火曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間15時30分-16時30分 
発表者永山忍  
発表者の紹介広島市立大学大学院情報科学研究科
タイトルZDD を用いた正規表現マッチングについて 
発表の概要この講演では、ZDD を用いた正規表現マッチング手法について紹介します。本手法では、マッチングのパターンとして与えられた正規表現を非決定性有限オートマトン NFA に変換し、その NFA をワンホット符号化と ZDD を用いてコンパクトに表現します。そして、NFA 上での状態遷移を ZDD 上での関係演算として実現することによって、高速な正規表現マッチングを可能にします。私たちが比較的小さな例題を用いて行った初期実験の結果では、ワンホット符号化と ZDD を用いることによって、正規表現マッチングの実行に必要なメモリ量を大幅に削減でき、また、実行速度も既存のマッチング手法に比べ約5倍の高速化を達成しました。そのような高速化をどのようにして達成したかについてや、正規表現マッチングを実行するために必要な ZDD 上の関係演算の詳細などについても紹介し、今後の課題や発展について、一緒に議論できればと考えております。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年7月4日(木曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間14時00分-16時00分 
発表者前原貴憲  
発表者の紹介国立情報学研究所 / JST ERATO 河原林プロジェクト 特任研究員
タイトル大規模グラフに関する行列計算 
発表の概要インターネットのWeb,FacebookやTwitterの友人関係などに代表される大規模グラフに対する解析手法の需要が高まっている.特に,グラフの接続構造を行列として表現し,連立方程式の求解や固有値計算によって得られるPageRankやSpectralCutなどの特徴量は応用上広く用いられており,大規模グラフに対するより高速な計算手法が求められている.
本研究では,大規模グラフを木分解することで木幅の小さな部分(フリンジ)とエクスパンダー的構造をもつ部分(コア)に分解できることに注目する.フリンジはガウスの消去法などの直接法によって効率的に処理でき,コアはCG法などの反復法が非常に高速に収束する,という性質をもつ.これらの特性を組み合わせることで,全体に対して高速に動作する手法が構築できる.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年7月2日(火曜日)
開催場所大阪オフィス
開催時間16時30分-18時30分 
発表者Marco Cuturi  
発表者の紹介Associate Professor, Graduate School of Informatics, Kyoto University
タイトルLightspeed Optimal Transportation Distances for Histograms 
発表の概要Optimal transportation distances are a fundamental family of parameterized distances for histograms. Despite their appealing theoretical properties, excellent performance and intuitive formulation, their computation involves the resolution of a linear program whose cost is prohibitive whenever the histograms' dimension exceeds a few hundreds. We will try to solve this challenge in this talk using two different sets of tools:

- Kernel methods: we prove that the classical transportation distance can be turned into a positive definite kernel by considering the generating function of the transportation polytope. Since this quantity is computationally intractable we study random sampling approaches by sampling vertices of the transportation polytope.The resulting kernel has a linear time complexity and performs slightly
worse than regular EMD in our experimental studies.

- Regularization: we smooth the classical optimal transportation problem with an entropic regularization term, and show that the resulting optimum is also a distance which can be computed through Sinkhorn-Knopp's matrix scaling algorithm. Through this trick, we avoid the computation of an LP and we obtain a distance which is up to 1.000.000 x faster to compute than classical EMD and can be parallelized on GPGPUs. This dramatic speed-up opens the door for large-scale applications of optimal transportation distances. We also report improved performance on the MNIST dataset.
接続サイト札幌,東京,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年5月29日(水曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間13時30分-15時30分 
発表者安田宜仁  
発表者の紹介NTT コミュニケーション科学基礎研究所
タイトル制約をともなう動的計画法のZDDを用いた解法 
発表の概要本発表では, 現在NTTコミュニケーション科学基礎研究所と北大湊教授と共同で進めている, 制約を伴うような動的計画法をZDDを用いて解く方法について述べる. 一般に, 動的計画法は何らかの制約のもとでの最適解を得るための手法として設計されている. しかし, 動的計画法で効率的に解くことができる既存の問題に対してさらに制約を追加したい場合, 設計が複雑になることが多い.
我々は, 近年フロンティア法と動的計画法の関連が注目されていること, およびZDDによって比較的容易に制約を満たす解の集合を表現できることに着目し, これまで動的計画法で解かれていた問題にさまざまな制約を追加しても容易に動的計画法を設計できるような手法を構築することをめざしている.このための直感的な方針としては, 既存の動的計画法で用いるテーブルを表現したZDDと, 追加の制約を表現するZDDとの演算によって, 解きたい問題のためのテーブルを表現するZDDを構築することが考えられる.
本発表ではさらに, 制約を表現したZDDに付加的な情報を与えることで, ZDDの演算を行うことなく,直接動的計画法を実行する方法についても述べる.例題として根つき部分木からのナップサック問題を取り上げながら現在の検討範囲を紹介する.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年5月9日(木曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間15時30分-17時30分 
発表者Florian Horn   
発表者の紹介CNRS researcher at LIAFA
タイトルStochastic Games in Verification 
発表の概要Games are a classical tool for the synthesis of controllers in reactive systems. In this setting, the system and its evolution are represented by a graph (the arena), on which two players (Adam and Eve) move a token for an infinity of steps. The winner of a play is decided by a subset of the infinite sequences of steps.
In this talk, I will introduce the important concepts of game theory in this field, and present some of my results about the usual problems the we consider : How to decide the winner of a given game? What kind of strategies do the players need to achieve their objectives? How much memory do these strategies require ?
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年4月24日(水曜日)
開催場所大阪オフィス
開催時間15時00分-17時00分 
発表者Michael E. Houle  
発表者の紹介Visiting Professor, National Institute of Informatics
タイトルIntrinsic Dimensionality and Discriminability of Data 
発表の概要In this presentation, we examine the uses of a measure of intrinsic dimensionality, the "generalized expansion dimension", in a variety of applications in search and data mining. The original formulation of expansion dimension was formulated in 2002 by Karger and Ruhl for the theoretical analysis of search indices. However, generalized versions of this measure turn out to be quite useful not only theoretically, but also as the basis of runtime testing. We will summarize two results that were presented at IEEE ICDM 2012, one on practical methods for estimation of intrinsic dimensionality (presentation at a workshop associated with ICDM 2012), and the other on an application of intrinsic dimensional testing for search using lower-bounding distance functions (a full-paper presentation at the main conference).
A brief survey will also be provided of other papers presented at ICDM 2012 that may be of interest to members of the ERATO Minato project. The talk will conclude with a report on ongoing work on a continuous variant of intrinsic dimension for arbitrary data distributions.
接続サイト札幌,東京,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年4月12日(金曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間15時30分-17時30分 
発表者美添一樹  
発表者の紹介JST ERATO研究員
タイトル分散並列モンテカルロ木探索および囲碁への応用(中間報告) 
発表の概要2011年度に提案した TDS-df-UCTアルゴリズムには探索の終了時にオーバーヘッドがあり、1,200コアで600~740倍程度の高速化にとどまっていた。特に 2,000並列以上で動作させた場合にオーバーヘッドが顕著になると言う問題があった。
そこで、メモリ消費量の増大と引き替えにメッセージのサイズと頻度を減少させる手法を提案し、TDS-df-UCT の性能を向上させることに成功した。仮想ゲーム木では 4,800 コアを用いて最大 3,200倍の高速化を達成している(未発表)。まず改良された TDS-df-UCT アルゴリズムについて述べる。
さらに、この手法を用いた囲碁プログラムを実装し、1,024並列までで動作させて速度、棋力の向上などを測定した。その過程で明らかになった幾つかの問題点、および今後の改良点などについて述べる。
余談として時間に余裕があれば、UEC杯コンピュータ囲碁大会の参戦記、および苦労話について述べる。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年3月26日(火曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時00分-16時30分 
発表者杉本雅則  
発表者の紹介北海道大学大学院情報科学研究科 教授
タイトル音響信号を用いたセンシング技術 
発表の概要本発表では、国立情報学研究所と共同で開発を進めている音響信号を用いたセンシング技術について述べる。まず最初に、世界最高性能を達成した超音波測距技術とそれに基づく測位システム、ならびにその応用について説明する。次に、合成送信開口に基づく音響イメージング手法について議論する。
接続サイト東京,大阪,九州(予定)

開催時間16時30分-18時00分 
発表者吉田 哲也  
発表者の紹介北海道大学大学院情報科学研究科 准教授
タイトルネットワークからのコミュニティ発見に関する取り組み 
発表の概要近年のネットワーク環境の進展に伴い,ソーシャルネットワークサービスなどが新しいコミュニケーションメディアとして広く用いられるようになってきている.本講演では,ネットワークからのコミュニティ発見に対し,ネットワークのノード情報を考慮する手法と,ひとつのノードが複数のコミュニティに所属することを許す重複コミュニティ発見に対する手法について紹介する.
接続サイト東京,大阪,九州(予定)

    
閉じる

詳細

閉じる
開催日2013年3月22日(金曜日)
開催場所東工大サテライトラボ
開催時間15時00分-17時00分 
発表者石畠 正和   
発表者の紹介東京工業大学大学院情報理工学研究科 計算工学専攻
タイトルProposionalized Probability Computation and Learning on Binary Decision Diagrams 
発表の概要人工知能や機械学習の分野において、自然言語や遺伝子データ、関係データベースなどの記号データ中の不確実性を扱う方法として、記号データ上の確率モデルが広く利用されている。確率モデルはデータ中の不確実性や曖昧性などの確率的関係を効率的に表現できる一方、データ間の規則や制約などの決定的関係を効率的に扱えない。確率的関係と論理的関係の双方を効率的に表現する枠組みとして、論理に基づく確率モデリングが提案されている。論理に基づく確率モデリングでは、論理の高い表現力により、既存のよく知られた確率モデルを含む様々な確率モデルを記述することが可能である。よって論理に基づく確率モデルに対する確率推論法が存在すれば、モデルを書き換えても推論法の変更は不要であり、新たなデータに対する適切なモデルの設計が容易になる。このような一般的なモデルクラスとそれに附随する一般的なアルゴリズムはInterface layerと呼ばれ、近年、注目されている。しかし、論理に基づく確率モデリングに対する一般的な確率推論の計算量は指数的であるという問題が存在する。この問題を解決するため、多くの既存手法では表現できるモデルや扱える確率推論に制限を設けている。より良いInterface layer を実現するためには、より一般的かつ効率的な確率モデリング法とそれに附随する様々な確率推論法が必要である。
本発表では論理に基づく確率モデリングに対し、一般的かつ効率的な確率推論を提案する。一般的であるために、提案手法は任意の命題論理式で表現される確率モデルを対象にする。また、効率的であるために、提案手法は論理関数をコンパクトに圧縮する二分決定図を利用する。提案手法は任意の論理式で表現される確率モデルを二分決定図として圧縮し、そのモデル上の確率推論を二分決定図上の動的計画法として効率的に実行する。二分決定図上の確率推論として、確率計算、Viterbi 計算、サンプリング、最尤推定そしてベイズ推定を提案する。また、提案手法を人工データおよび実データに適用することで提案手法が確かに一般的かつ効率的であることを実験的および解析的に示す。
接続サイト札幌,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年3月21日(木曜日)
開催場所東工大 西8号館E棟10階E1011(東京サテラボ向かい側)
開催時間15時00分-16時30分 
発表者Martin Müller  
発表者の紹介 University of Alberta
タイトルMove Quality in Monte Carlo Simulation: A Case Study using the Fuego Go Program 
発表の概要Despite half a dozen years of intense research, designing effective simulation policies for Monte Carlo Tree search in Go is still considered something of a black art, and driven largely by trial and error. Important ideas that have evolved include pattern- and tactics-based playouts, simulation balancing, and several schemes to dynamically modify simulation policies online. In this study, we take an in-depth look at what happens when the Go program Fuego runs its playouts. We develop several methods to evaluate the quality of moves played in these simulations, and we evaluate the contribution of the different components of Fuego's playout policy. We study the distribution of both the number of blunders, or result-changing moves, and the absolute loss - in terms of number of points - for many variations of the Fuego playout policy. We use this study to identify an improvement to the Fuego default policy.
接続サイト札幌,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年3月11日(月曜日)
開催場所大阪オフィス
開催時間16時00分-18時00分 
発表者斎藤寿樹  
発表者の紹介神戸大学大学院工学研究科
タイトル区間グラフおよび関連クラスに対する部分表現拡張問題 
発表の概要幾何的な特徴を持つグラフに区間グラフがある.区間グラフは区間表現と呼ばれる区間の集合を持つグラフで,グラフの頂点は区間と対応し,2つ の頂点が隣接する必要十分条件は対応する2つの区間に重なりがあることである.本発表では,区間グラフにおける部分表現拡張問題について扱 う.区間グラフにおける部分表現拡張問題とは,区間グラフGとGの誘導部分グラフG'の区間表現I'が与えられ,I'を拡張してGの区間表現 を求める問題である.本発表では,区間表現を離散的に扱った場合での部分表現拡張問題に対する計算複雑度を与える.また,区間グラフにスー パークラスであるコーダルグラフやパスグラフ,部分クラスである真区間グラフに対しても同様成果を与える.
接続サイト札幌,東京,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年3月9日(土曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間10時30分-12時00分 
発表者岩下洋哲,中澤 吉男  
発表者の紹介JST ERATO研究員,フリープログラマー
タイトル最小完全ハッシュ関数を用いたグリッドグラフ上の効率的なパス数え上げ 
発表の概要正方形を縦横それぞれ n 分割してできる (n+1)×(n+1) グリッドグラフにおいて、対角の2頂点を結ぶパスの数は n に対して急激に増大する。例えば n=10 に対しては 10^24 もの数となり、もはや一つずつ列挙するようなことはできない大きさである。これまでに Knuth のアルゴリズムに基づく方法で n=21 までのパス数が計算されていたが、我々はグリッドグラフの性質を利用して計算速度と使用メモリを大幅に改善し、n=23 までの計算に成功した。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年1月31日(木曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間16時00分-17時30分 
発表者宮川 晋   
発表者の紹介NTTコミュニケーションズ(株) 先端IPアーキテクチャセンタ 担当部長 / 北陸先端科学技術大学院大学 客員教授
タイトル最新IP技術開発の現場から 
発表の概要高速化するTCP/IPネットワークの状態をリアルタイムに把握し、必要な手をうつことを可能にする技術 - Samurai - および、最近のインターネットトラフィックの傾向とそれが指し示すインターネットの構造の変化の現状とそれに対する取り組みについて紹介する。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年1月28日(月曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間13時00分-16時00分 
発表者Robert Wille and Mathias Soeken  
発表者の紹介University of Bremen
タイトルSynthesis of Reversible Circuits using Decision Diagrams: Background,Recent Accomplishments, and Open Challenges 
発表の概要Due to its promising applications in domains such as quantum computation and low-power design, synthesis of reversible circuits has become an intensely studied topic. However, many synthesis methods are limited by non-scalable function representations such as truth tables. As an alternative, synthesis exploiting graph-based representations has been suggested. The underlying structure is a decision diagram (DD) that may vary regarding reduction methods, decomposition rules, or ordering restrictions.
In this talk, we are proving a comprehensive overview on this particular research area. First, we review the background on reversible circuits and their applications as an emerging technology followed by a summary of the recent accomplishments in the synthesis of these circuits using decision diagram. With this as basis, the second part of the talk outlines open research problems and provides possible solutions as well as recent work in progress on how to solve these problem.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年1月15日(火曜日)
開催場所大阪オフィス
開催時間16時30分-18時00分 
発表者吉仲亮  
発表者の紹介京都大学 情報学研究科 助教
タイトル近年の文脈自由文法のアルゴリズム的学習について
 
発表の概要形式文法のアルゴリズム的学習を研究する文法推論の分野では、正規言語の学習については十分に研究され多くの肯定的結果とそれらの間の関係が明らかになっていた一方で、文脈自由言語の学習については効率的な学習に関する結果は非常に乏しい状態が続いていた。近年、A. Clark らを中心とする研究者によって、部分文字列と部分文字列が出現しうる文脈のあいだの共起関係の分析に基づく、「分布学習」とよばれるアプローチが盛んに研究されており、文脈自由言語に対する効率の良い学習アルゴリズムがいくつも提案されている。本談話ではこれらの結果を紹介する。特に、学習アルゴリズムにおける文字列と文脈の対称的な性質について述べる。
接続サイト札幌,東京,九州(予定)
    
閉じる

詳細

閉じる
開催日2013年1月11日(金曜日)
開催場所北海道大学工学部C304  ERATO セミナー室
開催時間16時00分-17時30分 
発表者湊 真一  
発表者の紹介北海道大学 大学院 情報科学研究科 教授
タイトル本プロジェクトの近況と今後の方向性について 
発表の概要ERATO湊離散構造処理系プロジェクトが本格的な研究活動を開始してから約3年が経過した。この間、プロジェクトメンバや共同研究者・連携研究者の方々の協力により、多くの興味深い研究成果が得られている。本講演では、本プロジェクトのこれまでの研究の流れを簡単に振り返り、最近の研究状況について述べる。本プロジェクトの研究期間はあと2年3ヶ月あるが、現在の状況を踏まえて、今後、我々がより注力すべき研究分野をいくつか指摘し、それらについてセミナー参加者による討論を行いたい。
接続サイト東京オフィス,大阪オフィス,九州大学,京都大学
    
閉じる

詳細

閉じる
開催日2012年12月12日(水曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時00分-15時30分 
発表者遠藤敏夫  
発表者の紹介東京工業大学 & JST CREST
タイトルポストペタスケール時代のメモリ階層の深化に対応するソフトウェア技術 
発表の概要メモリの速度性能・容量の伸びがメニーコア化するプロセッサの伸びに追いつかないという、メモリウォール問題は、今後のスパコンアーキテクチャにおいて顕著となり、科学技術計算を現状よりもさらに大規模化・精緻化する上での障害となると考えられています。その解決を目的として、2012年10月から開始したJST-CRESTプロジェクト「ポストペタスケール時代のメモリ階層の深化に対応するソフトウェア技術」の概要を説明します。本プロジェクトでは、不揮発メモリも含めた異種のメモリを混在させたスパコンアーキテクチャを想定し、それを有効活用するコンパイラ・メモリ管理技術・応用アルゴリズムなどにまたがった新しいソフトウェア技術の研究開発を推進します。
接続サイト東京,大阪,九州(予定)

開催時間15時30分-16時00分 
発表者佐藤仁  
発表者の紹介東京工業大学 & JST CREST
タイトルGPU MapReduceによる大規模グラフ処理 
発表の概要MapReduceモデルに基づいたGIM-V(Generalized Iterative Matrix-Vector multiplication)グラフ処理アルゴリズムを複数GPU環境へ適用した事例について紹介する。東工大のTSUBAME2.0スーパーコンピュータの256ノード、768台のGPUを用いて、2^30頂点、2^34辺のグラフに対するPageRank処理を行った結果、87.04 ME/s (mega edges per second)を達成し、スケーラブルな性能を示すことを確認した。
接続サイト東京,大阪,九州(予定)

開催時間16時00分-16時45分 
発表者安井雄一郎  
発表者の紹介中央大学, JST CREST
タイトルメモリ階層構造を考慮した大規模グラフ処理の高速化 
発表の概要本発表では基本的なグラフ処理である幅優先探索, 最短路問題, 中心性指標計算に焦点を当てて,メモリ階層構造を考慮した高速計算について述べていく. 我々の実装 NETAL (NETwork Analysis Library) は,2400万点5800万枝からなる全米道路ネットワークに対する各2点間の最短路長を7.75日で,377万点1652万枝からなる特許引用ネットワークに対する中心性指標計算を2.52時間で, 厳密計算に成功している. また,幅優先探索性能は最新の Graph500 List において, CPU 主体の単一計算機上で最も高速かつ, 消費電力あたりの性能が最も高い.これらを実現するために必要な計算機の特徴を捉えたアルゴリズムとデータ構造、その実装方法を紹介する.
接続サイト東京,大阪,九州(予定)

開催時間16時45分-17時30分 
発表者藤澤克樹  
発表者の紹介中央大学, JST CREST
タイトル大規模最適化問題に対するソフトウェア開発と高速&安定計算 --理論からスパコンまで-- 
発表の概要最適化手法とコンピュータが生まれてから60年以上の間、常に計算機、最適化アルゴリズム共に進歩を遂げてきました。優れた理論から必ずしも優れたソフトウェアが生まれるとは限らないのですが、今回の講演では 1990年代半ばに誕生した半正定値計画問題(SDP)に対する理論(主双対内点法)を題材に取って、この理論がその後どのような経緯を辿って、ソフトウェア化 --> 一般公開 --> 高精度化 --> スパコン上で大規模並列計算へと進んで行ったのかについてお話したいと思います。内容はSDP に関する最適化理論、定式化等から応用分野、ソフトウェア化、大規模計算までと多岐に渡る予定です。
接続サイト東京,大阪,九州(予定)

    
閉じる

詳細

閉じる
開催日2012年12月6日(木曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間16時00分-18時00分 
発表者笠原 正治  
発表者の紹介奈良先端科学技術大学院大学 情報科学研究科
タイトルクラウド・コンピューティングにおけるタスク・スケジューリング問題と確率論的アプローチ 
発表の概要クラウド・コンピューティングで提供される分散並列処理サービスでは,巨大なタスクが複数のサブタスクに分割され,それらが多数のワーカと呼ばれるマシン上で同時実行される.本発表では,大規模なワーカ群で並列処理を行うときのタスク完了時間分布を極値理論により近似解析するアプローチについて紹介し,サブタスクの複製を複数生成して別々のワーカマシンで処理させるタスク複製法による性能改善効果について検討した結果を説明する.またクラウド・コンピューティングにおける省電力化に向けた電力オフ・スケジューリング問題についても紹介を行う.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年12月5日(水曜日)
開催場所東京サテライトオフィス(東工大)
開催時間13時30分-15時30分 
発表者Rajeev Raman  
発表者の紹介University of Leicester, UK
タイトルDynamizing Succinct Tree Representations 
発表の概要We consider succinct, or space-efficient, representations of ordinal trees. Representations exist that take 2n + o(n) bits to represent a static n-node ordinal tree - close to the information-theoretic minimum - and support navigational operations in O(1) time on a RAM model; and some implementations have good practical performance. The situation is different for dynamic ordinal trees. Although there is theoretical work on succinct dynamic ordinal trees, there is little work on the practical performance of these data structures. Motivated by applications to representing XML documents, in this paper, we report on a preliminary study on dynamic succinct data structures. Our implementation is based on representing the tree structure as a sequence of balanced parentheses, with navigation done using the min-max tree of Sadakane and Navarro (SODA '10). Our implementation shows promising performance for update and navigation, and our findings highlight two issues that we believe will be important to future implementations: the difference between the finger model of (say) Farzan and Munro (ICALP ’09) and the parenthesis model of Sadakane and Navarro, and the choice of the balanced tree used to represent the min-max tree.
接続サイト札幌,大阪,九州(予定)
開催時間15時30分-17時30分 
発表者Roberto Grossi  
発表者の紹介University of Pisa, Italy
タイトルEmpowering Succinct Data Structures for Strings and Sequences 
発表の概要The talk describes some problems that arise in industrial applications and how succinct and compressed data structures for strings and sequences can help using little space. The first part of the talk is devoted to semi-indexing semi-structured data, e.g. query log data in JSON format. The second part involves prefix searching on a set of strings which is helpful e.g. in search engines, and describes some succinct data structures for storing a set of strings. The third part of the talk considers a sequence of strings (not to be confused with a set of strings) and introduces the wavelet trie for storing textual data (e.g. URLs) in time order and supporting extra functionalities that exploit this order. The discussed results are joint works with Giuseppe Ottaviano presented at ACM CIKM 2011, ACM-SIAM ALENEX 2012, and ACM PODS 2012.
接続サイト札幌,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年11月22日(木曜日)
開催場所大阪オフィス
開催時間13時00分-15時00分 
発表者Alexandre Termier  
発表者の紹介Assitant Prof., LIG (Laboratoire d'Informatique de Grenoble), Universite Joseph Fourier, France
タイトルParaMiner: generic and parallel pattern mining scaling to real-world data 
発表の概要In this talk, we present the PhD works of Benjamin Negrevergne, conduced at the University of Grenoble. The goal of these works is to propose an efficient parallel algorithm than can solve a broad range of pattern mining problems. In this regard, we exploit the results on polynomial-delay / polynomial space enumeration of Arimura and Uno [SDM'09] and of Boley et al. [Th.Comp.Sci.'10] on strongly accessible set systems. We pair these works with a novel dataset reduction technique, EL-reduction, that exploits some characteristics of the enumeration strategy for reducing the dataset. We show that this combination allows to mine real world datasets with a generic algorithm, with performances comparable with specialized algorithms, for a broad range of pattern mining problems. We will also present some recent developments on the problems of doing a dataset reduction in parallel on a multicore processor, and a solution we found for alleviating some of these problems and improving parallel scaling.

(*) Benjamin Negreverge's PhD was supervised by Alexandre Termier, Marie-Christine Rousset and Jean-Francois Mehaut.
接続サイト札幌,東京,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年11月19日(月曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間15時30分-17時30分 
発表者夫 紀恵  
発表者の紹介東京大学大学院情報理工学系研究科コンピュータ科学専攻
タイトルToric idealを用いた平面的periodicグラフ上最短路問題及びパラメトリック整数計画問題のための高速アルゴリズム 
発表の概要Abe et al.(2005)によって開発された、結晶表面上の原子を組換えることにより任意の原子配置を実現するというナノテクノロジの運用には、結晶表面上の最短路計算のための強多項式時間アルゴリズムが不可欠となる。一方、結晶のモデルとして用いられるperiodicグラフ上の最短路計算は一般にNP困難である。本講演では、タイリング状の結晶表面に対応する平面的periodicグラフのみに対象を限定し、強多項式時間アルゴリズムの構築についてお話する。具体的には、平面的periodicグラフを記述するデータ構造であるstaticグラフから得られる、incidence-transit行列のtoric idealがsquare-freeであることを示すことで、平面的periodicグラフがさらにcoherenceと呼ばれる性質を満たすならば最短路が線形計画によって求まることを示す。続いて、パラメトリック整数計画問題についてお話する。Coherentなperiodicグラフのパラメトリック距離計算がパラメトリック整数計画問題を解くことで可能であり、上記の結晶表面上再配置への応用が可能であるほか、コンパイラにおけるループ最適化など、他の問題への応用がある重要な問題であり、これまでにいくつかのアルゴリズム及びその高速な実装が提案されてきたが、変数の数が増えるにつれ性能が著しく落ちることが問題であった。本講演では、toric idealのGr\"{o}bner基底とその標準対分解を用いたアルゴリズムと、その論理関数双対化を用いた高速実装が、この変数が多数である場合において有効であることを紹介する。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年11月14日(水曜日)
開催場所東工大サテライトラボ
開催時間15時30分-17時30分 
発表者林浩平  
発表者の紹介東京大学大学院 / JSPS特別研究員
タイトルテンソル分解による関係データ解析 
発表の概要WWW,ソーシャルネットワーク,DNA,マイクロアレイなど,オブジェクト間の多項関係を定量化したものを関係データと呼ぶ.一般的にm項関係を表現する関係データは m次のテンソル(あるいは m 次元配列) として表現されるが,データの総数がm乗のオーダで増加し高次元となるため直接的な解析は難しい.テンソル分解はこれら高次のデータテンソルを少数のパラメータで表現することで情報の圧縮,特徴抽出,可視化,データ補完を可能とする.本発表ではテンソル分解の基本モデルや実問題への応用例を簡単に紹介する.またテンソル分解を確率モデルとして拡張し,センサデータの解析に応用した事例についても述べる.
接続サイト札幌,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年11月12日(月曜日)
開催場所東工大サテライトラボ
開催時間15時00分-17時00分 
発表者S.R.K. Branavan  
発表者の紹介Chief Scientist, Natural Language Processing at Millennium Information Technologies, Colombo, Sri Lanka
タイトルGrounding Linguistic Analysis in Control Applications 
発表の概要Natural languages are the medium in which the majority of humanity's collective knowledge is recorded and communicated. If machines were able to automatically access and leverage this information, they could effectively perform many tasks that are currently considered to be computationally intractable, thus requiring human involvement. Today, the only way to infuse human knowledge into computational algorithms is to have humans in the loop - i.e., to manually encode the knowledge into heuristics, through annotations, or directly into the model
structure itself.
Our ultimate goal is to automate this process, so that machines can access required knowledge directly from text. One path to this goal is to perform a semantic interpretation of text by grounding the textual information in the objects, actions and dynamics of the physical world. From a linguistic viewpoint, this grounding of language in control applications presents a very natural notion of language semantics. I.e., by allowing us to define semantics with respect to the control application, and avoid imposing subjective human notions of correctness.
In this talk, I will explore two aspects of the connection between language and control applications: first, how the semantic analysis of language can be driven by control performance; and second, how information from text can be leveraged to improve performance in complex control systems. These two aspects are in fact complementary, and language analysis is central to them both. Addressing these aspects jointly is particularly challenging. However, as our empirical results show, connecting the semantic analysis of language to control applications allow us to leverage the synergy between the two to simultaneously learn both language analysis and application control with little or no prior knowledge.
接続サイト札幌,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年11月9日(金曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間16時00分-17時30分 
発表者白井康之  
発表者の紹介JST ERATO
タイトルSet-Similarity Joins (北海道大学集中講義「大規模離散計算科学特論」) 
発表の概要近年,データベース中に含まれる類似データを発見するための Similarity Joins に関する研究が盛んにおこなわれている.データ連結やデータクリーニング等,幅広い応用可能性を持つことが研究動機となっているが,数百万オーダーレベルのデータベース間の類似性を探索するためには,効率的なアルゴリズムの開発もまた必須である.本報告では,既存のフィルタリングに基づく効率化技法やトライ構造を用いた探索手法について触れ,あわせて,当グループで研究開発を進めているZDD-Join についても解説する.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年11月6日(火曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間15時30分-17時30分 
発表者戸田貴久  
発表者の紹介JST ERATO湊離散構造処理系プロジェクト研究員
タイトルOn Separating Convex Points with Lines 
発表の概要本発表では、平面上の点配置に対する一種の幾何学的な分離パターンを扱う。そのようなパターンを線形分離族と呼ぶ。点配置が凸の位置にあるとき、線形分離族に単純なグラフ表示を与えることができる。このグラフを直線的に並べた節点上のグラフとして見るとき、節点の自然な順序によって定義される辺の交差概念を用いて単純な特徴づけを与えることができる。また、視覚的に興味深い形をしたグラフでもある。さらに、極小な線形分離族に対応するグラフに焦点を当てるとき、円周上の点配置に対する非交差木やlinked diagramといった興味深いグラフとの対応関係が明らかになる。この対応関係を通して数え上げの結果がいくつか導かれる。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年11月2日(金曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間16時00分-17時30分 
発表者鷲尾 隆  
発表者の紹介大阪大学 産業科学研究所 / JST ERATO
タイトルGlobal Maximization of Submodular Function and Its application to Machine Learning(北海道大学集中講義「大規模離散計算科学特論」) 
発表の概要Feature selection is a highly important task to enhance generality and transparency of multi-variate prediction models including classifiers and regression models in machine learning and statistics. It also contributes to identify feature variables (or factors) dependent on the objective prediction variable in the generation process of a given data set. Particularly, the globally optimum feature set providing the minimum prediction error of the model should be explored for the later purpose under the assumption that the prediction model captures the given data generation process. The model prediction error is known to be a submodular function of a feature subset where improvement of the error is less when the size of the selected feature subset gets larger, and thus the task to derive the globally optimum feature set is a submodular optimization problem which is NP-hard.
Based on this background, my talk addresses the development of an efficient algorithm for the global submodular maximization and its application to the optimum feature selection .
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年10月26日(金曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間16時00分-17時30分 
発表者津田宏治  
発表者の紹介産業技術総合研究所 / JST ERATO
タイトル大量データの類似度検索技術(北海道大学集中講義「大規模離散計算科学特論」) 
発表の概要近年、Big Data時代といわれるように、インターネット経由で得られる情報の量は急激に増加しており、膨大な数のデータサンプルをどのように利用するかが重要な研究課題となっている。類似度検索を高速化するのに大事なポイントは、データサンプルを離散化して圧縮し、それらを全てクラスタマシンの分散メモリ上に載せてしまい、ディスクアクセスを極力避けることである(In-Memory Data Grid)。本講演では、Locality Sensitive Hashingという離散化テクニックを用いたSketchSortという全ペア類似度検索の手法と、簡潔データ構造の一種であるWavelet Treeを用いたBag-of-wordsデータの高速な検索法について述べる。両手法とも、離散化と、その効率的な索引化が高速化のキーとなっている。画像データ、タンパク質の3次元構造データ、次世代シークエンサーデータなどの実データでの応用についても述べる。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年10月3日(水曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間15時30分-17時30分 
発表者Lukasz Kaiser  
発表者の紹介LIAFA, CNRS & Universite Paris 7
タイトルLearning and Playing Board Games using Descriptive Complexity 
発表の概要Imagine that a few moves of an unknown game are demonstrated to you, as well as some winning and losing positions, and your task is to guess the rules of the game and then to develop a method to play it competitively. While this task might seem to be unrelated to mathematical logic and even a bit imprecise, I will argue that using descriptive complexity one can give a convincing precise definition. To give an algorithmic solution, I will introduce a few techniques from finite model theory, such as the Weisfeiler-Lehman algorithm, the guarded fragment and Ehrenfeucht-Fraisse games. Finally, I will demonstrate the resulting program on a few simple games and discuss other possible applications of descriptive complexity in program learning.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年9月14日(金曜日)
開催場所北海道大学工学部C304  ERATO セミナー室
開催時間15時30分-17時30分 
発表者鍋島 英知  
発表者の紹介山梨大学大学院医学工学総合研究部 准教授
タイトル高速 SAT ソルバーの原理 
発表の概要命題論理式の充足可能性を判定する問題(SAT)は,計算機科学における最も基本的で本質的な組合せ問題である.この SAT 問題を解くソルバーの性能は90年代末頃から飛躍的に向上しており,数百万変数からなる大規模な SAT 問題を解くことが可能になってきている.この性能向上をうけて,SAT はシステム検証やプランニング,スケジューリング,制約充足問題 (CSP) などの分野に応用され,近年急速に発展を続けている.本発表では,高速 SAT ソルバーの代表的な要素技術について紹介する.
    
閉じる

詳細

閉じる
開催日2012年9月13日(木曜日)
開催場所北海道大学工学部C304  ERATO セミナー室
開催時間15時30分-17時30分 
発表者谷 誠一郎  
発表者の紹介NTT コミュニケーション科学基礎研究所
タイトル匿名ネットワーク上の分散計算におけるメッセージ圧縮とその応用 
発表の概要多くの分散計算アルゴリズムは,ネットワークを構成するノードが識別子を持っている事を(当然のこととして)仮定している.このような仮定を置かない,より一般的な状況下における分散計算の能力を調べるために(あるいは逆説的に,ノード識別子を仮定することがどれほど本質的であるかということを調べるために)匿名ネットワーク(識別子を持たないノードで構成されるネットワーク)モデルが1980年にAngluin [STOC80] によって導入された.本発表では,匿名ネットワーク上での計算に関する基本的な性質,および,これまでに知られている主要な結果を述べるとともに,Yamashita-Kameda [PODC88] によって与えられた汎用アルゴリズムのメッセージ圧縮にOBDDを準既約にするアイデアが使えることを示す.さらに,量子分散アルゴリズムへの応用にも触れる.
    
閉じる

詳細

閉じる
開催日2012年9月12日(水曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間13時30分-15時30分 
発表者Prof. Rusins Freivalds  
発表者の紹介Institute of Mathematics and Computer Science, University of Latvia, Riga, Latvia
タイトルUltrametric automata and Turing machines 
発表の概要We introduce a notion of ultrametric automata and Turing machines using p-adic numbers to describe random branching of the process of computation. These automata have properties similar to the properties of probabilistic automata but complexity of probabilistic automata and complexity of ultrametric automata can differ very much.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年9月7日(金曜日)
開催場所北海道大学工学部C304  ERATO セミナー室
開催時間15時30分-17時30分 
発表者堀山貴史  
発表者の紹介埼玉大学
タイトル多面体の展開図の数え上げについて 
発表の概要多面体の展開図は,多面体を辺に沿って切り開くことで得られる多角形である.切り開く辺が異なっても,同型な展開図が得られることがある.例えば,立方体には 384通りの展開の仕方 (つまり辺の切り開き方) があるが,同型なものを除去することで,11種類の本質的に異なる (非同型な) 展開図が得られる.本講演では,任意の多面体に対し,本質的に異なる (非同型な) 展開図の個数を数え上げる方法について述べる.また,この手法をすべての整面凸多面体(正多面体,半正多面体,ジョンソン・ザルガラーの多面体,アルキメデスの角柱と反角柱) に適用し,それぞれについて本質的に異なる (非同型な) 展開図の個数を示す.たとえば,サッカーボールやフラーレン C_60 に見られる構造である,角切り二十面体には,375,291,866,372,898,816,000通り (3垓 7529京1866兆 3728億9881万 6000通り) の展開方法があるが,同型なものを排除することで3,127,432,220,939,473,920種類 (312京 7432兆 2209億 3947万 3920種類) の異なる展開図が存在する.また,角切り二十・十二面体には,21,789,262,703,685,125,511,464,767,107,171,876,864,000通り(2正 1789澗2627溝 0368穣 5125杼 5114垓 6476京 7107兆 1718億7686万 4000通り) の展開方法があるが,同型なものを排除することで181,577,189,197,376,045,928,994,520,239,942,164,480種類 (181澗5771溝8919穣 7376杼 0459垓 2899京 4520兆 2399億 4216万 4480種類) の異なる展開図が存在する.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年8月10日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間10時30分-12時00分 
発表者山西芳裕  
発表者の紹介九州大学生体防御医学研究所
タイトル薬・標的タンパク質間相互作用ネットワーク予測のための機械学習法 
発表の概要ほとんどの薬は低分子化合物であり、標的とするタンパク質との相互作用を介して、薬効や副作用という形で人体に影響を及ぼす。しかしながら、薬の分子は本来目標とした標的タンパク質にのみ相互作用するとは限らず、それ以外の複数のタンパク質に相互作用し予想外の作用を起こすことがある。そのため、薬・標的タンパク質間相互作用のゲノムワイドな同定は、創薬において最重要課題である。本研究では、薬・標的タンパク質間相互作用ネットワークを二部グラフと見なし、教師付き学習の枠組みで薬・標的タンパク質間相互作用ネットワークを予測する機械学習の手法を開発した。薬やタンパク質に関する異質な情報(薬の化学構造、薬効、副作用、タンパク質のアミノ酸配列など)を融合し、多様なファミリーのタンパク質に対して薬が相互作用するかどうかを判定する統計モデルが特長である。提案手法を、ヒトの酵素、イオンチャネル、G蛋白質共役型受容体、核内受容体などで構成される相互作用ネットワークに適用し、クロスバリデーション実験により提案手法の有効性を示した。更に網羅的な予測を行い、潜在的な薬と標的タンパク質の間における潜在的な相互作用を検出した。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年8月3日(金曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間10時30分-12時00分 
発表者相田 慎  
発表者の紹介豊橋技術科学大学 情報・知能工学系
タイトル福島復興プロジェクト「ふるさとめぐみラボ」 
発表の概要 いわきを拠点とする福島復興プロジェクト「ふるさとめぐみラボ」(http://furusatomegumi.com/ )とは、地元の方々へ身近に体感できる様々な科学コミュニケーションイベントを提供することで、「いわきの農業・漁業、豊かな自然、科学と文化を学び、楽しむ」環境づくりを企図した、地域密着型復興活動のヴァーチャルラボラトリである。
ラボの運営に関する議論は、ソーシャルメディア(Facebook)上で行う。その場において、科学への理解活動の在り方などを検討し、イベント・Web 等のコンテンツを策定をする。そして、それらをいわき在住メンバーが現地で実施する。このラボは、現地メンバーが主体であり、研究者ら他のメンバーは、あくまで舞台裏から現地をサポートする。
「科学」は表面上理性的であるが、現実の「科学の営為」は、個々の研究者が有する「知的好奇心」という感性によって駆動される。そこで我々は、放射線測定・科学実験・社会見学・談話会など、「理性(考える)と感性(感じる)」両面を十分考慮した多面的科学コミュニケーションを実践し、参加者の意見・不安・悩みなどの「感性情報」を汲み取り、ラボにフィードバックすることで、活動のさらなる向上を目指す。そのようなことも含め、ラボの方針・方法論・実践例などについて発表する。
接続サイト大阪,東京,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年7月6日(金曜日)
開催場所大阪オフィス
開催時間15時30分-17時30分 
発表者番原 睦則  
発表者の紹介神戸大学 情報基盤センター
タイトルSAT 技術を用いた組合せテストケース生成 
発表の概要命題論理の充足可能性判定問題 (SAT) は, 与えられた命題論理式の充足可能性を判定する問題であり,最初に NP 完全性が証明された問題でもある.SAT は人工知能および計算機工学における最も基本的な問題として,論理合成,システム検証,プランニング問題,スケジューリング問題,制約充足問題 (CSP),定理証明など,さまざまな分野に応用されている.
近年,106-107 個の変数をもつ大規模な SAT 問題を,非常に高速に解くことが可能な SAT ソルバーが実現され, これらの分野への実用的応用が急速に拡大している.なかでも,問題を CSP を用いてモデリング,CSP を SAT 問題に符号化 (SAT 符号化) した後,SAT ソルバーを用いて求解する CSP-SAT 型アプローチが成功を収めている.
組合せテスト (combinatorial testing) はソフトウェア/ハードウェアのテスト手法の一つである.この手法の特長は,欠陥の多くは少数のパラメータの組み合わせによって発生するという観測を元に,テストケースの増大を回避し,現実的かつ効果的なテストケースを生成できる点である.
本発表では,組合せテストのテストケース生成問題を例にとり,CSP-SAT 型アプローチを用いた解法について述べる.
接続サイト札幌,東京,九州
    
閉じる

詳細

閉じる
開催日2012年6月8日(金曜日)
開催場所ERATO C304会議室
開催時間15時30分-17時30分 
発表者瀧川一学  
発表者の紹介北海道大学 創成研究機構
タイトル創薬・生命科学におけるデータマイニング 
発表の概要生命科学では実験機器の進歩を受けて様々な量が計測できるようになっている。こうした実験の機械化・高精度化・大規模化により、科学の現場にも手に余る規模で多様な複雑データが生み出され、科学的発見もまたこうしたデータの高度な解析によって支えられるようになっている。本発表ではこの分野の背景やトピック、および、発表者が行った創薬における薬剤-標的ネットワークの解析事例について紹介する。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年5月30日(水曜日)
開催場所ERATO C304会議室

開催時間14時30分-16時00分 
発表者山室健  
発表者の紹介NTT サイバースペース研究所
タイトルCompression and Searches with Modern Processors (Practice and Implementation) 
発表の概要CPUのマルチコア/メニーコア化や様々な拡張命令の実装によるハードウェアの性能向上が積極的に行われている中,既存アルゴリズムのCPU特性考慮の有無での性能格差が問題視されている.そのような研究背景において,現在私が興味を持っている/取り組んでいる(主に整数列と文字列の)圧縮と探索に関するCPUの最適化手法や現在の課題に関する話題を取り上げる.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年5月30日(水曜日)
開催場所ERATO C304会議室
開催時間16時30分-17時30分 
発表者鬼塚真  
発表者の紹介NTT サイバースペース研究所
タイトル大規模データを対象とした分析処理の高速化に関する取り組み 
発表の概要近年,大規模データに対するコンピューティング技術が着目されている.我々は SQL を用いたOLAPによる統計処理やクラスタリング・ランダムウォークなどの機械処理を対象として,アルゴリズムによる高速化やMapReduce などの分散処理基盤の高速化技術に取り組んできている.本講演では,特に4つの具体的な技術について講演する.
1) Map Multi-Reduce: インクリメンタル処理による集約処理の高速化
2) PJoin: MapReduce におけるセミジョインビューを利用した結合処理の高速化
3) K-dash: Random Walk with Restart による高速 top-k 検索アルゴリズム
4) グラフクラスタリングの高速化アルゴリズム
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年5月24日(木曜日)
開催場所ERATO C304会議室 
開催時間15時30分-17時30分 
発表者竹内聖悟  
発表者の紹介JST ERATO湊離散構造処理系プロジェクト
タイトル第22回世界コンピュータ将棋選手権参加報告、及び、GPS 将棋のアルゴリズム 
発表の概要本年1月に将棋プログラム「ボンクラーズ」が元名人の米長邦雄日本将棋連盟会長を破り、ニュースとして大きく取り上げられた。近年の将棋プログラムの強さはプロレベルに近づきつつあり、プロ棋士との対局イベント電王戦が予定されるなど、コンピュータ将棋への注目度は高い。
第22回世界コンピュータ将棋選手権が本年5月3日から5月5日にかけ電気通信大学において開催された。優勝プログラムは、発表者が開発に参加しているGPS 将棋であり、上位5プログラムが電王戦へ出場することが決まった。
セミナーでは、第22回世界コンピュータ将棋選手権の雰囲気や参加チームの特徴を紹介し、参加報告を行う。その後、コンピュータ将棋で使われるアルゴリズムや技術について、特にGPS 将棋で使われている手法について説明を行う。また、コンピュータ将棋に関する雑多な話題について取り扱う予定である。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年4月20日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時30分 
発表者青木 洋士  
発表者の紹介立命館大学 理工学研究科
タイトル文字列の集合を表すSeqBDDに関する種々の技法について 
発表の概要ZDDから派生したデータ構造として,文字列の集合を表現するデータ構造Sequence BDD (SeqBDD)が提案されている.本発表では,SeqBDDに関する2つの技法について概説する.1つ目は,入力として与えられたSeqBDDが表す文字列の集合の要素を全て逆順にしたSeqBDDを効率良く構築する手法である.SeqBDDは,接頭辞による文字列検索は単一パスを辿る高速な手法で実現できるが,接尾辞による検索はそうではない.本アルゴリズムによって,文字列の集合に含まれる全ての文字列を逆順にした文字列の集合を効率良く構築できると,接尾辞を指定した文字列の検索を効率良く行うことができるようになる.2つ目は,SeqBDDの枝に属性として文字の写像を付与する手法である.この手法は,SeqBDDの各節点のもつ一部の情報を枝に抽出することによって,SeqBDDの接尾辞でより多くの同一な部分グラフが形成されるようにするものである.これにより,節点の共有が進み,SeqBDD構築の上での必要な節点数を削減することができる.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年4月13日(金曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時30分 
発表者福田健介  
発表者の紹介国立情報学研究所
タイトルインターネットバックボーントラフィックにおける異常検出 
発表の概要インターネット上では莫大な量のデータ(トラフィック)が日々やりとりされており,その多くは正常なデータであるが,異常なデータ(ウィルス,攻撃,フラッシュクラウド,設定間違いなど)が含まれている.このような異常トラフィックを効率良く発見し対処することはネットワークの運用に不可欠であり,これまでに多くの研究がなされている.本トークでは,我々が開発している複数の異常検出器(PCA, sketch-gamma, image-based)および,それらを組み合わせることで高精度の検出が可能となるベンチマークアーキテクチャについて説明する.また,10年にわたる公開トラフィックデータに対して異常検出器を適用して得られた異常トラフィックデータベースについての紹介も行う.
接続サイト東京,大阪,九州
    
閉じる

詳細

閉じる
開催日2012年3月30日(金曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間15時30分-17時30分 
発表者鈴木 真一朗  
発表者の紹介日本科学未来館
タイトルつながりをつくる -日本科学未来館の取り組み- 
発表の概要
接続サイト大阪,東京,九州(予定)
    
閉じる

詳細

閉じる
開催日2012年2月24日(金曜日)
開催場所東京サテライトオフィス(東工大)
開催時間15時30分-17時30分 
発表者美添 一樹  
発表者の紹介東京大学大学院情報理工学系研究科コンピュータ科学専攻
タイトル超並列分散モンテカルロ木探索 
発表の概要既存の多くの探索アルゴリズムが評価関数を用いて探索の方向を決定するのに対し、モンテカルロ木探索 (Monte-Carlo Tree Search; MCTS) はランダムサンプリングの結果によって探索の方向を決定するアルゴリズムである。MCTS は囲碁プログラムの棋力を飛躍的に向上させたことで特に有名であるが、囲碁以外の多くのゲーム、さらにゲームではないいくつかの問題にも適用可能であることが示されつつあり、汎用性の高い探索アルゴリズムとして期待されている。そのためにMCTSの高速化には大きな意義がある。

単一CPUコアの性能向上が頭打ちになり今後はコア数が増大すると思われている現状では、高速化手法としては並列化が有望である。我々は 1,000倍以上の速度向上を得ることを目標に分散並列 MCTS の研究を行っており、分散ハッシュテーブルを用いた並列探索手法 (Transposition Driven Scheduling; TDS)を MCTS に適用することによって人工的な探索木においては 1,200 コアを用いて600--740倍程度の高速化を達成した。

現在は我々の提案する手法を囲碁を含むいくつかの問題に適用することを計画している。本講演では研究の重要な背景であるコンピュータ囲碁の進歩についての解説を含めながら我々の提案手法について解説し、今後の展望についての議論を行う。
接続サイト札幌,大阪
    
閉じる

詳細

閉じる
開催日2012年2月20日(月曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間15時30分-17時30分 
発表者石畠正和  
発表者の紹介東京工業大学 大学院情報理工学研究科
タイトルBayesian networks and BDDs 
発表の概要Bayesian network (BN)は確率変数間の条件付き独立性を非循環有向グラフで表現するグラフィカルモデルである.BN上の周辺確率の計算は一般的に指数的な時間を要するが,これを高速に行う方法として論理に基づく手法がいくつか提案されている.これらの手法は,目的の確率計算式をまず論理式に変換し,その式をd-DNNFやBDD/ZDDなどの論理式をコンパクト表現するデータ構造を用いて圧縮する.そして目的の周辺確率を圧縮されたデータ構造上の動的計画法により高速に計算する.論理を用いる更なる利点として,通常のBNでは表現できないより細かい依存関係であるcontext specific independence や決定性を効率的に表現できることが知られている.一方,Stanford University の Donald E. Knuth はこれらの研究の流れとは別に,Donald Knuth's Annual Christmas Tree Lecture (2011/12/08) において "Bayesian trees and BDDs" と題し,BNの一種である Bayesian binary tree の周辺確率をquasi-BDD (QDD) を用いて高速に計算する方法を紹介した.本発表では従来の論理に基づく手法とKnuthの手法を比較し,更にKnuthの手法が同じ計算量で確率学習に一般化可能であることを示す.
    
閉じる

詳細

閉じる
開催日2012年2月10日(金曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間15時30分-17時30分 
発表者Charles Jordan  
発表者の紹介北海道大学大学院情報科学研究科
タイトルDescriptive Programming 
発表の概要Imagine we have some problem that we hope to solve, and so we write a program to compute the answer. Programming is time-consuming and error-prone, and developing optimized programs for hard problems is especially difficult.
In many cases, we don't care exactly how the answer is computed -- we just want to answer our problem. Instead of specifying exactly how the computation will proceed, couldn't we just pose our problem in some formal language and get an answer?
I'll describe recent joint work on a descriptive programming environment (DE). DE implements the objects of descriptive complexity theory in a programming environment, allowing users to automatically generate counter-examples to conjectures, examine reductions between problems, and rapidly develop reasonably-efficient programs for various problems.
DE is intended to be useful for researchers and students (we use it!), but it could be used more widely. We'll discuss related work and future plans, while focusing on examples where it could be useful. We encourage everyone to experiment with DE and would love to hear of any ideas, insights or improvements.
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2012年1月20日(金曜日)
開催場所東工大サテライトラボ
開催時間15時30分-17時30分 
発表者渋谷哲朗  
発表者の紹介東京大学医科学研究所ヒトゲノム解析センター
タイトル統計モデルと大規模パタンマッチングアルゴリズム 
発表の概要パタンマッチングのアルゴリズムの研究は、古くから現在に至るまで、多くの洗練されたアルゴリズムが提案されてきた。一方、機械学習などの分野では、データの統計的な偏りを利用して学習が行われることが多く、多くの学習手法において、そのデータの偏りを見出すのに、パタンマッチングの技術が様々に活用されてきた。その意味で、組み合わせパタンマッチングの研究分野と、統計モデルや機械学習の研究分野は切っても切れない関係にある。しかしながら、組み合わせパタンマッチング手法を活用した統計的学習の研究は多くあっても、統計モデルを活用したパタンマッチングアルゴリズム設計の研究は、単純な平均計算量解析を除き、ほとんどされてこなかった。本講演では、大規模データベース検索において、複雑な統計モデルを考慮することでアルゴリズムを高速化を実現した例として、モチーフデータベースおよびタンパク質立体構造データベースといった大規模実データベース上での検索アルゴリズム設計の例を示し、今後様々なデータベースが更に大規模化する中でのデータベース検索あるいはパタンマッチング技術の研究の方向について議論したい。
接続サイト札幌,大阪,九州
    
閉じる

詳細

閉じる
開催日2011年12月26日(月曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時30分 
発表者戸田貴久  
発表者の紹介京都大学大学院人間・環境学研究科
タイトル集合の2分割のなす分離族について 
発表の概要集合の2分割(すなわち、集合の2つの部分への分け方)は、組合せ論、離散数学、計算機科学などにおいて様々な形で現れる。例えば、2分割の集まりは、以下のように1つの論理関数に対応付けることができる:台集合の1つの元を任意に固定して、他の元を論理関数の変数とみなす;1つの2分割は、固定元を含む方の部分が真、含まない方が偽とすることで、変数への真理値割り当てを定める;よって、2分割の集まりを、論理関数を真にする真理値割り当ての集まりとみなすことで、1つの論理関数が定まる。

本講演では、2分割の集まりによって伴われる以下の分離概念を扱う:2分割の集まりFが分離族とは、台集合のどの2元もFに属する2分割によって分けることができるときをいう。本講演では、任意サイズの分離族の個数を求める公式を導く。この数え上げを、上述の対応により、真理値表の数え上げに帰着する論法を解説する。

本講演で扱われる分離概念は、1961年レニーによって始められた探索の理論において扱われる分離系の概念と密接に関係しているので、これら関連研究の解説もしたい。
接続サイト東京,大阪(予定)
    
閉じる

詳細

閉じる
開催日2011年12月19日(月曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間10時30分-12時00分 
発表者堀田 敬介  
発表者の紹介文教大学情報学部准教授
タイトル一票の格差の観点からの選挙区割と最適化 
発表の概要現在,衆議院議員は小選挙区制(300人)と比例代表制(180人)で選出されており,衆議院の小選挙区制における一票の格差は2009年選挙 時点で2.31倍である.衆議院小選挙区における一票の格差とは,300小選挙区の内,最大人口を有する選挙区を最小人口を有する選挙区で除した 値のことである.これが2倍を超えるという状態が,日本国憲法第14条「法の下の平等」に反するとして選挙の度に訴訟がおこされている.

衆議院が小選挙区制を導入したのは1994年であり,1996年10月選挙(2.31倍),2000年5月選挙(2.47倍),2005年9月選 挙(2.17倍),2009年8月選挙(2.31倍)の各衆議院選挙において一票の格差の訴訟が起こされた.最高裁判決は1996年,2000 年,2005年については「合憲」としたが,2009年については小選挙区制になって初めて「違憲状態」の判決を出した(ただし,選挙無効請求は棄却).衆議院小選挙区制の一票の格差については,その限界がどこにあるのかを,ルールに則って問題をモデル化し最適化を利用して限界を導出した根本・堀田による一連の定量分析研究がある.これにより,都道府県毎の現行の区割による格差と最適区割による限界格差の差,および全国格差の限界値が初め て明らかとなった.また定数配分・区割画定の方策を変更した場合に格差に与える影響など,様々な状況に置ける結果を示した.

ここでは,以上の結果や最新データによる結果を踏まえながら,現行制度の改善すべき点,どのような制度設計が格差を下げる上で望ましいのか,数理 計画手法や最適化がこの問題に対してどのように有効であるのか,などについて述べる.
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2011年11月25日(金曜日)
開催場所ERATOセミナー室
開催時間16時00分-18時00分 
発表者鷲尾 隆  
発表者の紹介大阪大学 産業研究所 教授, ERATO湊離散構造処理系プロジェクト グループリーダー, 北海道大学 客員教授
タイトル関数モデル上の統計的因果推論研究の現状(連携講座集中講義) 
発表の概要統計や人工知能の分野では,統計的観測データに含まれる複数変数の値の分布関係をうまく説明する因果構造候補を導出する因果推論やベイジアンネットワーク構造学習について,多数の手法が研究されてきた.しかしながら,マルコフ同値性や忠実性という前提条件が成立しないと,因果構造を曖昧さなく正確に導出することができなかった。これに対して,近年,観測データに含まれる複数変数の期待値の関係が関数モデルで表される場合について,変数値間の同時分布が持つある種の非対称性から,これらの制限を乗り越えて因果構造を導出可能な方法論が提案され,研究が盛んになっている.本講では,この分野の最近の幾つかの代表的研究について概観・議論すると共に,この新しい原理と従来の因果推論・構造学習の原理の関係を簡単に論ずる.更に,この新たな因果推論・構造学習手法の例として,関数モデルが複数2値変数間のブール関数であらわされる場合の我々の研究についても説明する.
    
閉じる

詳細

閉じる
開催日2011年11月24日(木曜日)
開催場所ERATOセミナー室
開催時間16時00分-18時00分 
発表者白井康之  
発表者の紹介JST ERATO湊プロジェクト 技術参事・研究員,北海道大学 客員教授
タイトル大規模実データを用いた解析事例の紹介(連携講座集中講義) 
発表の概要主に産業界で実際に収集・蓄積されたデータを用いた解析事例について紹介する.具体的には,WEB閲覧履歴や,携帯電話による行動履歴情報,ブログ,健康支援のための行動情報ログ等をもとに,クラス分類やエマージングパタン・系列パタン抽出,自然言語処理による特徴抽出等の技術を適用した例を紹介し,今後想定される大規模実データ解析における課題を明らかにする.
    
閉じる

詳細

閉じる
開催日2011年11月14日(月曜日)
開催場所ERATO C304会議室
開催時間15時30分-17時30分 
発表者吉澤 真吾  
発表者の紹介北海道大学 大学院情報科学研究科
タイトルアルゴリズムFPGA/LSIハードウェア実装の研究戦術 
発表の概要アルゴリズムの専用ハードウェア実装による高速化は数十年来続く汎用プロセッサの性能向上にもかかわらず現在でも多種多様な研究が盛んに行われている。
本講演ではアルゴリズムのFPGA/LSIハードウェア実装に関する設計開発手法や研究事例からハードウェア実装の研究戦術(ノウハウ)を紹介する。
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2011年10月27日(木曜日)
開催場所ERATO C304会議室
開催時間15時30分-17時00分 
発表者浅野哲夫  
発表者の紹介北陸先端科学技術大学院大学 教授
タイトル省メモリのための新たなアルゴリズム設計技法:制限された作業用メモリでアルゴリズムを如何に設計するか 
発表の概要IT技術の進歩により最近のディジタルカメラやiPadに代表される端末には非常に高度な機能が組み込まれている.そのようなソフトは組み込みソフトという名前で研究されてきたが,アルゴリズムを改良するというよりはメモリ節約の技術開発が主眼であった.計算機が誕生した頃には省メモリのテクニックが色々と開発されたが,メモリが安価になるにつれ,そのようなテクニックが忘れ去られようとしている.
本講演では,非常に限定された作業領域だけで問題を解くためのアルゴリズム技法を紹介したい.対数メモリアルゴリズムのような理論研究もあるが,本講演では実用的な観点からの省メモリアルゴリズム設計技法について述べる.
接続サイト東京,大阪,九州(予定)
    
閉じる

詳細

閉じる
開催日2011年10月14日(金曜日)
開催場所ERATOセミナー室
開催時間16時00分-18時00分 
発表者津田宏治  
発表者の紹介産業総合研究所 生命情報工学研究センター 主任研究員
ERATO湊離散構造処理系プロジェクト グループリーダー
北海道大学客員教授
タイトル複合ソート法による高速な全ペア類似度検索とその生物学データへの応用(連携講座集中講義) 
発表の概要大学院集中講義「大規模離散計算科学特論」の概要
産業プロセスの最適化や解析,マーケティング,バイオインフォマティクスなど,様々な情報処理の局面に現れる大規模な離散構造データ(計算機が行う論理的な処理を表現したデータ) を、数学的に簡約化し効率よく計算するための各種のアルゴリズム技術とその応用について解説する。データマイニング、統計数理、機械学習、列挙アルゴリズム、簡潔データ構造、確率計算モデルなどを含む分野横断的な基盤技術とそれらを用いた最新の研究成果、および産業界への実応用の事例について学ぶ。
    
閉じる

詳細

閉じる
開催日2011年10月12日(水曜日)
開催場所北大工学部C304 ERATOセミナ室(TV会議中継あり)
開催時間15時30分-17時30分 
発表者富田 悦次  
発表者の紹介電気通信大学 先進アルゴリズム研究ステーション/JST ERATO 湊離散構造処理系プロジェクト/ 東京工業大学 大学院 情報理工学研究科
タイトル最大クリーク問題の多項式時間的可解性について 
発表の概要対象グラフ中に所定サイズのクリークが存在するか否かを判定する最大クリーク問題は,典型的なNP完全問題であり,多項式時間的に本問題を解くことはほぼ不可能であると強く推測されている.そこで,出来る限り自然で緩やかな条件として,どの様な場合ならばこのNP完全問題が多項式時間的に可解と証明出来るかを示すことは,重要な問題となる.

本発表では,この問題に対して従来の結果,および,下記の新しい結果を示す.これらは,節点数$n$のグラフ中の極大クリークを$O(3^{n/3})$時間で全列挙するアルゴリズムCLIQUES (Tomita et al., Theoretical Computer Science,vol.363, 2006) を基礎としている.``節点数$n$の一般グラフにおいて,任意の隣接2節点$p,q$に対して $\min\{deg(p), deg(q)\} \le 2.994d \lg n$ ($d \geq 0$: 定数)なる条件が満たされているとき,このグラフの最大クリーク問題は$O(n^{ 2+\max \{d, 1\} })$なる多項式時間で可解である. ただし,$deg(r)$は節点$r$の次数."

ここで,隣接2節点$p,q$に対する条件において,$\max \{deg(p), deg(q)\} =deg(q)$であり,節点$q$が$deg(q)$よりも次数の大きい節点に隣接していないならば,節点$q$に対する次数の条件は何ら課さない.これまでに,全ての節点次数に対して同様な制限を課すことにより,同問題の多項式時間的可解性を示してきたが,本発表では,グラフ中で非常に次数の大きい(ハブに相当する様な)節点が散在しても,そのグラフが前記条件を満たしていさえすれば,多項式時間的可解性は保証されることを意味している.
接続サイト東京,大阪,埼玉大学
    
閉じる

詳細

閉じる
開催日2011年9月30日(金曜日)
開催場所ERATOセミナー室
開催時間15時30分-17時30分 
発表者千葉 英史  
発表者の紹介法政大学 理工学部 経営システム工学科
タイトル液晶製造に関連した最適化問題としての定式化と効率的な解決法の提案 
発表の概要液晶や半導体などの製造は,複数の専用処理装置を介して行われる.各処理は全自動化されており,問題が生じたときにはその都度,専門家が対応してきた.しかし,問題が個別に解決されても,全体として真に最適稼働しているかどうかには疑問が残る.ここでは,全体としての生産性を向上させるために,我々が最近取り組んできた試みを紹介する.
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2011年9月14日(水曜日)
開催場所ERATO C304会議室
開催時間15時00分-17時00分 
発表者穴井 宏和  
発表者の紹介富士通研究所/九州大学
タイトルQEの計算アルゴリズムとその応用~数式処理による最適化 
発表の概要最近、計算機代数いわゆる数式処理の手法が産業上のいろいろな問題に対して用いられるようになってきた。本講演では、最適化問題の代数的な解法でもある限量記号消去(quantifier elimination:QE)について紹介する。限量記号消去は、一階述語論理式を対象として、限量記号を消去した等価な式を計算するアルゴリズムである。限量記号消去を活用することで可能となる記号最適化・パラメトリック最適化手法を説明し、その有効性について具体的な応用例を取り上げながら解説する。
    
閉じる

詳細

閉じる
開催日2011年8月30日(火曜日)
開催場所ERATO C304会議室
開催時間10時30分-12時00分 
発表者佐久間 淳  
発表者の紹介筑波大学システム情報工学研究科
タイトル知識発見におけるデータ匿名化とプライバシ保護データマイニング 
発表の概要Webサービスやセンシング技術の発展により、経済活動や人間同士の関係、人間とサービスの関係など、個人の生活に密接に関係した情報の蓄積が可能になりつつあります。詳細度の高い個人情報は悪用を防ぐための慎重な取り扱いを要しますが、私たちの生活を支援する画期的なサービスを生み出す源泉ともなります。講演では、このような個人情報の匿名化やランダム化、暗号プロトコルを使ったプライバシ保護データマイニングなどの知識発見技術を紹介します。
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2011年8月29日(月曜日)
開催場所ERATO C304会議室
開催時間15時30分-18時00分 
発表者堀山 貴史  
発表者の紹介埼玉大学
タイトル最小/最大の直径、幅および包囲長方形を持つ正多面体の展開図について 
発表の概要正多面体の展開図は、正四面体には2種類、正六面体と正八面体には11種類、正十二面体と正二十面体には43,380種類が存在する。本発表では、正四面体、正六面体、正八面体、正十二面体、正二十面体のそれぞれについて、直径や幅、面積最小の包囲長方形や周長最小の包囲長方形がそれぞれ最小または最大となる展開図を示す。
    
閉じる

詳細

閉じる
開催日2011年8月26日(金曜日)
開催場所ERATO C304会議室
開催時間15時30分-17時30分 
発表者加藤直樹  
発表者の紹介京都大学大学院工学研究科建築学専攻
タイトル最適避難計画の理論と応用 
発表の概要3月11日に東日本を襲った大地震、大津波からの教訓として、地震や津波などの大規模災害発生に伴い、迅速に避難所に避難することが重要であることが再認識されています。私の研究室では最速な避難計画をネットワークフローを用いて作るという問題にこの5年間取り組んできました。今回は理論的な話もいたしますが、実データを用いた地震や津波からの最適避難計画の実験結果についても重点をおいてお話しする予定です。
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2011年8月25日(木曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間10時30分-12時00分 
発表者中原 啓貴  
発表者の紹介九州工業大学
タイトル多分岐決定図に基くプロセッサとその応用 
発表の概要既約順序付き2分岐決定図(BDD: Binary Decision Diagram)とは,ブール関数を表現するのに使われるデータ構造であり,LSI設計の論理検証や制約充足問題を解くために利用されている.また, BDDよりも高速に評価できる多分岐決定図(MDD: Multi-valued Decision Diagram)が提案されている.
講演では, MDDに基くプロセッサとその応用について述べる.まず, BDDとMDDに基くプロセッサについて述べ,MDDに基くプロセッサが優れていることを示す.次に, MDDに基くプロセッサの応用分野について述べ,最後に, 今後の課題について述べる.
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2011年8月25日(木曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間15時30分-17時30分 
発表者岸本章宏  
発表者の紹介東京工業大学大学院情報理工学研究科数理・計算科学専攻助教
タイトルDepth-First Proof-Number Search in the Presence of Repetitions 
発表の概要Depth-first proof-number search (df-pn) is a powerful AND/OR tree search algorithm proven to be effective in solving positions in games. However, df-pn has a notorious problem of infinite loops when applied to domains with repetitions. Df-pn(r) practically cures it by ignoring proof and disproof numbers that may lead to infinite loops.

In this talk, I point out that df-pn(r) has a serious issue of underestimating proof and disproof numbers, while it also suffers from the overestimation problem occurring in directed acyclic graph. I present two practical solutions to these problems. While bypassing infinite loops, the threshold controlling algorithm (TCA) solves the underestimation problem by increasing the thresholds of df-pn. The source node detection algorithm (SNDA) detects the cause of overestimation and modifies the computation of proof and disproof numbers. Both TCA and SNDA are implemented on top of df-pn to solve tsume-shogi (checkmating problem in Japanese chess). Results show that df-pn with TCA and SNDA is far superior to df-pn(r). Our tsume-shogi solver is able to solve several difficult positions previously unsolved by any other solvers.
接続サイト東京,大阪,九州
    
閉じる

詳細

閉じる
開催日2011年8月24日(水曜日)
開催場所ERATO C304会議室
開催時間15時00分-18時00分 
発表者定兼 邦彦   
発表者の紹介国立情報学研究所 情報学プリンシプル研究系准教授
タイトル簡潔データ構造 
発表の概要簡潔データ構造とは,データを極限まで圧縮しつつ,様々な問い合わせを高速に実現できるデータ構造である.本講義では,基本的な簡潔データ構造とそれらの応用を説明する.
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2011年8月23日(火曜日)
開催場所ERATO C304会議室 
開催時間10時30分-12時00分 
発表者杉山将  
発表者の紹介東京工業大学 計算工学専攻
タイトル確率密度比を用いた統計的機械学習の新しいアプローチ 
発表の概要統計的機械学習のほとんどの課題は,データの生成確率分布の推定を介して解決することができる.しかし,確率分布の推定は機械学習における最も困難な問題の一つとして知られているため,現実的には分布推定を回避しながら対象となる課題を解決することが望ましい.例えば,パターン認識法の一つであるサポートベクトルマシンでは,データの生成確率を推定することなくパターン認識に最低限必要な決定境界を直接学習することにより,高い汎化性能の獲得を可能にした.

これまで,分布推定を介さない学習アルゴリズムの開発は,個々の機械学習課題に対して個別に行われてきた.それに対し我々は,様々な機械学習課題に対して統一的に分布推定を避けることのできる汎用的な枠組みを提案してきた.この枠組みでは,確率分布でなく確率密度関数の比を考え,分子と分母の確率密度関数を推定することなくそれらの比を直接推定する.密度比推定によって,重点サンプリング(共変量シフト適応,ドメイン適応,マルチタスク学習),ダイバージェンス推定(二標本検定,外れ値検出,変化点検知),相互情報量推定(独立性検定,独立成分分析,特徴選択,十分次元削減,因果推定),条件付き確率推定(確率的パターン認識,条件付き密度推定)など様々な機械学習課題が解決できることを示してきた.従って,我々の開発してきた密度比直接推定手法を用いることにより,上記の機械学習課題群を一挙に,かつ,高精度に解決できるようになった.

本講演では,この枠組の全体像を紹介すると共に,最新の研究成果についても述べる.
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2011年8月23日(火曜日)
開催場所ERATO C304会議室
開催時間15時30分-17時30分 
発表者伊藤大雄  
発表者の紹介京都大学大学院情報学研究科 准教授
タイトル定数時間アルゴリズムとその基本定理 --- 正則性補題と分割定理 
発表の概要本講演では、定数時間で問題を解くテクニックとそれを支える基本定理を紹介する。「定数時間」とは、つまり「インスタンスのサイズがどんなに大きくても、それに関係ない定数の計算時間で問題を解く」という意味である。直感的にはこれは不可能であるが、次に示す二つの緩和を入れることで達成する。

1. 与えられたインスタンス(例えばグラフ)が性質P(例えば平面性)を満たすか、それよりε遠隔(ε-far)である(ただし0<ε<1は任意の定数)かを区別すれば良い。
2. 確率2/3以上で成功する乱択アルゴリズムである。

あるインスタンスがある性質Pに対してε遠隔であるとは、インスタンスの表現のうち少なくともεの割合を書き換えないと性質Pを満たさないことを言う。定数時間で作動するということはアルゴリズムはインスタンスの情報を全て見ることはできず、オラクルによって知る。例えば密なグラフモデルの場合には、任意の2節点i,j間に枝があるか否かをオラクルは答えてくれる(節点数nは既知とする)。入力の表現にNバイト用いる場合、オラクルに与える質問回数がo(N)であるようなものを、検査(testing)アルゴリズムと言う。特に質問回数が定数であるものが典型的であり、本講演でもそれを扱う。

グラフの検査問題には、密グラフの場合と疎グラフの場合と二つの大きな枠組みがある。密グラフについては、遺伝的(hereditary)な(すなわち節点の削除に閉じている)性質はすべて定数時間検査可能であり[Alon-Shapira, FOCS05]、疎グラフの場合には、マイナーについて閉じている性質はすべて定数時間で検査可能である[Benjamini-Schramm-Shapira, STOC08]ことが分かっている。どちらもグラフ理論の非常に重要な基本定理、すなわち前者は正則性補題(Regularity Lemma [Szemeredi, 78])に、後者は分割定理(Separator Theorem [Alon-Seymour-Thomas, STOC90])に基づいている。本講演では、この二つの基本定理を(できれば証明も)説明し、それらを如何に使って定数時間検査を達成するかを説明する。
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2011年8月9日(火曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間15時30分-17時30分 
発表者宇野毅明  
発表者の紹介国立情報学研究所情報学プリンシプル研究系
タイトル必ず2つ以上子供を持つ木の圧縮 
発表の概要子供を持つ頂点(内点)が、必ず子供を2人以上持つような木をreduced tree と呼ぶ。reduced tree は、PQ-tree や cograph といった、グラフで構造を表現するときに良く現れる構造である。本発表では、葉を m 枚持つ reduced tree を 2m ビットでエンコード、つまり 2m ビットの(他のreduced tree と必ず異なる)文字列に変換する方法について述べる。また、この方法を拡張し、直並列グラフを 2.5283 ビットでエンコードする方法についても述べる。
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2011年7月29日(金曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間15時30分-17時30分 
発表者竹内 聖悟  
発表者の紹介東京大学大学院総合文化研究科
タイトルモンテカルロ木探索の将棋への応用とパラメータ調整 
発表の概要近年、コンピュータ囲碁においてモンテカルロ木探索と呼ばれるゲーム木探索手法が成功を収めている。これは、終局までゲームをシミュレーションし、複数回行った結果の勝率から着手を決定するモンテカルロ法とゲーム木探索を組み合わせた手法である。今回の発表では、モンテカルロ木探索のコンピュータ将棋への応用と探索パラメータの調整について発表する。
将棋へのモンテカルロ木探索の応用については、他のゲームでモンテカルロ木探索を用いる際に使われた工夫と将棋に向けた改良について説明する。
パラメータ調整については、コンピュータ囲碁においてモンテカルロシミュレーションに関するパラメータを調整したSimulation Balancing、コンピュータチェスにおいてアルファベータ探索での枝刈に関するパラメータを遺伝的アルゴリズムで調整した研究を紹介し、それらのモンテカルロ木探索将棋への応用と、発表時点での実験結果について発表する。
接続サイト東京,関西,九大(伊都キャンパス) [予定]
    
閉じる

詳細

閉じる
開催日2011年7月15日(金曜日)
開催場所ERATOセミナー室
開催時間15時30分-17時30分 
発表者西野 正彬  
発表者の紹介NTT サイバーソリューション研究所
タイトルZDDを用いた効率的な集合拡張の計算 
発表の概要ZDDをデータ構造として用いることで集合拡張を効率的に計算する手法についてお話ししたいと思います.集合拡張とは,あるアイテムの集合と,種集合とよばれるアイテム集合の小さな部分集合を入力して受け取り,種集合と似たアイテムの部分集合を出力するアルゴリズムのことをいいます.集合拡張を実行する際には,アイテム集合を表す行列と,種集合ごとに計算される実数ベクトルとの乗算によるスコア算出を繰り返し実行する必要があります.この計算に必要な計算回数を,アイテム集合を表す2値行列をZDDを用いて表現し,ZDDの構造を利用して実数ベクトルと行列との積を計算することによって削減する手法を検討しました.
接続サイト東京,大阪,埼玉大学
    
閉じる

詳細

閉じる
開催日2011年7月8日(金曜日)
開催場所ERATOセミナー室
開催時間15時30分-18時00分 
発表者松崎和賢  
発表者の紹介三菱総合研究所 情報技術研究センター
タイトルデータ匿名化の現状に関する一考察 
発表の概要パーソナル情報(単独で個人情報に該当するか否かにかかわらず、個人と連結可能な情報)を匿名化して、社会的に役立てる形で二次利用するという動きが、世界的に進展している。医療情報を製薬業界での分析・研究用途に匿名化して提供する事例や、公的統計のミクロデータを研究用途に匿名化して提供する事例が、代表的である。
本発表では、平成22年度に実施された『パーソナル情報利用のための調査研究』(日本情報処理開発協会)での実地調査などで得た知見を基にして、医療と統計分野でのパーソナル情報の匿名化を取り巻く状況と、現場で利用されている技術についてご紹介する。
また、国内のパーソナル情報利用を検討する動向についても触れ、匿名化の技術面での検討状況をご紹介する。その上で、スケールアウトする匿名化方式を導入する試案についても最後に触れる。(予定)
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2011年7月1日(金曜日)
開催場所ERATOセミナー室
開催時間15時30分-17時30分 
発表者湊 真一  
発表者の紹介北海道大学大学院情報科学研究科 教授 兼 JST ERATO湊離散構造処理系プロジェクト研究総括
タイトル米国CMU訪問および国際会議SAT2011の参加報告 
発表の概要 本年6月23,24日に研究総括の湊が、米国ピッツバーグのカーネギーメロン大学
(CMU)を訪問し、BDD演算アルゴリズムを最初に考案したBryant教授と面会し、
ERATOの紹介と離散構造処理系に関する技術討論を行った。さらに同大学所属で
チューリング賞受賞者のEd Clarke教授を始めとする数名の関連分野の教授と技
術討論・情報交換を行ってきたのでその様子を報告する。なお、偶然同じ日に
CMUにオバマ大統領が来訪し、米国の科学技術プロジェクトに関する演説を行っ
たので、その内容と背景についても簡単に述べる。
 上記のCMU訪問に先立ち、6月19~22日にデトロイト近郊のミシガン大学で開催
された国際会議SAT2011(http://www.lri.fr/SAT2011/)に参加し、湊が考案した
順列集合を処理する新しいBDD(πDD)の論文発表を行うとともに、SAT(充足可能
性問題)に関する研究コミュニティの最近の動向について情報収集を行ってきた
ので、こちらについても報告する。同会議併催のSAT competition の今年度の結
果や、日本からの参加者の活動状況などについても述べる。
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2011年6月17日(金曜日)
開催場所ERATOセミナー室
開催時間15時30分-17時30分 
発表者岩下洋哲  
発表者の紹介JST ERATO湊離散構造処理系プロジェクト 研究員
タイトルZDD-Mate法(仮称)によるグラフのパス列挙 
発表の概要与えられたグラフの上を探索しながらパス集合のZDDを直接組み上げていくKnuthのパス列挙法やMate-ZDD法などに対して、本手法ではパス集合のスーパーセットを表すZDDを構築した後でそのZDD構造の上を探索します。スーパーセットを表すZDDは特定の条件で枝刈りされた後の探索木とも見ることができるため、探索処理の計算コストは従来よりも小さくなることが期待されます。
この技術はまだ実験段階のものですので、基本アイディアと現在までの結果をご紹介した後、今後の改善や応用についても議論させて頂ければと思います。
接続サイト東京,大阪,九州
    
閉じる

詳細

閉じる
開催日2011年5月24日(火曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間15時30分-16時45分 
発表者Prof. Neil Immerman  
発表者の紹介Professor, University of Massachusetts Amherst
タイトル"P versus NP: Approaches, Rebuttals, and Does It Matter?" 
発表の概要NP contains all those problems that we could efficiently solve if "guessing were free", i.e., all those problems whose solutions we could recognize as correct if they were given to us in an appropriate format and context. We've known since 1971 that a large class of important combinatorial problems including boolean satisfiablity (SAT) are NP complete, i.e, hardest problems in NP.
If any of these had a solution in P, then so would all other problems in NP.

How hard is SAT, or any other NP-complete problem? It is well believed that P is not equal to NP and that SAT requires exponential time on some hard instances. However, SAT solvers are now in practical use as general problem solvers, currently working even on instances with a million variables.

I will explain some of these issues, laying out what we do know, what we do not know, and what we hope to understand once the P versus NP question, together with many similar but less famous open questions, are finally resolved. At the same time, this talk will present a survey of descriptive complexity -- the logical approach to complexity that I have been pursuing for years.
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2011年5月20日(金曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間15時30分-17時30分 
発表者川原 純   
発表者の紹介JST ERATO湊離散構造処理系プロジェクト 研究員
タイトルZDDを用いたパスの列挙と索引生成 
発表の概要グラフ中の2点間の全パスを列挙する問題は,多くの応用が存在する重要な問題
である.一般に解の数は極めて多く,従来手法では数十節点を超えるグラフの
パス列挙は不可能であった.近年 Knuth は The Art of Computer Programming 4-1 の演習問題として,従来手法と比べると非常に高速なアルゴ
リズム Simpath を示した.例えば 10×10 のグリッドグラフ(121節点)の対
角2節点間の全パスは,従来手法では1日以上かかるが,Simpath では1秒以内で
列挙する.解となるパス全体の集合は,1つのパスを枝の集合と考えることで,
枝の集合族とみなせ,ZDD として表すことができる。Simpath アルゴリズムは
そのような ZDD を決められた枝順にトップダウンに構築する手順であると解釈
できる.解はZDD として出力されるので,解の列挙のみならず,解の索引生成
やフィルタリングも容易に行える.本発表では,まず Simpath アルゴリズムを
紹介し,次に Simpath を基にした,ZDD の基本演算のみを用いてボトムアップ
に ZDD を構築することでパス列挙を行うアルゴリズムを提案する.ボトムアッ
プ的な構築法では,Simpath のトップダウン的な手法より計算速度は低下する
が,枝の使用条件を柔軟かつ簡潔に記述でき,例えば,特定の2本の枝を同時に
使用しない等の条件付きパス列挙が容易になる.これらの手法と既存手法との
比較実験を行い,ZDD によるパスの列挙手法の利を論ずる.さらに,パス列挙
アルゴリズムのネットワーク信頼性評価等への応用についても述べる.
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2011年4月21日(木曜日)
開催場所ERATO C304会議室
開催時間15時30分-17時30分 
発表者湊 真一  
発表者の紹介北海道大学大学院情報科学研究科 教授 兼 JST ERATO湊離散構造処理系プロジェクト研究総括
タイトルπDD: 順列集合を演算処理する二分決定グラフについて 
発表の概要「順列」は「組合せ」と並んで離散数学や計算機科学の基礎をなす重要な概念で
あり,ソーティング,順序付け,マッチング,符号化等,多くの局面に現れる.
本発表では,「πDD」(順列二分決定グラフ)と呼ぶ新しい二分決定グラフを提
案する.πDDは,多数の順列を要素として含む順列集合をコンパクトかつ一意に
表現し,演算処理を効率よく行える.中でも,全ての順列の合成を求める直積演
算は強力で実用的である.本発表ではπDDの基本的なデータ構造と演算アルゴリ
ズムを示し,さらに簡単な応用例として,あみだくじの解析およびルービックキュー
ブの解析の実験結果を示す.πDDは数十億もの膨大な個数の順列を現実的な計算
時間と記憶量で列挙し,さらに順列集合演算を適用して様々な制約充足問題を解
くことができる.
接続サイト東京, 大阪, 九州
    
閉じる

詳細

閉じる
開催日2011年4月15日(金曜日)
開催場所関西サテライトラボ
開催時間15時30分-17時30分 
発表者梅谷 俊治   
発表者の紹介大阪大学 大学院情報科学研究科 情報数理学専攻
タイトル大規模な集合被覆問題に対する数理計画法に基づく発見的解法 
発表の概要集合被覆問題(set covering problem; SCP)は,乗務員スケジューリング問題や配送計画問題,施設配置問題,データの論理的解析など多くの現実的な問題を応用に持つ基本的な組合せ最適化問題の1つである.一方で,集合被覆問題はNP困難のクラスに属する問題であり,現実的な計算時間 で厳密な最適解を求めることは困難である.しかし,近年の最適化手法の進歩により,線形計画緩和やラグランジュ緩和を利用した高性能な発見的解法が提案され,実際の配送計画や乗務員スケジューリングで生じる大規模な(100万変数程度の)問題例でも,短時間で精度の高い近似解 が得られるようになった.本発表では,集合被覆問題に対する最適化手法を用いた効率的な発見的解法について紹介した後に,集合被覆問題の拡張に対する発見的解法の最近の進展について報告する.

接続サイト札幌,東京,九州
    
閉じる

詳細

閉じる
開催日2011年4月8日(金曜日)
開催場所関西サテライトラボ
開催時間15時30分-17時30分 
発表者Michael Houle  
発表者の紹介国立情報学研究所
タイトルIntrinsic Dimensionality and its Applications to Databases and Data Mining 
発表の概要In recent years, important applications in the areas of machine learning, data mining, and bioinformatics have been developed that rely on the search for similarities among data structures as a fundamental operation. Typically, the computation of structural similarity is performed using a computationally-expensive exhaustive search over all possibilities. Effective indexing methods for structural similarity search, together with appropriate measures of inter-structure similarity, could potentially have a significant impact on the overall performance of such applications.

In this presentation, we propose a general framework within which the effectiveness of similarity search and other data operations can be assessed, independently of the nature of the data being considered. Within this framework, we discuss how a form of intrinsic dimensionality in the neighborhood of a test or query item, the "stereological dimension", can be assessed using two measurements of the distance and ranks of items within the neighborhood. Examples will be shown of the use of stereological dimension in the design and performance analysis of a variety of applications, such as similarity search, aggregation of search results, and anomaly detection (a paper describing the latter application received the Best Research Paper Award" at IEEE ICDM 2010). The presentation will conclude with a discussion of the potential of this framework for the development of effective applications based on structural similarity search.
接続サイト札幌,東京
    
閉じる

詳細

閉じる
開催日2011年3月23日(水曜日)
開催場所ERATO セミナー室
開催時間15時30分-17時00分 
発表者湊 真一  
発表者の紹介北海道大学大学院情報科学研究科 教授 兼 JST ERATO湊離散構造処理系プロジェクト研究総括
タイトルBDD/ZDDパッケージ講習会(第二回) 
発表の概要
接続サイト東京,大阪,埼玉大学
    
閉じる

詳細

閉じる
開催日2011年3月22日(火曜日)
開催場所北海道大学工学部C306  ERATO セミナー室
開催時間15時30分-17時00分 
発表者湊 真一  
発表者の紹介北海道大学大学院情報科学研究科 教授 兼 JST ERATO湊離散構造処理系プロジェクト研究総括
タイトルBDD/ZDDパッケージ講習会(第一回) 
発表の概要
接続サイト東京,関西,埼玉大学
    
閉じる

詳細

閉じる
開催日2011年3月7日(月曜日)
開催場所北海道大学 ERATO C306会議室
開催時間15時30分-17時30分 
発表者 Dr. Benjamin Rossman   
発表者の紹介Department of Electrical Engineering and Computer Science, MIT
タイトルAverage-case complexity of detecting cliques  
発表の概要We investigate the average-case complexity of the k-CLIQUE problem on random graphs with an appropriate density of edges. Our results are lower bounds of n^{k/4} for two well-studied classes of circuits: bounded-depth circuits and monotone circuits. Besides being the first lower bounds for k-CLIQUE in the average-case (and moreover essentially tight), these results lead to a new "size ierarchy theorem" for AC^0 and settle a longstanding open question in finite model theory.
    
閉じる

詳細

閉じる
開催日2011年2月28日(月曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間15時30分-17時30分 
発表者倉井龍太郎  
発表者の紹介株式会社はてな
タイトルWebサービス事業者の最新動向と株式会社はてなの研究開発事例 
発表の概要インターネットの本格的な普及から十数年が経過し、成熟しつつあるように見えるWebサービス業界ですが、現在も驚くべき速度で技術革新や新たなサービスが生まれています。なかでも Twitter や Facebookといったリアルタイム性が高く、そしてソーシャルな関係性をもったサービスは高い関心を集めています。
一方で各サービスが扱うデータベースはより大量かつ高速な処理が求められており、RDBMSだけでは対処できず、NoSQLと呼ばれるSQLに代わるDBシステムが台頭しはじめています。またWebサービスを通じて集積された巨大なデータに対してはMapReduce(Hadoop)を利用したデータマイニング・機械学習が、クライアントサイドに対しては、スマートフォンに向けたアプリケーション開発が注目されるなど、幅広く様々な技術がWeb業界と関わるようになっています。今回はこれらの現在注目されている技術やサービスについて、株式会社はてなでの研究開発事例も交えながら解説します。
また、はてなでの研究開発事例については
- 現在Webで注目されているドキュメントの発見
- ドキュメントのクラスタリングとトピック抽出といった研究事例
- スマートフォンアプリ開発動向
について説明させていただきます。
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2011年2月24日(木曜日)
開催場所ERATOセミナー室
開催時間16時00分-18時00分 
発表者植野 剛  
発表者の紹介京都大学情報学研究科論理生命学講座, 2011.4.1より ERATO湊離散構造処理系プロジェクト 研究員
タイトル統計学習による強化学習の考察 
発表の概要強化学習は心理学、神経科学,統計,コンピュータ科学,最適制御などさまざ まな研究分野に起因する機械学習法の1つである.近年,強化学習は未知の環 境に置かれた学習エージェントが自律的に行動方策を学習する方法として, 人 工知能分野でスタンダードなツールとしてとなるまで発展しており,様々な実問題に応用され成果を挙げている.

現在,強化学習アルゴリズムにおいて中心的な役割を担っているのはTD学習に 代表されるモデルフリー方策評価法を組み込んだ強化学習法である.この手法は方策の"価値"(期待累積報酬和)の推定を行う,(モデルフリー)方策評価と,推定した価値に基づく方策の改善, 方策改善を交互に行うことで方策の学習を行う枠組みである.この学習法の最大の特長は方策評価時にタスク環境の推定せずに現在の方策の”価値” を推定する点である,つまりタスク環境のダイナミクスを知ることなく,方策の学習を行うことができる.この望ましい性質は,多くの研究者を魅了し,多くの新しいモデルフリー方策評価法とそれを組み込んだ強化学習法がこれまで提案されている.しかしながら, 提案されたモデルフリー方策評価アルゴリズムの理論解析,特に価値推定の推定精度に関しては ほとんど検証されておらず,アルゴリズム間の推定精度による比較など理論的 な考察は十分に行われていない.

本発表ではモデルフリー方策評価法に着目し,統計学習の観点から統計的な性質を考察する.本研究の主たるアイディアはモデルフリー方策評価問題をより一般的なセミパラメトリック統計モデルに基づく統計推定問題として再定式化することにある.これによりこれまで統計学習分野で培われてきた統計解析手法をそのまま応用することを可能にし,モデルフリー方策評価法全体に共通する統計的な性質を明らかにすることができる.

本発表は次の3部構成で発表する.まず第1部ではモデル方策評価に基づく強化学習法の簡単な導入を行い, その問題点を明らかにする.第2部では,我々の提案手法であるセミパラメトリック統計推論に基づく方策評価法を紹介し,その統計的な性質を明らかにする.第3部では実応用として2足歩行ロボットの歩行学習について発表する.
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2011年2月7日(月曜日)
開催場所ERATOセミナー室
開催時間14時30分-16時30分 
発表者Dr. Paula Brito  
発表者の紹介Associate Professor in Statistics and Data Analysis at the Faculty of Economics, The University of Porto
タイトルIntroduction to Symbolic Data Analysis (An interaction movement between statistics and data processing) 
発表の概要In classical data analysis, data is represented in a n×p matrix where n individuals (in rows) take exactly one value for each variable (in olumns). However, this model is too restrictive to represent complex data, which may comprehend variability and/or uncertainty. The need to consider data that contain information which cannot be epresented within the classical framewok lead to the development of Symbolic Data Analysis. Symbolic data extend the classical model, by allowing multiple, possibly weighted, values for each variable. New variable types have therefore been introduced, which allow us to represent ariability and/or uncertainty inherent to the data:multi-valued variables, nterval variables and modal variables. This approach is of particular and rowing interest in the analysis of huge sets of data, recorded in very large databases, when the units of interest are not the individual records (the microdata), but rather some second-level entities. For instance, in a database of credit card purchases, we are probably more terested in describing the behaviour of some person (or even some pre-defined class or group of persons) rather than each purchase by itself. By aggregating the purchase data for each person (or group), we obtain the information of interest; the observed variability for each person or within each group is preserved, and ith is of utmost importance. But are we still in the same framework when we allow for the variables to take multiple values? Are the definitions of basic statistical notions still so straightforward? What properties remain valid? In this talk we will discuss some issues that arise when trying to apply classical data analysis techniques to symbolic data. The central question of the evaluation of dispersion, and the consequences of different possible choices in the design of multivariate methods, will be addressed. Dispersion is a key issue in clustering, since the result of any lustering method depends heavily on the scales used for the variables; natural clustering structures can sometimes only be detected after an appropriate rescaling of ariables. The standardization problem has been addressed by De Carvalho, Brito & Bock, and three tandardization techniques for interval-type variables have been proposed. Furthermore, many exploratory ultivariate methodologies rely heavily on the notion of linear combination and on the properties of ispersion measures under linear transformations. This problem has been addressed in work of Duarte Silva & Brito in the context of linear discriminant analysis of interval data. Different approaches have been considered by various authors to address these and other questions and to propose a symbolic counterpart of statistical multivariate data analysis methods. As we can see, in recent years there has been a growing literature proposing methodologies for the analysis of symbolic data. However, most existing methods take a non-parametric descriptive approach. In a recent work, Brito and Duarte Silva focus on the analysis of interval data, for which probabilistic models are proposed and used. For modelling purposes, a parameterization consisting in representing each interval Iij=[lij , uij] by its midpoint cij=(lij+uij)/2 and range rij=uij-lij is adopted. The approach consists in modelling each pdimensional interval vector by a 2p-dimensional Normal or Skew-Normal distribution for the interval midpoints and log-ranges. One advantage of the Normal model is its analytical tractability and the possibility of straightforward applications of classical inference methods. On the other hand, the Skew-Normal model offers greater flexibility for the shape of the distributions. In the most general formulation we allow for non-zero correlations among all midpoints and log-ranges, but other particular cases of interest may also be taken into account. The proposed modelling may be applied to multivariate methodologies where a parametric distribution is to be assumed. Firstly, this odelling is employed in the context of (M)ANOVA techniques. This allows, in particular, assessing the relevance of different (interval) variables for a given partition on interval data. Secondly, a model-based clustering method (without fixing in advance the number of clusters), is eveloped, where a mixture distribution approach is followed, arameters and clusters are determined by maximum likelihood via the EM algorithm. This framework may be extended to other statistical methodologies, opening the way to inference approaches for symbolic data. In a most resent approach, quantile representation (Ichino, 2008) provides a common framework to represent symbolic data described by variables of different types. The principle is to express the observed variable values by some predefined quantiles of the underlying distribution. In the interval variable case, a distribution is assumed within each observed interval, e.g. uniform (Bertrand and Goupil, 2000) ; for a histogram-valued variable, quantiles of any histogram may be obtained by simply interpolation, assuming a uniform distribution in each class (bid); for categorical multi-valued variables, quantiles are determined from the ranking defined on the categories based on their frequencies. When quartiles are chosen, the epresentation for each variable is defined by the 5-tuple (Min, Q1, Q2, Q3, Max). This common representation then allows for a unified analysis of the data set, taking all variables simultaneously into ccount. In a numerical clustering context, the Ichino-Yaguchi dissimilarity is used to compare data units; hierarchical and pyramidal models, with several aggregation indices, may be applied and clusters are formed on the basis of quantile proximity. We also focus on a conceptual clustering approach. In this case, clusters are epresented, for each variable, by a mixture of the quantile-distributions of the merged clusters and then compared on the basis of the current quantile representation. The proposed hierarchical/pyramidal clustering model follows a bottom-up approach; at each step, the algorithm selects the two clusters with closest quantile representation to be merged. The newly formed cluster is then represented according to the same model, i.e., a quantile representation for the new cluster is determined from the uniform mixture cumulative distribution. Much remains however to be done. We have just rather briefly discussed some of the issues that arise when we leave the classical data framework and allow for more complex variable types. Usual properties, generally taken for granted, often do not apply any longer, and new concepts much be put forward. Among these, parametric statistical analysis is an important challenge. A whole world of problems still remains open, waiting to be explored.
Keywords : Symbolic data analysis, Interval data, Imprecise data,Standardization, Clustering, Discriminant Analysis, Parametric modelling of interval data, Statistical tests for interval data, Skew-Normal distribution, (M)ANOVA, Quantile representation
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2011年1月31日(月曜日)
開催場所ERATOセミナー室
開催時間13時15分-15時00分 
発表者Dr. Mathias Soeken  
発表者の紹介University of Bremen
タイトルFormal Verification of UML-based Specifications 
発表の概要In the recent years, researchers started to enrich the classical
textbook specification of embedded systems by more formal descriptions
such as the Unified Modeling Language (UML). This enables to lift the
starting point for verifcation techniques to the specification level
and leads to an improved design flow, where crucial flaws can be
detected, even if no executable implementation is available. However,
research on efficient solving techniques for the respective
verification tasks is just at the beginning.
In the talk, the improved design flow based on specifications enriched
with formal descriptions is introduced. We illustrate how early design
flaws become evident within this flow and briefly review algorithms
aimed at detecting them. Furthermore, first experimental results are
presented. Overall, the aim of the talk is to provide an introduction
into this emerging area and to present first results.
接続サイト東京
    
閉じる

詳細

閉じる
開催日2011年1月28日(金曜日)
開催場所ERATOセミナー室
開催時間16時00分-17時30分 
発表者岩下 洋哲  
発表者の紹介富士通研究所 デザインイノベーション研究部, 2011.4.1より ERATO湊離散構造処理系プロジェクト 研究員 (出向)
タイトルImproving Simulation Coverage of Metastability Effects in Clock Domain Crossing Verification
 
発表の概要複数の非同期クロックドメインを含むハードウェアの論理検証には、非同期信号受信時に発生する信号値のランダム性をモデル化した「CDCシミュレーション」が不可欠である。CDCシミュレーションでは、使用したシミュレーションパターンの集合が障害検出に十分なものであるかという問題と、それぞれのシミュレーションパターンに対して十分な種類のランダム動作が試されたかという問題が、その検証品質を決定する。本文では、CDCモデルに制約ソルバを組み合わせることにより、上記2つの問題を改善する手法を提案する。本手法により、短時間で高い検証品質のCDCシミュレーションが実行可能になる。
    
閉じる

詳細

閉じる
開催日2011年1月21日(金曜日)
開催場所東工大サテライトラボ
開催時間15時30分-17時30分 
発表者小寺正明  
発表者の紹介京都大学バイオインフォマティクスセンター
タイトルメタボローム技術で得られる代謝経路不明な多数の化合物の組み合わせから経路を予測する手法の開発 
発表の概要生体内での存在が確認されているがその生合成・生分解経路の不明な化合物(orphan metabolites)は多く知られており、近年のメタボローム関連技術の発達によりその数はますます増えることが予想される。過去の研究では、そのような orphan metabolites の組み合わせから可能な酵素反応式を構築し、それらに適切な酵素番号(EC番号)を推定する手法を開発した。KEGGデータベース中に登録されている任意の2つの orphan metabolites に対して二次元化学構造比較(化学アラインメント)を行い、既知の酵素反応式を構成する部分反応式との照合を行うことで、可能性の高い酵素反応式を構築した。既知の酵素反応式を用いたクロスバリデーションでは 77% の酵素反応式を再構築することができた。再構築できなかった式の多くは、具体的な化学構造を持たない化合物を含むものであった。構築された反応式の妥当性チェックとEC番号推定にはランダムフォレスト(random-forest)が用いられ、クロスバリデーションで98% の精度を得た。ここで開発した手法の欠点のひとつは、酵素反応式の構築方法が非効率であるため膨大な計算時間を要求することである。今回の発表では、この研究の背景や手法について説明した後、問題点やその解決案について紹介する。

参考文献:
Kotera M, McDonald AG, Boyce S, Tipton KF. J.Chem.Inf.Model. 2008,
48(12):2335-2349.
接続サイト札幌,大阪
    
閉じる

詳細

閉じる
開催日2011年1月11日(火曜日)
開催場所ERATOセミナー室
開催時間15時30分-17時00分 
発表者金沢 誠  
発表者の紹介国立情報学研究所
タイトルA Chomsky-Sch\"{u}tzenberger-Weir Representation Theorem for Simple Context-Free Tree Grammars 
発表の概要Analogues of the Chomsky-Sch\"{u}tzenberger Theorem for context-free
languages have been obtained for two distinct classes of languages,
both of which have sometimes been identified with the informal notion
of "mildly context-sensitive" languages.

In 1988, Weir showed that each tree-adjoining language is a
homomorphic image of the intersection of two Dyck languages over 2n
pairs of brackets and a regular set, where the two Dyck languages are
related by a permutation of the alphabet that maps

[_{2i+1} ]_{2i+1} [_{2i+2} ]_{2i+2}

to

[_{2i+1} [_{2i+2} ]_{2i+2} ]_{2i+1}

for each i = 0,...,n-1.

Recently, Yoshinaka et al. (2010) obtained a representation theorem
for each level in the two-dimensional hierarchy of multiple
context-free languages, which subsumes tree adjoining languages and
much more. They introduced the notion of "multiple Dyck languages"
(for each dimension and rank), and showed that every multiple
context-free language of a given dimension and rank is a homomorphic
image of the intersection of a multiple Dyck language and a regular
set.

In this talk, I generalize Weir's representation theorem for the
tree-adjoining grammars to the simple (i.e., non-deleting and
non-duplicating) context-free tree grammars, which correspond at the
level of string languages to the "well-nested" multiple context-free
grammars. The well-nested multiple context-free languages form a
large subclass of the multiple context-free languages with some
interesting distinguishing properties. In this representation, each
string language generated by a context-free tree grammar of rank m is
obtained as a homomorphic image of the intersection of two Dyck
languages over (m+1)n pairs of brackets and a regular set, where the
two Dyck languages are related by a permutation of the alphabet that
maps

[_{mi+1} ]_{mi+1} [_{mi+2} ]_{mi+2} ... [_{mi+m} ]_{mi+m}

to

[_{mi+1} [_{mi+2} ]_{mi+2} [_{mi+3} .... ]_{mi+m} ]_{mi+1}

for each i = 0,...,n-1. This is obtained as a consequence of a
representation theorem at the level of tree languages of simple
context-free tree grammars, where a tree analogue of Dyck languages
plays the role of the usual Dyck languages.
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2011年1月7日(金曜日)
開催場所ERATOセミナー室
開催時間15時30分-17時30分 
発表者伊藤公人  
発表者の紹介北海道大学 人獣共通感染症リサーチセンター 准教授
タイトルPrediction of amino acid substitutions on the hemagglutinin molecules of influenza A viruses
 
発表の概要Human influenza viruses mutate from time to time, causing annual
epidemics worldwide. Given the high mutation rate of the viral gene, it
is difficult to select an effective vaccine strain prior to each influenza season. In order to elucidate the pattern of viral evolution, we Prediction of amino acid substitutions on the hemagglutinin molecules of influenza A viruses introduce a bioinformatics technology that analyzes a large number of epidemic strains in a multidimensional space. We found that the relative sequence distances among past epidemic strains could be predicted by a mathematical model. Retrospective tests for 12 years showed that the model could predict the direction of viral evolution with high accuracy.
Through these technologies, we investigate the past, current and future evolution of influenza A viruses.
    
閉じる

詳細

閉じる
開催日2010年12月17日(金曜日)
開催場所関西サテライトラボ
開催時間15時30分-00時01分 
発表者Guan-Cheng Li  
発表者の紹介PhD student in Computer Science, University of California, Berkeley
タイトルMining Psychology from English News and Applications on Finance.
 
発表の概要Our perceptions of the world are largely shaped by news media.
Understanding the psychology of how media portray certain words is a
critical step towards assessing media's influence on those
perceptions. We implement a system which analyzes the 'image' of a
given query word in a given corpus of news texts by producing a list
of other words with which this query is strongly associated, which
will be used to construct a covariance matrix amongst financial
assets, based on their co-appearances on news. The presentation will
cover theories of computational linguistics, machine learning,
sentiment analysis, and implementation issues in real time news
analysis.
接続サイト東京,札幌
    
閉じる

詳細

閉じる
開催日2010年11月19日(金曜日)
開催場所関西サテライトラボ
開催時間00時01分-00時01分 
発表者Prof. Kai Ming Ting   
発表者の紹介Gippsland School of Information Technology, Monash University
Associate Professor
タイトルMulti-Dimensional Mass Estimation and Mass-based Clustering
 
発表の概要
接続サイト東京,札幌
    
閉じる

詳細

閉じる
開催日2010年11月15日(月曜日)
開催場所ERATOセミナー室
開催時間15時30分-17時30分 
発表者Prof. Adnan Darwiche  
発表者の紹介
タイトルEfficient Representations of Boolean Functions: The View from Knowledge Compilation 
発表の概要We provide an overview of the area of knowledge compilation, which is
concerned with the systematic study of efficient representations of
propositional knowledge bases (aka, Boolean functions). We discuss the
two key dimensions of knowledge compilation: succinctness of the
representation, and the set of operations it supports in polytime. We
focus on two key representations: The well-studied Ordered Binary
Decision Diagram (OBDD) and the more recent Decomposable Negation
Normal Form (DNNF). We highlight the relationship between these two
representations, while stressing some of the more recent developments
on DNNFs. This includes lower and upper bounds on the size of DNNFs
and how they relate to similar bounds on OBDDs; the notion of a vtree
and how it generalizes the notion of a variable order; and the newly
discovered notion of "interaction function" and the role it plays in
the decomposition and efficient representation of Boolean functions.
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2010年11月12日(金曜日)
開催場所関西サテライトラボ
開催時間15時30分-17時30分 
発表者鈴木譲  
発表者の紹介大阪大学大学院理学研究科数学専攻 助教授
タイトル連続データにも使えるMDL基準の一般化 
発表の概要機械学習の知識や科学の法則を発見するための基準として、MDL原理がよく適用される。実データが与えられたときに、規則を記述し、その規則で説明しきれないデータの箇所(例外もしくは雑音とよばれる)を記述際に、両方の記述長の合計を最小にする規則を、簡潔でデータに対して適合した規則とみなす原理である。MDLに関しては、理論的な側面は、1990年代に(解決できるものは)ほぼ解決されたといわれている。しかしながら、ファイルやテキストのようにひずみのない(完全に復元可能な)圧縮では、データ列の個々の記号が有限集合に含まれていることが前提となる。すなわち、MDL原理は、実データが連続である場合には、適用されない。非常に大きな問題点でありながら、着手されず、放置されてきた問題であるといってよい。
本研究では、Radon-Nykodim微分を用いて、記述長ではなく記述長の差を計算して、規則間の優劣を決定する方法を提案する。従来の実データが有限である場合をすべて含む一般化になっている。応用として、Bayesianネットワークの構造学習で、一部の確率変数が連続データを含む場合も全く問題なく対応できる(自然な一般化である)ことを示す。
接続サイト東京,札幌
    
閉じる

詳細

閉じる
開催日2010年11月5日(金曜日)
開催場所ERATOセミナー室
開催時間15時30分-17時30分 
発表者吉仲 亮  
発表者の紹介JST ERATO湊離散構造処理系プロジェクト研究員
タイトルSeq BDD と既存手法との比較について,
 
発表の概要ZDD から派生したデータ構造として,文字列集合や系列(sequential)データを表現するためのseqBDD が提案されている.本発表では seqBDD の概説を行う.
特に,1つの文字列の全ての部分文字列を表現する手法について,既存のDAWG などのデータ構造との比較を行う.
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2010年11月5日(金曜日)
開催場所北大工学部C304 ERATOセミナ室
開催時間15時30分-17時30分 
発表者伝住周平  
発表者の紹介北海道大学情報科学研究科修士課程
タイトルSeqBDD : Introduction to Sequence BDD 
発表の概要ZDD から派生したデータ構造として,文字列集合や系列(sequential)データを表現するためのseqBDD が提案されている.本発表では seqBDD の概説を行う.
特に,1つの文字列の全ての部分文字列を表現する手法について,既存のDAWG などのデータ構造との比較を行う.
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2010年10月29日(金曜日)
開催場所ERATOセミナー室
開催時間15時30分-17時30分 
発表者井上 武  
発表者の紹介NTT未来ねっと研究所
(2011.5より ERATO湊離散構造処理系プロジェクト 研究員(出向))
タイトル通信ネットワークの構造分析について 
発表の概要インターネットをはじめとする通信ネットワークは,人工物であるにも関
わらずその構造・特性があまり理解されていない.現状,通信ネットワー
クの設計・運用は,局所的な最適化と経験・勘によって行われている.こ
の問題を顧みて,近年,科学的な視点からネットワーク構造を理解する試
みが行われている.
その理論基盤となっているのは,複雑ネットワークと呼ばれる新しい学際
的な科学領域である.前世紀末以降,多くの自然・人工物ネットワークに
共通した特徴 (特に,スモールワールドやスケールフリーと呼ばれるよう
なグラフとしての特徴) が発見され,その構造や振る舞いが熱心に研究さ
れている.
理論の明快さを優先した複雑ネットワークの科学と異なり,通信ネットワー
クには固有の工学的特性があり,それらを考慮した分析が求められる.た
とえば,複雑ネットワークの研究者はインターネットのアキレス腱 (構造
上の弱点) を指摘したが,実際にはそのようなものは存在しない.構成装
置の特性を考慮して複雑ネットワークの理論を修正することで,インター
ネットを生み出すダイナミズムを説明できる.
大規模かつ現実的な複雑さを持つネットワークを分析するためには,本質
を突く着眼点と,効率的な解析手法・アルゴリズムが求められる.本公演
では,通信ネットワークの構造分析に関する研究を,講演者の研究を含め
て幅広く紹介する.
    
閉じる

詳細

閉じる
開催日2010年10月22日(金曜日)
開催場所ERATOセミナー室
開催時間15時30分-17時01分 
発表者湊 真一  
発表者の紹介北海道大学大学院情報科学研究科 教授 兼 JST ERATO湊離散構造処理系プロジェクト研究総括
タイトルBDD/ZDDを基盤とする種々の離散構造の演算処理と代数系(algebra)
について 
発表の概要本ERATOプロジェクトでは、離散構造を統合的に扱う基本処理系としてBDD/ZDDを位置づけ,分野横断的な応用を持つ技術体系として再構築することを目指して研究活動を開始している.本講演では,BDD/ZDDを基盤とする離散構造とその演算処理の代数系(algebra)の例として,BDDによる論理関数処理系, ZDDによる組合せ集合の処理系,ZDDベクトル表現による組合せ頻度表の演算処理系,およびSequence BDDによる系列集合の演算処理系を取り上げ、それらの代数系を比較するとともに、今後の展望について述べる。
(先月、ドイツで開催された国際ワークショップIWSBP2010での招待講演とほぼ同じ内容を日本語でお話しします。)
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2010年9月27日(月曜日)
開催場所ERATOセミナー室
開催時間10時00分-12時30分 
発表者比戸将平  
発表者の紹介IBM東京基礎研究所
タイトルハッシュを用いた高速なグラフカーネルとZDD 
発表の概要大規模グラフにおける機械学習を目的とした、スケーラブルなグラフカ
ーネルを紹介する。その鍵は、ラベルをビット列で表現し、近接ノード集合のラベル分布を論理演算でハッシュ値とする近傍ハッシュである。2つのグラフのノード集合間で近傍ハッシュ値を比較することで、グラフ間のカーネルを構成する。計算量は高々エッジ数に線形である。実験において、近傍ハッシュカーネルは数千ノードのグラフに適用可能であることが示され、ベンチマークにおいて既存カーネルよりも良い性能を示した。また、ZDDを用いたカーネルの高速化に関してもアイデアを述べる。

接続サイト東京,大阪
開催時間10時00分-12時30分 
発表者今道貴司  
発表者の紹介IBM東京基礎研究所
タイトル非線形最適化を用いた図形の充填問題の解法 
発表の概要図形の充填問題とは、与えられた図形を容器の中に図形の衝突がないよ
うに配置する問題である。図形の種類、配置の制約、容器の形状などにより様々なバリエーションがあり、広く応用のある重要な問題である。本発表では、図形同士の衝突や図形の容器からの突出にペナルティをかけ、その総和を非線形最適化の手法を用いることで、配置を改善する手法の紹介をする。適用例として、多角形の充填問題、道路ラベルの配置問題、タンパク質の充填問題などの結果を紹介する
接続サイト東京,大阪
開催時間10時00分-12時30分 
発表者井手剛  
発表者の紹介IBM東京基礎研究所
タイトル経路のコストに関する回帰問題について 
発表の概要空間を時系列的に移動する物体の軌跡、すなわちトラジェクトリに対す
るデータマイニングの問題は、実用的にも理論的にも興味深い研究テーマである。
本講演では、ネットワーク上のトラジェクトリ(経路)のコスト予測問題についての最近の我々の研究成果を紹介する。経路のコスト推定問題の典型的な応用例は、任意経路に対する所要時間の予測問題である。講演ではまず、経路コスト予測問題を、カーネル回帰の枠組みで定式化する。次に、いわばその双対問題として別の定式化を導き、これら2つのアプローチの関係について論ずる。最後に、交通シミュレーションのデータを用いて、我々の手法が、考えうる既存手法と比べて優れた予測性能を持つことを示す。
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2010年9月16日(木曜日)
開催場所ERATOセミナー室
開催時間15時00分-17時00分 
発表者堀山 貴史  
発表者の紹介埼玉大学
タイトル回転によるタイリングについて 
発表の概要タイリングは,基本図形に平行移動,回転,すべり鏡映などの単純な操作を繰り返し適用することにより,隙間なく重なりなく平面を埋め尽くすことを指す.
本発表では,回転操作によるタイリングに注目し,タイリング可能な基本図形を生成する手法を示す.具体的には,90度回転による p4 タイリングと60度回転による p6 タイリングを対象とし,それぞれ polyomino (単位正方形の辺接続による図形) および polyiamond (単位正三角形の辺接続による図形) を基本図形とする.
    
閉じる

詳細

閉じる
開催日2010年9月2日(木曜日)
開催場所ERATOセミナー室
開催時間15時30分-17時00分 
発表者Prof. Randy Goebel  
発表者の紹介カナダ・アルバータ大学 教授
タイトルChallenges for a theory of visualization: what is semantic symmetry? 
発表の概要While there is no theory of visualization, there should be. Such a theory would provide a framework to assess a variety of information visualization techniques, to understand their comparative value in helping humans to draw inferences on large data. One simple concept
related to a theory of visualization is semantic symmetry, which can be
considered as the property that change in one representation space (e.g., a visual vocabulary space) can be accurately propogated to another space (e.g., a numeric tabular space). We explain the idea of semantic symmetry, and its potential role in a theory of visualization.
接続サイト大阪
    
閉じる

詳細

閉じる
開催日2010年8月26日(木曜日)
開催場所ERATOセミナー室
開催時間15時30分-17時30分 
発表者田部井靖生  
発表者の紹介JST ERAT湊離散構造処理系プロジェクト研究員
タイトルスケッチソート法による全点間類似度検索 
発表の概要近年、画像やテキストなどのウェブデーター、化合物やタンパク質などの生物学的データーなど、ベクトルとして表現されるデーターが大量に生成され、それらを効率的に処理する手法の開発が求められている。大規模データーから近傍検索を行う代表的な手法にChariker (2002) らが提案した手法がある。これは、ベクトルデーターを2点間の距離関係を保ったままバイナリデーターへと射影した後、ソートとバイナリーサーチにより近傍点を検索する手法であるが、検索速度が遅いという欠点がある。そこで、我々は複合ソート法による全点間類似度検索法を提案する。提案手法は、ソート容量が大きくなる代わりに、近傍候補の距離計算を減少させることがで
き、高次元データーに対して効率的に類似度検索を行うことができる。大規模画像データーを用いた実験では、最近の近傍探索法との比較により提案手法の有効性が示を示す。
接続サイト大阪
    
閉じる

詳細

閉じる
開催日2010年8月23日(月曜日)
開催場所ERATOセミナー室
開催時間14時30分-16時00分 
発表者柴田剛志  
発表者の紹介東京大学大学院情報学環 特任研究員
タイトルデータインテンシブな計算方法としての分散ワークフローに関する研究の紹介 
発表の概要近年、コンピュータで処理すべきデータの量がムーアの法則を超える勢いで急激に増加している。 このような大量のデータを処理するのに適し、かつ並列計算をあまり意識せず記述できる並列計算の枠組みとして、
ワークフローというものが知られている。
本講演では次のことについて発表予定である。
(1) ワークフローとはどのようなものか
(2) GXPmakeというワークフローシステムの説明と実際のデモ(Povray)
(3) ファイルアクセスログと可視化について
(4) ワークフローの実際の応用例をいくつか
(5) 広域に散らばる計算機を使った時のワークフローのための遅延隠蔽方法
    
閉じる

詳細

閉じる
開催日2010年8月20日(金曜日)
開催場所ERATOセミナー室
開催時間10時30分-12時00分 
発表者山下茂  
発表者の紹介立命館大学 教授
タイトル量子回路設計とは? 
発表の概要量子回路で計算を行うとは,どのようなことであるのかを基本的な内容を含め説明する.また,「量子回路設計」の意味について概説する.
接続サイト東京, 大阪
    
閉じる

詳細

閉じる
開催日2010年8月20日(金曜日)
開催場所ERATOセミナー室
開催時間10時30分-12時00分 
発表者Byung-Soo Choi  
発表者の紹介韓国/梨花女子大学 研究教授
タイトルTopological Quantum Computerのための量子回路設計問題 
発表の概要現在,注目されている「エラーに強い」量子計算のスキームであるTopological Quantum Computerについて,その動作原理を簡単に説明した後,その設計のために必要な最適化問題に関する定式化を行う.
接続サイト東京, 大阪
    
閉じる

詳細

閉じる
開催日2010年8月6日(金曜日)
開催場所ERATOセミナー室
開催時間10時00分-12時00分 
発表者宇野 毅明   
発表者の紹介国立情報学研究所
タイトル山登りは大変なので沢登りアルゴリズム 
発表の概要山登りアルゴリズムは非常に多くの問題に対して採用されているが、極小元を見つける場合、極小元とは関係ない高い山を登り切ってしまうという意味で無駄が多くなり、効率的でなくなる。本発表では、ハイパーグラフ双対化という極小元列挙問題に対して、極小解を山の頂上にして山登りアルゴリズムを適用するというアルゴリズムを提案し、効率的な計算方法も合わせて提案する。計算実験により、本アルゴリズムは多くの問題に対して非常に効率良く動くことを示す。
接続サイト東京, 大阪
    
閉じる

詳細

閉じる
開催日2010年8月6日(金曜日)
開催場所ERATOセミナー室
開催時間13時00分-16時00分 
発表者山本章博  
発表者の紹介京都大学 教授
タイトル分散データベースからの頻出飽和アイテム集合のプライバシー保護発見 
発表の概要水平分割され分散配置されたトランザクションデータベースに,全体として
頻出する飽和アイテム集合を暗号化と組み合わせて発見する手続きを提案する.頻出飽和アイテム集合は,頻出アイテム集合の圧縮形とみなせることから,分散配置されたデータベースからのプライバシー保護発見に有用と考えられる.本講では基本アイデアを実験結果とともに報告する
接続サイト東京, 大阪
    
閉じる

詳細

閉じる
開催日2010年8月4日(水曜日)
開催場所ERATOセミナー室
開催時間10時00分-14時00分 
発表者上原 隆平  
発表者の紹介北陸先端科学技術大学院大学 教授
タイトルじゃばら折りの一般化とその複雑さの研究 
発表の概要日本での折紙の研究は,数学的な観点からの研究が先行してきた.しかしLang,Domain,O'Rourkeといった研究者の活躍により,最近computational origami という言葉が市民権を得つつある.しかし理論計算機科学としての枠組みは,まだまだ未整備である.折紙を計算機科学の対象としたときの単純なモデルとは何だろうか.ここではごく単純な折紙モデルとして,次のものを考える.入力として与えられるのは,長さ n+1 の紙と,長さ n の{M,V}上の文字列である.ここで M は山折り,V は谷折りを意味している.つまり長さ n+1の紙の上に,等間隔に山/谷が指定されている.この文字列にしたがって紙を折る問題を考える.まず時間計算量に対しては,折りの回数が自然に対応すると考えることができる.この観点から,じゃばら折りとその一般化に対して,講演者らは,ほぼ最適な折りアルゴリズムを設計した.では領域計算量に対応する概念は何だろうか.これに対してはみんなが合意する概念は存在しない.講演者は,折り目に挟まる紙の枚数を基準として提案し,これに関する最適化問題を研究している.部分的な解は得られているものの,まだ残された研究課題の方が多いのが実状である.
    
閉じる

詳細

閉じる
開催日2010年8月3日(火曜日)
開催場所関西サテライトラボ
開催時間15時30分-17時30分 
発表者山下茂  
発表者の紹介立命館大学 情報理工学部 情報システム学科
タイトルIntroduction to Grover Algorithm 
発表の概要
接続サイト札幌, 東京
    
閉じる

詳細

閉じる
開催日2010年8月3日(火曜日)
開催場所関西サテライトラボ
開催時間15時30分-17時30分 
発表者Prof. Byung-Soo Choi  
発表者の紹介梨花女子大学 研究教授
タイトルGrover Search and its Applications 
発表の概要
接続サイト札幌, 東京
    
閉じる

詳細

閉じる
開催日2010年7月23日(金曜日)
開催場所ERATOセミナー室
開催時間15時30分-17時30分 
発表者喜田拓也  
発表者の紹介北海道大学大学院 情報科学研究科 准教授
タイトル効率よいVF符号の設計 
発表の概要VF符号とは、情報源系列を可変長のブロックに分割し、各ブロックに対して固定長の符号語を割り当てることで圧縮を達成する情報源符号化の一種である。
入力系列(テキスト)の分割には、主に分節木と呼ばれる木構造が用いられる。
VF符号は、近年、パターン照合を高速化することのできるデータ圧縮法として見直されている。しかしながら、VF符号は、符号語長が固定であるという制約から高い圧縮率を得ることが難しく、実用的な符号化方法は存在しなかった。
発表者らは、これまで、テキストに対する接尾辞木をもとに、それを刈り込んだ木を分節木とすることで圧縮率の高い符号化を提案し、その改良を行ってきた。本発表では、我々の手法とその実験的評価について紹介する。
    
閉じる

詳細

閉じる
開催日2010年7月9日(金曜日)
開催場所ERATOセミナー室
開催時間15時30分-17時30分 
発表者白井康之  
発表者の紹介ERATO湊離散構造処理系プロジェクト 技術参事/研究員
タイトルデータ匿名化に関する検討事項  
発表の概要個人情報をはじめとする機微なデータから個人が特定されないようにする技術は,近年の個人の行動履歴情報の利活用の進展に伴い,特にデータマイニングの分野で注目を集めている.
k 匿名性をはじめとする匿名化技術は,基本的にはデータ項目の組み合わせ問題に帰着するが,匿名化されたデータの効率的な管理という側面から見れば,ZDDをはじめとしたデータベースの効率的な管理手段が必要とされる分野である.
本発表では,データの匿名化が必要とされる背景や研究動向等のサーベイを行った上で,必要とされる匿名化技術の概要ならびに ZDDによるコーディング手法に関する検討結果について触れる.

接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2010年7月2日(金曜日)
開催場所ERATOセミナー室
開催時間15時30分-17時30分 
発表者斎藤寿樹  
発表者の紹介ERATO湊離散構造処理系プロジェクト 研究員
タイトルProper Interval Graphのランダム生成と列挙 
発表の概要Interval Graphは,スケジューリング問題やバイオインフォマティクスなど,いくつもの応用を持つことが知られている.そのため,Interval Graphについての研究はいくつも存在し,またInterval Graph上のアルゴリズムが開発されている.実際の応用で開発されたアルゴリズムを適用する場合,そのアルゴリズムは理論的に効率がよいだけでなく,実装上効率がよいことを実験的解析によって示す必要がある.実験的に解析をするとき,テストデータに偏りがある場合,正しい解析結果を得ることができないため,偏りのないテストデータを生成する必要がある.
本発表では,Interval Graphの部分クラスであるProper Interval Graphをランダム生成や列挙するアルゴリズムを提案する.ランダム生成アルゴリズムは数え上げを用いたアルゴリズムで,n 頂点の連結なProper Interval Graphを一様ランダムに生成する.列挙アルゴリズムは逆探索に基づいたアルゴリズムで,n頂点の連結なProper Interval Graphを漏れなく,重複なく出力する.
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2010年6月18日(金曜日)
開催場所ERATOセミナー室
開催時間15時30分-17時30分 
発表者川原 純  
発表者の紹介ERATO湊離散構造処理系プロジェクト 研究員
タイトルオンラインユニットクラスタリング問題の競合比の改良 
発表の概要将来の入力情報が未知である状況をモデル化した最適化問題をオンライン問題という。オンラインユニットクラスタリング問題はChanらによって提案された問題であり、以下の様に定義されている。各点はd次元のユークリッド空間上に与えられる。それに対して、アルゴリズムは(次以降の点の発生箇所が未知の状態で)d次元の多面体を作成しなければならない。その多面体の各辺の長さは、作成した時点では0であり、アルゴリズムは各次元ごとに単位長まで伸ばすことが出来る。アルゴリズムの役割は新しいクラスタを作成するか、過去に作成した既存のクラスタの辺を拡張して、与えられる新しい点を被覆することである。
問題の目的は作成するクラスタの数の最小化である。
1次元(すなわち、d=1)の場合に対して、我々は新しい決定性オンラインアルゴリズムである、グルーピング・アルゴリズムを考案し、競合比(アルゴリズムのコストと入力が既知であると仮定したときの最適コストの比)の上限の値を7/4 (= 1.75) から 5/3 (= 1.667) に改良した。
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2010年6月4日(金曜日)
開催場所ERATOセミナー室
開催時間15時30分-17時30分 
発表者吉仲 亮  
発表者の紹介ERATO離散構造処理系プロジェクト 研究員
タイトルChomsky-Schützenberger-Type Characterization of Multiple Context-Free Languages 
発表の概要It is a well-known theorem by Chomsky and Sch◯tzenberger (1963) that every context-free language can be represented as a homomorphic image of the intersection of a Dyck language and a regular language.
This paper gives a Chomsky-Sch◯tzenberger-type characterization for multiple context-free languages, which are a natural extension of context-free languages, with introducing the notion of multiple Dyck languages, which also are a generalization of Dyck languages.
接続サイト東京,埼玉大学
    
閉じる

詳細

閉じる
開催日2010年5月21日(金曜日)
開催場所ERATOセミナー室
開催時間15時30分-17時30分 
発表者湊 真一  
発表者の紹介北海道大学大学院情報科学研究科 教授 兼 JST ERATO湊離散構造処理系プロジェクト研究総括
タイトル北大版BDD/ZDDパッケージの概要/北大ERATOオフィスのIT系インフラ構成の現状と今後の課題について 
発表の概要
接続サイト東京,大阪
    
閉じる

詳細

閉じる
開催日2010年5月14日(金曜日)
開催場所ERATOセミナー室
開催時間15時30分-18時00分 
発表者荒井迅  
発表者の紹介北海道大学創成科学共同研究機構テニュア・トラック助教
タイトル計算ホモロジー理論とその応用 
発表の概要位相幾何学とは、空間をぐにゃぐにゃと連続変形しても不変な性質を研究する数学であり、様々な数学の分野で重要な道具となっている。近年、より現実的な問題に位相幾何学を応用るために、計算機を用いて位相不変量を計算するアルゴリズムの開発が活発になっており、本講演ではその中の一つである計算ホモロジー理論について、その基礎とセンサーネットワークの被覆問題への応用について解説する。
センサーネットワークにおいては、大量のセンサー、例えば人間の存在を感知したり、温度を測定するセンサーがあちこちにばらまかれた状況を考える。このとき、センサーたちの感知領域が、正しく目的の領域を被覆しているか、すなわちどこかに見逃しがないか、という問題が重要になる。GPS などを用いて各センサーの位置情報を求めれば計算幾何を用いることが出来るが、消費電力を小さくおさえるためには、なるべく少ない情報で解決したい。R. Ghrist らの研究により、センサーネットワークから定義されるRis 複体のホモロジーを計算すれば、この被覆問題を少ない情報で綺麗に記述できる事がわかったのだが、今度は「Rips 複体のホモロジーをいかに小さいコストで計算するか」という問題が生じた。
この問題に対し、林和則、平岡裕章両氏との共同研究で得られた、マイヤービートリス系列を用いて分散計算をするアプローチと、Ali Jadbabaie らが進めているネットワーク上のラプラシアンを用いたアプローチを紹介する。
    
閉じる