MF研究者総覧

研究者データベース

詳細
有村　博紀(アリムラ　ヒロキ)
情報科学研究院　情報理工学部門　知識ソフトウェア科学分野
教授
researchmap個人ページ
Last Updated :2024/05/16

基本情報

所属

  • 情報科学研究院　情報理工学部門　知識ソフトウェア科学分野

職名

  • 教授

学位

  • 博士（理学）（1996年06月 九州大学，大学院総合理工学研究科）
  • 修士（理学）（1990年03月 九州大学，理学部）
  • 学士（理学）（1988年03月 九州大学，理学部）

ホームページURL

ORCID ID

J-Global ID

プロフィール

  • 1990年九州大学大学院修士課程修了．同年，九州工業大学助手．その後，九州工業大学講師および助教授，九州大学大学院助教授および准教授などを経て，2004年から北海道大学情報科学研究科教授，現在に至る．博士(理学)．1999～2002年 JST PREST「情報と知」（領域総括:安西祐一郎）研究員．2007～2011年度 文科省グローバルCOEプログラム「知の創出を支える次世代IT基盤拠点」拠点リーダー．2013〜2014年度 北海道大学知識メディアラボラトリー長. 2016〜2017年度 北海道大学ビッグデータ・サイバーセキュリティ グローバルステーション (GSB) 拠点長. 2015年度および2018〜2021年度 北海道大学共同プロジェクト拠点「知識メディアラボラトリー」リーダー. 2020〜2025年度JST PREST/さきがけ「信頼されるAIの基盤技術」研究総括.
    現在，人工知能と, データマイニング，機械学習, 情報検索，アルゴリズムとデータ構造等の研究に従事．電子情報通信学会，情報処理学会，日本データベース学会, 人工知能学会会員, ACM, IEEE．

研究キーワード

  • 情報科学   人工知能   データ構造とアルゴリズム   データマイニング   情報検索   機械学習   列挙アルゴリズム   グラフ   決定木   テキスト索引   文字列アルゴリズム   半構造データ   ウェブマイニング   パターン発見   機械学習における説明可能性   データベース   時空間データ   圧縮   ストリーム処理   知識発見   ビッグデータ   

研究分野

  • 情報通信 / 情報学基礎論 / アルゴリズム
  • 情報通信 / データベース / データマイニング・情報検索
  • 情報通信 / 知能情報学 / 人工知能・機械学習

担当教育組織

職歴

  • 2021年04月 - 現在 GI-CoRE連携教員
  • 2019年04月 - 現在 北海道大学 大学院情報科学研究院 教授（改組のため）
  • 2020年04月 - 2026年03月 JST 戦略的創造研究推進事業 さきがけ「信頼されるAIの基盤技術」(信頼されるAI) 研究総括
  • - 2025年03月 北海道大学 電子科学研究所附属社会創造数学研究センター 兼務教員
  • 2018年04月 - 2022年03月 北海道大学共同プロジェクト拠点 知識メディアラボラトリー リーダー（拠点長）
  • 2008年01月 - 2022年03月 国立情報学研究所 連携研究部門 客員教授
  • 2016年04月 - 2021年03月 北海道大学 国際連携研究教育局 教授（兼務）
  • 2004年04月 - 2019年03月 北海道大学 大学院・情報科学研究科 教授
  • 2016年04月 - 2018年03月 北海道大学「ビッグデータ・サイバーセキュリティ グローバルステーション」 拠点長
  • 2015年04月 - 2017年03月 北海道大学共同プロジェクト拠点 知識メディアラボラトリー リーダー（拠点長）
  • 2013年04月 - 2015年03月 北海道大学知識メディアラボラトリー ラボラトリー長
  • 2007年07月 - 2012年03月 北海道大学情報科学研究科 グローバルCOEプログラム「知の創出を支える次世代IT基盤拠点」 拠点リーダー
  • 2005年03月 - 2005年06月 リヨン大学第1訪問研究員（文科省）
  • 1996年04月 - 2004年03月 九州大学 大学院システム情報科学研究科 助教授（2000年から組織改編により准教授）
  • 2002年04月 - 2003年03月 九州大学 情報基盤センター研究部 兼任准教授
  • 2001年04月 - 2002年03月 九州大学 付属図書館研究開発室 兼任准教授
  • 1999年10月 - 2002年03月 科学技術事業団さきがけ研究21 「情報と知」領域 研究者
  • 1996年06月 - 1996年10月 ヘルシンキ大学訪問研究員（学振特定国交流研究員）．
  • 1995年04月 - 1996年03月 九州工業大学 情報工学部 助教授
  • 1994年04月 - 1995年03月 九州工業大学 情報工学部 講師
  • 1990年04月 - 1994年03月 九州工業大学 情報工学部 助手

学歴

  • 1994年06月 -   博士(理学)、九州大学   大学院総合理工学府   情報システム学専攻
  • 1988年04月 - 1990年03月   九州大学   大学院総合理工学研究科   情報システム学専攻修士課程
  • 1984年04月 - 1988年03月   九州大学   理学部   物理学科

所属学協会

  • 日本データベース学会 (DBSJ)   電子情報通信学会 (IEICE)   Association for Computing Machinery (ACM)   人工知能学会 (JSAI)   情報処理学会 (IPSJ)   IEEE Computer Society   

研究活動情報

論文

  • Shunsuke Inenaga, Takuya Mieno, Hiroki Arimura, Mitsuru Funakoshi, Yuta Fujishige
    Combinatorial Algorithms - 35th International Workshop, IWOCA 2024, Tainan, Taiwan, June 7-10, 2023, Proceedings. Lecture Notes in Computer Science, Springer 2024年07月 [査読有り][通常論文]
  • Yuto Shida, Giulia Punzi, Yasuaki Kobayashi, Takeaki Uno, Hiroki Arimura
    35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024), Leibniz International Proceedings in Informatics 296 21:0 - 21:17 2024年06月 [査読有り][通常論文]
  • Hiroki Arimura, Shunsuke Inenaga, Yasuaki Kobayashi, Yuto Nakashima, Mizuki Sue
    SPIRE2023 28 - 34 2023年09月 [査読有り][通常論文]
    ダウンロード
  • Hiroki Arimura, Tatsuya Gima, Yasuaki Kobayashi 0001, Hiroomi Nochide, Yota Otachi
    CoRR abs/2305.07259 2023年
  • Kota Mata, Kentaro Kanamori, Hiroki Arimura
    Proc. the 18th International Conference on Machine Learning and Data Mining (MLDM 2022) abs/2204.11285 2022年07月 [査読有り][通常論文]
  • Tsubasa Oizumi, Takeshi Kai, Takuya Mieno, Shunsuke Inenaga, Hiroki Arimura
    Proc. the 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), Leibniz International Proceedings in Informatics (LIPIcs) LIPIcs223 14:1 - 14:18 2022年06月 [査読有り][通常論文]
  • Kentaro Kanamori, Takuya Takagi, Ken Kobayashi, Hiroki Arimura
    Transactions of the Japanese Society for Artificial Intelligence 36 6 C - L44_1 2021年11月01日 [査読有り][通常論文]
  • Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, Takeaki Uno
    Discrete Applied Mathematics 303 283 - 295 2021年11月 [査読有り]
  • Kentaro Kanamori, Takuya Takagi, Ken Kobayashi, Hiroki Arimura
    Transactions of the Japanese Society for Artificial Intelligence 36 4 B - L13_1 2021年07月01日 [査読有り][通常論文]
  • Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki Arimura
    Theoretical Computer Science 874 32 - 41 2021年06月 [査読有り][通常論文]
  • Kentaro Kanamori, Takuya Takagi, Ken Kobayashi, Yuichi Ike, Kento Uemura, Hiroki Arimura
    Proceedings of the AAAI Conference on Artificial Intelligence 35 13 11564 - 11574 2021年02月 [査読有り]
  • Kentaro Kanamori, Takuya Takagi, Ken Kobayashi, Yuichi Ike, Kento Uemura, Hiroki Arimura
    Thirty-Fifth AAAI Conference on Artificial Intelligence(AAAI) 11564 - 11574 2021年
  • Kentaro Kanamori, Takuya Takagi, Ken Kobayashi, Hiroki Arimura
    Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20) 2855 - 2862 2021年01月 [査読有り]
  • Takuya Takagi, Shunsuke Inenaga, Hiroki Arimura, Dany Breslauer, Diptarama Hendrian
    Algorithmica 82 5 1346 - 1377 2020年 [査読有り]
  • Yusaku Kaneta, Takeaki Uno, Hiroki Arimura
    String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Segovia, Spain, October 7-9, 2019, Proceedings 241 - 257 Springer 2019年10月 [査読有り][通常論文]
  • Route graph: joint map-matching by maximizing posterior probability,
    Hiroya Inakoshi, Junichi Shigezumi, Tatsuya Asai, Takuya Kida, Hiroki Arimura
    IPSJ Transactions on Mathematical Modeling and Its Applications 12 1 1 - 9 2019年09月 [査読有り][通常論文]
  • Hiroya Inakoshi, Tatsuya Asai, Takuya Kida, Hiroki Arimura
    Transactions of the Japanese Society for Artificial Intelligence 34 3 D - I56_1 2019年05月01日 [査読有り][通常論文]
  • WASA Kunihiro, YAMANAKA Katsuhisa, ARIMURA Hiroki
    IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences E102-D 3 464 - 469 一般社団法人 電子情報通信学会 2019年03月 [査読有り][通常論文]
     

    Given two feasible solutions A and B, a reconfiguration problem asks whether there exists a reconfiguration sequence (A0=A, A1,...,Aℓ=B) such that (i) A0,...,Aℓ are feasible solutions and (ii) we can obtain Ai from Ai-1 under the prescribed rule (the reconfiguration rule) for each i ∈ {1,...,ℓ}. In this paper, we address the reconfiguration problem for induced trees, where an induced tree is a connected and acyclic induced subgraph of an input graph. We consider the following two rules as the prescribed rules: Token Jumping: removing u from an induced tree and adding v to the tree, and Token Sliding: removing u from an induced tree and adding v adjacent to u to the tree, where u and v are vertices of an input graph. As the main results, we show that (I) the reconfiguration problemis PSPACE-complete even if the input graph is of bounded maximum degree, (II) the reconfiguration problem is W[1]-hard when parameterized by both the size of induced trees and the length of the reconfiguration sequence, and (III) there exists an FPT algorithm when the problem is parameterized by both the size of induced trees and the maximum degree of an input graph under Token Jumping and Token Sliding.

  • Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, Takeaki Uno
    CoRR abs/1906.09680 2019年 [査読有り][通常論文]
  • Yoichi Sasaki, Tetsuo Shibuya, Kimihito Ito, Hiroki Arimura
    IEICE Transactions 102-A 9 1159 - 1170 2019年 [査読有り][通常論文]
     
    In this paper, we study the approximate point set matching (APSM) problem with minimum RMSD score under translation, rotation, and one-to-one correspondence in d-dimension. Since most of the previous works about APSM problems use similality scores that do not especially care about one-to-one correspondence between points, such as Hausdorff distance, we cannot easily apply previously proposed methods to our APSM problem. So, we focus on speed-up of exhaustive search algorithms that can find all approximate matches. First, we present an efficient branch-and-bound algorithm using a novel lower bound function of the minimumRMSD score for the enumeration version of APSM problem. Then, we modify this algorithm for the optimization version. Next, we present another algorithm that runs fast with high probability when a set of parameters are fixed. Experimental results on both synthetic datasets and real 3-D molecular datasets showed that our branch-and-bound algorithm achieved significant speed-up over the naive algorithm still keeping the advantage of generating all answers.
  • Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki Arimura
    Lecture Notes in Computer Science 339 - 351 2019年 [査読有り]
  • Kentaro Kanamori, Satoshi Hara, Masakazu Ishihata, Hiroki Arimura
    2019 Workshop on Human In the Loop Learning (HILL 2019), In conjunction with ICML 2019, CoRR abs/1906.01876 2019年 [査読有り][通常論文]
  • Iku OHAMA, Takuya KIDA, Hiroki ARIMURA
    IEICE Transactions on Information and Systems E101.D 12 3108 - 3122 2018年12月01日 [査読有り]
  • Shuhei Denzumi, Jun Kawahara, Koji Tsuda, Hiroki Arimura, Shin-ichi Minato, Kunihiko Sadakane
    Algorithms 11 8 128 - 128 2018年08月 [査読有り][通常論文]
  • 坂上 陽規, 栗田 和宏, 瀧川 一学, 有村 博紀
    人工知能学会研究会資料 人工知能基本問題研究会 105 12  一般社団法人 人工知能学会 2018年01月22日
  • KURITA Kazuhiro, WASA Kunihiro, UNO Takeaki, ARIMURA Hiroki
    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 101 9 1383 - 1391 一般社団法人 電子情報通信学会 2018年 [査読無し][通常論文]
     

    In this study, we address a problem pertaining to the induced matching enumeration. An edge set M is an induced matching of a graph G=(V,E). The enumeration of matchings has been widely studied in literature; however, there few studies on induced matching. A straightforward algorithm takes O(Δ2) time for each solution that is coming from the time to generate a subproblem, where Δ is the maximum degree in an input graph. To generate a subproblem, an algorithm picks up an edge e and generates two graphs, the one is obtained by removing e from G, the other is obtained by removing e, adjacent edge to e, and edges adjacent to adjacent edge of e. Since this operation needs O(Δ2) time, a straightforward algorithm enumerates all induced matchings in O(Δ2) time per solution. We investigated local structures that enable us to generate subproblems within a short time and proved that the time complexity will be O(1) if the input graph is C4-free. A graph is C4-free if and only if none of its subgraphs have a cycle of length four.

  • Kazuhiro Kurita, Kunihiro Wasa, Alessio Conte, Takeaki Uno, Hiroki Arimura
    Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Singapore, July 16-19, 2018, Proceedings 201 - 213 Springer 2018年 [査読有り][通常論文]
  • Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, Takeaki Uno
    The 29th International Symposium on Algorithms and Computation (ISAAC 2018) 8 - 13 2018年 [査読有り][通常論文]
  • Iku Ohama, Issei Sato, Takuya Kida, Hiroki Arimura
    Proc. the 31st Annual Conference on Neural Information Processing Systems (NIPS2017) 2017年12月 [査読有り][通常論文]
  • Takuya Takagi, Shunsuke Inenaga, Kunihiko Sadakane, Hiroki Arimura
    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E100A 9 1785 - 1793 2017年09月01日 [査読有り][通常論文]
     
    We present a new data structure called the packed compact trie (packed c-trie) which stores a set S of k strings of total length n in n log + O(k log n) bits of space and supports fast pattern matching queries and updates, where is the alphabet size. Assume that = log n letters are packed in a single machine word on the standard word RAM model, and let f (k n) denote the query and update times of the dynamic predecessor/successor data structure of our choice which stores k integers from universe [1 n] in O(k log n) bits of space. Then, given a string of length m, our packed c-tries support pattern matching queries and insert/delete operations in O( m f (k n)) worst-case time and in O( m + f (k n)) expected time. Our experiments show that our packed c-tries are faster than the standard compact tries (a.k.a. Patricia trees) on real data sets. We also discuss applications of our packed c-tries.
  • Junpei Komiyama, Masakazu Ishihata, Hiroki Arimura, Takashi Nishibayashi, Shin-Ichi Minato
    Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 129685 897 - 906 2017年08月13日 [査読有り][通常論文]
     
    Emerging patterns are patterns whose support significantly differs between two databases. We study the problem of listing emerging patterns with a multiple testing guarantee. Recently, Terada et al. proposed the Limitless Arity Multiple-testing Procedure (LAMP) that controls the family-wise error rate (FWER) in statistical association mining. LAMP reduces the number of "untestable" hypotheses without compromising its statistical power. Still, FWER is restrictive, and as a result, its statistical power is inherently unsatisfying when the number of patterns is large. On the other hand, the false discovery rate (FDR) is less restrictive than FWER, and thus controlling FDR yields a larger number of significant patterns. We propose two emerging pattern mining methods: the first one controls FWER, and the second one controls FDR. The effectiveness of the methods is verified in computer simulations with real-world datasets.
  • Iku Ohama, Hiromi Iida, Takuya Kida, Hiroki Arimura
    Proc. the 26th International Joint Conference on Artificial Intelligence (IJCAI 2017) 2578 - 2584 2017年08月 [査読有り][通常論文]
  • Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki Arimura
    CoRR abs/1707.02740 2017年 [査読有り][通常論文]
  • Takuya Takagi, Keisuke Goto, Yuta Fujishige, Shunsuke Inenaga, Hiroki Arimura
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10508 304 - 316 2017年 [査読有り][通常論文]
     
    In this paper, we propose a novel approach to combine compact directed acyclic word graphs (CDAWGs) and grammar-based compression. This leads us to an efficient self-index, called Linear-size CDAWGs (L-CDAWGs), which can be represented with O(ẽT log n) bits of space allowing for O(log n) -time random and O(1)-time sequential accesses to edge labels, and O(m log σ + occ) -time pattern matching. Here, ẽT is the number of all extensions of maximal repeats in T, n and m are respectively the lengths of the text T and a given pattern, σ is the alphabet size, and occ is the number of occurrences of the pattern in T. The repetitiveness measure ẽT is known to be much smaller than the text length n for highly repetitive text. For constant alphabets, our L-CDAWGs achieve O(m + occ ) pattern matching time with O(eT r log n) bits of space, which improves the pattern matching time of Belazzougui et al.’s run-length BWT-CDAWGs by a factor of log log n, with the same space complexity. Here, eT r is the number of right extensions of maximal repeats in T. As a byproduct, our result gives a way of constructing a straight-line program (SLP) of size O(ẽT) for a given text T in O(n + ẽT log σ) time.
  • Mayumbo Nyirenda, Ryosuke Omori, Heidi L. Tessmer, Hiroki Arimura, Kimihito Ito
    PLOS ONE 11 11 e0166107  2016年11月 [査読有り][通常論文]
     
    The prediction of the lineage dynamics of influenza B viruses for the next season is one of the largest obstacles for constructing an appropriate influenza trivalent vaccine. Seasonal fluctuation of transmissibility and epidemiological interference between the two major influenza B lineages make the lineage dynamics complicated. Here we construct a parsimonious model describing the lineage dynamics while taking into account seasonal fluctuation of transmissibility and epidemiological interference. Using this model we estimated the epidemiological and evolutional parameters with the time-series data of the lineage specific isolates in Japan from the 2010-2011 season to the 2014-2015 season. The basic reproduction number is similar between Victoria and Yamagata, with a minimum value during one year as 0.82 (95% highest posterior density (HPD): 0.77-0.87) for the Yamagata and 0.83 (95% HPD: 0.74-0.92) for Victoria, the amplitude of seasonal variation of the basic reproduction number is 0.77 (95% HPD: 0.66-0.87) for Yamagata and 1.05 (95% HPD: 0.89-1.02) for Victoria. The duration for which the acquired immunity is effective against infection by the Yamagata lineage is shorter than the acquired immunity for Victoria, 424.1days (95% HPD: 317.4-561.5days). The reduction rate of susceptibility due to immune cross-reaction is 0.51 (95% HPD: 0.084-0.92) for the immunity obtained from the infection with Yamagata against the infection with Victoria and 0.62 (95% HPD: 0.42-0.80) for the immunity obtained from the infection with Victoria against the infection with Yamagata. Using estimated parameters, we predicted the dominant lineage in 2015-2016 season. The accuracy of this prediction is 68.8% if the emergence timings of the two lineages are known and 61.4% if the emergence timings are unknown. Estimated seasonal variation of the lineage specific reproduction number can narrow down the range of emergence timing, with an accuracy of 64.6% if the emergence times are assumed to be the time at which the estimated reproduction number exceeds one.
  • Shuhei Denzumi, Ryo Yoshinaka, Hiroki Arimura, Shin-ichi Minato
    DISCRETE APPLIED MATHEMATICS 212 61 - 80 2016年10月 [査読有り][通常論文]
     
    The manipulation of large sequence data is one of the most important problems in string processing. In this paper, we discuss a new data structure for storing and manipulating sets of strings, called Sequence Binary Decision Diagrams (sequence BDDs), which has recently been introduced by Loekito et al. (2010) as a descendant of both acyclic DFAs (ADFAs) and binary decision diagrams (BDDs). Sequence BDDs can compactly represent sets of sequences similarly to minimal ADFAs, and allow efficient set operations inherited from BDDs. We study fundamental properties of sequence BDDs, such as the characterization of minimal sequence BDDs by reduced sequence BDDs, non-trivial relationships between sizes of minimal sequence BDDs and minimal ADFAs, the complexities of minimization, Boolean set operations, and sequence BDD construction. We also show experimental results for real and artificial data sets. (C) 2014 Elsevier B.V. All rights reserved.
  • Takuya Takagi, Shunsuke Inenaga, Hiroki Arimura
    Proc. the 27th Annual Symposium on Combinatorial Pattern Matching (CPM'16), Leibniz International Proceedings in Informatics (LIPIcs) 54 22:1 - 22:13 2016年06月 [査読有り][通常論文]
  • Iku Ohama, Hiromi Iida, Takuya Kida, Hiroki Arimura
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E99D 4 1139 - 1152 2016年04月 [査読有り][通常論文]
     
    Latent variable models for relational data enable us to extract the co-cluster structures underlying observed relational data. The Infinite Relational Model (IRM) is a well-known relational model for discovering co-cluster structures with an unknown number of clusters. The IRM assumes that the link probability between two objects (e.g., a customer and an item) depends only on their cluster assignment. However, relational models based on this assumption often lead us to extract many non-informative and unexpected clusters. This is because the underlying co-cluster structures in real-world relationships are often destroyed by structured noise that blurs the cluster structure stochastically depending on the pair of related objects. To overcome this problem, in this paper, we propose an extended IRM that simultaneously estimates denoised clear co-cluster structure and a structured noise component. In other words, our proposed model jointly estimates cluster assignment and noise level for each object. We also present posterior probabilities for running collapsed Gibbs sampling to infer the model. Experiments on real-world datasets show that our model extracts a clear co-cluster structure. Moreover, we confirm that the estimated noise levels enable us to extract representative objects for each cluster.
  • Mayumbo Nyirenda, Hiroki Arimura, Kimihito Ito
    PROCEEDINGS OF 2016 5TH INTERNATIONAL CONFERENCE ON MULTIMEDIA COMPUTING AND SYSTEMS (ICMCS) 189 - 194 2016年 [査読有り][通常論文]
     
    Data access of a massive collection of geographic spatial data is one of the serious bottlenecks in large-scale datacentric applications in the big data era such as data assimilation and urban data analytic systems. In this paper, we consider the issue of implementation of distributed spatial indices, specifically quad trees, on a distributed computing system in the shared-nothing memory approach. We discuss static and dynamic partitioning and allocation strategies for data and queries across distributed nodes. Using scale-down parallel data load and search experiments with a small distributed processor system as proof-of-concept, we show that the proposed approach with a collection of small indices of distributed shared-nothing memory is more efficient than the conventional approach with a single processor with a large external index. We also observed that the proposed tree-based partitioning and assignment strategy using sampling reduces query time than other conventional partitioning strategies used in databases. We also discuss how to allocate a collection of small tree indices among distributed processors. These results suggest that the use of parallelized access to databases with spatial indexing functions can enhance the throughput of large-scale data-centric applications.
  • Kunihiro Wasa, Katsuhisa Yamanaka, Hiroki Arimura
    LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS, LATA 2016 9618 330 - 342 2016年 [査読有り][通常論文]
     
    A reconfiguration problem asks when we are given two feasible solutions A and B, whether there exists a reconfiguration sequence (A(0) = A, A(1),..., A(l) = B) such that (i) A(0),..., A(l) are feasible solutions and (ii) we can obtain A(i) from A(i-1) under the prescribed rule (the reconfiguration rule) for each i = 1,..., l. In this paper, we address the reconfiguration problem for induced trees, where an induced tree is a connected and acyclic induced graph of an input graph. This paper treats the following two rules as the prescribed rules: Token Jumping; removing u from an induced tree and adding v to the tree, and Token Sliding; removing u from an induced tree and adding v adjacent to u to the tree, where u and v are vertices in an input graph. As the main results, we show (I) the reconfiguration problem is PSPACE-complete, (II) the reconfiguration problem is W[1]-hard when parameterized by both the size of induced trees and the length of the reconfiguration sequence, and (III) there exists an FPT algorithm when parameterized by both the size of induced trees and the maximum degree of an input graph, under each of Token Jumping and TOKEN SLIDING.
  • Takuya Takagi, Shunsuke Inenaga, Kunihiko Sadakane, Hiroki Arimura
    Combinatorial Algorithms 9843 213 - 225 2016年 [査読有り][通常論文]
     
    We present a new data structure called the packed compact trie (packed c-trie) which stores a set S of k strings of total length n in n log sigma + O(k log n) bits of space and supports fast pattern matching queries and updates, where sigma is the alphabet size. Assume that a = log(sigma) n letters are packed in a single machine word on the standard word RAM model, and let f (k, n) denote the query and update times of the dynamic predecessor/successor data structure of our choice which stores k integers from universe [1, n] in O (k log n) bits of space. Then, given a string of length m, our packed c- tries support pattern matching queries and insert/delete operations in O(m/alpha f (k, n)) worst-case time and in O(m/alpha + f (k, n)) expected time. Our experiments show that our packed c-tries are faster than the standard compact tries (a.k.a. Patricia trees) on real data sets. We also discuss applications of our packed c-tries.
  • 二部グラフ中に含まれる弦二部誘導グラフの列挙
    和佐 州洋, 有村 博紀, 宇野 毅明, 平田 耕一
    第154回情報処理学会アルゴリズム研究会 154 1 - 8 2015年09月 [査読無し][通常論文]
  • Iku Ohama, Takuya Kida, Hiroki Arimura
    Proc. 2015 SIAM International Conference on Data Mining (SDM'15) 9  2015年04月 [査読有り][通常論文]
  • 大規模軌跡データからの群パターン発見のための実用的アルゴリズム
    耿 暁亮, 宇野 毅明, 有村 博紀
    Transactions of IPSJ 56 4 1292 - 1304 2015年04月 [査読有り][通常論文]
  • Yoichi Sasaki, Tetsuo Shibuya, Kimihito Ito, Hiroki Arimura
    SIMILARITY SEARCH AND APPLICATIONS, SISAP 2015 9371 191 - 203 2015年 [査読有り][通常論文]
     
    In this paper, we study approximate point subset match (APSM) problem with minimum RMSD score under translation, rotation, and one-to-one correspondence in d-dimension. Since this problem seems computationally much harder than the previously studied APSM problems with translation only or distance evaluation only, we focus on speed-up of exhaustive search algorithms that can find all approximate matches. First, we present an efficient branch-and-bound algorithm using a novel lower bound function of the minimum RMSD score. Next, we present another algorithm that runs fast with high probability when a set of parameters are fixed. Experimental results on real 3-D molecular data sets showed that our branch-and-bound algorithm achieved significant speed-up over the naive algorithm still keeping the advantage of generating all answers.
  • 文字列の圧縮列挙索引技術とパターン照合技術
    伝住周平, 有村博紀, 定兼邦彦
    電子情報通信学会誌 97 12 1080 - 1085 2014年12月 [査読有り][通常論文]
  • Xiaoliang Geng, Takuya Takagi, Hiroki Arimura, Takeaki Uno
    Proceedings of the 5th ACM SIGSPATIAL International Workshop on GeoStreaming, IWGS 2014 53 - 61 2014年11月04日 [査読有り][通常論文]
     
    In this paper, we consider the problem of mining the complete set of spatio-temporal patterns, called maximal-duration flock patterns (Gudmundsson and van Kreveld, Proc. ACM GIS 2006) from massive mobile GPS location streams. Such algorithms are useful for mining and analysis of real-time geographic streams in geographic information systems. Although a polynomial time algorithm exists for finding a maximal-duration flock pattern from a collection of trajectories, it has not been known whether it is possible to find all maximal-duration flock patterns with theoretical guarantee of its computational complexity. For this problem, we present efficient depth-first algorithms for finding all maximal-duration patterns in a collection of trajectories without duplicates that run in polynomial time per discovered pattern using polynomial space in the total size of input trajectories. To achieve the output-sensitive complexity above, our algorithms adopt depth-first search strategy to avoid the use of exponentially large memory. We also propose a speed-up technique using geometric indexes. Finally, we show experimental results on artificial data to evaluate the proposed algorithms.
  • Hirohito Sasakawa, Hiroki Harada, David A. Du Verle, Hiroki Arimura, Koji Tsuda, Jun Sakuma
    Proceedings of the ACM Conference on Computer and Communications Security 21 - 30 2014年11月03日 [査読有り][通常論文]
     
    Various string matching problems can be solved by means of a deterministic finite automaton (DFA) or a non-deterministic finite automaton (NFA). In non-oblivious cases, DFAs are often preferred for their run-time efficiency despite larger sizes. In oblivious cases, however, the inevitable computation and communication costs associated with the automaton size are more favorable to NFAs. We propose oblivious protocols for NFA evaluation based on homomorphic encryption and demonstrate that our method can be orders of magnitude faster than DFA-based methods, making it applicable to real-life scenarios, such as privacy-preserving detection of viral infection using genomic data.
  • Ryutaro Kurai, Norihito Yasuda, Hiroki Arimura, Shinobu Nagayama, Shin-ichi Minato
    Proc. Prague Stringology Conference 2014 (PSC'14) 3 - 16 2014年09月 [査読有り][通常論文]
  • K-縮退グラフに含まれる誘導木の列挙
    和佐州洋, 有村博紀, 宇野毅明
    第148回情報処理学会アルゴリズム研究会 148 17 1 - 6 2014年06月 [査読無し][通常論文]
  • Kunihiro Wasa, Yusaku Kaneta, Takeaki Uno, Hiroki Arimura
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E97D 3 421 - 430 2014年03月 [査読有り][通常論文]
     
    By the motivation to discover patterns in massive structured data in the form of graphs and trees, we study a special case of the k-subtree enumeration problem with a tree of n nodes as an input graph, which is originally introduced by (Ferreira, Grossi, and Rizzi, ESA' 11, 275-286, 2011) for general graphs. Based on reverse search technique (Avis and Fukuda, Discrete Appl. Math., vol.65, pp.21-46, 1996), we present the first constant delay enumeration algorithm that lists all k-subtrees of an input rooted tree in O(1) worst-case time per subtree. This result improves on the straightforward application of Ferreira et al's algorithm with O(k) amortized time per subtree when an input is restricted to tree. Finally, we discuss an application of our algorithm to a modification of the graph motif problem for trees.
  • Shuhei Denzumi, Jun Kawahara, Koji Tsuda, Hiroki Arimura, Shin-ichi Minato, Kunihiko Sadakane
    EXPERIMENTAL ALGORITHMS, SEA 2014 8504 187 - 198 2014年 [査読有り][通常論文]
     
    In many real-life problems, we are often faced with manipulating families of sets. Manipulation of large-scale set families is one of the important fundamental techniques for web information retrieval, integration, and mining. For this purpose, a special type of binary decision diagrams (BDDs), called Zero-suppressed BDDs (ZDDs), is used. However, current techniques for storing ZDDs require a huge amount of memory and membership operations are slow. This paper introduces DenseZDD, a compressed index for static ZDDs. Our technique not only indexes set families compactly but also executes fast member membership operations. We also propose a hybrid method of DenseZDD and ordinary ZDDs to allow for dynamic indices.
  • Kunihiro Wasa, Hiroki Arimura, Takeaki Uno
    ALGORITHMS AND COMPUTATION, ISAAC 2014 8889 94 - 102 2014年 [査読有り][通常論文]
     
    In this paper, we address the problem of enumerating all induced subtrees in an input k-degenerate graph, where an induced subtree is an acyclic and connected induced subgraph. A graph G = (V, E) is a k-degenerate graph if for any its induced subgraph has a vertex whose degree is less than or equal to k, and many real-world graphs have small degeneracies, or very close to small degeneracies. Although, the studies are on subgraphs enumeration, such as trees, paths, and matchings, but the problem addresses the subgraph enumeration, such as enumeration of subgraphs that are trees. Their induced subgraph versions have not been studied well. One of few examples is for chordless paths and cycles. Our motivation is to reduce the time complexity close to O(1) for each solution. This type of optimal algorithms is proposed many subgraph classes such as trees, and spanning trees. Induced subtrees are fundamental object thus it should be studied deeply and there possibly exist some efficient algorithms. Our algorithm utilizes nice properties of k-degeneracy to state an effective amortized analysis. As a result, the time complexity is reduced to O(k) time per induced subtree. The problem is solved in constant time for each in planar graphs, as a corollary.
  • Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagrams
    Shuhei Denzumi, Koji Tsuda, Hiroki Arimura, Shin-ichi Minato
    In Proc. of Prague Stringology Conference 2013 (PSC2013) 157 - 167 2013年09月 [査読有り][通常論文]
  • 有村 博紀, 耿 暁亮, 宇野 毅明
    第144回情報処理学会アルゴリズム研究会 2013-AL-144 3 1 - 8 一般社団法人情報処理学会 2013年05月 [査読無し][通常論文]
     
    本論文では，（Gudmundsson and van Kreveld, ACM GIS 2006; Benkert, Gudmundsson et al., Computational Geometry, 41(111), 2008）によって導入された群れパターン（flock pattern）の軌跡集合データからの発見問題について考察する．L2ノルムをもつ2次元平面上の軌跡集合に対して，最大幅と最小長さが固定の時に，最大数の軌跡を含む群れパターンを見つける問題は，直径の2-σを許してもNP困難である．その一方で，最小軌跡数と最大幅が固定で，長さ最大の群れパターン一つは多項式時間で求まることが示されている．これに対して，本論文では，L∞ノルムをもつ2次元平面上のn本の長さTの軌跡の集合に対して，最大幅rかつ最小長さk以上で，長さ（方向の区間）極大の群れパターンをO(mnT2)遅延とO(m2)領域ですべて列挙する多項式時間遅延かつ多項式領域の列挙アルゴリズムを与える．ここに，m = |X|は列挙されるパターンのサイズ（それが含む軌跡数）である．In this paper, we study the problem of finding a class of spatio-temporal patterns called (m, k)-flock patterns (Gudmundsson and van Kreveld, Proc. ACM GIS'06; Benkert, Gudmundsson, Hubner, Wolle, Computational Geometry, 41:11, 2008), which represent a groups of moving objects close each other within width at most r under L∞-norm in a given time segment of length at least k, in a collection of 2-dimensional trajectories. For max-width r > 0, min-length k, and a collection S of n trajectories of legnth T, the proposed algorithm finds all length-maximal (m, k) flock patterns in an input collection of trajectory data in O(pnT2) delay and O(p2) space, p = |X| is the size of ID set being enumerated. We also present a practical improvement using geometric indexes.
  • Shuhei Denzumi, Jun Kawahara, Koji Tsuda, Hiroki Arimura, Kunihiko Sadakane, Shin-ichi Minato
    電子情報通信学会コンピュテーション研究会, 信学技報 112 498 23 - 30 一般社団法人電子情報通信学会 2013年03月 [査読無し][通常論文]
     
    多くの実問題の中において,集合族を扱う必要に迫られることはままあることである.大規模な集合族を操作することはウェブからの情報抽出や,情報統合,データマイニングに対する重要な基盤技術である.こういった目的に対し,ゼロサプレス型二分決定グラフ(ZDD)と呼ばれる特別な二分決定グラフ(BDD)が使用されることがある.しかしながらZDDを格納するためには巨大なメモリ領域が必要であり,また所属性判定演算も低速であるという問題がある.本論文では静的なZDDを圧縮した索引である密集ゼロサプレス型二分決定グラフ(DenseZDD)を導大する.この技術では集合族をコンパクトに索引化するだけではなく所属性判定演算も高速に行えるようになる.さらに,DenseZDDと通常のZDDの混成手法により動的な索引を実現する方法も提案する.
  • 山本 潤, 岩森利弘, 星 直樹, 阿部拓三, 坂岡桂一郎, 亀井佳彦, 高木省吾, 沼本 修, 阪 幸宏, 桜井泰憲, 末岡和久, 有村博紀, 渡邉日出海
    水産技術 5 2 171 - 174 水産総合研究センター 2013年02月 [査読有り][通常論文]
     
    We developed a battery powered compact 2000m class ROV (Remotely Operated Vehicle) system with a High-Definition video camera. It does not require specialized equipment to operate. It can be operated using only general purpose equipment. This system mainly consists of a shipboard controller, a vehicle and a launcher. A thin, light optical fiber cable (diameter 9mm, length 2,500m), the primary cable, transfers control data and video images between the shipboard controller and the launcher. The secondary cable, a composite cable (diameter 14.2mm, length 50m), transfers control data and video images and supplies power to the vehicle from the six packs of lithium-ion batteries, which are mounted in the launcher. The launcher is suspended by a rope from the support ship, and the depth of the launcher is adjusted by changing the length of the rope using a general purpose rewinder.
    Although initially, we had some trouble due to the launcher rope and the primary cable getting tangled, a newly-designed instrument that restricts the movement of the carabiner, and the use of a low expansion rope, facilitated smoother operation and an easier recovery of the ROV.
  • Kunihiro Wasa, Kouichi Hirata, Takeaki Uno, Hiroki Arimura
    SIMILARITY SEARCH AND APPLICATIONS (SISAP) 8199 73 - 84 2013年 [査読有り][通常論文]
     
    In this paper, we study efficient computation of tree similarity for ordered trees based on compressed subtree enumeration. The compressed subtree enumeration is a new paradigm of enumeration algorithms that enumerates all subtrees of an input tree T in the form of their compressed bit signatures. For the task of enumerating all compressed bit signatures of k-subtrees in an ordered tree T, we first present an enumeration algorithm in O(k)-delay, and then, present another enumeration algorithm in constant-delay using O(n) time preprocessing that directly outputs bit signatures. These algorithms are designed based on bit-parallel speed-up technique for signature maintenance. By experiments on real and artificial datasets, both algorithms showed approximately 22% to 36% speed-up over the algorithms without bit-parallel signature maintenance.
  • Iku Ohama, Hiromi Iida, Takuya Kida, Hiroki Arimura
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7819 2 147 - 159 2013年 [査読有り][通常論文]
     
    The Infinite Relational Model (IRM) introduced by Kemp et al. (Proc. AAAI2006) is one of the well-known probabilistic generative models for the co-clustering of relational data. The IRM describes the relationship among objects based on a stochastic block structure with infinitely many clusters. Although the IRM is flexible enough to learn a hidden structure with an unknown number of clusters, it sometimes fails to detect the structure if there is a large amount of noise or outliers. To overcome this problem, in this paper we propose an extension of the IRM by introducing a subset mechanism that selects a part of the data according to the interaction among objects. We also present posterior probabilities for running collapsed Gibbs sampling to learn the model from the given data. Finally, we ran experiments on synthetic and real-world datasets, and we showed that the proposed model is superior to the IRM in an environment with noise. © Springer-Verlag 2013.
  • Kunihiro Wasa, Takeaki Uno, Kouichi Hirata, Hiroki Arimura
    DISCOVERY SCIENCE 8140 308 - 323 2013年 [査読有り][通常論文]
     
    In this paper, we study the problem of finding all tree-like substructure contained in a hypergraph, with potential applications to substructure mining from relational data. We employ the class of connected and Berge acyclic sub-hypergraphs as definition of tree-like substructures, which is the most restricted notion of acyclicities for hypergraphs. Then, we present an efficient depth-first algorithm that finds all connected and Berge acyclic sub-hypergraphs S in a hypergraph H with m hyperedges and n vertices in O(nm(2)) time per solution (delay) using O(N) space, where N = parallel to H parallel to is the total input size. To achieve efficient enumeration, we use the notion of the maximum border set. This result gives the first polynomial delay and time algorithm for enumeration of connected and Berge-acyclic sub-hypergraphs. We also present an incremental enumeration algorithm that finds all solutions S in O(Delta MB(S)tau(m)) = O(rd .tau (m)) delay using O(N) space and preprocessing, whose delay depends only on the difference of solutions, where S is the enumerated sub-hypergraph, Delta MB(S) is the number of newly added hyperedges to the maximum border of S, r and d are the rank and degree of H, respectively, and tau(m) = ((log logm)(2)/log log logm).
  • 超グラフ中に含まれる非巡回部分超グラフの効率よい列挙,
    和佐州洋, 有村博紀, 宇野毅明, 平田耕一
    第88回人工知能基本問題研究会 88 85 - 90 2013年01月 [査読無し][通常論文]
  • Ryo Yoshinaka, Jun Kawahara, Shuhei Denzumi, Hiroki Arimura, Shin-ichi Minato
    INFORMATION PROCESSING LETTERS 112 16 636 - 640 2012年08月 [査読有り][通常論文]
     
    In this article, we disprove the long-standing conjecture, proposed by R.E. Bryant in 1986, that his binary decision diagram (BDD) algorithm computes any binary operation on two Boolean functions in linear time in the input-output sizes. We present Boolean functions for which the time required by Bryant's algorithm is a quadratic of the input-output sizes for all nontrivial binary operations, such as boolean AND, boolean OR, and circle plus. For the operations boolean AND and boolean OR. we show an even stronger counterexample where the output BDD size is constant, but the computation time is still a quadratic of the input BDD size. In addition, we present experimental results to support our theoretical observations. (C) 2012 Elsevier B.V. All rights reserved.
  • Yusaku Kaneta, Hiroki Arimura, Rajeev Raman
    Journal of Discrete Algorithms 14 119 - 135 2012年07月 [査読有り][通常論文]
     
    In this paper, we consider the unordered pseudo-tree matching problem, which is a problem of, given two unordered labeled trees P and T, finding all occurrences of P in T via such many-to-one matchings that preserve node labels and parent-child relationship. This problem is closely related to the tree pattern matching problem for XPath queries with child axis only. If m> w, we present an efficient algorithm that solves the problem in O(nmlog(w)/w) time using O(hm/w+mlog(w)/w) space and O(mlog(w)) preprocessing on a unit-cost arithmetic RAM model with addition, where m is the number of nodes in P, n is the number of nodes in T, h is the height of T, and w is the word length, and we assume that w≥logn. We also discuss a modification of our algorithm for the unordered tree homeomorphism problem, which corresponds to the tree pattern matching problem for XPath queries with descendant axis only. © 2011 Elsevier B.V.
  • Yusaku Kaneta, Shingo Yoshizawa, Shin-ichi Minato, Hiroki Arimura, Yoshikazu Miyanaga
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E95D 7 1847 - 1857 2012年07月 [査読有り][通常論文]
     
    In this paper, we propose a novel architecture for large-scale regular expression matching, called dynamically reconfigurable bit-parallel NFA architecture (Dynamic BP-NFA), which allows dynamic loading of regular expressions on-the-fly as well as efficient pattern matching for fast data streams. This is the first dynamically reconfigurable hardware with guaranteed performance for the class of extended patterns, which is a subclass of regular expressions consisting of union of characters and its repeat. This class allows operators such as character classes, gaps, optional characters, and bounded and unbounded repeats of character classes. The key to our architecture is the use of bit-parallel pattern matching approach, in which the information of an input non-deterministic finite automaton (NFA) is first compactly encoded in bit-masks stored in a collection of registers and block RAMs. Then, the NFA is efficiently simulated by a fixed circuitry using bitwise Boolean and arithmetic operations consuming one input character per clock regardless of the actual contents of an input text. Experimental results showed that our hardwares for both string and extended patterns were comparable to previous dynamically reconfigurable hardwares in their performances.
  • 笹川 裕人, 金田 悠作, 有村 博紀
    日本データベース学会論文誌 11 1 55 - 60 日本データベース学会 2012年06月 [査読無し][通常論文]
  • 伝住 周平, 有村 博紀, 湊 真一
    電子情報通信学会技術研究報告 : 信学技報 112 93 9 - 16 電子情報通信学会 2012年06月 [査読無し][通常論文]
     
    大規模な文字列データを操作することは文字列処理の分野において重要な課題である.本稿では2009年にLoekitoらによって提案された系列二分決定グラフ(Sequence Binary Decision Diagram)と呼ばれるデータ構造を取り扱う.このデータ構造は多数の文字列を要素として含む文字列集合をコンパクトかつ一意に表現し,演算処理を効率良く行える.しかし,今まで提案された処理系では最小限の基本的な集合演算しか用意されていなかった.本稿では系列二分決定グラフの基本的な構造を示した上で,多様かつ高機能な文字列集合の演算体系を定義し,それらを実現する効率の良いアルゴリズムを提案する.
  • 木に含まれる限定サイズ部分木の列挙
    和佐 州洋, 宇野 毅明, 有村 博紀
    第140回情報処理学会アルゴリズム研究会 2012-AL-140 4 1 - 8 2012年05月 [査読無し][通常論文]
  • Kunihiro Wasa, Yusaku Kaneta, Takeaki Uno, Hiroki Arimura
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7434 347 - 359 2012年 [査読有り][通常論文]
     
    By the motivation to discover patterns in massive structured data in the form of graphs and trees, we study a special case of the ksubtree enumeration problem, originally introduced by (Ferreira, Grossi, and Rizzi, ESA'11, 275-286, 2011), where an input graph is a tree of n nodes. Based on reverse search technique, we present the first constant delay enumeration algorithm that lists all k-subtrees of an input tree in O(1) worst-case time per subtree. This result improves on the straightforward application of Ferreira et al's algorithm with O(k) amortized time per subtree when an input is restricted to tree. Finally, we discuss an application of our algorithm to a modification of the graph motif problem for trees. © 2012 Springer-Verlag.
  • Xiaoliang Geng, Hiroki Arimura, Takeaki Uno
    Proceedings of the 2012 IIAI International Conference on Advanced Applied Informatics, IIAIAAI 2012 60 - 65 2012年 [査読有り][通常論文]
     
    In this paper, we consider data mining from large discrete trajectory data. We study closed pattern mining for the class of trajectory envelope patterns. First, we introduce the basic definition of trajectory data. Then, we present a depthfirst search algorithm that finds all trajectory envelope patterns in a given database that satisfies constrants on maximum width, minimum length, and minimum frequency. Finally, we ran experiments on a real trajectory dataset to evaluate our algorithm. © 2012 IEEE.
  • Hirohito Sasakawa, Hiroki Arimura
    Proceedings of the 2012 IIAI International Conference on Advanced Applied Informatics, IIAIAAI 2012 66 - 71 2012年 [査読有り][通常論文]
     
    In this paper, we study massive trajectory search based on string matching technology. We first propose byteoriented encoding scheme for trajectory data allowing multiresolution search. Then, we present an efficient bit-parallel trajectory matching algorithm on byte-oriented encoded texts based on Extended SHIFT-AND method (Navarro and Raffinot, RECOMB 2001). Finally, we ran experiments on the real world trajectory data to evaluate the efficiency of the proposed algorithm. The results showed good performance enough for real applications. © 2012 IEEE.
  • High-speed String and Regular Expression Matching on FPGA
    Yusaku Kaneta, Shingo Yoshizawa, Shin-ichi Minato, Hiroki Arimura
    Proc. of Asia Pacific Signal and Information Processing Association Annual Summit and Conference 2011 (APSIPA ASC 2011 2011年10月 [査読有り][通常論文]
  • Yusaku Kaneta, Hiroki Arimura
    COMBINATORIAL ALGORITHMS 6460 68 - 81 2011年 [査読有り][通常論文]
     
    In this paper, we consider the unordered pseudo-tree matching problem, which is a problem of, given two unordered labeled trees P and T, finding all occurrences of P in via such many-one embeddings that preserve node labels and parent-child relationship. This problem is closely related to tree pattern matching problem for XPath queries with child axis only. If m > we present an efficient algorithm that solves the problem in O(nm log(w)/w) time using O(hm/w + m log(w)/w) space and O(m log(w)) preprocessing on a unit-cost arithmetic RAM model with addition, where in is the number of nodes in P, n is the number of nodes in T, h is the height of T, and w is the word length. We also discuss a modification of our algorithm for the unordered tree homeomorphism problem, which corresponds to a tree pattern matching problem for XPath queries with descendant axis only.
  • Shuhei Denzumi, Ryo Yoshinaka, Hiroki Arimura, Shin-ichi Minato
    PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2011 147 - 161 2011年 [査読有り][通常論文]
     
    Manipulation of large sequence data is one of the most important problems in string processing. Recently, Loekito et al. (Knowl. Inf. Syst., 24(2), 235-268, 2009) have introduced a new data structure, called Sequence Binary Decision Diagrams (SeqBDDs, or SDDs), which are descendants of both acyclic DFAs (ADFAs) and binary decision diagrams (BDDs). SDDs can compactly represent sets of sequences as well as minimal ADFAs, while SDDs allow efficient set operations inherited from BDDs. A novel feature of the SDDs is that different SDDs can share equivalent subgraphs and duplicated computation in common to save the time and space in various operations. In this paper, we study fundamental properties of SDDs. In particular, we first present non-trivial relationships between sizes of minimum SDDs and minimal ADFAs. We then analyze the complexities of algorithms for Boolean set operations, called the binary synthesis. Finally, we show experimental results to confirm the results of the theoretical analysis on real data sets.
  • Shuhei Denzumi, Hiroki Arimura, Shin-ichi Minato
    ERLANG 11: PROCEEDINGS OF THE 2011 ACM SIGPLAN ERLANG WORKSHOP 90 - 91 2011年 [査読有り][通常論文]
     
    In this paper, we present an implementation of Erlang of an efficient index structure, called Sequence Binary Decision Diagrams (SeqBDDs), for knowledge discovery in large sequence data. Recently, Loekito, Bailey, and Pei (KAIS, 2009) proposed SeqBDD. SeqBDDs are a compact indices for efficiently representing the set of sequences. Furthermore, SeqBDDs provide a rich collection of operations for sets of sequences, which are useful for implementing sequence mining algorithms. We propose SeqBDDs as powerful framework for string processing and Erlang is appropriate language for SeqBDD. SeqBDD system heavily uses hash tables to avoid redundant memory and computation. We implemented SeqBDD package with ETS for hash tables.
  • Takashi Uemura, Hiroki Arimura
    COMBINATORIAL PATTERN MATCHING, 22ND ANNUAL SYMPOSIUM, CPM 2011 6661 246 - 260 2011年 [査読有り][通常論文]
     
    The sparse suffix trees (SST), introduced by (Karkkainen and Ukkonen, COCOON 1996), is the suffix tree for a subset of all suffixes of an input text T of length n. In this paper, we study a special case that an input string is a sequence of k codewords drawn from a regular prefix code Delta subset of Sigma(+) recognized by a finite automaton, and index points locate on the code boundaries. In this case, we present an online algorithm that constructs the sparse suffix tree for an input string T on any variable-length regular prefix code, called the code suffix tree (CST), in O(n + m) time and O(k) additional space for a fixed base alphabet Sigma, where m is the size of an automaton for.. Furthermore, we present a modified algorithm for l-truncated version of code suffix trees that runs in the same time and space complexities. Hence, these results generalize the previous results (Inenaga and Takeda, CPM 2006) for word suffix trees and (Na, Apostolico, Iliopoulos, and Park, Theor. Comp. Sci., 304, 2003) for truncated suffix trees on arbitrary variable-length regular prefix codes, such as Huffman codes and multi-byte codes (e.g. UTF-8).
  • Uemura Takashi, Ikeda Daisuke, Kida Takuya, Arimura Hiroki
    Information and Media Technologies 6 1 231 - 240 Information and Media Technologies 編集運営会議 2011年 
    In this paper, we study content-based spam detection for spams that are generated by copying a seed document with some random perturbations. We propose an unsupervised detection algorithm based on an entropy-like measure called document complexity, which reflects how many similar documents exist in the input collection of documents. As the document complexity, however, is an ideal measure like Kolmogorov complexity, we substitute an estimated occurrence probability of each document for its complexity. We also present an efficient algorithm that estimates the probabilities of all documents in the collection in linear time to its total length. Experimental results showed that our algorithm especially works well for word salad spams, which are believed to be difficult to detect automatically.
  • Hiroki Arimura, Raoul Medina, Jean-Marc Petit, Franz Baader, Jean-François Boulicaut, Bruno Crémilleux, Luc De Raedt, Khaled Elbassioni, Alain Gely, Bart Goethals, Sergei Kuznetsov, Dominique Laurent, Hong-Cheu Liu, Joao Marques-Silva, Rokia Missaoui, Siegfried Nijssen, Lhouari Nourine, Marie-Christine Rousset, Lakhdar Sais, Thomas Schiex, Takeaki Uno, Jef Wijsen
    Proceedings - IEEE International Conference on Data Mining, ICDM liii - liv 2011年 [査読有り][通常論文]
  • Takashi Katoh, Hiroki Arimura, Kouichi Hirata
    NEW FRONTIERS IN ARTIFICIAL INTELLIGENCE 6284 331 - 344 2010年 [査読有り][通常論文]
     
    In this paper, we introduce the class of k-partite episodes, which are time-series patterns of the form < A(1), ... , A(k)> for sets A(i) (1 <= i <= k) of events meaning that, in an input event sequence, every event of A(i) is followed by every event of A(i+1) for every 1 <= i < k. Then, we present a backtracking algorithm KPAR and its modification KPAR2 that find all of the frequent k-partite episodes from an input event sequence without duplication. By theoretical analysis, we show that these two algorithms run in polynomial delay and polynomial space in total input size.
  • Yusaku Kaneta, Shin-ichi Minato, Hiroki Arimura
    STRING PROCESSING AND INFORMATION RETRIEVAL 6393 372 - 384 2010年 [査読有り][通常論文]
     
    In this paper, we extend the SHIFT-AND approach by Baeza-Yates and Gonnet (CACM 35(10), 1992) to the matching problem for network expressions, which are regular expressions without Kleene-closure and useful in applications such as bioinformatics and event stream processing. Following the study of Navarro (RECOMB, 2001) on the extended string matching, we introduce new operations called Scatter, Gather, and Propagate to efficiently compute epsilon-moves of the Thompson NFA using the Extended SHIFT-AND approach with integer addition. By using these operations and a property called the bi-monotonicity of the Thompson NFA, we present an efficient algorithm for the network expression matching that runs in O(ndm/w) time using O(dm) preprocessing and O(dm/w) space, where m and d are the length and the depth of a given network expression, n is the length of an input text, and w is the word length of the underlying computer. Furthermore, we show a modified matching algorithm for the class of regular expressions that runs in O(ndm log(m)/w) time.
  • Yusaku Kaneta, Shingo Yoshizawa, Shin-Ichi Minato, Hiroki Arimura, Yoshikazu Miyanaga
    Proceedings - 2010 International Conference on Field-Programmable Technology, FPT'10 21 - 28 2010年 [査読有り][通常論文]
     
    In this paper, we propose a novel FPGA-based architecture for large-scale regular expression matching, called dynamic reconfigurable bit-parallel NFA architecture (Dynamic BP-NFA) that allows dynamic reconfiguration of the patterns using bit-parallel NFA-simulation. This is the first dynamic reconfigurable FPGA-based hardware with guaranteed performance for the class of extended patterns, where an extended pattern is a restricted regular expression in linear form consisting of letters, classes of letters, don't cares, optional letters, bounded and unbounded length gaps and repeatable letters. The key to our architecture is the use of bit-parallel pattern matching approach that has been developed in string matching communities for the decades. In this approach, the information of an input NFA is compactly encoded in bit-masks stored in a collection of registers and block RAMs. Then, the NFA is efficiently simulated by a fixed circuitry using a combination of bit- and arithmetic-operations on these bit-masks consuming one input letter per clock. As compared with the previous approaches of DFA-based dynamic reconfigurable architectures, experimental results show that the proposed architecture achieves higher throughput for the class of exact string patterns and comparable for the class of extended patterns. © 2010 IEEE.
  • Katoh Takashi, Arimura Hiroki, Hirata Kouichi
    Information and Media Technologies 5 2 459 - 470 Information and Media Technologies 編集運営会議 2010年 
    In this paper, we study the problem of mining frequent diamond episodes efficientlyfrom an input event sequence with sliding a window. Here, a diamond episode is of the form a → E → b, which means that every event of E follows an event a and is followed by an event b. Then, we design a polynomial-delay and polynomial-space algorithm PolyFreqDmd that finds all of the frequent diamond episodes without duplicates from an event sequence in O(|Σ|2l) time per an episode and in O(|Σ|+l) space, where Σ and l are an alphabet and the length of the event sequence, respectively. Finally, we give experimental results on artificial and real-world event sequences with varying several mining parameters to evaluate the efficiency of the algorithm.
  • Tatsuya Asai, Seishi Okamoto, Hiroki Arimura
    NEW FRONTIERS IN APPLIED DATA MINING 5433 13 - + 2009年 [査読有り][通常論文]
     
    In this paper, we study the problem the problem of sorting a large collection of strings in external memory. Based on adaptive construction of a summary data structure, called adaptive synopsis trie, we present a practical string sorting algorithm DISTSTRSORT, which is suitable for sorting string collections of large size in external memory, and also suitable for more complex string processing problems in text and semi-structured databases such as counting, aggregation, and statistics. Case analyses of the algorithm and experiments on real datasets show the efficiency of our algorithm in realistic setting.
  • Takuya Kida, Tomoya Saito, Hiroki Arimura
    NEW FRONTIERS IN APPLIED DATA MINING 5433 1 - 12 2009年 [査読有り][通常論文]
     
    In this paper, we study a complex time-series patten matching problem over a multi-dimension continuos data stream. For each data stream, a pattern is given as a sequence of predicates, which specify a sequence of element sets on the stream. The pattern matching problem over such a multi-dimension data stream, is to find all occurrences where all predicates in the pattern. We consider four types of data streams especially: textual, categorical, ordered, and numeric, that is, those are a sequence of streings, concepts with taxonomic information, small integers, and real numbers (or large integers), respectiively. We also present that time complexities to do pattern matching for those data types.
  • Hideyuki Ohtani, Takuya Kida, Takeaki Uno, Hiroki Arimura
    Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication, ICUIMC'09 457 - 464 2009年 [査読有り][通常論文]
     
    Recently, knowledge discovery in large data increases its importance in various fields. Especially, data mining from time-series data gains much attention. This paper studies the problem of finding frequent episodes appearing in a sequence of events. We propose an efficient depth-first search algorithm for mining frequent serial episodes in a given event sequence using the notion of right-minimal occurrences. Then, we present some techniques for speeding up the algorithm, namely, occurrence-deliver and tail-redundancy pruning. Finally, we ran experiments on real datasets to evaluate the usefulness of the proposed methods. Copyright 2009 ACM.
  • Takashi Katoh, Hiroki Arimura, Kouichi Hirata
    DISCOVERY SCIENCE, PROCEEDINGS 5808 136 - + 2009年 [査読有り][通常論文]
     
    In this paper, first we introduce a bipartite episode of the form A bar right arrow B for two sets A and B of events, which means that every event of A is followed by every event of B. Then, we present an algorithm that finds all frequent bipartite episodes from an input sequence without duplication in O(vertical bar Sigma vertical bar . N) time per an episode and in O(vertical bar Sigma vertical bar(2)n) space, where Sigma is an alphabet, N is total input size of S, and n is the length of S. Finally, we give experimental results on artificial and real sequences to evaluate the efficiency of the algorithm.
  • 上村 卓史, 喜田 拓也, 有村 博紀
    電子情報通信学会論文誌. D, 情報・システム 91 3 595 - 607 一般社団法人電子情報通信学会 2008年03月 [査読無し][通常論文]
     
    プロパティ付きテキストとは，長さnのテキストに，補助情報としてテキスト上の互いにオーバラップを許した区間の集合(プロパティという)が付加された構造化文書の一種であり，アノテーション付きの系列データの形式的なモデルとなっている. このプロパティ付きテキストへの全文テキスト索引として， Amirら(CPM2006) は，プロパティ接尾辞木を提案した. これは，プロパティの各区間に含まれるすべての部分文字列を格納する索引構造であり，遺伝子情報や，ビデオストリーム，メタデータ付き時系列データなどへの応用がある. また，高度な検索問題である重み付きパターン照合にも用いられる. Amirらは，定数サイズのアルファベット上で，プロパティ接尾辞木をO(n log log n)時間でオフライン構築するアルゴリズムを与えたが，その線形時間構築アルゴリズムは，現在まで未解決の問題であった. 本論文では，定数アルファベット上で，プロパティ接尾辞木を線形時間で構築するオフラインアルゴリズムを与え，この問題を肯定的に解決する. 提案アルゴリズムは，接尾辞リンクの巡回を用いた簡潔な手法であり，理論的に効率良いだけでなく，実際のデータに対しても高速に動作する. 更に，人工データ上の計算機実験を行い，実際の性能を評価する.
  • Takeaki Uno, Hiroki Arimura
    ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PROCEEDINGS 5012 357 - + 2008年 [査読有り][通常論文]
     
    Mining frequently appearing patterns in a database is a basic problem in recent informatics, especially in data mining. Particularly, when the input database is a collection of subsets of an itemset, called transaction, the problem is called the frequent itemset mining problem, and it has been extensively studied. The items in a frequent itemset appear in many records simultaneously, thus they can be considered to be a cluster with respect to these records. However, in this sense, the condition that every item appears in each record is quite strong. We should allow for several missing items in these records. In this paper, we approach this problem from the algorithm theory, and consider the model that can be solved efficiently and possibly valuable in practice. We introduce ambiguous frequent itemsets which allow missing items in their occurrence records. More precisely, for given thresholds theta and sigma, an ambiguous frequent itemset P has a transaction set T, |T| >= sigma, such that on average, transactions in T include ratio theta of items of P. We formulate the problem of enumerating ambiguous frequent itemsets, and propose an efficient polynomial delay polynomial space algorithm. The practical performance is evaluated by computational experiments. Our algorithm can be naturally extended to the weighted version of the problem. The weighted version is a natural extension of the ordinary frequent itemset to weighted transaction databases, and is equivalent to finding submatrices with large average weights in their cells. An implementation is available at the author's homepage(1).
  • Shin-ichi Minato, Takeaki Uno, Hiroki Arimura
    ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PROCEEDINGS 5012 234 - + 2008年 [査読有り][通常論文]
     
    Frequent itemset mining is one of the fundamental techniques for data mining and knowledge discovery. In the last decade, a number of efficient algorithms have been presented for frequent itemset mining, but most of them focused on only enumerating the itemsets that satisfy the given conditions, and how to store and index the mining result in order to ensure an efficient data analysis is a different matter. In this paper, we propose a fast algorithm for generating very large-scale all/closed/maximal frequent itemsets using Zero-suppressed BDDs (ZBDDs), a compact graph-based data structure. Our method, "LCM over ZBDDs," is based on one of the most efficient state-of-the-art algorithms proposed thus far. Not only does it enumerate/list the itemsets, but it also generates a compact output data structure on the main memory. The result can be efficiently postprocessed by using algebraic ZBDD operations. The original LCM is known as an output linear time algorithm, but our new method requires a sub-linear time for the number of frequent patterns when the ZBDD-based data compression works well. Our method will greatly accelerate the data mining process and this will leads to a new style of on-memory processing for dealing with knowledge discovery problems.
  • Hiroki Arimura
    ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PROCEEDINGS 5012 2 - + 2008年 [査読有り][通常論文]
     
    In this talk, we study effcient algorithms that find frequent patterns and maximal (or closed) patterns from large collections of semi-structured data. We review basic techniques developed by the authors, called the rightmost expansion and the PPC-extension, respectively, for designing efficient frequent and maximal/closed pattern mining algorithms for large semi-structured data. Then, we discuss their applications to design of polynomial-delay and polynomial-space algorithms for frequent and maximal pattern mining of sets, sequences, trees, and graphs.
  • Takashi Uemura, Daisuke Ikeda, Hiroki Arimura
    DISCOVERY SCIENCE, PROCEEDINGS 5255 319 - + 2008年 [査読有り][通常論文]
     
    In this paper, we study a content-based spam detection for a specific type of spans, called blog and bulletin board spans. We develop an efficient unsupervised algorithm DCE that detects span documents from a mixture of spam and non-span documents using an entropy-like measure, called the document complexity. Using suffix trees, the algorithm computes the document complexity for all documents in linear time w.r.t. the total length of input documents. Experimental results showed that our algorithm especially works well for detecting word salad spans, which are believed to be difficult to detect automatically.
  • 擬似頻出アイテムの集合の多項式遅延列挙アルゴリズム
    宇野 毅明, 有村 博紀
    第4回 人工知能学会 データマイニングと統計数理研究会（SIG-DMSM）, 2007 2007年07月 [査読無し][招待有り]
  • Tatsuya Asai, Kenji Abe, Shinji Kawasoe, Hiroki Arimura, Setsuo Arikawa
    NEW FRONTIERS IN ARTIFICIAL INTELLIGENCE 3609 29 - + 2007年 [査読有り][通常論文]
     
    In this paper, we study an online data mining problem from streams of semi-structured data such as XML data. Modeling semi-structured data and patterns as labeled ordered trees, we present an online algorithm StreamT that receives fragments of an unseen possibly infinite semi-structured data in the document order through a data stream, and can return the current set of frequent patterns immediately on request at any time. We give modifications of the algorithm to other online mining models. Furthermore we implement our algorithms in different online models and candidate management strategies, then show empirical analyses to evaluate the algorithms.
  • Takeaki Uno, Hiroki Arimura
    DISCOVERY SCIENCE, PROCEEDINGS 4755 219 - + 2007年 [査読有り][通常論文]
     
    Mining frequently appearing patterns in a database is a basic problem in informatics, especially in data mining. Particularly, when the input database is a collection of subsets of an itemset, the problem is called the frequent itemset mining problem, and has been extensively studied. In the real-world use, one of difficulties of frequent itemset mining is that real-world data is often incorrect, or missing some parts. It causes that some records which should include a pattern do not have it. To deal with real-world problems, one can use an ambiguous inclusion relation and find patterns which are mostly included in many records. However, computational difficulty have prevented such problems from being actively used in practice. In this paper, we use an alternative inclusion relation in which we consider an itemset P to be included in an itemset T if at most k items of P are not included in T, i.e., vertical bar P\T vertical bar <= k. We address the problem of enumerating frequent itemsets under this inclusion relation and propose an efficient polynomial delay polynomial space algorithm. Moreover, To enable us to skip many small non-valuable frequent itemsets, we propose an algorithm for directly enumerating frequent itemsets of a certain size.
  • Hiroki Arimura, Takeaki Uno, Shinichi Shimozon
    DISCOVERY SCIENCE, PROCEEDINGS 4755 42 - + 2007年 [査読有り][通常論文]
     
    A geometric graph is a labeled graph whose vertices are points in the 2D plane with an isomorphism invariant under geometric transformations such as translation, rotation, and scaling. While Kuramochi and Karypis (ICDM2002) extensively studied the frequent pattern mining problem for geometric subgraphs, the maximal graph mining has not been considered so far. In this paper, we study the maximal (or closed) graph mining problem for the general class of geometric graphs in the 2D plane by extending the framework of Kuramochi and Karypis. Combining techniques of canonical encoding and a depth-first search tree for the class of maximal patterns, we present a polynomial delay and polynomial space algorithm, MaxGeo, that enumerates all maximal subgraphs in a given input geometric graph without duplicates. This is the first result establishing the output-sensitive complexity of closed graph mining for geometric graphs. We also show that the frequent graph mining problem is also solvable in polynomial delay and polynomial time.
  • Minato Shin-ichi, Arimura Hiroki
    Information and Media Technologies 2 1 309 - 316 Information and Media Technologies 編集運営会議 2007年 
    Frequent item set mining is one of the fundamental techniques for knowledge discovery and data mining. In the last decade, a number of efficient algorithms for frequent item set mining have been presented, but most of them focused on just enumerating the item set patterns which satisfy the given conditions, and it was a different matter how to store and index the result of patterns for efficient data analysis. Recently, we proposed a fast algorithm of extracting all frequent item set patterns from transaction databases and simultaneously indexing the result of huge patterns using Zero-suppressed BDDs (ZBDDs). That method, ZBDD-growth, is not only enumerating/listing the patterns efficiently, but also indexing the output data compactly on the memory to be analyzed with various algebraic operations. In this paper, we present a variation of ZBDD-growth algorithm to generate frequent closed item sets. This is a quite simple modification of ZBDD-growth, and additional computation cost is relatively small compared with the original algorithm for generating all patterns. Our method can conveniently be utilized in the environment of ZBDD-based pattern indexing.
  • Tomoya Saito, Takuya Kida, Hiroki Arimura
    2007 IEEE INTERNATIONAL WORKSHOP ON DATABASES FOR NEXT GENERATION RESEARCHERS 13 - + 2007年 [査読有り][通常論文]
     
    In this paper, we study a complex pattern matching problem over a single continuous stream of numerical values. Based on bit-parallel technique for string matching, we propose an efficient algorithm called BPS (Bit-Parallel matching on Streams) that finds the set of all occurrences of a given pattem of length m in an input stream of length n in 0 (1/w mn) time for ordered values and in 0 (1/w mn log m) time for real values over a fixed data range, where w is the bit-width of registers. This time complex properly improves the time complexity, 0 (ran) of the previous algorithms. The keys of the algorithm are fast NFA simulation based on bit-parallel operation and hit predicate table lookup technique. We also present empirical analysis to evaluate the performance of the algorithm showing that the proposed algorithm is twice as fast as and more stable than the previous algorithms.
  • 大規模テキストマイニングのための特徴部分列抽出と極大パター ン発見を組み合わせた効率的アルゴリズム,
    有村 博紀, 宇野 毅明
    第63回人工知能学会人工知能基礎問題研究会 45 - 52 2006年09月 [査読無し][通常論文]
  • ２次元離散テキストからの効率よい極大パターンマイニング
    下薗 真一, 宇野 毅明, 有村 博紀
    第63回人工知能学会人工知能基本問題研究会 2006年09月 [査読無し][招待有り]
  • 上村 卓史, 喜田 拓也, 有村 博紀
    情報科学技術レターズ 5 5 - 8 FIT(電子情報通信学会・情報処理学会)運営委員会 2006年08月 [査読無し][通常論文]
  • Joerg Rothe, Hiroki Arimura
    JOURNAL OF UNIVERSAL COMPUTER SCIENCE 12 6 579 - 580 2006年 [査読有り][通常論文]
  • H Arimura, S Jain
    THEORETICAL COMPUTER SCIENCE 348 1 1 - 2 2005年12月 [査読無し][招待有り]
  • S Minato, H Arimura
    International Workshop on Challenges in Web Information Retrieval and Integration, Proceedings 4 - 11 2005年 [査読有り][通常論文]
     
    Manipulation of large-scale combinatorial data is one of the important fundamental technique for web information retrieval, integration, and mining. In this paper we propose a new approach based on BDDs (Binary Decision Diagrams) for database analysis problems. BDDs are graph-based representation of Boolean functions, now widely used in system design and verification area. Here we focus on Zero-suppressed BDDs (ZBDDs), a special type of BDDs, which are suitable for handling large-scale sets of combinations. Using ZBDDs, we can implicitly enumerate combinatorial item set data and efficiently compute set operations over the ZBDDs. We present some encouraging experimental results of frequent item set mining problem for practical benchmark examples, some of which have never been generated by previous method.
  • Satoshi Morinaga, Hiroki Arimura, Takahiro Ikeda, Yosuke Sakao, Susumu Akamine
    Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 666 - 671 2005年 [査読有り][通常論文]
     
    We propose a new text mining system which extracts characteristic contents from given documents. We define Key semantics as characteristic sub-structures of syntactic dependencies in the given documents, and consider the following three tasks in this paper: 1) Key semantics extraction: extracting characteristic syntactic dependency structures not only as ordered trees but also as unordered trees and free trees, 2) Redundancy reduction: from the result of extraction, deleting redundant dependency structures such as sub-structures or equivalent structures of the others, and 3) Phrase/sentence reconstruction: generating a phrase or sentence in a natural language corresponding to the extracted structure. Our system is a combination of natural language processing techniques and tree mining techniques. The system consists of the following five units: 1) syntactic dependency analysis unit, 2) input filters, 3) characteristic ordered subtree extraction unit, 4) output filters, and 5) phrase/sentence reconstruction unit. Although ordered trees are extracted in the third unit, the overall behavior of the system can be switched into the extraction of ordered trees, unordered trees, or free trees depending on which of the input filters is/are applied in the second step. The output filters delete redundant trees from the extraction, result for efficient knowledge discovery. Finally, phrases or sentences corresponding to the extracted subtrees are reconstructed by utilizing the input documents. We demonstrate the validity of our system by showing experimental results using real data collected at a help desk and TDT pilot corpus. Copyright 2005 ACM.
  • H Arimura, T Uno
    ALGORITHMS AND COMPUTATION 3827 724 - 737 2005年 [査読有り][通常論文]
     
    In this paper, we consider the problem of enumerating all maximal motifs in an input string for the class of repeated motifs with wild cards. A maximal motif is such a representative motif that is not properly contained in any larger motifs with the same location lists. Although the enumeration problem for maximal motifs with wild cards has been studied in (Parida et al., CPM'01), (Pisanti et al.,MFCS'03) and (Pelfrene et al., CPM'03), its output-polynomial time computability is still open. The main result of this paper is a polynomial space polynomial delay algorithm for the maximal motif enumeration problem for the repeated motifs with wild cards. This algorithm enumerates all maximal motifs in an input string of length n with O(n(3)) time per motif with O(n(2)) space and O(n(3)) delay. The key of the algorithm is depth-first search on a tree-shaped search route over all maximal motifs based on a technique called prefix-preserving closure extension. We also show an exponential lowerbound and a succinctness result on the number of maximal motifs, which indicate the limit of a straightforward approach.
  • Special Issue on Algorithmic Learning Thoery
    Hiroki Arimura
    2005年
  • T Asai, K Abe, S Kawasoe, H Sakamoto, H Arimura, S Arikawa
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E87D 12 2754 - 2763 2004年12月 [査読有り][通常論文]
     
    In this paper, we consider a data mining problem for semistructured data. Modeling semi-structured data as labeled ordered trees, we present an efficient algorithm for discovering frequent substructures from a large collection of semi-structured data. By extending the enumeration technique developed by Bayardo (SIGMOD'98) for discovering long itemsets, our algorithm scales almost linearly in the total size of maximal tree patterns contained in an input collection depending mildly on the size of the longest pattern. We also developed several pruning techniques that significantly speed-up the search. Experiments on Web data show that our algorithm runs efficiently on real-life datasets combined with proposed pruning techniques in the wide range of parameters.
  • Kida Takuya, Arimura Hiroki
    Asia Information Retrieval Symposium (AIRS2004) 265 - 268 Asia Information Retrieval Symposium 2004年10月 
    In this paper, we study the pattern matching problem with taxonomic information (PMTX, for short), where taxonomy is a partially ordered set of letters describing an IS-A hierarchy. We present an efficient algorithm for PMTX that runs in O(mn/w) time with O(m+mh/w) preprocess and O(mσ/w) extra space, where h, m, t, σ, and w are the size of the taxonomic information H, the length of the pattern P ∈ Σ∗, the length of the text T ∈ Σ∗, the cardinality of the sorted alphabet Σ, and the computer word length, respectively. If the patternlength m is less than w, it runs in O(n) time, O(m + h) preprocess, and O(σ) space, and works very fast in practice. We also discuss various improvements of the algorithms for real world applications.
  • 頻出・飽和・極大頻出集合の効率的な列挙アルゴリズムとその実装
    宇野 毅明, 有村 博紀
    日本ソフトウェア科学会, 第4回データマイニングワークショップ 47 - 54 2004年09月 [査読無し][通常論文]
  • LCM: 頻出飽和アイテム集合を列挙する高速なアルゴリズム
    宇野 毅明, 内田 雄三, 浅井 達哉, 有村 博紀
    第54回人工知能学会人工知能基礎論研究会 23 - 29 2004年03月 [査読無し][通常論文]
  • 房延慎二, 浅井達哉, 有村博紀, 宇野毅明, 中野眞一
    第１５回データ工学ワークショップ（DEWS2004） 2004年03月 [査読無し][通常論文]
  • Takeaki Uno, Masashi Kiyomi, Hiroki Arimura
    FIMI '04, Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations, Brighton, UK, November 1, 2004 CEUR-WS.org 2004年 [査読有り][通常論文]
  • T Uno, T Asai, Y Uchida, H Arimura
    DISCOVERY SCIENCE, PROCEEDINGS 3245 16 - 31 2004年 [査読有り][通常論文]
     
    The class of closed patterns is a well known condensed representations of frequent patterns, and have recently attracted considerable interest. In this paper, we propose an efficient algorithm LCM (Linear time Closed pattern Miner) for mining frequent closed patterns from large transaction databases. The main theoretical contribution is our proposed prefix-preserving closure extension of closed patterns, which enables us to search all frequent closed patterns in a depth-first manner, in linear time for the number of frequent closed patterns. Our algorithm do not need any storage space for the previously obtained patterns, while the existing algorithms needs it. Performance comparisons of LCM with straightforward algorithms demonstrate the advantages of our prefix-preserving closure extension.
  • H Sakamoto, K Hirata, H Arimura
    THEORETICAL COMPUTER SCIENCE 298 1 21 - 50 2003年04月 [査読有り][通常論文]
     
    The elementary formal system (EFS) is a kind of logic programs which directly manipulates strings, and the learnability of the subclass called hereditary EFSs (HEFSs) has been investigated in the frameworks of the PAC-learning, query-learning, and inductive inference models. The hierarchy of HEFS is expressed by HEFS(m,k,t,r), where m, k, t and r denote the number of clauses, the occurrences of variables in the head, the number of atoms in the body, and the arity of predicate symbols. The present paper deals with the learnability of HEFS in the query learning model using equivalence queries and additional queries such as membership, predicate membership, entailment membership, and dependency queries. We show that the class HEFS(*, k, t, r) is polynomial-time learnable with the equivalence and predicate membership queries and the class HEFS(*,k,*,r) with termination property is polynomial-time learnable with the equivalence, entailment membership, and dependency queries for the unbounded parameter *. A lowerbound on the number of queries is presented. We also show that the class HEFS(*,k,t,r) is hard to learn with the equivalence and membership queries under the cryptographic assumptions. Furthermore, the learnability of the class of unions of regular pattern languages, which is a subclass of HEFSs, is investigated. The bounded unions of regular pattern languages are polynomial-time predictable with membership query. However, all unbounded unions of regular pattern languages are not polynomial-time predictable with membership queries if neither are the DNF formulas. (C) 2002 Published by Elsevier Science B.V.
  • Takeaki Uno, Tatsuya Asai, Yuzo Uchida, Hiroki Arimura
    FIMI '03, Frequent Itemset Mining Implementations, Proceedings of the ICDM 2003 Workshop on Frequent Itemset Mining Implementations, 19 December 2003, Melbourne, Florida, USA CEUR-WS.org 2003年 [査読有り][通常論文]
  • T Asai, H Arimura, T Uno, S Nakano
    DISCOVERY SCIENCE, PROCEEDINGS 2843 47 - 61 2003年 [査読有り][通常論文]
     
    In this paper, we study a frequent substructure discovery problem in semi-structured data. We present an efficient algorithm Unot that computes all frequent labeled unordered trees appearing in a large collection of data trees with frequency above a user-specified threshold. The keys of the algorithm are efficient enumeration of all unordered trees in canonical form and incremental computation of their occurrences. We then show that Unot discovers each frequent pattern T in O(kb(2)m) per pattern, where k is the size of T, b is the branching factor of the data trees, and m is the total number of occurrences of T in the data trees.
  • T Asai, K Abe, S Kawaoe, H Arimura, H Sakamoto, S Arikawa
    PROCEEDINGS OF THE SECOND SIAM INTERNATIONAL CONFERENCE ON DATA MINING 158 - 174 2002年 [査読有り][通常論文]
  • Kenji Abe, Shinji Kawasoe, Tatsuya Asai, Hiroki Arimura, Setsuo Arikawa
    Principles of Data Mining and Knowledge Discovery, 6th European Conference, PKDD 2002, Helsinki, Finland, August 19-23, 2002, Proceedings 1 - 14 Springer 2002年 [査読有り][通常論文]
  • T Asai, H Arimura, K Abe, S Kawasoe, S Arikawa
    2002 IEEE INTERNATIONAL CONFERENCE ON DATA MINING, PROCEEDINGS 27 - 34 2002年 [査読有り][通常論文]
     
    In this paper, we study an online data mining problem from streams of semi-structured data such as XML data. Modeling semi-structured data and patterns as labeled ordered trees, we present an online algorithm StreamT that receives fragments of an unseen possibly infinite semi-structured data in the document order through a data stream, and can return the current set of frequent patterns immediately on request at any time. A crucial part of our algorithm is the incremental maintenance of the occurrences of possibly frequent patterns using a tree sweeping technique. We give modifications of the algorithm to other online mining model. We present theoretical and empirical analyses to evaluate the performance of the algorithm.
  • Hiroshi Sakamoto, Hiroki Arimura, Setsuo Arikawa
    Progress in Discovery Science, Final Report of the Japanese Discovery Science Project 586 - 599 Springer 2002年 [査読有り][通常論文]
  • Hiroki Arimura, Hiroshi Sakamoto, Setsuo Arikawa
    Progress in Discovery Science, Final Report of the Japanese Discovery Science Project 123 - 139 Springer 2002年 [査読有り][通常論文]
  • H Arimura
    COMBINATORIAL PATTERN MATCHING 2373 17 - 19 2002年 [査読有り][通常論文]
  • Kenji Abe, Shinji Kawasoe, Tatsuya Asai, Hiroki Arimura, Hiroshi Sakamoto, Setsuo Arikawa
    Active Mining - New Directions of Data Mining 79 83 - 94 IOS Press 2002年 [査読有り][通常論文]
  • Efficiently Mining Frequent Substructures from Semi-structured Data
    Tatsuya Asai, Kenji Abe, Shinji Kawasoe, Hiroshi Sakamoto, Hiroki Arimura, Setsuo Arikawa
    Proc. International Workshop on Informations & Electrical Engineering (IWIE2002) 59 - 64 2002年 [査読有り][通常論文]
  • 安積 裕樹, 川副 真治, 安部 潤一郎, 有村 博紀, 有川 節夫
    情報処理学会論文誌. 数理モデル化と応用 42 14 14 - 24 一般社団法人情報処理学会 2001年12月15日 [査読無し][通常論文]
     
    本稿では, 分散記憶型並列計算機上での効率の良い全文索引構築法について考察する.接尾辞配列は, 最近提案された高機能全文索引であり, 情報検索や遺伝子情報などに広い応用を持つ.本稿では, 分散記憶型並列計算機上での効率の良い接尾辞配列構築法を提案する.Baeza-Yates-Gonnet-Sinder(BGS)アルゴリズムは, 最も広く使われている外部記憶上の構築アルゴリズムである.このBGSアルゴリズムを並列化し, 効率の良い並列構築アルゴリズムを与える.このアルゴリズムは, 並列計算機時間と通信量に関して, BGSの最適な並列化になっており, 従来からあるBGSの並列版のRiberio-Kitajima-Ziviani(RKZ)アルゴリズムに比べてより高速である.
  • 安積 裕樹, 川副 真治, 安部 潤一郎, 有村 博紀, 有川 節夫
    情報処理学会論文誌数理モデル化と応用（TOM） 42 14 14 - 24 一般社団法人情報処理学会 2001年12月15日 
    本稿では，分散記憶型並列計算機上での効率の良い全文索引構築法について考察する．接尾辞配列は，最近提案された高機能全文索引であり，情報検索や遺伝子情報などに広い応用を持つ．本稿では，分散記憶型並列計算機上での効率の良い接尾辞配列構築法を提案する．Baeza-Yates-Gonnet-Sinder（BGS ）アルゴリズムは，最も広く使われている外部記憶上の構築アルゴリズムである．このBGSアルゴリズムを並列化し，効率の良い並列構築アルゴリズムを与える．このアルゴリズムは，並列計算機時間と通信量に関して，BGS の最適な並列化になっており，従来からあるBGS の並列版のRiberio-Kitajima-Ziviani （RKZ ）アルゴリズムに比べてより高速である．In this paper,we study efficient parallel construction of full-text indexing structures for large text data.The suffix array is a compact full-text indexing structure that is useful in information retrieval and bio-informatics.We propose an efficient parallel algorithm for constructing suffix arrays on distributed memory parallel computers.This algorithm is a parallel implementation of the well-known external memory algorithm,called Baeza-Yates-Gonnet-Sinder (BGS)algorithm.By theoretical analysis,we show that our algorithm runs more efficiently than Riberio-Kitajima-Ziviani (RKZ) algorithm,another parallel implementation of the BGS algorithm,in terms of parallel time and communication complexities.
  • 村上 義継, 坂本 比呂志, 有村 博紀, 有川 節夫
    情報処理学会論文誌数理モデル化と応用（TOM） 42 14 39 - 49 一般社団法人情報処理学会 2001年12月15日 
    World Wide Web で収集したHTML テキストから部分的にデータを取り出すプログラムをHTMLWrapper と呼ぶ．本研究ではHTML Wrapper のための新しいデータモデルを提案し，与えられたHTML から所望のテキストデータを切り出すためのHTML Wrapper を自動生成する機械学習アルゴリズムを構築する．さらにこのアルゴリズムをJava によって実装し，このアルゴリズムの有効性を検証する．This paper introduces the new model of the HTML Wrapper for the information extraction from HTML documents and presents the learning algorithm for the HTML Wrappers in the framework of learning by exmaples. The expressiveness of this model is shown by experimental results.
  • 村上 義継, 坂本 比呂志, 有村 博紀, 有川 節夫
    情報処理学会論文誌. 数理モデル化と応用 42 14 39 - 49 一般社団法人情報処理学会 2001年12月 [査読無し][通常論文]
  • Akihiro Yamamoto, Kimihito Ito, Akira Ishino, Hiroki Arimura
    Inductive Logic Programming, 11th International Conference, ILP 2001, Strasbourg, France, September 9-11, 2001, Proceedings 240 - 247 Springer 2001年 [査読有り][通常論文]
  • Hiroshi Sakamoto, Yoshitsugu Murakami, Hiroki Arimura, Setsuo Arikawa
    Proceedings of the Fourteenth International Florida Artificial Intelligence Research Society Conference, May 21-23, 2001, Key West, Florida, USA 264 - 268 AAAI Press 2001年 [査読有り][通常論文]
  • Katsuaki Taniguchi, Hiroshi Sakamoto, Hiroki Arimura, Shinichi Shimozono, Setsuo Arikawa
    Discovery Science, 4th International Conference, DS 2001, Washington, DC, USA, November 25-28, 2001, Proceedings 2226 378 - 388 Springer 2001年 [査読有り][通常論文]
  • Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, Kunsoo Park
    Combinatorial Pattern Matching, 12th Annual Symposium, CPM 2001 Jerusalem, Israel, July 1-4, 2001 Proceedings 181 - 192 Springer 2001年 [査読有り][通常論文]
  • Hiroki Arimura, Hiroki Asaka, Hiroshi Sakamoto, Setsuo Arikawa
    Combinatorial Pattern Matching, 12th Annual Symposium, CPM 2001 Jerusalem, Israel, July 1-4, 2001 Proceedings 152 - 156 Springer 2001年 [査読有り][通常論文]
  • Hiroki Arimura, Hiroshi Sakamoto, Setsuo Arikawa
    Algorithmic Learning Theory, 12th International Conference, ALT 2001, Washington, DC, USA, November 25-28, 2001, Proceedings 315 - 331 Springer 2001年 [査読有り][通常論文]
  • T Shinohara, H Arimura
    THEORETICAL COMPUTER SCIENCE 241 1-2 191 - 209 2000年06月 [査読有り][通常論文]
     
    A pattern is a string consisting of constant symbols and variables. The language of a pattern is the set of constant strings obtained by substituting nonempty constant strings for variables in the pattern. In this paper we consider the inductive inference of unbounded unions of pattern languages from positive data. For any fixed k, the class of unions of at most k pattern languages is already shown to be inferable from positive data. The class of unbounded unions is not inferable, because any pattern with at least one variable defines an infinite language and any constant string defines a singleton Set consisting of itself, and therefore, the class of unions becomes super-finite, that is, it contains all the finite languages and at least one infinite language. In this paper, we consider several restrictions on patterns to investigate the inferability of unbounded unions of their languages from positive data. A proper pattern contains at least one variable. A regular pattern contains at most one occurrence of every variable. Although the class of unbounded unions of proper pattern languages is not super-finite, it is shown not to be inferable from positive data, even if patterns are restricted to be regular or one-variable. When regular patterns are restricted to be of the form "xwy", where x and y are variables and w is a constant string, the class of unbounded unions is shown to be inferable from positive data. When regular patterns do not contain more than l consecutive occurrences of constant symbols, for some fixed l, the class of unbounded unions is shown to be inferable from positive data. Extended pattern languages, where substitutions of the empty string for some variables are allowed, are also considered from the viewpoint of relationship to the inferability of unbounded unions of non-extended pattern languages. (C) 2000 Elsevier Science B.V. All rights reserved.
  • Tatsuya Akutsu, Hiroki Arimura, Shinichi Shimozono
    RECOMB 2000 1 - 7 2000年 [査読有り][通常論文]
  • R Fujino, H Arimura, S Arikawa
    KNOWLEDGE DISCOVERY AND DATA MINING, PROCEEDINGS 1805 281 - 293 2000年 [査読有り][通常論文]
     
    This paper considers the problem of finding all frequent phrase association patterns in a large collection of unstructured texts, where a phrase association pattern is a set of consecutive sequences of arbitrary number of keywords which appear together in a document. For the ordered and the unordered versions of phrase association patterns, we present efficient algorithms, called Levelwise-Scan, based on the sequential counting technique of Apriori algorithm. To cope with the problem of the huge feature space of phrase association patterns, the algorithm uses the generalized suffix tree and the pattern matching automaton. By theoretical and empirical analyses, we show that the algorithms runs quickly on most random texts for a wide range of parameter values and scales up for large disk-resident text databases.
  • H Arimura, J Abe, R Fujino, H Sakamoto, S Shimozono, S Arikawa
    2000 KYOTO INTERNATIONAL CONFERENCE ON DIGITAL LIBRARIES: RESEARCH AND PRACTICE, PROCEEDINGS 220 - 226 2000年 [査読有り][通常論文]
     
    This paper describes applications of the optimized pattern discovery framework to text and Web mining. In particular, we introduce a class of simple combinatorial patterns over phrases, called proximity phrase association patterns, and consider the problem of finding the patterns that optimize a given statistical measure within the whole class of patterns in a large collection of unstructured texts. For this class of patterns, we develop fast and robust text mining algorithms based on techniques in computational geometry and string matching. Finally, we successfully apply the developed text mining algorithms to the experiments on interactive document browsing in a large text database and keyword discovery from Web bases.
  • Hiroki Arimura, Hiroshi Sakamoto, Setsuo Arikawa
    Inductive Logic Programming, 10th International Conference, ILP 2000, Work-in-progress reports, London, UK, July 2000, Proceedings CEUR-WS.org 2000年 [査読有り][通常論文]
  • H Sakamoto, H Arimura, S Arikawa
    GRAMMATICAL INFERENCE: ALGORITHMS AND APPLICATIONS 1891 241 - 255 2000年 [査読有り][通常論文]
     
    Two models for simple translation between ordered trees are introduced. First is that output is obtained from input by renaming labels and deleting nodes. Several decision problems on the translation are proved to be tractable and intractable. Second is term rewriting system, called k-variable linear translation. The efficient learnability of this system using membership and equivalence queries is shown.
  • S Shimozono, H Arimura, S Arikawa
    NEW GENERATION COMPUTING 18 1 49 - 60 2000年 [査読有り][通常論文]
     
    We study efficient discovery of proximity word-association patterns, defined by a sequence of strings and a proximity gap, from a collection of texts with the positive and the negative labels. We present an algorithm that finds all d-strings k-proximity word-association patterns that maximize the number of texts whose matching agree with their labels. It runs in expected time complexity O(k(d-1) n log(d) n) and space O(k(d-1)n) with the total length n of texts, if texts are uniformly random strings. We also show that the problem to find one of the best word-association patterns with arbitrarily many strings is MAX SNP-hard.
  • Hiroki Arimura, Akihiro Yamamoto
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E83D 1 10 - 18 2000年01月 [査読有り][招待有り]
     
    Inductive Logic Programming (ILP) is a study of machine learning systems that use clausal theories in first-order logic as a representation language. In this paper, we survey theoretical foundations of ILP from the viewpoints of Logic of Discovery and Machine Learning, and try to unify these two views with the support of the modern theory of Logic Programming. Firstly, we define several hypothesis construction methods in ILP and give their proof-theoretic foundations by treating then as a procedure which complete incomplete proofs. Next, we discuss the design of individual learning algorithms using these hypothesis construction methods. We review known results on learning logic programs in computational learning theory, and show that these algorithms are instances of a generic learning strategy with proof completion methods.
    ダウンロード
  • T Takae, M Chikamune, H Arimura, A Shinohara, H Inoue, S Takeya, K Uezono, T Kawasaki
    DISCOVERY SCIENCE, PROCEEDINGS 1721 359 - 361 1999年 [査読有り][通常論文]
  • 笠井 透, 有村 博紀, 篠原 武
    Research reports on information science and electrical engineering of Kyushu University 3 2 185 - 190 九州大学 1998年09月 
    A regular pattern is a string consisting of constant symbols and mutually distinct variables, and represents the set of the constant strings obtained by substituting possibly empty constant strings for the variables. A learning algorithm, called k-minimal multiple generalization (k-rnmg), finds a minimally general collection of at most k regular patterns that explains all the positive examples. Recently, several attempts have been made at applying this algorithm to protein motif discovery and other knowledge acquisitions. In such applications, its performance is considerably influenced by a class of data and values of learning parameters. This paper empirically evaluates performance of the algorithm k-rnmg on synthesized data to apply it to protein motif discovery.
  • H Arimura, A Wataki, R Fujino, S Araikawa
    ALGORITHMIC LEARNING THEORY 1501 247 - 261 1998年 [査読有り][通常論文]
     
    We consider a data mining problem in a large collection of unstructured texts based on association rules over subwords of texts. A tare-words association pattern is an expression such as (TATA, 30, AGGAGGT) --> C that expresses a rule that if a text contains a subword TATA followed by another subword AGGAGGT with distance no more than 30 letters then a property C will hold with high probability. The optimized confidence pattern problem is to compute frequent patterns (alpha, kappa, beta) that optimize the confidence with respect to a given collection of texts. Although this problem is solved in polynomial time by a straightforward algorithm that enumerates all the possible patterns in time O(n(5)), we focus-on the development of more efficient algorithms that can be applied to large text databases. We present an algorithm that solves the optimized confidence pattern problem in time O(max{k, m}n(2)) and space O(kn), where m and n are the number and the total length of classification examples, respectively, and Ic is a small constant around 30 similar to 50. This algorithm combines the suffix tree data structure in combinatorial string matching and the orthogonal range query technique in computational geometry for fast computation. Furthermore for most random texts like DNA sequences, we show that a modification of the algorithm runs very efficiently in time O(knlog(3) n) and space O(kn). We also discuss some heuristics such as' sampling and pruning as practical improvement. Then, we evaluate the efficiency and the performance of the algorithm with experiments on;genetic sequences. A relationship with efficient Agnostic PAC-learning is also discussed.
  • H Arimura, A Wataki, R Fujino, S Shimozono, S Arikawa
    DISCOVERY SCIENCE 1532 393 - 394 1998年 [査読有り][通常論文]
     
    In this poster, we present demonstration of a prototype system for efficient discovery of combinatorial patterns, called proximity word-association patterns, from a collection of texts. The algorithm computes the best k-proximity d-word patterns in almost linear expected time in the total input length n, which is drastically faster than a straightforward algorithm of O(n(2d+l)) time complexity.
  • H Ishizaka, H Arimura, T Shinohara
    ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 23 1-2 101 - 115 1998年 [査読有り][通常論文]
     
    This paper is concerned with the problem of finding a hypothesis in TP2 consistent with given positive and negative examples. The hypothesis class TP2 consists of all sets of at most two tree patterns and represents the class of unions of at most two tree pattern languages. Especially, we consider the problem from the point of view of the consistency problem for TP2. The consistency problem is a problem for deciding whether there exists a consistent hypothesis with given positive and negative examples within some fixed hypothesis space. Efficient solvability of that problem is closely related to the possibility of efficient machine learning or machine discovery. Unfortunately, however, the consistency problem is known to be NP-complete for many hypothesis spaces. In this paper, the problem for the class TP2 is also shown to be NP-complete. In order to overcome this computational hardness, we try to use additional information obtained by making queries. First, we give an algorithm that, using restricted subset queries, solves the consistency problem for TP2 in time polynomial in the total size of given positive and negative examples. Next, we show that each subset query made by the algorithm can be replaced by several membership queries under some condition on a set of function symbols. As a result, we have that the consistency problem for TP2 is solved in polynomial time using membership queries.
  • H Arimura, S Shimozono
    ALGORITHMS AND COMPUTATIONS 1533 39 - 48 1998年 [査読有り][通常論文]
     
    We study the efficient discovery of word-association patterns, defined by a sequence of strings and a proximity gap, from a collection of texts with binary labels. We present an algorithm that finds all d strings and Ic proximity word-association patterns that maximizes agreement with the labels. It runs in expected time complexity O(k(d-1)nlog(d+1) n) and O(k(d-1)n) space with the total length n of texts, if texts are uniformly random strings. We also show that the problem to find a best word-association pattern with arbitrarily many strings is MAX SNP-hard.
  • ARIMURA H.
    Theor. Comput. Sci. 185 1 47 - 62 1997年10月
  • Hiroki Arimura, Hiroki Ishizaka, Takeshi Shinohara
    Lecture Notes in Computer Science 66 - 79 1995年
  • A Generalization of the Least General Generalization
    Hiroki Arimura
    1994年
  • 有村 博紀, 藤野 亮一, 篠原 武, 有川 節夫
    Genome Informatics 5 39 - 48 Japanese Society for Bioinformatics 1994年 
    Recently, several attempts have been made at applying machine learning method to protein motif discovery, but most of these methods require negative examples in addition to positive examples. This paper proposes an efficient method for learning protein motif from positive examples. A regular pattern is a string consisting of constant symbols and mutually distinct variables, and represents the set of the constant strings obtained by substituting nonempty constant strings for variables. Regular patterns and their languages are called extended if empty substitutions are allowed. Our learning algorithm, called k-minimal multiple generalization (k-mmg), finds a minimally general collection of at most k regular patterns that explains all the positive examples. We have implemented this algorithm for subclasses for regular patterns and extended regular patterns where the number of variables are bounded by a small constant, and run experiments on protein data taken from GenBank and PIR databases. We incorporate three heuristics into these algorithms for controlling nondeterministic choices. The experiments show that the k-mmg algorithm can very quickly find a hypothesis on the computers in practice, and that the results of our system are comparable with the results of learning method from positive and negative data.
  • Inductive inference of Prolog programs with linear data dependency from positive data
    Hiroki Arimura, Takeshi Shinohara
    Information Modelling and Knowledge Bases V 365 - 375 1993年08月 [査読有り][通常論文]
  • 石坂 裕毅, 有村 博紀, 篠原 武, Hiroki Ishizaka, Hiroki Arimura, Takeshi Shinohara, (株)富士通研究所国際情報社会科学研究所, IIAS-SIS Fujitsu Laboratories Ltd., Faculty of Computer Science and Systems Eng. Kyushu Institute of Technology, Faculty of Computer Science and Systems Eng. Kyushu Institute of Technology
    人工知能学会誌 = Journal of Japanese Society for Artificial Intelligence 8 4 419 - 426 1993年07月01日 
    We consider the polynomial time inferability of primitive Prologs from positive facts. The class of primitive Prologs is a proper subclass of that of linear Prologs which is known to be inferable from only positive facts. In this paper, we discuss the polynomial time inferability of the subclass using minimal multiple generalizations. The minimal multiple generalization is a natural extension of the least generalization given by Plotkin in 1970. The minimal multiple generalization generalizes given first order words by several words, while the least generalization does by a single word. The property of the minimal multiple generalization makes it possible to perform fine generalization and to construct the heads of several clauses in a target program at the same time. We give an outline of a consistent polynomial time inference algorithm which identifies the class of primitive Prologs in the limit. The algorithm infers the heads of clauses in a target program as a minimal multiple generalization of a set of given positive facts. Furthermore, we give a similar result on the inferability of a subclass of context-free transformations which includes several well-known Prolog programs.
  • ARIMURA H.
    Bulletin of Informatics and Cybernetics 25 3-4 125 - 136 1993年06月 [査読有り][通常論文]
  • ARIMURA H.
    Proc. NIL-91 659 118 - 131 Springer-Verlag 1993年02月 [査読有り][通常論文]
     
    Post-proceedings of the 2nd International Workshop on Nonmonotonic and Inductive Inference (NIL'91), Reinhardsbrunn Castle, Germany, December 2-6, 1991
  • Hiroki Ishizaka, Hiroki Arimura, Takeshi Shinohara
    Lecture Notes in Computer Science 743 135 - 146 1993年 [査読有り][通常論文]
  • Hiroki ARIMURA, Takeshi SHINOHARA, Setsuko OTSUKI
    IEICE TRANSACTIONS on Information and Systems E75-D 4 426 - 434 1992年07月 [査読有り][通常論文]
     
    In this paper, we consider the polynomial time inferability from positive data for unions of two tree pattern languages. A tree pattern is a structured pattern known as a term in logic programming, and a tree pattern language is the set of all ground instances of a tree pattern. We present a polynomial time algorithm to find a minimal union of two tree pattern languages containing given examples. Our algorithm can be considered as a natural extension of Plotkin's least generalization algorithm, which finds a minimal single tree pattern language. By using this algorithm, we can realize a consistent and conservative polynomial time inference machine that identifies unions of two tree pattern languages from positive data in the limit.
  • ARIMURA H.
    Proc. COLT'92 136 - 143 1992年 [査読有り][通常論文]
  • ARIMURA H.
    Proc. ALT '91 105 - 114 1991年10月 [査読有り][通常論文]
  • ARIMURA H.
    Soft-ware Science and Engineering 227 - 245 1991年09月

書籍

  • 言語処理学事典
    有村 博紀 (担当:分担執筆範囲:「半構造化されたテキストからの情報抽出」)
    共立出版 2009年12月
  • Computational Challenges of Massive Data Sets and Randomness in Computation, Special Issue on the First and Second Japanese-German Frontiers of Science Symposia
    J. Rothe, H. Arimura (範囲:editors)
    Journal of Universal Computer Science, Vol. 12, issue 6, 579-761. doi: 10.3217/jucs-012-06 2006年07月
  • 人工知能学辞典，(編)人工知能学会，共立出版，2005.
    有村 博紀 (担当:分担執筆範囲:小項目「テキストマイニング」)
    共立出版 2005年12月
  • 第11回計算論的学習理論国際会議会議録
    有村 博紀 (担当:編者(編著者))
    Springer-Verlag 2000年10月
  • Springer 2000年

講演・口頭発表等

  • 有村 博紀
    フォレストワークショップ2024 2024年03月 シンポジウム・ワークショップパネル（指名） TKPガーデンシティPREMIUM札幌大通カンファレンスルーム，札幌市 コンピューティング基盤CREST「学習/数理モデルに基づく時空間展開型アーキテクチャの創出と応用」(代表：本村真人(東工大))機械学習グループ, 信頼されるAIシステムCREST「D3-AI: 多様性と環境変化に寄り添う分散機械学習基盤の創出」（代表：高前田伸也(東大)）
    ダウンロード
  • 文字列集合に対する多様な最長共通部分列の発見  [通常講演]
    志田祐仁, 有村博紀, 小林靖明
    電子情報通信学会技術研究報告(Web), 信学技報, vol. 123, no. 325, COMP2023-23, pp. 45-52, 2023年12月 2023年12月 口頭発表（一般） 宮崎大学 まちなかキャンパス
    ダウンロード
  • Hiroki Arimura, Tatsuya Gima, Yasuaki Kobayashi, Hiroomi Nochide, Yota Otachi
    The 23rd Japan–Korea Joint Workshop on Algorithms and Computation (WAAC 2023), 口頭発表（一般） June 24–25, 2023 Nagoya University, Nagoya, Japan the Special Interest Group on Algorithms (SIGAL) of the Information Processing Society of Japan and the Special Interest Group on Theoretical Computer Science (SIGTCS) of the Korean Institute of Information Scientists and Engineers (KIISE).
  • コンパクト非巡回語グラフに基づく連長圧縮Burrows-Wheeler変換の効率良い構築  [通常講演]
    須江瑞樹, 小林靖明, 有村博紀, 中島祐人, 稲永俊介
    電子情報通信学会技術研究報告(Web), 信学技報, vol.122, no.294, COMP2022-25, pp.21-28(COMP) 2022年12月 口頭発表（一般） 愛媛大メディアホール
    ダウンロード
  • 有村 博紀
    2023年度 第2回領域集会, 学術変革(A)「社会変革アルゴリズム基盤」(AFSA) 2022年10月 ポスター発表 熱海ニューフジヤホテル, 静岡県熱海市 科研費 学術変革(A)「社会変革アルゴリズム基盤」(AFSA)
    ダウンロード
  • 一般化階層をもつ関係データベース上の閉パターンの発見  [通常講演]
    有村 博紀, 田口 尚生, 王 叶
    人工知能学会 2022年度人工知能学会全国大会 (JSAI2022) 口頭発表（一般） 国立京都国際会館, オンライン 有村 博紀, 田口 尚生, 王 叶
  • デカルト木部分列照合問題の高速なアルゴリズム  [通常講演]
    大泉 翼, 有村博紀
    アルゴリズム（AL）研究会, 2022-AL-186, Vol.3, pp.1-8 口頭発表（一般） オンライン 情報処理学会
    ダウンロード
  • 半順序集合の弱埋め込み問題に対するパラメータ化アルゴリズム
    宮崎怜子, 有村博紀, 小林靖明
    電子情報通信学会技術研究報告(Web) 2022年
  • Explainable Machine Learning for Trustworthy AI  [招待講演]
    Hiroki Arimura
    HU-DUT Workshop for Big data and AI, Hokkaido University 2021年12月 口頭発表（招待・特別）
  • ルールリストに対するRashomon集合の厳密計算と予測多重性解析  [通常講演]
    又 康太, 金森 憲太朗, 有村 博紀
    第24回情報論的学習理論ワークショップ (IBIS 2021), 一般セッション, 2-3 モデル解釈・検証, 106 2021年11月 口頭発表（一般） オンライン
  • デカルト木照合の部分系列への拡張  [通常講演]
    加井丈志, 光吉健汰, 古谷 勇, 有村博紀
    コンピュテーション（COMP）研究会, COMP2021-6 2021年05月 口頭発表（一般） オンライン 電子情報通信学会
  • 一貫性に基づいた特徴選択のための高速な列挙アルゴリズム  [通常講演]
    王 叶, 有村 博紀
    第116回人工知能基本問題研究会(SIG-FPAI) 2021年03月 口頭発表（一般） オンライン 人工知能学会
  • Variable Importance Cloudの要約方法と決定木に対する実験的評価  [通常講演]
    又 康太, 金森 憲太朗, 有村 博紀
    第23回情報論的学習理論ワークショップ (IBIS 2020) 口頭発表（一般） オンライン 電子情報通信学会
  • 決定木要約の効率良い構築法 -- 説明可能な人工知能の実現に向けて --  [通常講演]
    有村 博紀, 金森 憲太朗, 王 叶
    2020年度人工知能学会全国大会 (JSAI2020), 3E1-GS-2-05 口頭発表（一般） オンライン 人工知能学会
  • 混合整数線形計画法に基づく実現可能性を考慮した反事実的説明法  [通常講演]
    金森 憲太朗, 高木 拓也, 小林 健, 有村 博紀
    2020年度人工知能学会全国大会 (JSAI2020), インタラクティブセッション, 3Rin4-44 口頭発表（一般） オンライン 人工知能学会,
  • 決定木アンサンブルにおける出現頻度比に基づく変数重要度  [通常講演]
    又 康太, 金森 憲太朗, 有村 博紀
    2020年度人工知能学会全国大会 (JSAI2020) , インタラクティブセッション, 4Rin1-26 口頭発表（一般） オンライン 人工知能学会
  • 説明可能な機械学習のための拡張シャープレイ値の厳密指数時間アルゴリズム  [通常講演]
    大泉翼, 有村 博紀
    第12回データ工学と情報マネジメントに関するフォーラム (DEIM2020), インタラクティブセッション, P2-23 口頭発表（一般） オンライン 電子情報通信学会DE研究専門委員会，日本データベース学会，情報処理学会DBS研究会
  • 密なデータベースに対する動的な探索順序を用いた高速な顕在パターンマイニング手法
    岩下 洋哲, 高木 拓也, 鈴木 浩史, 後藤 啓介, 大堀 耕太郎, 有村 博紀
    人工知能学会研究会資料 人工知能基本問題研究会 111 8-8 2020年01月 口頭発表（一般）
  • Distribution-Aware Counterfactual Explanation by Mixed-Integer Linear Optimization  [通常講演]
    金森憲太朗, 高木拓也, 小林健
    第22回情報論的学習理論ワークショップ (IBIS 2019), ポスター, 1-069 口頭発表（一般） ウインクあいち, 名古屋市 電子情報通信学会
  • 説明可能な機械学習に向けて：整数計画法と列挙に基づく最適決定木の厳密学習アルゴリズムの実験的比較  [通常講演]
    王 叶, 有村 博紀
    第22回情報論的学習理論ワークショップ (IBIS 2019), ポスター, 2-089 口頭発表（一般） ウインクあいち, 名古屋市 電子情報通信学会
  • 決定木アンサンブル予測器の効率的ハードウェア実装のための簡約化に関する研究  [通常講演]
    松田 祐汰, 瀧川 一学, 有村 博紀
    第22回情報論的学習理論ワークショップ (IBIS 2019), ポスター, 2-088 口頭発表（一般） ウインクあいち, 名古屋市 電子情報通信学会
  • 最大クリークサイズが定数であるグラフに対する独立点集合のならし定数時間列挙
    栗田 和宏, 和佐 州洋, 宇野 毅明, 有村 博紀
    電子情報通信学会コンピューテーション研究会 119(249) COMP2019 18-28 2019年11月 口頭発表（一般）
  • Fairness-aware Edit of Thresholds in a Learned Decision Tree Using a Mixed Integer Programming Formulation  [通常講演]
    金森 憲太朗, 有村 博紀
    2019年度人工知能学会全国大会 (JSAI2019), 人工知能学会, インタラクティブセッション, 3Rin2-11 2019年06月 口頭発表（一般） 朱鷺メッセ, 新潟市 人工知能学会
  • イベント系列からの有意なエピソードの効率良いマイニング
    谷 陽太, 平田 耕一, 有村 博紀
    第11回データ工学と情報マネジメントに関するフォーラム (DEIM2019), H1-4 口頭発表（一般） ホテルオークラJRハウステンボス, 佐世保市 電子情報通信学会DE研究専門委員会，日本データベース学会，情報処理学会DBS研究会
  • An Efficient Algorithm for Enumerating Chordal Bipartite Induced Subgraphs in Graphs  [通常講演]
    栗田 和宏, 和佐 州洋, 宇野 毅明, 有村 博紀
    第108回人工知能基本問題研究会(SIG-FPAI), SIG-FPAI-B802-02, 6-11 口頭発表（一般） 大阪府立大学 I-siteなんば, 大阪市 人工知能学会
     
    受賞：研究会優秀賞, 金森 憲太朗, 有村 博紀, 2018年度，人工知能学会，2019年6月27日
  • 大きな正規表現に対する系列二分決定グラフを用いた効率よい照合手法
    瀧澤涼介, 喜田拓也, 有村博紀, 瀧川一学
    電子情報通信学会技術研究報告 2019年
  • Subgraph Enumeration: Efficient Algorithms and Empirical Studies  [通常講演]
    Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki Arimura
    The 2nd International Workshop on Enumeration Problems & Application (WEPA2018) 2018年11月 口頭発表（一般） University of Pisa
  • Kurita Kazuhiro, Wasa Kunihiro, Arimura Hiroki, Uno Takeaki
    数理解析研究所講究録 2018年08月 京都大学数理解析研究所
     
    Dominating sets are fundamental graph structures. However, enumeration of dominating sets has not received much attention. This study aims to propose an efficient enumeration algorithms for bounded degenerate graphs. The algorithm enumerates all the dominating sets for k-degenerate graphs in O(k) time per solution using O(n+m) space. Since planar graphs have a constant degeneracy, this algorithm can enumerate all such sets for planar graphs in constant time per solution.
  • モデル選択のためのサポートベクトル列挙  [通常講演]
    金森 憲太朗, 原 聡, 石畠 正和, 有村 博紀
    第29回IBISML研究会 口頭発表（一般） 沖縄科学技術大学院大学(OIST) 情報論的学習理論と機械学習研究会, 電子情報通信学会 情報・システムソサイエティ
  • グラフ断片決定木を用いたグラフ特徴抽出手法  [通常講演]
    坂上 陽規, 瀧川 一学, 有村 博紀
    人工知能学会2018年全国大会(JSAI2018),インタラクティブセッション, 3Pin1-10 口頭発表（一般） 城山観光ホテル、鹿児島県鹿児島市 人工知能学会
  • イベント系列からの有意性を考慮した菱形エピソードマイニング  [通常講演]
    谷 陽太, 古谷 勇, 平田 耕一, 有村 博紀
    人工知能学会2018全国大会(JSAI2018), インタラクティブセッション, 3Pin1-10 口頭発表（一般） 城山観光ホテル、鹿児島県鹿児島市 人工知能学会
  • 栗田 和宏, Alessio Conte, 和佐 州洋, 宇野 毅明, 有村 博紀
    情報処理学会第80回全国大会講演論文集, Vol.80, No.1, 1.347-1.348 2018年03月 情報処理学会
     
    内周はグラフに含まれる最小の閉路長を表し,グラフの内周を計算する問題はよく研究されている.ItaiとRodehは一般グラフの内周を計算する非自明な最初のアルゴリズムを開発した.このアルゴリズムは最悪時O(nm)時間で動作し,平均時間O(n^2)時間で動作する.重みなし平面グラフに対しては,DjidjevがO(n^{5/4} log n)時間アルゴリズムを与え,Changらがこのアルゴリズムを改良し線形時間アルゴリズムを与えた.我々の知る限りでは大きな内周を持つ連結な部分グラフを列挙するアルゴリズムは存在しない.本論文では,これらの問題を解く列挙アルゴリズムを与える.このアルゴリズムの単純な拡張により,k以上の内周を持つ重み付きグラフの部分グラフや非連結なグラフの列挙も可能である.
  • 順序決定木に対する正則化パラメータ推定の高速化  [通常講演]
    金森 憲太朗, 石畠 正和, 湊 真一, 有村 博紀
    第105回人工知能基本問題研究会(SIG-FPAI)，SIG-FPAI-B508 口頭発表（一般） 石垣島大濱信泉記念館, 沖縄県石垣市 人工知能学会
  • 決定化されたグラフパターントライの学習アルゴリズム  [通常講演]
    坂上 陽規, 栗田 和宏, 瀧川 一学, 有村 博紀
    第105回人工知能基本問題研究会(SIG-FPAI)，SIG-FPAI-B508 口頭発表（一般） 石垣島大濱信泉記念館, 沖縄県石垣市 人工知能学会
  • 栗田 和宏, 和佐 州洋, 宇野 毅明, 有村 博紀
    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 2017年12月 電子情報通信学会
  • 長部 和仁, 宇野 毅明, 有村 博紀
    人工知能基本問題研究会 2016年12月 人工知能学会
  • グラフに含まれる誘導マッチングの列挙
    栗田和宏, 和佐州洋, 喜田拓也, 有村博紀
    情報処理学会研究報告(Web) 2016年
  • 笹川 裕人, 有村 博紀
    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 2015年06月 電子情報通信学会
  • 高木 拓也, 有村 博紀
    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 2015年06月 電子情報通信学会
  • 和佐 州洋, 山中 克久, 有村 博紀
    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 2015年06月 電子情報通信学会
  • 三次元空間における効率良い近似点集合マッチングと分子パターン照合への応用
    佐々木耀一, 渋谷哲朗, 伊藤公人, 有村博紀
    電子情報通信学会技術研究報告 2015年
  • 原田 弘毅, 笹川 裕人, 有村 博紀, 佐久間 淳
    コンピュータセキュリティシンポジウム2013論文集 2013年10月
  • 大濱 郁, 喜田 拓也, 有村 博紀, 阿部 敏久
    電子情報通信学会技術研究報告. IBISML, 情報論的学習理論と機械学習 = IEICE technical report. IBISML, Information-based induction sciences and machine learning 2011年03月 一般社団法人電子情報通信学会
     
    我々は,人間行動履歴の地理的クラスタリングについて議論する.本論文では,この問題を,二次元時系列データのセグメンテーション問題として定式化し,二つのクラスタリング手法,LS-linHMMとX-linHMMを提案する.前者のLS-linHMMは,線形制約付きHMMを用いたクラスタリングと情報量規準を用いたモデル選択を組み合わせ,クラスタ数の自動推定を行う.また,X-linHMMは,x-meansのアイデアを取り入れた2状態線形HMMによる階層的クラスタリングであり,LS-linHMMよりも高速なクラスタリングを実現している.今回,これらの手法を,GPSタグ付き写真コンテンツのクラスタリングに適用することを試みる.また,実データを用いた実験により,単純なx-meansよりも提案手法が効果的に動作することを確認した.
  • D-4-2 オンラインXMLストリーム処理のための効率良い木正規表現パターン照合アルゴリズム(D-4.データ工学,一般セッション)
    藤兼 靖之, 金田 悠作, 有村 博紀
    電子情報通信学会総合大会講演論文集 2011年02月 一般社団法人電子情報通信学会
  • TK-7-1 知の創出を支える次世代IT基盤拠点(TK-7.情報・電気・電子グローバルCOEの活動と今後の計画,大会委員会企画)
    有村 博紀
    電子情報通信学会総合大会講演論文集 2011年02月 一般社団法人電子情報通信学会
  • 柳橋 史成, 伊藤 公人, 有村 博紀
    人工知能基本問題研究会 2010年11月 人工知能学会
  • 河東 孝, 有村 博紀, 平田 耕一
    人工知能基本問題研究会 2010年09月 人工知能学会
  • 金田 悠作, 湊 真一, 有村 博紀
    情報処理学会研究報告 2010年06月 情報処理学会
  • 金田 悠作, 湊 真一, 有村 博紀
    電子情報通信学会技術研究報告. COMP, コンピュテーション 2010年05月 一般社団法人電子情報通信学会
     
    正規表現は,アルファべットΣの文字と,結合"・"と選択"|"だけから構成されるとき,非巡回正規表現(acyclic regular expression)と呼ばれる.本稿では,非巡回正規表現のクラスに対して,長さmと深さdをもつ非巡回正規表現と長さnをもつ入力テキストを入力として受け取り,O(md)の前処理時間とO(md/w)領域を用いて,O(nmd/w)時間で正規表現照合問題を解く効率よいアルゴリズムを与える.このために,正規表現と等価な非決定性有限オートマトン(NFA)の状態遷移計算をビット演算と加減算を用いて模倣する分配集積演算と呼ぶビット並列計算手法を開発し,WuとManberらのSHIFT-AND手法(CACM 35(10), 1992)を,非巡回正規表現パターンに拡張している.本結果は,定数深さの非巡回正規表現に対して,O(m/w)領域を達成しつつ,一般の正規表現照合に対するBilleのアルゴリズム(ICALP, 2006)のよりも時間計算量が小さい.
  • 金田 悠作, 湊 真一, 有村 博紀
    電子情報通信学会総合大会講演論文集 2010年03月 一般社団法人電子情報通信学会
  • 河東 孝, 有村 博紀, 平田 耕一
    人工知能基本問題研究会 2010年01月 人工知能学会
  • 金田 悠作, 吉澤 真吾, 湊 真一, 有村 博紀, 宮永 喜一
    電子情報通信学会技術研究報告. VLD, VLSI設計技術 2010年01月 一般社団法人電子情報通信学会
     
    本稿では,重要なデータストリーム処理問題の一つである正規表現パターン照合に対して,ビット並列型パターン照合手法に基づいた高速なハードウェア指向アルゴリズムを提案する.並列ビット分配と呼ぶ新しいビット並列手法を用いて,文字と,連接,和,Kleeneプラスから構成させる非消去的正規表現のクラスに対して,O(mdlogb+m|Σ|)前処理時間とO(mdlogb/w+m|Σ|/w)領域を用いて,O(mdlogb/w)領域の高速なアルゴリズムを与える.ここで,nは入力長を表わし,mとd,bは,それぞれ,パターンの長さと,深さ,最大戻り幅を,wは計算機のワード長,|Σ|はアルファベットの要素数を表わす.さらに,このアルゴリズムを用いて,回路の再構成を伴わずにパターンの変更を可能なハードウェア実装のアーキテクチャをしめす.
  • 金 在成, 吉澤 真吾, 金田 悠作, 湊 真一, 有村 博紀, 宮永 喜一
    電子情報通信学会技術研究報告. VLD, VLSI設計技術 2010年01月 一般社団法人電子情報通信学会
     
    FPGA (Field Programmable Gate Array)は製造後も論理回路を再構成することが可能であり,近年ではLSI設計分野以外の研究者や開発者がFPGAを利用して専用計算機の構築する研究例が多く見られる.しかしながら,FPGA研究に参入するには専門のハードウェア知識の習得や設計環境の整備等の障壁を乗り越える必要がある.本報告では,異分野共同研究を円滑に実施するためのeラーニングと連携した遠隔FPGAシステムの開発を行った.本システムは利用者がコンピュータを用意するのみで遠隔でFPGAの設計教育,研究開発,実証利用を行うことができる.本システムの構成およびシステムを利用した共同研究実施例を述べる.
  • 金田 悠作, 吉澤 真吾, 湊 真一, 有村 博紀, 宮永 喜一
    電子情報通信学会技術研究報告. CPSY, コンピュータシステム 2010年01月 一般社団法人電子情報通信学会
     
    本稿では,重要なデータストリーム処理問題の一つである正規表現パターン照合に対して,ビット並列型パターン照合手法に基づいた高速なハードウェア指向アルゴリズムを提案する.並列ビット分配と呼ぶ新しいビット並列手法を用いて,文字と,連接,和,Kleeneプラスから構成される非消去的正規表現のクラスに対して,O(md log b+m|Σ|)前処理時間とO(md log b/ω+m|Σ|/ω)領域を用いて,O(mdn log b/ω)実行時間の効率的な正規表現照合アルゴリズムを与える.これはd,b,|Σ]|が定数の場合に,O(mn/ω)実行時間とO(m/ω)領域の高速なアルゴリズムを与える.ここで,nは入力長を表し,mと,d,bは,それぞれ,パターンの長さと,深さ,最大戻り幅を,ωは計算機のワード長,|Σ|はアルファベットの要素数を表す.さらに,このアルゴリズムを用いて,回路の再構成を伴わずにパターンの変更を可能なハードウェア実装のアーキテクチャを示す.
  • 金 在成, 吉澤 真吾, 金田 悠作, 湊 真一, 有村 博紀, 宮永 喜一
    電子情報通信学会技術研究報告. CPSY, コンピュータシステム 2010年01月 一般社団法人電子情報通信学会
     
    FPGA (Field Programmable Gate Array)は製造後も論理回路を再構成することが可能であり,近年ではLSI設計分野以外の研究者や開発者がFPGAを利用して専用計算機の構築する研究例が多く見られる.しかしながら,FPGA研究に参入するには専門のハードウェア知識の習得や設計環境の整備等の障壁を乗り越える必要がある.本報告では,異分野共同研究を円滑に実施するためのeラーニングと連携した遠隔FPGAシステムの開発を行った.本システムは利用者がコンピュータを用意するのみで遠隔でFPGAの設計教育,研究開発実証利用を行うことができる.本システムの構成およびシステムを利用した共同研究実施例を述べる.
  • 金田 悠作, 吉澤 真吾, 湊 真一, 有村 博紀, 宮永 喜一
    電子情報通信学会技術研究報告. RECONF, リコンフィギャラブルシステム 2010年01月 一般社団法人電子情報通信学会
     
    本稿では,重要なデータストリーム処理問題の一つである正規表現パターン照合に対して,ビット並列型パターン照合手法に基づいた高速なハードウェア指向アルゴリズムを提案する.並列ビット分配と呼ぶ新しいビット並列手法を用いて,文字と,連接,和,Kleeneプラスから構成される非消去的正規表現のクラスに対して,O(md log b+m|Σ|)前処理時間とO(md log b/w+m|Σ|/w)領域を用いて,O(mdn log b/w)実行時間の効率的な正規表現照合アルゴリズムを与える.これはd,b,|Σ|が定数の場合に,O(mn/w)実行時間とO(m/w)領域の高速なアルゴリズムを与える.ここで,nは入力長を表し,mと,d,bは,それぞれ,パターンの長さと,深さ,最大戻り幅を,wは計算機のワード長,|Σ|はアルファベットの要素数を表す.さらに,このアルゴリズムを用いて,回路の再構成を伴わずにパターンの変更を可能なハードウェア実装のアーキテクチャを示す.
  • 金 在成, 吉澤 真吾, 金田 悠作, 湊 真一, 有村 博紀, 宮永 喜一
    電子情報通信学会技術研究報告. RECONF, リコンフィギャラブルシステム 2010年01月 一般社団法人電子情報通信学会
     
    FPGA(Field Programmable Gate Array)は製造後も論理回路を再構成することが可能であり,近年ではLSI設計分野以外の研究者や開発者がFPGAを利用して専用計算機の構築する研究例が多く見られる.しかしながら,FPGA研究に参入するには専門のハードウェア知識の習得や設計環境の整備等の障壁を乗り越える必要がある.本報告では,異分野共同研究を円滑に実施するためのeラーニングと連携した遠隔FPGAシステムの開発を行った.本システムは利用者がコンピュータを用意するのみで遠隔でFPGAの設計教育,研究開発,実証利用を行うことができる.本システムの構成およびシステムを利用した共同研究実施例を述べる.
  • 河東 孝, 有村 博紀, 平田 耕一
    人工知能学会全国大会論文集 2010年 人工知能学会
  • 金田 悠作, 吉澤 真吾, 湊 真一, 有村 博紀, 宮永 喜一
    電子情報通信学会総合大会講演論文集 2009年03月 一般社団法人電子情報通信学会
  • 河東 孝, 有村 博紀, 平田 耕一
    論文集 2009年 人工知能学会
  • 筒井 淳平, 有村 博紀
    情報処理学会研究報告データベースシステム（DBS） 2008年09月 一般社団法人情報処理学会
     
    本稿では， GUI 上での XQuery 問合せの対話的な構築と編集を考察する． Braga らによる XQuery の視覚言語表現 XQBE に基づき，問合せの内部表現として木構造表現 TQ を提案し，さらに， GUI 上での図像表現 XQUBE を提案する．解析では，クラス TQ と XQUBE が， XQuery の自然な部分クラス TQ-XQuery を表現することを示す．また，この図像表現を用いた具体例に基づく編集と，演示による学習について議論する．This paper studies visual languages for interactive construction and editting of XQuery. We present a tree pattern-like representation TQ by extending Braga et al.'s XQBE (TODS, 30:2, 2005), and then give its visual language counterpart XQUBE. Furthermore, we show that these two representations are equivalent to a restricted fragment of XQuery called TQ-XQuery that has for, child-axis paths, concatenation constructions, but does not have let, if/where constructions, and arbitrary compsition.
  • 大谷 英行, 喜田 拓也, 宇野 毅明, 有村 博紀
    情報処理学会研究報告. 情報学基礎研究会報告 2008年06月 一般社団法人情報処理学会
     
    巨大なデータ集合の中から,有用な知識や情報を発見するデータマイニングは,現代の様々な分野で重要な技術であり,特に,時系列データを対象とした時系列データマイニングが注目を集めている.本論文では,頻出時系列エピソード発見問題を研究する.これは,与えられた系列データから,最大窓幅wの制約の元で,頻出エピソードと呼ばれる頻出する部分系列を効率的に取り出す問題である.本稿では,高速な頻出集合発見アルゴリズムLCMを元にして,エピソード発見のための深さ優先型探索アルゴリズムといくつかの高速化手法を提示し,計算機実験で評価する.技法の一部は,高速系列パターン発見エンジンLCM_seqに実装されており,本稿はこれらの技法の系列マイニングにおける有効性について考察する.
  • 上村 卓史, 喜田 拓也, 有村 博紀
    全国大会講演論文集 2008年03月 一般社団法人情報処理学会
  • 伊藤 公人, 谷口 剛, 村上 悌治, 有村 博紀, 原口 誠
    情報処理学会研究報告. BIO, バイオ情報学 2008年03月 一般社団法人情報処理学会
     
    塩基やアミノ酸の多重配列アライメントから,同時に変異する傾向にある塩基または残基位置の集合を高速に列挙する手法を提案する.本研究では,共変異の検出において,1)条件付きエントロピーH(i|j)を指標として用いることが有効であること,2)条件付きエントロピーH(i|j)の指標を条件付き同時エントロピーH(i_1…i_m|j)へと自然に拡張することにより,三つ以上の位置における共変異を検出可能であること,3)条件付き同時エントロピーの単調性を利用した枝刈り規則と,位置集合と配列集合に関する閉包性を用いることにより,共変異位置集合の列挙アルゴリズムを著しく高速化することが可能であることを示す.
  • 上村 卓史, 喜田 拓也, 有村 博紀
    情報科学技術フォーラム一般講演論文集 2007年08月 FIT(電子情報通信学会・情報処理学会)運営委員会
  • 斉藤 智哉, 喜田 拓也, 有村 博紀
    情報科学技術フォーラム一般講演論文集 2007年08月 FIT(電子情報通信学会・情報処理学会)運営委員会
  • 有村 博紀, 宇野 毅明, 下菌 真一
    人工知能基本問題研究会 2007年07月 人工知能学会
  • 筒井 淳平, 金田 悠作, 有村 博紀
    人工知能基本問題研究会 2007年07月 人工知能学会
  • 上村 卓史, 喜田 拓也, 有村 博紀
    電子情報通信学会技術研究報告. COMP, コンピュテーション 2007年04月 一般社団法人電子情報通信学会
     
    高度なテキスト検索処理においては,テキストの特性(プロパティ)を考慮し,ある条件を満たす区間のみを対象として検索を行うという要求が存在する.本論文では,このプロパティを考慮した索引構造を構築する問題に取り組む.2006年にAmirらは,プロパティに属する区間に含まれる部分文字列のみを格納するプロパティ付き接尾辞木PSTを提案した.彼らの構築アルゴリズムは,接尾辞木から不要なノードを削除することでプロパティ付き接尾辞木を得るものである.本論文では,PSTの線形時間構築への第一歩として,必要な部分と不要な部分との境界となる位置を見つけるための新たなアルゴリズムを提案する.アルゴリズム全体の線形時間性の証明は今後の課題である.
  • 阿久津 達也, 有村 博紀, 下薗真一
    情報処理学会研究報告バイオ情報学（BIO） 2007年03月 一般社団法人情報処理学会
     
    局所マルチプルアラインメントは、複数のＤＮＡ配列、もしくは、タンパク質配列が入力された時に、スコアが最適となるように、それぞれの配列から固定長の領域を選ぶという問題であり、モチーフ検出などの応用を持つ。本稿では、相対エントロピースコア、ＳＰスコア、および、ＭＬｉらにより提案された相対エントロピーに類似したスコアの３種類について、いずれのスコアを用いても局所マルチプルアラインメントがＮＰ困難であることを示す。特に、相対エントロピースコアのもとでこの問題がＡＰＸ困難であることを示す。また、ＳＰスコアを用いた場合などに対する近似アルゴリズムも示す。This article studies the local multiple alignment problem, which is, given protein or DNA se quences, to locate a region (i.e., a substring) of fixed length from each sequence so that the score determined from the set of regions is optimized. We consider the following scoring schemes: the relative entropy score (i.e., average information content), the sum-of-pairs score and a relative entropy-like score introduced by Li et al. We prove that multiple local alignment is NP-hard under each of these scoring schemes. In particular, we prove that multiple local alignment is APX-hard under relative entropy scoring. It implies that unless P = NP there is no polynomial time algorithm whose worst case approximation error can be arbitrarily specified (precisely, a polynomial time approximation scheme). Several related theoretical results are also provided.
  • 有村 博紀, 宇野 毅明, 下薗 真一
    人工知能基本問題研究会 2006年09月 人工知能学会
  • 浅井 達哉, 岡本 青史, 有村 博紀
    情報科学技術フォーラム一般講演論文集 2006年08月 FIT(電子情報通信学会・情報処理学会)運営委員会
  • 有村 博紀, 宇野 毅明
    知識ベ-スシステム研究会 2006年03月 人工知能学会
  • 湊 真一, 有村 博紀
    電子情報通信学会論文誌. D, 情報・システム 2006年02月 一般社団法人電子情報通信学会
     
    大規模なトランザクションデータを,計算機上でコンパクトに表現して効率的に処理することは,データマイニングにおける重要な基盤技術の一つである.本論文では,VLSI CADの分野で大規模論理関数データの表現法として広く用いられている二分決定グラフ(BDD: Binary Decision Diagrams)をデータマイニングの分野に応用する方法を提案する.BDDの中でも「ゼロサプレス型BDD」(ZBDD: Zero-suppressed BDD)と呼ばれるデータ構造は,大規模な組合せ集合データを非明示的に列挙し,効率良く演算処理することができる.このZBDDを用いて,トランザクションデータベースに関する種々の計算処理を行う手法について述べ,実験結果を示す.
  • 有村 博紀, 宇野 毅明
    電子情報通信学会技術研究報告. COMP, コンピュテーション 2005年09月 一般社団法人電子情報通信学会
     
    モチーフとは定数文字と一文字ワイルドカードoからなるABoBoBCのような文字列である.極大モチーフ列挙問題とは, 与えられた文字列上に指定回数以上出現し, しかもより長いモチーフに含まれないようなモチーフをすべて列挙する問題であり, 分子生物学や時系列解析に広い応用をもつ.本論文では, ワイルドカードをもつモチーフの族に対して, 入力文字列長の多項式領域と多項式遅延時間を達成する効率よい極大モチーフ列挙アルゴリズムを与える.具体的には, このアルゴリズムは, 極大モチーフに対する全域木上の深さ優先探索を用いて, すべての極大モチーフを一つあたりO(mn^2)時間とO(lm)領域を用いて列挙する.ここに, nは入力文字列の長さであり, 列挙される極大モチーフxに対して, m=|L(x)|はxの入力文字列中の出現数であり, l=|x|はxの長さである.さらに, 頻出および極大モチーフ数の下限を与え, 単純な列挙方式の限界を示す.
  • 有村 博紀, 宇野 毅明
    人工知能基本問題研究会 2004年11月 人工知能学会
  • 有村 博紀, 宇野 毅明
    情報処理学会研究報告. AL, アルゴリズム研究会報告 2004年10月 一般社団法人情報処理学会
     
    本稿では,系列データベースにおける飽和パターンの新しいクラスを導入し,頻出飽和系列パターンの列挙問題を考察する.位置出現に関する飽和系列パターン(position-closed sequence patterns)は,データベース中で同じ出現位置をもつような同値なパターンの中で最も「くわしい」情報をもつ代表元パターンであり,通常の文書出現に関するものよりも弱い概念の飽和系列パターンである.本稿では,与えられた系列データベース上のすべての頻出飽和系列パターンを一つあたり入力サイズの多項式時間で重複なしに列挙する効率よいアルゴリズムE_<NUM>C_<LOSED>S_<EQ>を与える.これにより,出現位置に関する頻出飽和系列パターンの列挙問題が出力多項式時間で解けることが示される.この結果は,未解決の問題である文書出現に関する飽和系列パターンの多項式時間列挙に,一歩近づくものである.
  • 有村 博紀, 宇野 毅明
    電子情報通信学会技術研究報告. COMP, コンピュテーション 2004年10月 一般社団法人電子情報通信学会
     
    本稿では,系列データベースにおける飽和パターンの新しいクラスを導入し,頻出飽和系列パターンの列挙問題を考察する.位置出現に関する飽和系列パターン(position-closed sequence patterns)は,データベース中で同じ出現位置をもつような同値なパターンの中で最も「くわしい」情報をもつ代表元パターンであり,通常の文書出現に間するものよりも弱い概念の飽和系列パターンである.本稿では,与えられた系列データベース上のすべての頻出飽和系列パターンを一つあたり入力サイズの多項式時間で重複なしに列挙する効率よいアルゴリズムENUMCLOSEDSEQを与える.これにより,出現位置に関する頻出飽和系列パターンの列挙問題が出力多項式時間で解けることが示される.この結果は,未解決の問題である文書出現に関する飽和系列パターンの多項式時間列挙に,一歩近づくものである.
  • 森永 聡, 有村 博紀, 池田 崇博, 坂尾 要祐, 赤峯 享
    情報科学技術フォーラム一般講演論文集 2004年08月 FIT(電子情報通信学会・情報処理学会)運営委員会
  • 喜田 拓也, 有村 博紀
    人工知能基本問題研究会 2004年07月 人工知能学会
  • 浅井 達哉, 房延 慎二, 有村 博紀, 宇野 毅明, 中野 眞一
    数理解析研究所講究録 2004年05月 京都大学
  • 浅井 達哉, 房延 慎二, 有村 博紀
    人工知能基礎論研究会 2004年03月 人工知能学会
  • 宇野 毅明, 浅井 達哉, 有村 博紀, 内田 雄三
    第94回情報処理学会アルゴリズム研究会 2004年03月 一般社団法人情報処理学会
     
    本稿では，トランザクションデータベース中の頻出集合・頻出closed集合・極大頻出集合の列挙アルゴリズムの高速化技術に関して議論する．まず，第89回アルゴリズム研究会に報告された極大2部クリークの列挙アルゴリズムを用いて，頻出closed集合の列挙アルゴリズムを構築する．このアルゴリズムの理論計算量は，頻出closed集合1つあたり多項式時間である．これは，他の頻出closed集合列挙アルゴリズムに対しては示されていない．さらに，このアルゴリズムを改良することにより，全ての頻出集合・極大頻出集合を列挙するアルゴリズムを構築する．昨年米国で行われた頻出集合列挙アルゴリズムの大会での結果を用いて、このアルゴリズムが有効であり，特に現実的で大きな問題に大して有効であることを示す．In this paper, we address practical techniques for efficiently mining all frequent item sets, frequent closed item sets, and maximal ,frequent item sets, respectively, from transaction databases. We modify the algorithm for enumerating maximal bipartite cliques proposed in SIGAL89 [9,10], and propose an algorithm for frequent closed item set enumeration. The computation time of the algorithm is theoretically proved to be linear in the number of output, which is not proved for existing algorithms. We further modify the algorithm for practical computation, and for enumerating all frequent item sets, and maximal frequent item sets. By computational experiments, which is done by a competition of frequent set mining algorithms, we showed our approach is quite efficient, especially for realworld problems witch are said to be difficult.
  • 浅井 達哉, 房延 慎二, 有村 博紀, 宇野 毅明, 中野 眞一
    電子情報通信学会技術研究報告. COMP, コンピュテーション 2004年01月 一般社団法人電子情報通信学会
     
    本稿では,XML文書に代表される半構造データからのデータマイニング問題を考察する.我々は,半構造データのモデルとしてラベルつき無順序木を採用し,与えられた半構造データの集積から出現頻度の高い部分構造を発見するアルゴリズムUNOTを開発した.このアルゴリズムは,逆探索に基づいて無順序木パターンを高速に列挙し,各パターンの出現リストを漸増的に計算することにより,パターン1つあたりO(kb^2m)時間ですべての頻出無順序木パターンTを計算する.ここに,kはTの大きさであり,bはデータ木の最大枝分かれ数,mはTのデータ木への総出現数である.
  • 浅井 準哉, 有村 博紀, 宇野 毅明, 中野 眞一
    電子情報通信学会技術研究報告. DE, データ工学 2003年10月 一般社団法人電子情報通信学会
     
    本稿では,XML文書に代表される半構造データからのデータマイニング問題を考察する.我々は,半構造データのモデルとしてラベルつき無順序木を採用し,与えられた半構造データの集積から出現頻度の高い部分構造を発見するアルゴリズムUNOTを開発した.このアルゴリズムは,逆探索に基づいて無順序木パターンを高速に列挙し,各パターンの出現リストを漸増的に計算することにより,パターン1つあたりO(kb^2m)時間ですべての頻出無順序木パターンTを計算する.ここに,kはTの大きさであり,bはデータ木の最大枝分かれ数,mはTのデータ木への総出現数である.
  • 浅井 準哉, 有村 博紀, 宇野 毅明, 中野 眞一
    電子情報通信学会技術研究報告. DC, ディペンダブルコンピューティング 2003年10月 一般社団法人電子情報通信学会
     
    本稿では,XML文書に代表される半構造データからのデータマイニング問題を考察する.我々は,半構造データのモデルとしてラベルつき無順序木を採用し,与えられた半構造データの集積から出現頻度の高い部分構造を発見するアルゴリズムUNOTを開発した.このアルゴリズムは,逆探索に基づいて無順序木パターンを高速に列挙し,各パターンの出現リストを漸増的に計算することにより,パターン1つあたりO(kb^2m)時間ですべての頻出無順序木パターンTを計算する.ここに,kはTの大きさであり,bはデータ木の最大枝分かれ数,mはTのデータ木への総出現数である.
  • 浅井 達哉, 有村 博紀, 宇野 毅明, 中野 眞一
    電子情報通信学会技術研究報告. DE, データ工学 2003年10月
  • 有村 博紀
    人工知能学会誌 2003年09月 社団法人人工知能学会
  • 浅井 達哉, 有村 博紀, 宇野 毅明, 中野 眞一
    電子情報通信学会技術研究報告. AI, 人工知能と知識処理 2003年07月 一般社団法人電子情報通信学会
     
    本稿では,XML文書に代表される半構造データからのデータマイニング問題を考察する.我々は,半構造データのモデルとしてラベルつき無順序木を採用し,与えられた半構造データの集積から出現頻度の高い部分構造を発見するアルゴリズムUNOTを開発した.このアルゴリズムは,逆探索に基づいて無順序木パターンを高速に列挙し,各パターンの出現リストを漸増的に計算することにより,パターン1つあたりO(kb^2m)時間ですべての頻出無順序木パダーンTを計算する.ここに,kはTの大きさであり,bはデータ木の最大枝分かれ数,mはTのデータ木への総出現数である.
  • 宇野 毅明, 有村 博紀, 浅井 達哉
    電子情報通信学会技術研究報告. AI, 人工知能と知識処理 2003年07月 一般社団法人電子情報通信学会
     
    顧客の売上データのような,アイテムの部分集合族により定められるデータに対して,その族のある一定数以上の要素に合まれるアイテム集合を頻出集合とよぶ.頻出集合はデークマイニングの分野への応用を持つ.近年,極大な頻出集合と,同じような頻出集合を1つにまとめて扱うclosed item setが注目されている.それぞれを列挙することにより,頻出集合の中から意味のある部分を効率よく抽出できるからである.本稿では,極大2部クリークを列挙することにより. closed item setを高速に列挙する手法と,それを用いて極大頻出集合を列挙する手法を提案する.さらに,ベンチマーク問題を用いた計算実験により,既存の手法よりも高速であることを示す.
  • 森川 裕章, 浅井 達哉, 有村 博紀
    情報処理学会研究報告. データベース・システム研究会報告 2003年07月 一般社団法人情報処理学会
     
    最近研究が盛んなスタック有限状態機械(pushdown stack finite state machine)方式のオンラインXPath問合せ機構について,既存方式に比べて簡潔で拡張性が高い方式を提案し,実装と評価実験を行なった.
  • 森川 裕章, 浅井 達哉, 有村 博紀
    電子情報通信学会技術研究報告. DE, データ工学 2003年07月 一般社団法人電子情報通信学会
     
    最近研究が盛んなスタック有限状態機械(pushdown stack finite state machine)方式のオンラインXPath問合せ機構について,既存方式に比べて簡潔で拡張性が高い方式を提案し,実装と評価実験を行なった.
  • 浅井 達哉, 安部 賢治, 川副 真治, 有村 博紀, 有川 節夫
    数理解析研究所講究録 2003年05月 京都大学
  • 有村 博紀, 浅井 達哉
    Computer today 2003年03月 サイエンス社
  • 川副 真治, 浅井 達哉, 有村 博紀
    人工知能学会全国大会論文集 2003年 人工知能学会
  • 浅井 達哉, 有村 博紀, 安部 賢治, 川副 真治, 有川 節夫
    電子情報通信学会技術研究報告. DE, データ工学 2002年10月 一般社団法人電子情報通信学会
     
    本稿では,半構造データのストリームに対するオンライン型データマイニング問題を考察する.我々は,半構造データとパターンのモデルとしてラベルつき順序木を採用し,与えられた半構造データストリームから,任意の時点で現在の頻出パターンを出力するオンライン型半構造データマイニングアルゴリズムStreamTを開発した.このアルゴリズムでは,掃木枝を右へ動かすことによりパターンの出現を漸増的に検知する.我々は,アルゴリズムが無限のデータストリームに対して,有限の資源しか用いずに効率的に働くことを示した.
  • 浅井 達哉, 有村 博紀, 安部 賢治, 川副 真治, 有川 節夫
    電子情報通信学会技術研究報告. DC, ディペンダブルコンピューティング 2002年10月 一般社団法人電子情報通信学会
     
    本稿では,半構造データのストリームに対するオンライン型データマイニング問題を考察する.我々は,半構造データとパターンのモデルとしてラベルつき順序木を採用し,与えられた半構造データストリームから,任意の時点で現在の頻出パターンを出力するオンライン型半構造データマイニングアルゴリズムStreamTを開発した.このアルゴリズムでは,掃木枝を右へ動かすことによりパターンの出現を漸増的に検知する.我々は,アルゴリズムが無限のデータストリームに対して,有限の資源しか用いずに効率的に働くことを示した.
  • 坂本 比呂志, 谷口 力昭, 有村 博紀
    知識ベ-スシステム研究会 2001年11月 人工知能学会
  • 坂本 比呂志, 谷口 力昭, 有村 博紀
    人工知能基礎論研究会 2001年11月 人工知能学会
  • 浅井 達哉, 安部 賢治, 川副 真治, 有村 博紀, 有川 節夫
    電子情報通信学会技術研究報告. DE, データ工学 2001年10月 一般社団法人電子情報通信学会
     
    本稿では, 半構造データベースからのデータマイニングを考察する.我々は半構造データマイニングを, 与えられた半構造データの集積から出現頻度の高い部分構造を発見する問題と定式化し, 頻出する部分構造パターンを発見する効率よいアルゴリズムを与える.このアルゴリズムは, Bayardo(SIGMOD'98)による集合枚挙木に基づくアイテム集合の枚挙法を, 順序木の枚挙へ拡張することにより実現している.さらに, ウェブデータ上で実験を行い, 開発したアルゴリズムの有効性を確認した.
  • 有村 博紀, 安部 潤一郎, 坂本 弘呂志, 有川 節夫
    情報基盤センター年報 2001年10月 九州大学
  • 有村 博紀
    電子情報通信学会ソサイエティ大会講演論文集 2001年08月 一般社団法人電子情報通信学会
  • 平田 耕一, 坂本 比呂志, 有村 博紀
    数理解析研究所講究録 2001年05月 京都大学
  • 安積 裕樹, 安部 潤一郎, 有村 博紀, 有川 節夫
    情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 2001年03月 一般社団法人情報処理学会
     
    本論文では,分散記憶型並列計算機上での効率のよい全文索引構築法について提案する.接尾辞配列は,最近提案された高機能全文索引であり,情報検索や遺伝子情報などに広い応用をもつ.Baeza-Yates-Gonnet-Sinder(BGS)アルゴリズムは,最も広く使われている外部記憶上の接尾辞配列構築アルゴリズムである.このBGSアルゴリズムを並列化し,効率のよい並列接尾辞配列構築アルゴリズムを与える.提案アルゴリズムは,並列計算機時間と通信量に関して,BGSの最適な並列化になっており,従来からあるBGSの並列版のRiberio-Kitajima-Ziviani(RKZ)アルゴリズムに比べてより高速である.
  • 村上 義継, 坂本 比呂志, 有村 博紀, 有川 節夫
    情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 2001年03月 一般社団法人情報処理学会
  • 有村 博紀
    電子情報通信学会技術研究報告. IT, 情報理論 2000年10月 一般社団法人電子情報通信学会
     
    データマイニング(DataMining)は, データベースからの知識発見とも呼ばれ, データベースに蓄積された一見無意味にみえる大量のデータから, 自明でない規則性やパターンを半自動的にとりだす方法についての科学的研究である.データマイニングの研究は, 1990年代初頭から顕在化し, 現在, ビジネス分野や科学技術分野をはじめとするさまざまな対象領域で, その適用が盛んにおこなわれている.本稿では, テキストデータとウェブデータを対象としたデータマイニング研究の最新動向について解説する.
  • 坂本 比呂志, 有村 博紀, 有川 節夫
    人工知能基礎論研究会 2000年07月 人工知能学会
  • 高江 徹, 安部 潤一郎, 坂本 比呂志, 有村 博紀, 井上 仁, 武谷 俊一, 上園 慶子, 川崎 晃一
    人工知能学会全国大会論文集 = Proceedings of the Annual Conference of JSAI 2000年07月 人工知能学会
  • 安部 潤一郎, 藤野 亮一, 下薗 真一, 有村 博紀, 有川 節夫
    人工知能学会誌 2000年07月 社団法人人工知能学会
     
    This paper describes applications of text data mining to interactive document browsing and web mining. We develop a fast text data mining method based on optimal pattern discovery, and make experiments on large collections of documents and Web pages to evaluate the proposed method.
  • K語近接相関パタンの高速発見アルゴリズム
    下薗 真一, 有村 博紀, 有川 節夫
    電子情報通信学会技術研究報告. COMP, コンピュテーション 1999年11月 一般社団法人電子情報通信学会
     
    与えられた大量の文書の集積から, 分類精度を最大にする文字列パタンを見つける問題を考察する.複数の文字列の近接した出現を記述する近接語相関パタンを導入し, 文字出現が独立で一様な確率分布にしたがうランダムテキストに対して, 分類精度を最大化する近接度がkでd個の語からなる語相関パタンを平均計算時間O(k^nlog^n)および領域O(k^n)で計算するアルゴリズムを与える.このアルゴリズムは, すべての部分語を枚挙する自明なアルゴリズムの時間計算量O(n^<2d+1>)に対して, 著しい高速化を達成しており, 遺伝子情報データのようなほぼランダムなテキストに対するデータマイニング問題に適用可能である.この結果は, 任意個数の語からなる近接相関パタンに対して, 分類精度最適化問題が多項式時間近似スキームをもたない事実と対照的である.
  • 安部 潤一郎, 笠井 透, 有村 博紀
    人工知能基礎論研究会 1999年07月 人工知能学会
  • 板井 力, 笠井 透, 有村 博紀, 有川 節夫
    人工知能学会全国大会論文集 = Proceedings of the Annual Conference of JSAI 1999年06月 人工知能学会
  • 藤野 亮一, 有村 博紀, 有川 節夫
    人工知能学会全国大会論文集 = Proceedings of the Annual Conference of JSAI 1999年06月 人工知能学会
  • 笠井 透, 有村 博紀, 有川 節夫
    数理解析研究所講究録 1999年04月 京都大学
  • 笠井 透, 有村 博紀, 有川 節夫
    全国大会講演論文集 1999年03月 一般社団法人情報処理学会
  • 高江 徹, 近棟 稔, 有村 博紀, 篠原 歩, 井上 仁, 武谷 俊一, 上園 慶子, 川崎 晃一
    全国大会講演論文集 1999年 一般社団法人情報処理学会
  • 阿久津 達也, 有村 博紀, 下薗 真一
    合同研究会AIシンポジウム 1999年 人工知能学会
  • 下薗 真一, 有村 博紀, 有川 節夫
    電子情報通信学会技術研究報告. COMP, コンピュテーション 1998年11月 一般社団法人電子情報通信学会
     
    与えられた大量の文書の集積から, 分類精度を最大にする文字列パタンを見つける問題を考察する.複数の文字列の近接した出現を記述する近接語相関パタンを導入し, 文字出現が独立で一様な確率分布にしたがうランダムテキストに対して, 分類精度を最大化する近接度がkでd個の語からなる語相関パタンを平均計算時間O(k^<d-1>nlog^<d+1>n)および領域O(k^<d-1>n)で計算するアルゴリズムを与える.このアルゴリズムは, すべての部分語を枚挙する自明なアルゴリズムの時間計算量O(n^<2d+1>)に対して, 著しい高速化を達成しており, 遺伝子情報データのようなほぼランダムなテキストに対するデータマイニング問題に適用可能である.この結果は, 任意個数の語からなる近接相関パタンに対して, 分類精度最適化問題が多項式時間近似スキームをもたない事実と対照的である.
  • 笠井 透, 有村 博紀, 篠原 武
    全国大会講演論文集 1998年10月 一般社団法人情報処理学会
  • 笠井 透, 有村 博紀, 篠原 武
    Research reports on information science and electrical engineering of Kyushu University 1998年09月 九州大学
  • 笠井 透, 有村 博紀, 藤野 亮一, 有川 節夫
    情報処理学会研究報告. データベース・システム研究会報告 1998年07月 一般社団法人情報処理学会
     
    与えられた大量の文書の集積から, 分類精度を最大化にする文字列パタンを見つける問題を考察する.複数の文字列の近接した出現を記述する近接語相関パタンを導入し, 一様確率で生成されたランダムテキストに対して, 分類精度を最大にする(d, k)-語相関パタンを平均計算時間O(k^<d-1>nlog^<d+1>nおよび領域O(k^<d-1>n)で計算するアルゴリズムを与える.さらに, 大規模テキストデータ向けの索引構造である接尾語配列上での実装方法についても考察する.
  • 稲子 希望, 有村 博紀
    数理解析研究所講究録 1998年04月 京都大学
  • 渡木 厚, 有村 博紀, 藤野 亮一, 有川 節夫
    数理解析研究所講究録 1998年04月 京都大学
  • 有村 博紀, 渡木 厚, 下薗 真一
    電子情報通信学会技術研究報告. COMP, コンピュテーション 1997年10月 一般社団法人電子情報通信学会
     
    与えられた大量の文書の集積から, 分類精度を最大にする文字列パタンを見つける問題を考察する. 二つの文字列の近接した出現を要求する二語相関パタンを導入し, 分類精度を最大化する最適パタンをO(n^2) 時間および領域O(kn) 領域で計算するアルゴリズムを与える. また, 相関パターンの語数を制限しない場合, 分類精度の最大化問題が多項式時間での任意の近似が困難であることを示す.
  • 有村 博紀, 渡木 厚, 藤野 亮一, 有川 節夫
    全国大会講演論文集 1997年09月 一般社団法人情報処理学会
     
    本研究では, 大量の文書の集積から, 分類精度を最適化するパタンを見つける問題を考察する。二語相関パタンとよばれる単純なパタンを仮説としたとき, 分類精度を最大化する最適パタンをO(n^2)時間および領域O(kn)領域で計算するアルゴリズムを与える。
  • 峯 恒憲, 佐藤 周行, 正代 隆義, 廣川 佐千男, 有村 博紀, 森 雅生, 篠原 歩, 竹田 正幸
    情報処理学会研究報告. DD, [デジタル・ドキュメント] 1997年05月 一般社団法人情報処理学会
     
    九州大学では、毎年およそ2,300人の新入生が情報処理の入門教育を受講する。これらの学生は、Windows95の動くパソコン上で、プログラミングを始めとする情報処理の基礎を学ぶ。個人差が大きくなりがちな情報処理を学ぶ学生の習熟度に対処するため、講義をサポートし、かつ、講義時間外に利用できる自学自習用のホームページを用意した。このページでは、我々のこれまでの情報処理教育の経験から得た講義のエッセンスを再現(Lecture Capture)している。しかし、プログラムが如何に動作するかを理解させることは難しかった。そこで、我々は、プログラムの動作の理解を助ける機能として、「プログラムアニメーションコンパイララ」と呼ぶPascalプログラムをJava Appletに変換するシミュレータを開発した。これにより、Webのブラウザを通してプログラムの動きを体験し、実感してもらえるようになった。本稿では、本システムのアイデアと概要、並びに今後の開発予定について報告する。
  • 池田 大輔, 有村 博紀
    数理解析研究所講究録 1997年05月 京都大学
  • ALT'96報告  [通常講演]
    杉本 典子, 平田 耕一, 有村 博紀
    人工知能学会誌 1997年03月 社団法人人工知能学会
  • 有川 節夫, 有村 博紀
    人工知能学会誌 1997年03月 社団法人人工知能学会
  • 有村 博紀, 篠原 武
    数理解析研究所講究録 1996年05月 京都大学
  • 宮崎 哲司, 平田 博明, 古賀 寿憲, 深町 修一, 有村 博紀, 篠原 武
    全国大会講演論文集 1995年09月 一般社団法人情報処理学会
     
    情報検索の問題の1つとして,パターン照合問題がある.パターン照合間題とは,パターンおよびテキストという2つの文字列が与えられたとき,テキスト中におけるパターンのすべての出現を見つけだす問題である.このパターン照合問題を解くアルゴリズムに,Aho-Corasick法がある.Aho-Corasick法の特長は,パターンよりパターン照合機械という一種の有限オートマトンを作り,そのパターン照合機械をテキスト上で1回走査させるだけで複数のパターンを同時に検出できることである.Aho-Corasick法を用いて実際に検索を行う際に問題になるのが,ディスクからテキストを読み込むのに要する時間である.この間題に対して,テキストをあらかじめ圧縮しておき,その圧縮されたテキストを復号せずに検索する方法が提案されている.日本語テキストには,ひらがな,カタカナ,漢字,記号といった複数の文字種が存在し,テキスト中では同じ文字種が連続して出現するという性質がある.この性質を利用して,文字種ごとに圧縮符号を割り当てることにする.このとき,異なる文字種間で同じ符号が割り当てられる可能性があるので,文字種を保持する必要がある.文字種の変わり目に文字種が変わることを示すシフトコードを用いる.この方法により,文字種を考慮に入れずに全体で圧縮符号を割り当てた場合より圧縮率はよくなる.本稿では,Aho-Corasick法のパターン照合機械を拡張し,シフトコード付き圧縮符号によって圧縮された日本語テキストのためのパターン照合機械を設計した.これを用いて日本語テキストを対象として実験を行った結果,圧縮率は69.7%,走査時間は78.3%に短縮できた.
  • 有村 博紀, 篠原 武
    全国大会講演論文集 1995年09月 一般社団法人情報処理学会
     
    機械学習や帰納推論,仮説推論等における重要な推論手法の一つが,概念の汎化である.概念の汎化とは,いくつかの具体例が与えられたときに,それらを説明するより一般的な概念を見つけることであり,構成的学習において有効な手法である.とくに帰納論理プログラミング等の論理プログラムの学習の分野では,汎化にもとづく学習システムについて活発な研究がおこなわれている.本研究では,論理プログラムを背景知識の存在のもとで汎化する問題について議論する.とくに,高々k個の制約確定節からなる集合のうちで,例として与えられたすべての確定節を導き,背景知識Bのもとで含意に関して極小なものを見つける問題を考察し,この問題を多項式時間で解くアルゴリズムを与える.これは[2]の結果を複数の節からなる論理プログラムに拡張するものである.さらに,論理プログラムの学習への応用について述べる.
  • 山口 美千代, 篠原 武, 藤野 亮一, 有村 博紀, 有川 節夫
    情報処理学会研究報告. 情報学基礎研究会報告 1995年07月 一般社団法人情報処理学会
     
    正則パターンとは定数と互いに異なる変数からなる文字列であり,その正則パターン中の変数を空文字を含む定数文字列で置き換えて得られる定数文字列全体を表わす.本研究では,正例のみから複数のパターンを同時に学習するk極小多重汎化アルゴリズムを,アミノ酸配列からのタンパク質モチーフ発見に応用する.まず,このk極小多重汎化アルゴリズムに例の集合から例外となる文字列を積極的に検出する探索戦略を組み込み,次にその有用性を膜貫通領域を対象とした実験で実証する.実験では,この探索戦略を用いた学習アルゴリズムが,従来からの探索戦略に比較して高い精度の仮説を,安定して,より短い時間で見つけることを確認した.
  • 篠原 武, 藤野 亮一, 有村 博紀, 有川 節夫
    人工知能学会全国大会論文集 = Proceedings of the Annual Conference of JSAI 1995年07月
  • 有村 博紀, 石坂 裕毅, 篠原 武
    人工知能学会全国大会論文集 = Proceedings of the Annual Conference of JSAI 1995年07月
  • 深町 修一, 下薗 真一, 有村 博紀, 篠原 武
    電子情報通信学会技術研究報告. NLC, 言語理解とコミュニケーション 1995年05月 一般社団法人電子情報通信学会
     
    もとのアルファベットからより小さなサイズkのアルファベットへの写像は,k-indexingと呼ばれ,損失のある圧縮符号とみなすことができる.損失のある符号を用いて圧縮されたテキスト上での文字列パターン照合は,圧縮率が高くなるために高速化が期待できるが,誤検出の可能性がある.2^n-indexingを用いると,nビットの固定長符号で,長さlのパターンの誤検出の期待値がほぼ<1/2>^<nl>となるような圧縮を行うことができる.文字ごとの照合に対する最適化,さらに2-gram,3-gramに対する最適化を行い,実際の英文テキストを用いて実験を行った.
  • 沼尾 正行, 有村 博紀, 原口 誠, 平田 耕一, 斉藤 和巳, 諏訪 正樹, 月本 洋, 元田 浩
    人工知能学会誌 1994年03月 社団法人人工知能学会
  • 有村 博紀, 篠原 武
    人工知能学会全国大会論文集 = Proceedings of the Annual Conference of JSAI 1993年07月
  • 石坂 裕毅, 有村 博紀, 篠原 武
    人工知能学会誌 1993年07月 社団法人人工知能学会
     
    We consider the polynomial time inferability of primitive Prologs from positive facts. The class of primitive Prologs is a proper subclass of that of linear Prologs which is known to be inferable from only positive facts. In this paper, we discuss the polynomial time inferability of the subclass using minimal multiple generalizations. The minimal multiple generalization is a natural extension of the least generalization given by Plotkin in 1970. The minimal multiple generalization generalizes given first order words by several words, while the least generalization does by a single word. The property of the minimal multiple generalization makes it possible to perform fine generalization and to construct the heads of several clauses in a target program at the same time. We give an outline of a consistent polynomial time inference algorithm which identifies the class of primitive Prologs in the limit. The algorithm infers the heads of clauses in a target program as a minimal multiple generalization of a set of given positive facts. Furthermore, we give a similar result on the inferability of a subclass of context-free transformations which includes several well-known Prolog programs.

その他活動・業績

受賞

  • 2022年06月 情報処理学会 2022年度コンピュータサイエンス領域奨励賞（指導学生）
     デカルト木部分列照合問題の高速なアルゴリズム，アルゴリズム(AL)研究会情報処理学会, 2022-AL-186, 2022年1月（著者：大泉 翼，有村博紀） 
    受賞者: 大泉翼
  • 2022年06月 人工知能学会 2021年度論文賞
     Distribution-Aware Counterfactual Explanation by Mixed-Integer Linear Optimization 
    受賞者: Kentaro Kanamori;Takuya Takagi;Ken Kobayashi;Hiroki Arimura
  • 2019年01月 人工知能学会 研究会優秀賞
     整数計画法に基づく学習済み決定木の公平性を考慮した編集法 
    受賞者: 金森憲太朗;有村博紀
  • 2016年06月 情報処理学会 論文賞
     大規模軌跡データからの群パターン発見のための実用的アルゴリズム 
    受賞者: 耿暁亮;宇野毅明;有村博紀
  • 2016年03月 情報処理学会 2016年度（平成28年度）山下記念研究賞
     三次元空間における効率良い近似点集合マッチングと分子パターン照合への応用，バイオ情報学研究会/MPS研究パターン照合への応用，バイオ情報学研究会/MPS研究会，201会，2015-BIO-42，2015-MPS-104, 2015/6（著者：佐々木耀一，渋谷哲朗，伊藤公人，有村博紀） 
    受賞者: 佐々木 耀一
  • 2015年 情報処理学会 全国大会 学生奨励賞（指導学生〕
     三次元空間における効率良い近似点集合マッチングと分子パターン照合への応用 
    受賞者: 佐々木 耀一
  • 2013年06月 人工知能学会 研究会優秀賞
     超グラフ中に含まれる非巡回部分超グラフの効率よい列挙 
    受賞者: 和佐 州洋;有村 博紀;宇野 毅明;平田 耕一
  • 2010年06月 電子情報通信学会 情報・システムソサイエティ 論文賞（先見論文）
     「ゼロサプレス型二分決定グラフを用いたトランザクションデータベースの 効率的解析手法」 
    受賞者: 湊真一;有村博紀
  • 2005年02月 日本データベース学会 上林記念研究奨励賞
     
    受賞者: 有村 博紀
  • 2004年11月 2nd Workshop on Frequent Itemset Mining Implementations (FIMI'04), in conjunction with IEEE ICDM'04 BEST IMPLEMENTATION AWARD
     
    受賞者: Takeaki Uno;Masashi Kiyomi;Hiroki Arimura
  • 2004年11月 人工知能学会 2004年研究会優秀賞
     「大規模系列データから代表的な頻出エピソードを発見するための効率よいアルゴリズム」 
    受賞者: 有村博紀;宇野毅明
  • 2004年07月 電子情報通信学会DE研究会第１５回データ工学ワークショップ DEWS2004優秀論文賞
     「半構造データマイニングのための高速な無順序木パターン発見手法」 
    受賞者: 房延慎二;浅井達哉;有村博紀;宇野毅明;中野眞一
  • 2003年06月 電子情報通信学会DE研究会第１４回データ工学ワークショップ DEWS2003最優秀論文賞
     「領域効率の良い頻出データアイテム発見アルゴリズム」 
    受賞者: 川副真治;有村博紀
  • 2002年05月 電子情報通信学会DE研究会第１４回データ工学ワークショップ DEWS2002優秀論文賞
     
    受賞者: 浅井達哉;安部賢治;川副真治;坂本比呂志;有村博紀;有川節夫
  • 2001年05月 人工知能学会 2000年度論文賞
     「テキストデータからの高速データマイニング」, 安部潤一郎, 藤野亮一, 下薗真一, 有村博紀, 有川節夫（2000年7月掲載） 
    受賞者: 安部潤一郎;藤野亮一;下薗真一;有村博紀;有川節夫
  • 2000年04月 PAKDD2000 Paper with Merit Award
     "Discovering unordered and ordered phrase association patterns for text mining" 
    受賞者: Ryoichi Fujino;Hiroki Arimura;Setsuo Arikawa
  • 1999年12月 人工知能学会 1999年度全国大会優秀論文賞
     「 大規模テキストデータからの探索的文書ブラウジング」 
    受賞者: 板井力;笠井透;有村博紀;有川節夫
  • 1998年03月 情報処理学会 第５５回全国大会大会優秀賞
     「最適パタン発見に基づくテキストデータマイニング」 
    受賞者: 有村博紀;渡木厚;藤野亮一;有川節夫
  • 1992年07月 人工知能学会 全国大会優秀論文賞
     「極小汎化に基づくPROLOGプログラムの正事実からの多項式時間推論」 
    受賞者: 有村博紀;石坂裕毅;篠原武
  • 1992年06月 人工知能学会 1992年度研究奨励賞
     「Polynomial Time Inference of Unions of Tree Pattern Languages」 
    受賞者: 有村博紀;石坂裕毅;篠原武

共同研究・競争的資金等の研究課題

  • 日本学術振興会：科学研究費助成事業 学術変革領域研究(A)
    研究期間 : 2020年11月 -2025年03月 
    代表者 : 安田 宜仁, 有村 博紀, 鍋島 英知, 井上 武, 西野 正彬
     
    2020年度は採択後からの4か月の期間を、今後の研究活動の準備期間と捉え、 遠隔での交流のための環境整備や、実装を意識した場合に注力するべき項目の洗い出しを中心に行った。特に後者については、二分決定図を活用した既存ライブラリである graphillion の課題についての検討を進めた。 個別の研究としては、厳密被覆の全解列挙、非同期ストリーム索引、離散最適化を用いた説明可能性機械学習において進展があった。 厳密被覆(集合とそのいくつかの部分集合が与えられた場合に、和集合が重複なく入力集合を構成するような組合せを見つける問題)の全解列挙に関して、入力の部分集合の数が大きい場合でも効率的に動作するような方法を考案した。ゼロサプレス型二分決定図(ZDD)に類似する「DanceDD」というデータ構造を考案し、これを実現した。 高速非同期ストリーム索引について、高木と、稲永、有村、Breslauer、Hendrianらは、一本の成長する系列の索引である接尾辞木のオンライン線形時間構築法を、非同期に成長する複数本の系列の索引である「全オンライン接尾辞木」に自然に拡張することに世界で初めて成功し、その線形時間アルゴリズムを与えた（学術論文1）． 離散最適化を用いた説明可能性機械学習について、金森と有村等は、説明可能機械学習問題において、因果構造を反映した反実仮想説明の整数計画法を用いた生成手法を開発し、人工知能分野のトップ会議AAAI2021に採択され、2022年1月に発表を行った（国際会議発表1）。この成果は、日本経済新聞や各種ウェブメディア等で報道されるなど社会的関心を集めた （報道他1）．
  • 日本学術振興会：科学研究費助成事業 基盤研究(A)
    研究期間 : 2020年04月 -2025年03月 
    代表者 : 有村 博紀, 宇野 毅明, 平田 耕一, 山本 章博, 喜田 拓也, ジョーダン チャールズハロルド
  • 科学技術振興事業団（JST）：
    研究期間 : 2018年10月 -2025年03月 
    代表者 : 有村博紀, 中村篤祥, 瀧川一学, 和佐州洋, 栗田和宏
  • 日本学術振興会：科学研究費助成事業 挑戦的研究(萌芽)
    研究期間 : 2018年06月 -2021年03月 
    代表者 : 有村 博紀, トーマス ツォイクマン, 喜田 拓也
     
    本研究では，多様で膨大な実世界時空間ストリームデータに対する高速大規模処理の基盤技術として，複雑なパターンに対する検索・計数・発見技術を中心に研究開発している．研究組織として，研究代表者の有村が高速パターン検索・発見技術の研究開発を，研究分担者のトーマス ツォイクマンが多重ストリーム処理と知識発見の理論の構築を，連携研究者のジョーダン チャールズハロルドが超高速確率計算手法の開発を担当し，相互に協力つつ研究を遂行する．とくに本研究では，アルゴリズムの高速性と低メモリ性に加えて，実世界時空間ストリーム処理の特性に対応して，適応性・文脈性・多重性をもつアルゴリズムの開発に焦点を当てて研究した．各テーマごとに，アルゴリズム開発と，理論解析，実装評価を並行して進めた．具体的には，研究期間全体では，次の５つの分担研究項目の研究を行った: (A1) ビット並列技法を用いた超高速実世界ストリーム検索技術の研究開発（有村）計算ハードウェアに内在する並列性を利用して、ストリーム処理を準線形時間に高速化する。 (A2) 確率的手法に基づく超高速実世界ストリーム計数技術の研究開発（ジョーダン，有村）。確率的な情報処理の枠組みで、近似を許した上で高速なストリーム処理を行う。 (A3) 構造列挙手法に基づく超高速実世界ストリーム発見技術の研究開発（有村・ジョーダン）。回候補となる構造を高速にもれなく列挙する構造列挙手法をストリーム処理に拡張する。 (A4) 超高速ストリーム知識発見の理論的基盤の研究（ツォイグマン，有村）。有限オートマトンなどの計算モデルを用いて高速な多ストリーム処理の理論構築を行う。 (B1) プロトタイプシステム構築と予備評価実験．これまでに開発したアルゴリズムを実装して、高速ストリーム処理と大規模並列列挙のためのライブラリを提供し、その性能を実験的に評価する．
  • 日本学術振興会：科学研究費助成事業 基盤研究(A)
    研究期間 : 2016年04月 -2020年03月 
    代表者 : 有村 博紀, 宇野 毅明, 湊 真一, 平田 耕一, 伊藤 公人, 下薗 真一, 喜田 拓也
     
    本研究では，実世界と情報世界が融合した巨大な情報空間から有用な知識を効率よくとりだすための実世界知識基盤形成のための大規模半構造マイニング技術とその周辺技術の確立を目指して研究を行った．とくに，知識表現の発見のための高速半構造マイニングエンジン技術と，確率情報を用いた知識発見技術，実世界の多様な半構造データに適用するための超高速ストリーム処理技術や，高性能圧縮技術，知識索引技術を研究し，それらを実装し，理論解析および実証実験を行った．
  • 日本学術振興会：科学研究費助成事業 基盤研究(S)
    研究期間 : 2015年05月 -2020年03月 
    代表者 : 湊 真一, 有村 博紀, 瀧川 一学, 宇野 毅明, 堀山 貴史, 津田 宏治, 鷲尾 隆
     
    研究成果の概要（和文）：本研究では，離散構造処理系のコアとなる基盤アルゴリズムを構築し，高性能な基盤ソフトウェアを応用分野の研究者や技術者に提供することを目指した．主な成果の例として，①全国都道府県の隣接ブロック組合せの総数（約1098億通り）を初めて明らかにし，(独)統計センターから国民にデータを公開した，②異分野横断の交流から難関国際会議（AAAI,WWW,KDD,INFOCOM,AISTATS,SDM他）に採択される研究成果を多数生み出した，等が挙げられる．
  • 日本学術振興会：科学研究費助成事業
    研究期間 : 2017年04月 -2019年03月 
    代表者 : 小宮山 純平, 石畠 正和, 有村 博紀, 西林 孝, 湊 真一, 前原 貴憲
     
    パターンマイニングのアルゴリズムは、出現頻度の比率が一定以上大きい組合せ特徴量（パターン）集合を効率的に列挙する。しかし、データの確率的な偏りについては考慮がされず、興味のあるパターンが偶然の偏りによって出てきたものなのかが検証されない。本研究では、誤った発見をする確率に関して統計的保証を満たしたパターンマイニングの手法を提案し、データマイニングのトップ国際会議であるKDD2017において発表を行った。また、統計的保証の頑健性などについて研究を行った。いくつかのパターンがあるときに、そのうちのたまたまうまくいったものを選ぶ出版バイアスがどの程度の大きさになるか定量化することができた。
  • 日本学術振興会：科学研究費助成事業 基盤研究(B)
    研究期間 : 2015年04月 -2019年03月 
    代表者 : 本村 真人, 有村 博紀
     
    本研究では組合せ最適化問題の最適解を導き出すことを狙ったアーキテクチャ研究に注力した。従来の単一スパースハードウェアグラフでは、ハードウェア構造より密なグラフを再現する際、スピンを複製し、擬似的に密なグラフを再現するマイナーエンベディングという方法がとられる。スピンの状態の更新が、隣接スピンの状態とスピン間相互作用の積和演算によって再現されることを利用して、スパースなハードウェア構造それぞれに対して、時間方向の接続（積和演算を継続）を可能にすることで、複製スピンによる強い相互作用を加えることなく処理を行うことを実現し、大規模な問題から高い精度の解を得るアーキテクチャを提案した。
  • 日本学術振興会：科学研究費助成事業 挑戦的萌芽研究
    研究期間 : 2015年04月 -2018年03月 
    代表者 : 有村 博紀, トーマス ツォイクマン, ジョーダン チャールズハロルド
     
    本研究では，多様で膨大な実世界時空間ストリームデータに対する高速大規模処理の基盤技術として，複雑なパターンの検索・計数・発見技術に関して，アルゴリズムの高速性と，低メモリ性，適応性，文脈性，多重性に焦点を当て研究した．具体的には，次の研究項目を研究した：A1. ビット並列技法を用いた超高速実世界ストリーム検索技術（有村）．A2. 確率的近似検査法に基づく超高速実世界ストリーム計数技術（ジョーダン，有村）．A3. 構造列挙手法に基づく超高速実世界ストリーム発見技術（有村・ジョーダン）．A4. 超高速ストリーム知識発見の理論的基盤（ツォイグマン，有村）．B1. プロトタイプ構築と予備評価実験．
  • 日本学術振興会：科学研究費助成事業 基盤研究(A)
    研究期間 : 2012年04月 -2016年03月 
    代表者 : 有村 博紀, 宇野 毅明, 湊 真一, 平田 耕一, 伊藤 公人, 下薗 真一, 喜田 拓也
     
    本研究では，実世界と情報世界が融合した巨大な情報空間から有用な知識を効率よくとりだすための大規模半構造マイニング技術の確立を目指す．とくに，大規模規模知識基盤形成システムのための基礎技術として，超高速半構造マイニングエンジンと，時空間情報を用いた半構造マイニング技術の研究開発，周辺技術として，確率的情報スキーマの導入と，知識連係技術と知識索引技術の研究開発を行った．開発した技術の実装と最適化によりプロトタイプシステムの構築を行った．
  • 日本学術振興会：科学研究費助成事業 新学術領域研究(研究領域提案型)
    研究期間 : 2013年04月 -2015年03月 
    代表者 : 有村 博紀
     
    本研究が連携する計画研究A01班で構築するバイオミメティクス・データベースは，生物学や材料科学等の異分野のデータベースを，画像データ検索技術により横断的に検索し，クラスタリングして提示することで，専門の異なる研究者に新たな気づきを提供し，異分野連携と産学連携の強力な推進基盤となる．また，ISO においてバイオミメティクスの国際標準化の検討が開始されており，先に述べた画像検索技術を踏まえ，国際標準化に参画することで，我が国の国際競争力強化に貢献できる． 以上の背景のもと，本研究では，オープン・イノベーション・プラットフォームの実現に向けて，国際的産業応用可能なバイオミメティクス・データベースの機能についての検討を目的として調査研究を行った．産学連携については，国内外におけるバイオミメティクスに関する異分野連携・産学連携の動向について，欧州のBiomimicry Europa等，昨年度の調査対象組織のその後の動向について詳細に調べた． バイオミメティクスの国際標準化を検討する技術委員会ISO/TC266における標準化活動を行った．具体的には，国際委員会（第4回ISO総会，2014年10月，ベルギー），国内審議委員会としてISO国内審議委員会（2014年4月，第9回から第11回），国内WG4会議等に参加し，調査および標準化活動を行った．また，標準化に関連する大規模検索とデータ解析に関する技術開発も行った． 以上の活動により，我が国がバイオミメティクスの産業応用で世界に先んじ，我が国の産業界に資することを目指した．さらに，上記を通じて同分野の人材育成も行った．
  • 日本学術振興会：科学研究費助成事業
    研究期間 : 2011年04月 -2014年03月 
    代表者 : 申 吉浩, 岡本 洋, 有村 博紀, 坂本 比呂志, 久保山 哲二, CUTURI Marco
     
    ビッグデータなどの情報資産を将来の予測に役立てる機械学習技術の中で、カーネル法は多様なデータ構造に適用できる点で重要である。通常はベクター型のデータを仮定するが、現実には、DNA等の配列構造、蛋白質・構文木・XML文書等の木構造、各種ネットワーク等のグラフ構造など、構造をもつデータが多く存在する。本研究では、構造データを効率よく解析する手段として、構造カーネルの基礎理論構築と実用化に向けた研究を行った。具体的には、カーネルの必須要件である正定値性の判定理論、多様な構造への適用手法の開発、そして、研究者を対象者としたカーネル計算ユーティリティの構築とインターネット上での公開を行った。
  • 日本学術振興会：科学研究費助成事業 基盤研究(B)
    研究期間 : 2008年 -2011年 
    代表者 : 湊 真一, 有村 博紀, ツォイクマン トーマス, 喜田 拓也, 大久保 好章
     
    データベース分野では,当初はハードディスク内にデータを格納することが一般的だったが,2000年以降,中規模クラスの実用的なデータベースが計算機のメモリに納まるようになってきた.そこで本研究課題では,超大規模な単一実メモリ空間を持つ計算機に,二分決定グラフ(BDD)と呼ばれる巨大な圧縮データ構造を構築して,全てを高速アクセス可能なメモリ上に格納し,高速にデータベース解析処理を行う手法を提案し,その研究実用化を進めた.
  • 日本学術振興会：科学研究費助成事業 基盤研究(A)
    研究期間 : 2008年 -2011年 
    代表者 : 有村 博紀, 喜田 拓也, 湊 真一, 伊藤 公人, 宇野 毅明, 平田 耕一
     
    本研究では,ネットワーク上の大規模半構造データからの知識獲得のための超高速な半構造マイニングエンジン技術と,これを現実の多様な半構造データに適用するためのさまざまな周辺技術を開発した.さらに,開発した技術の計算機上への実装を行い,大規模半構造データからの知識発見実験を行った.
  • 日本学術振興会：科学研究費助成事業 特定領域研究
    研究期間 : 2009年 -2010年 
    代表者 : トーマス ツォイクマン, 湊 真一, 喜田 拓也, 下薗 真一, 高木 剛, 宇野 毅明, 有村 博紀
     
    本研究課題では,大規模知識処理のための超高速アルゴリズムの研究に取り組んでいる.本研究では,ウェブからの知識獲得を人間による大量のウェブ情報アクセスを支援する効率的な半自動的ツールとしてとらえ,従来の情報検索システムを超えた新しい情報アクセスシステムの開発を目指している.そのために,現在までに開発してきたウェブ情報処理技術を元に,中核技術として,機械学習と知識索引技術に基づく,適応的な知的情報獲得システムの基盤技術を開発することを目標としている. 特に本年度は,下記の課題に取り組み,各課題において多くの国際会議論文の採択を受けた. (1)自律・適応的な知識発見のための機械学習の研究.(ツォイクマン・湊) (2)超高速知識獲得アルゴリズムの研究.(ツォイクマン・宇野・有村) (3)ZDDに基づく大規模知識索引の研究.(湊・宇野・有村) (4)高速情報検索のためのデータ圧縮技術の研究.(喜田・有村・ツォイクマン) (5)開放分散環境における高度知識処理のためのプライバシー保護機構の研究.(高木・ツォイクマン) これら一連の知識発見に関する我々の仕事が国際的にも評価され,第25回計算機と情報科学に関する国際会議において,研究代表者であるツォイクマンを筆頭に,分担者である湊および有村らがそれぞれ招待講演者として招かれた.また,分担者の宇野毅明准教授が,文部科学大臣表彰若手科学者賞(業績名:巨大データ解析に対する超高速アルゴリズム構築法の研究)を受賞した.
  • 日本学術振興会：科学研究費助成事業 特別推進研究
    研究期間 : 2005年 -2007年 
    代表者 : 有村 博紀, 喜田 拓也, 湊 真一, 伊藤 公人
     
    本研究では,WWW(ウェブ)などの大規模半構造データからの知識基盤形成のための超高速半構造パターン発見技術とその周辺技術の研究開発を行う.本研究では,次の項目に関して研究開発を行った. (1)超高速半構造マイニングエンジンの研究として,変数付き系列モチーフや属性木等の有用かつ自明でない半構造データ族に対して,性能保障をもつ効率よいパターン発見アルゴリズムを開発した.これらの計算量を理論的に明らかにし,さらにこの枠組みを一般化することで,平面幾何グラフ,2次元画像パターン,伸張を許す極大系列パターン,近似アイテム集合等の半構造データ族に対して,効率よい多項式時間遅延・多項式領域アルゴリズムを開発した.統計的マイニングに関して,自然言語処理分野や,人獣共通感染症領域での遺伝子解析応用への応用を行った.(有村,伊藤,喜田). (2)知識基盤形成のための大規模知識索引技術として,ZBDD技術を用いた圧縮知識索引機構と,その上で対称パターンの発見や,飽和集合発見を行う高速アルゴリズムを開発し,様々な効率化技術を開発した(湊,有村). (3)半自動知識連係技術として,ビット並列手法に基づく多次元数値ストリームデータや,例からの学習を用いた情報抽出技術などネットワークからの情報抽出や高速半構造ストリーム処理に基づく効率よい情報収集技術を開発した.(伊藤,喜田,有村). (4)開発した知識発見・知識連携・知識索引技術に関して,これまでのアルゴリズム実装と,評価実験,理論的解析に基づき,知識発見ツールの集合として知識獲得プロトタイプシステムを構築し,適用実験を行った (湊・伊藤・喜田・有村).
  • 日本学術振興会：科学研究費助成事業 萌芽研究
    研究期間 : 2004年 -2005年 
    代表者 : 坂本 比呂志, 有村 博紀, 坂本 比呂志
     
    本研究では,半構造データに対する高速なXPath処理法を提案した.これまでに,データを効率的に圧縮する手法として知られている算術符号化を半構造データの検索に応用した,逆算術符号化が提案されている.これは,木構造データ上のパスの依存関係を,データを圧縮したまま復号化することなく検査できる手法であり,この関係性を利用することで,パスによる問い合わせを高速に処理できる.しかしながら,この問い合わせで利用可能なパスの形式は限定されているため,一般のXPathの問い合わせは処理が困難である.そこで本研究では,このような逆算術符号化にノード間の先祖子孫関係を判定可能な範囲ラベルを導入することにより,より複雑な問い合わせ処理を高速に実現するための手法を提案する.評価実験の結果,300MB程度のXMLデータに対してテキストを直接処理する既存の手法と比較し,数十から百倍の高速化を達成した.また,本研究では,畳み込みカーネルのアイディアに基づいた,ラベル付き順序木に対するこれまでにない新しいカーネル関数を提案した.まず,畳み込みカーネルの枠組みにおいてラベル付き順序木に対して任意の部分グラフを部分構造として用いた場合の,効率の良いカーネル計算のアルゴリズムを提案し,曖昧なラベルや構造を取り込むような拡張を行った.さらに,より一般的な木構造として,順序のないラベル付き根付き木に対するカーネルを考えた場合には,カーネルの計算が#P-完全問題であることを示した.
  • 日本学術振興会：科学研究費助成事業 特定領域研究
    研究期間 : 2004年 -2005年 
    代表者 : トーマス ツォイクマン, 有村 博紀, 坂本 比呂志, 篠原 歩, 下薗 真一, 湊 真一, 喜田 拓也, 竹田 正幸
     
    本研究は,大量のウェブページやXML等の大規模半構造データからのデータマイニング(ウェブマイニング)に基づき,大量のデータ解析を対話的に支援する効率的なツールとして,従来の情報検索システムを超えた新しい情報アクセスシステムの実現方式を明らかにすることを目標としている.その鍵になる技術として,最適パターン発見を木やグラフ構造に拡張し,計算量理論と計算学習理論の最新の成果を援用しながら,半構造データに対する頑健かつ高速な最適化パターン発見アルゴリズムの開発に取り組んだ. 平成17年度は,初年度から昨年度までの研究成果と統合し,最適半構造マイニングのプロトタイプシステム構築を目指した.研究項目としては,有用な情報源の発見,特徴的なパターンの発見,情報の抽出の3つの情報獲得問題に加えて,昨年度から新たに研究を開始した知識索引問題について取り組んだ.今年度得られた具体的な結果のうち主要なものは以下のとおりである. (1)大規模なトランザクションデータによく見られる疎な組み合わせ集合データを効率よく扱うことのできるデータ構造であるZBDD(Zero-suppress BDD)をベースに,その構造の元で重み付き積和集合を計算可能なZBDDパッケージツールVSOP(Valued Sum-Of-Products)の開発を推し進め,頻出するパターン集合を表現するZBDDを単純直交分解する機能を追加した.これにより,そのデータに内包された意味的構造を自動抽出することが可能になった.(湊) (2)パターン発見アルゴリズムによる分類・予測の長期的ふるまいに関する理論保証を与えることに成功した.(ツォイクマン) (3)系列データからの極大モチーフパターンを効率よく枚挙するアルゴリズムを得た.(有村:H13-H16代表) (4)Arc構造付きテキストに対する高速なパターン照合アルゴリズムを得た.(喜田)
  • 日本学術振興会：科学研究費助成事業 基盤研究(B)
    研究期間 : 2003年 -2005年 
    代表者 : 池田 大輔, 有村 博紀, 竹田 正幸, 篠原 歩, 喜田 拓也, 笠原 義晃, 石野 明
     
    ネットワーク上を時間的に変化しながら流れる大量半構造データストリームから有用な情報を効率よく獲得する超高速オンライン型データマイニング・システムの研究開発を行った.最終年度である平成17年度は,前年度までに研究開発した基礎理論の深化と,ネットワークデータへの応用の両面から,ストリーム指向パターン照合と半構造データマイニング,さらに,応用としてネットワーク不正侵入検出などの問題について,以下のように研究開発を行った.また,3年間の研究成果の発表・出版を行った. (1)半構造データストリームマイニングの調査と定式化:ネットワーク侵入検出やデータストリームマイニング等の実際のデータストリーム応用を解析し(池田・笠原・喜田),ストリームマイニングに関する最新の技術動向の調査を行った.また,昨年度までの調査結果を出版した(喜田・有村). (2)ストリーム指向半構造パターン照合技術の開発:データストリームを左から右へ一方向逐次走査に基づいた新しいストリーム検索技術について研究した.特に,XMLテキスト高速な木パターン照合処理技術と,シソーラアスやアノテーション等のメタデータを附加したストリームデータ検索技術を開発することに成功した(竹田・篠原・石野・喜田). (3)系列パターン発見に関して,長大な系列データを対象とした効率よいパターン発見アルゴリズムを開発した(篠原・竹田・有村).また,部分文字列の頻度に基づくパターン抽出手法について,そのパターン抽出性能と計算性能の改良を行った(池田・笠原・喜田).さらに,前年度に開発したワイルドカードをもつ極大パターンに対する高速パターンアルゴリズムに関する研究成果が出版された.また,昨年度の研究で開発した系列パターン発見アルゴリズムがH17年6月に,2004年人工知能学会研究会優秀賞を受賞した(篠原・竹田・有村).さらに,前年度までに,研究項目2と3で開発した半構造パターン照合技法とオンライン発見手法を元に開発した,ストリームデータに関する半構造データ族に対する高速半構造パターン発見アルゴリズムの研究成果の論文集への採択が決定した(有村・喜田). (4)応用研究として,現実の大規模高速ネットワークにおいて,実際に大量ネットワークデータに対するオンラインデータ収集と解析を行い,ネットワーク不正侵入検出に関する研究を行った(笠原・池田).
  • 日本学術振興会：科学研究費助成事業 特定領域研究
    研究期間 : 2001年 -2003年 
    代表者 : 有村 博紀, 篠原 歩, 竹田 正幸, 坂本 比呂志, 下薗 真一
     
    本研究では,大量のウェブページやXML等の大規模半構造データからのデータマイニング(ウェブマイニング)に基づき,大量のデータ解析を対話的に支援する効率的なツールとして,従来の情報検索システムを超えた新しい情報アクセスシステムの実現方式を明らかにすることを目標としている.鍵になる技術として,最適パターン発見を木やグラフ構造に拡張し,計算量理論と計算学習理論の最新の成果を援用しながら,半構造データに対する頑健かつ高速な最適化パターン発見アルゴリズムの開発に取り組んだ.平成15年度は,前年度の成果に基づき,(a)有用な情報源の発見,(b)特徴的なパターンの発見,(c)情報の抽出の3つの情報獲得問題について,次の研究を行った. (1)前年度開発した最適分類パターンを用いた高精度テキスト自動分類手法を一種の正規表現を扱えるよう一般化した.さらに,近似文字列照合を可能なパターン発見エンジンを開発し,加速学習法を用いて決定木学習システムBONSAIに組み込んだ(竹田・篠原). (2)XPathパターンに対する最適パターン発見アルゴリズムを設計し,半構造データマイニングエンジンを開発した.とくに今回は,より現実の半構造データに近い無順序木モデルに対して,高速なパターン発見エンジンを開発した.パターンの圧縮表現に対する,高速な列挙アルゴリズムを開発した.独自に開発したオンライン化技術を用いて,オンラインパターン発見手法を開発した(有村). (3)情報抽出に関して,現状の技術動向の調査を行い,水平方向制約(Sequence制約)付き半構造データに対するラッパー帰納アルゴリズムの設計を行った(坂本).さらに,半構造データに適した高性能圧縮アルゴリズムを開発し,性能に関する理論的解析を行った.並行して,開発したアルゴリズムの計算量を解析し(下薗,篠原),個々のアルゴリズムの最適化をおこない,性能を向上させた(全員).最後に,ウェブデータとXMLデータに関する評価実験をおこない,この方式の有効性を評価した(有村・篠原).
  • 最適パターン発見にもとづく高速テキストデータマイニングの研究
    科学技術事業団 (JST)：さきがけ研究21「情報と知」(領域代表者: 安西祐一郎)
    研究期間 : 1999年10月 -2002年03月 
    代表者 : 有村 博紀
  • 日本学術振興会：科学研究費助成事業
    研究期間 : 2002年 -2002年 
    代表者 : 有村 博紀, 下薗 真一, 篠原 歩, 竹田 正幸
     
    ネットワーク上に分散したウェブページやXML等の半構造データの急速な増大に対して,これらのコンテンツに直接アクセスするための効率良い手法の開発が緊急の課題となっている.本研究では,大規模半構造データからのデータマイニング(ウェブマイニング)に基づき,大量のデータ解析を対話的に支援する効率的なツールとして,従来の情報検索システムを超えた新しい情報アクセスシステムの開発を目指す. そのための鍵となる技術として,最適パターン発見を木やグラフ構造に拡張して,半構造データに対する頑健かつ高速な最適化パターン発見アルゴリズムを開発する.さらに,ウェブマイニングを(a)有用な情報源の発見,および(b)特徴的なパターンの発見,(c)情報抽出の3つの過程ととらえ,これらを有機的に結合して,半構造データを対象とした知識獲得システムの効率良い実現方式を明らかにすることを目標とする.また,計算量理論と計算学習理論の最新成果を援用し,計算量に徹底的に配慮した高速なアルゴリズムの開発を目指すのも特色である. 平成14年度は,次の研究成果を得た. (a)「有用な情報源の発見」に関しては,従来より表現力の高いパターンである可変長変数パターン(VLDCパターン)に対する新しいテキスト索引構造を開発し,これを用いて,効率よい最適化マイニングアルゴリズムを開発した. (b)「特徴的なパターンの発見」に関しては,XML-MessagingとSOAPへの応用を目指して,昨年開発した半構造データマイニング手法FREQTを元に,高速な半構造データストリームマイニングSTREAMTを開発した.これは,非常に少なく資源を使いながらデータストリームを監視し、有用なパターンを逐次報告するアルゴリズムである.また,FREQTの最適化マイニングへの拡張と理論的性能解析を行い,この方式の最適性を示した. (c)「情報抽出」に関しては,XMLデータ処理の基本技術である符号語列上のパターン照合機械技術を開発し,XMLパターン検索への応用を考察した.
  • 日本学術振興会：科学研究費助成事業
    研究期間 : 2001年 -2001年 
    代表者 : 有村 博紀, 篠原 歩, 竹田 正幸, 坂本 比呂志, 下薗 真一
     
    ネットワーク上に分散したウェブページやXML等の半構造データの急速な増大に対して,これらのコンテンツに直接アクセスするための効率良い手法の開発が緊急の課題となっている.本研究では,大規模半構造データからのデータマイニング(ウェブマイニング)に基づき,大量のデータ解析を対話的に支援する効率的なツールとして,従来の情報検索システムを超えた新しい情報アクセスシステムの開発を目指す. そのために,鍵となる技術として,最適パターン発見を木やグラフ構造に拡張して,半構造データに対する頑健かつ高速な最適化パターン発見アルゴリズムを開発する.さらに,ウェブマイニングを(a)有用な情報源の発見,および(b)特徴的なパターンの発見,(c)情報抽出の3つの過程からなると考え,これらを有機的に結合して,半構造データを対象とした知識獲得システムの効率良い実現方式を明らかにすることを目標とする,また,計算量理論と計算学習理論の最新の成果を援用して,計算量に徹底的に配慮した高速なアルゴリズムの開発を目指すことも特色である. 平成13年度は,次の研究成果を得た. (a)「有用な情報源の発見」に関しては,部分系列パターンとエピソードパターンと呼ぶ組合せパターンに対する効率よい最適化マイニングアルゴリズムを開発し,これを文字列分類のための決定木学習アルゴリズムBONSAIに組み込んだ. (b)「特徴的なパターンの発見」に関しては,半構造データを最も基本的なラベル付き順序木(labeled ordered trees)のクラスとしてモデル化し,データ中の頻出共通部分構造に対する高速な発見アルゴリズムを開発した.木に関するパターン発見問題は,一般に高い計算量をもつことが多い.そこで,最右枝拡張法という効率よい発見手法を与え,これを複数の最適化手法と組み合わせて,半構造データに対する高速なマイニングアルゴリズムを与えた. (c)「情報抽出」に関しては,ウェブからの情報抽出問題を考察し,HTMLデータから木構造の情報を利用して必要な情報を効率よく切り出すTree-Wrapperアルゴリズムを開発した.
  • 日本学術振興会：科学研究費助成事業 基盤研究(B)
    研究期間 : 1999年 -2001年 
    代表者 : 有村 博紀, 篠原 歩, 竹田 正幸, 正代 隆義, 平田 耕一, 石野 明
     
    本研究では,以下の三つの研究項目について研究を展開した. 1.半構造化文書からのデータマイニング方式.大量テキストからのテキストマイニング問題を考察し,これを情報検索の逆問題として定式化し,とくに,雑音の多い不完全なデータにおける頑健なパターン発見のために,統計的尺度を最適化するパターンを発見する最適パターン発見の枠組みを採用した.近接部分語パターンと呼ばれる単純なテキストパターンに対して,ランダムテキスト上できわめて高速にはたらく,最適パターン発見アルゴリズムを開発し,ウェブからのキーワード獲得問題や,対話的文書ブラウジングに適用した.さらに,ウェブやXMLデータなどの大規模半構造化文書を,「半構造化文書=テキスト+構造+属性データ」ととらえて,テキストマイニングの枠組みを木やグラフ構造に拡張した. 2.大量テキストデータに対する高速パターン照合方式.現実の大規模テキストデータベースシステムでは,大量のテキストデータを格納するため,テキストを圧縮して扱うことが多い.そのため,圧縮データ上のパターン照合アルゴリズムに力点をおいて研究した.これは,圧縮されたデータを陽に展開することなくパターン照合を行おうとするものである.本アプローチの独創的な点は,単にデータを圧縮することで記憶領域を削減するだけでなく,さらに,圧縮することでパターン照合そのものを高速化させるという狙いをもつことである.本研究では,一連の研究を通じて,一番目の目標だけでなく,二番目の目標も達成できることを実証した.さらに,既存のさまざまな圧縮方式に対して,その圧縮方式に適した圧縮照合アルゴリズムを開発すると同時に,より高い見地から多様な圧縮照合アルゴリズムを統一的にとらえる枠組みを提案することに成功した. 3.機械学習に基づくデータマイニング方式.一連の半構造化文書からの情報抽出問題を理論的に定式化し,与えられたデータからパターンを発見する問題の学習可能性と限界を理論的に明らかにした.次に,Tree Wrapperや生垣とよばれる木と文字列の双方の性質をもつ木構造パターンに対して,半構造化文書からの情報抽出のための効率よい情報抽出アルゴリズムを開発した.さらに,実際のウェブデータを対象として,さまざまなタイプの半構造化文書から,利用者が必要とする情報を獲得するという情報獲得実験を行い,その有効性を検証した.
  • 日本学術振興会：科学研究費助成事業 奨励研究(A)
    研究期間 : 1999年 -2000年 
    代表者 : 有村 博紀
     
    本研究の目的は,大規模知識データベースから,複雑な知識構造を効率よく獲得するシステムの実現方法を明らかにすることである.大規模知識データベースは,(i)大量の(ii)非均質なデータを含み,同時に(iii)その多くは正例だけを含むので,従来の知識獲得手法は適用できない.そこで,本研究では,このような大規模知識データベースに適用可能な新しい学習手法について研究をおこなった. 本年度は,以下の項目について研究を実施した. (1)前年度に開発した一般的な知識獲得手法を,ネットワーク上の半構造データからの知識獲得に応用した.具体的には,ネットワーク上でのデータ交換および記述言語として急速に利用が進んでいるXMLデータを対象とし,与えられたXMLデータから,対話によって,データ変換規則を効率良く発見するアルゴリズムを開発する.(ICGI 2000;人工知能学会誌Vol.16,No.2) (2)さらに(1)項の半構造データからのパターン発見アルゴリズムを,前年度に開発したテキストデータからのパターン発見手法と融合し,構造と内容の両方を利用した知識獲得手法を開発した.さらに,この手法の時間計算量と質問計算量を理論的に解析した.(PAKDD 2000;RECOMB 2000;ビット別冊) (3)開発した知識獲得手法の有効性を計算機実験を通じて評価する.開発中の知識獲得システムを,本研究で得たパターン発見手続きの導入によって拡張した.さらに,ネットワーク上に分散したウェブページからの知識獲得実験をおこなった.(Kyoto ICDL2000;人工知能学会誌Vol.15,No.4)
  • 日本学術振興会：科学研究費助成事業 特定領域研究(A)
    研究期間 : 1998年 -2000年 
    代表者 : 佐藤 泰介, 原口 誠, 今井 むつみ, 有村 博紀, 佐藤 優子, 篠原 武, 古川 康一
     
    H10年度からH12年度まで「推論による知識発見」という表題の下にデータの観測から知識発見へ至る様々な推論機構の研究・開発を行なった。一般に推論の形態は演繹推論、帰納推論、アブダクション(発想推論)に分類されるが、特に知識発見に深く関わる推論としてアブダクションと帰納推論に着目し、「統計的アブダクション」、「ILPによる知識発見」、「帰納推論」の3つのサブグループを設定し、幅広く研究を進めた。 「統計的アブダクション」では、佐藤(泰)が統計的学習機構と論理型言語を融合させた記号的統計モデリング言語PRISMの開発し、月本は観測事象の線形回帰式をブール関数で近似する事により、事象背後の論理的関係を取り出す方法を提案した。 一方、有村らはウェブマイニングやXMLなどの半構造データからの情報抽出に適したアルゴリズムを開発した。 「ILPによる知識発見」では、古川、今井らが理論的研究を進め、またILPにもとづいた幼児の名詞語彙獲得のモデルを開発した。 山本は節論理にもとづく発見の論理を構成し、ILPとの関連を探求した。 原口は複雑なデータの可読性を高めるデータベース抽象化の技法を開発しデータマイニングに応用した。 「帰納推論」では佐藤(優)らは、汚染データの扱いについて、形式言語に位相の近傍の概念を採り入れた極限同定の枠組を提案した。 篠原は記号的データや記号的推論の基礎となる実数データ、特に多次元ベクトルデータに対する空間検索の技法の開発を進めた。 一方、大澤はKeyGraph開発し、地震などの予兆発見に適用した。
  • 日本学術振興会：科学研究費助成事業 奨励研究(A)
    研究期間 : 1997年 -1998年 
    代表者 : 有村 博紀
     
    本研究では,構造化データからの対話的な知識獲得について,基礎的な研究をおこなった[1,3].まず,オブジェクト指向データベース等の複合オブジェクト(complex object)の単純なモデルとして,述語論理の一階項(first-order term)を考えた.さらに,能動的学習(active learning)の枠組みのもとで,さまざまな構造化パタン族に対して,効率的なパタン発見手法の開発と,発見問題の本質的複雑さの探求をおこない,次の結果を得た[1,3,2]. 1. 2個の一階項からなる簡単なパタンでさえ,効率よい学習が困難なことを示した.その一方で,所属性質問を用いて実験をおこなうことで,この種のパタンが効率よく多項式時間で同定できることを示した. 2. 上記の結果を2個以上の一階項からなるパタンに拡張して,所属性質問を用いた効率よい学習アルゴリズムを与えた.このアルゴリズムは構造化データの学習における基本的機構を確立するもので,所属性質問を用いるさまざまな学習モデルに適用可能である. 3. ACH(k)(acyclic constrained Horn programs of bounded arity k)と呼ばれる一階ホーン論理式の族(再帰論理プログラムの一種)が,含意に基づく学習(能動学習の一種)の枠組みで多項式時間学習可能であることを示した[1].さらに,質問計算量に関する下限定理と学習困難性を示して,一般的な一階ホーン論理式の学習には,質問の利用が不可欠なことを明らかにした. 以上の結果は,構造化データからの知識獲得の本質的難しさを明らかにするものである.同時に,対話による知識ベース構築のための基本的方法論を与えるものである.
  • 日本学術振興会：科学研究費助成事業 重点領域研究
    研究期間 : 1997年 -1997年 
    代表者 : 有村 博紀, 正代 隆義, 有川 節夫
     
    データマイニング(Data Mining)は,データベースからの知識発見とも呼ばれ,現在,ビジネス分野や科学技術分野等,さまざまな対象領域で,その適用が盛んにおこなわれている.しかし,現在のデータマイニングの対象は関係データベースが中心であり,現在急速に利用が進みつつあるテキストデータベースやオブジェクト指向データベースに関しては,明示的な構造をもたない,あるいは非均質な構造しかもたない,膨大なデータの集積であるなどの理由から,従来の手法をそのまま適用することができないため,ほとんど研究がおこなわれていない. そこで本研究では,ここにあげたような非構造的データや構造データからのデータマイニングについて研究した.平成9年度は,具体的にはつぎの問題に中心に研究した. 1.高速パターン発見アルゴリズムの研究:近年発展著しいテキストデータベースを対象に,高速なパターン発見アルゴリズムを開発した.とくに,単純なパタンに仮説を制限する代わりに,誤差や欠落を含む不完全データにたいしても働くような,頑健かつ高速な手法を開発することができた.また,確率的サンプリングを用いた高速化や効率的な探索の枝刈り法についても成果を得た. 2.属性効率のよいパタン発見アルゴリズム:テキストデータベースにおいては,属性に対応する部分列や語彙の数は膨大になる.本項では,1変数パタンと呼ばれる単純な規則を対象に,発見に必要な具体例が,発見対象に関連しない属性数にはほとんど依存しないような,「属性効率がよい」パタン発見アルゴリズムを開発し,この族が多項式オンライン学習可能であることを示した. 3.構造化データからの対話を用いた知識獲得:本項では,構造化データからの対話的な知識獲得について基礎的な研究をおこなった.関係データベースではさまざまな演繹質問や統合性制約が一階ホーン論理式として表される.主結果として,一階ホーン論理式の部分族ACH(k)に対する多項式時間学習アルゴリズムを与え,さらに,これが質問計算量に関してほぼ最適であることを示した. 他にも,テキストデータベース用の質問言語の計算量と表現力を調べ,完全に特徴づけた.また,本年度に1項のテキストデータマイニング・システムの小規模プロトタイプを試験的に実装し,問題点の洗い出しをした.次年度は,これに基づいて効果的な実装法を研究し,分子生物学のデータを対象として大規模な知識獲得実験をおこないたい.
  • 日本学術振興会：科学研究費助成事業 基盤研究(A)
    研究期間 : 1995年 -1997年 
    代表者 : 篠原 武, 深町 修一, 下薗 真一, 石坂 裕毅, 杉本 典子, 有村 博紀
     
    本研究の目的は、情報圧縮による逐次パターン照合処理の高速化技法を確立するとともに、そのテキストデータベースにおける有効性を実証することにある. 逐次処理の遅さの主な原因として,データの転送コストが考えられる.このコストを軽減するためには,情報圧縮の技術を用い,圧縮したデータを復号することなく探索する手法が有効である. 本研究では,テキストデータの標本として, ●遺伝子情報データ ●図書館データ ●英文テキストデータ の3種のものを取り扱うこととしている.平成9年度の研究では,主として英文テキストデータを対象にして,平成7年度および平成9年度に設計したアルゴリズムをさらに改良するための研究を行った.並列化による高速化パターン照合およびBPE符号による圧縮技法に関する研究の結果,つぎのことがわかった. 並列化によるパターン照合の高速化は,テキストを分割し,それぞれを並列に処理することで達成できるが,その際,分割したテキストを個々のプロセッサに配送するコストをできるだけ小さくすることが重要となる.このコストを小さくするために情報圧縮を用いればよいのであるが,ハフマン符号のような可変長符号を用いている場合には,テキストを分割するために,テキストを走査する必要が生じ,この走査は並列化できないという問題がある.BPE符号においては,固定長符号を用いるので,こうした問題を生ずることはなく,また英文テキストであれば,50%程度の高い圧縮率を達成できる.
  • 日本学術振興会：科学研究費助成事業 奨励研究(A)
    研究期間 : 1996年 -1996年 
    代表者 : 有村 博紀
     
    本研究の目的は,CADデータベースやマルチメディアデータベースのように,大量の非均質なデータを含み,同時に,主に正例だけを含むようなデータベースに対しても適用可能な,新しい学習手法を開発することである。具体的な学習手法としては,申請者らが開発した「極小多重汎化」手法を採用し,大規模科学データベースを対象として,高速な極小多重汎化手続きを開発することを目指して研究をおこなった. 具体的には,極小多重汎化をデータベースを対象に拡張し,高速な学習手続きを開発した. 1.まず,データの理論的モデルの基盤として,関係データベースをとりあげ,知識表現の立場からこれを概念階層の導入によって拡張した.こうして拡張されたデータベースを対象として,高速な極小多重汎化手続きを開発することに成功した.この手法の能力と適用限界を理論的に調べた. 2.さらにこの汎化手続きを計算機上に実装し,その有用性をデータベースからの知識獲得に関する計算機実験を通じて確認した.この際,確率的選択を含む数種の経験的発見法を導入により,実際的な効率の向上をはかった. 3.近年のマルチメディア等の高度データベースの急激な発展に対処するため,上で開発した拡張データベースにテキストデータかたの知識獲得手続きを組み込むための基礎的研究をおこなった.文字列パターンとよばれる表現をとりあげ,パターンへの概念階層の組み込みと高速汎化アルゴリズムの開発をおこなった. 4.また,複数概念の個数にあらかじめ上限を与えない場合の学習可能性について理論的考察をおこない,正例からの学習の可能性と上限を明らかにした. 5.背景知識を許した関係記述言語である基本形式体系の計算量についても考察した.
  • 日本学術振興会：科学研究費助成事業 奨励研究(A)
    研究期間 : 1995年 -1995年 
    代表者 : 有村 博紀
     
    本研究では,大規模オブジェクト指向データベースを対象とした知識獲得システムの実現方法をあきらかにすることを目的として,研究をおこなった.このために申請者が提案した学習手法である極小多重汎化を,データベースを対象に拡張し,高速な学習手続きを開発した.具体的には,つぎの研究をおこなった. (1)オブジェクト指向データベースにおける概念継承と背景知識を統一的にあつかうために,背景知識として論理プロブラムが与えられた場合に,与えられデータベースの極小汎化を求める問題を考察し,高速な汎化手続きを開発した.さらに,この汎化手続きによって,制限された述語論理プログラムのクラスが,正例だけから多項式時間極限可能であることを示した. (2)計算量理論の立場から,最も単純な体系である原子式の極小多重汎化問題を考察し,未知仮説の正確な同定に必要な時間計算量と質問情報量を理論的に明らかにした.これにより,正確な同定を高速におこなうには,知識獲得システム自身が決定実験をおこない,必要な例を動的に得る仕組みが必要なことがわかった. (3)開発中の知識獲得システムを,本研究で得た汎化手続きの導入によって拡張し,遺伝子配列と蛋白質に関するオブジェクト指向データベースを対象として知識獲得実験をおこなった.この計算機実験によって,開発した汎化手続きの実際のデータベースにおける有効性を検証した.
  • 日本学術振興会：科学研究費助成事業
    研究期間 : 1993年 -1993年 
    代表者 : 竹内 章, 有村 博紀
     
    発見的な学習を支援する知的教育システムに関する研究を行った。本研究では、発見的学習とAIとの関係から、2つの立場より研究を行った。一つは、知的教授システムを実験台にして、知識処理の特徴を体験を通して学習させる方法に関する研究、今一つは発見学習の支援方法に関する研究である。 前者は、知的教授システムの特徴的機能が知識処理によって初めて可能となることから、知識処理を学ぶよい教材となるのを利用して、実験によって知識処理の深い理解を得させるための環境に関する研究である。ここでは学習環境の構成方法と、計算機によってシミュレートされた疑似学習者の役割について提案を行った。 後者は、システムが学習者の振る舞いを認識して、学習者の意図に対して適応的な発見支援をめざす。このとき問題になるのは、学習者の意図を推定する方法と支援の方法である。我々は、学習者がすでに獲得済みの背景知識を用いながら、実験環境での試行錯誤を通して新しい概念を獲得するとの考えにたって、学習者とシステムが実験環境を共有し、協調作業を行う学習支援システムのアーキテクチャと、そこでの支援方法を提案した。ここでは発見のプロセスを、実験装置とデータの整理・加工のための道具の状態で表現される状態空間中での、それぞれの部品で定義されているオペレータの適用による移動としてモデル化した。この状態空間は、実験によるデータ収集を行う操作空間と、実験データをもとに仮説を生成する仮説空間に分けられる。また、システムが与えられた環境から規則を発見するため、そして学習者の指導のために用いる発見の戦略を、個々の環境に依存したもの、一つの領域に共通なもの、全体に共通なものの3レベルに分け記述した。
  • 日本学術振興会：科学研究費助成事業
    研究期間 : 1992年 -1992年 
    代表者 : 竹内 章, 有村 博紀
     
    マイクロワールドに代表される発見的学習環境と、知的教授システムに代表される問題解決中心の学習環境を統合した、Bimodus CAIと呼ぶ新しい教育環境を提案し、特に、発見学習の支援方法を中心に研究した。 Bimodus CAIにおける発見学習環境は、現実世界のモデルを計算機上に実現したダイレクト・マニピュレーション環境である。学習者はモデルを操作し、反応を観察しながら、モデルに埋め込まれた概念を獲得する。この過程で学習者は実験環境から情報を集め、整理し、自分の持っている背景知識を用いて仮説を立て、実験結果を解釈し、加工しながら、試行錯誤を繰り返す。 学習者が新しい概念を発見するには、それを導くための前提知識を持っていることが必要であるが、この条件のもので、学習者に対する支援は、次の二つの目的を満たすシステムの振舞いであると考える。 1)学習者の行う思考の領域を、背景知識全体から関連のある知識領域へ、さらに目標概念の発見に必要な前提知識領域へと、次第に縮小する。 2)前提知識の領域において、正しい知識を導出できるような実験環境を提示する。 学習者支援には学習者モデルが必要で、これは、システムに学習者と同じように実験環境から新しい概念を発見する機能をもたせ、学習者のふるまいをモニタして構築する。この機構は、内部実験装置、機械学習プログラム、背景知識から構成される。機械学習プログラムは、背景知識と内部実験装置から得られる情報を基に目標概念を獲得する。内部実験装置は学習者が行うのと同じ操作が可能で、学習者が収集するのと同じ情報が機械学習プログラムに与えられる。内部実験装置と学習者が操作する実験装置は表裏一体の関係にあり、学習者の操作をモニターしたり、システムが実験装置を操作してその結果を学習者に示したりする。

教育活動情報

主要な担当授業

  • 情報知識ネットワーク特論
    開講年度 : 2021年
    課程区分 : 修士課程
    開講学部 : 情報科学研究科
    キーワード : 大規模データ（ビッグデータ）処理アルゴリズム，離散アルゴリズム，データマイニング，情報検索，半構造データ，グラフ，木，系列処理，列挙，照合，最適化
  • 情報知識ネットワーク特論
    開講年度 : 2021年
    課程区分 : 修士課程
    開講学部 : 情報科学院
    キーワード : 大規模データ（ビッグデータ）処理アルゴリズム，離散アルゴリズム，データマイニング，情報検索，半構造データ，グラフ，木，系列処理，列挙，照合，最適化
  • Introduction to Artificial Intelligence, Big Data, and Cybersecurity for Graduate Students
    開講年度 : 2021年
    課程区分 : 修士課程
    開講学部 : 情報科学院
    キーワード : artificial intelligence, big data, cryptography, information retrieval, machine learning
  • 情報知識ネットワーク特論
    開講年度 : 2021年
    課程区分 : 博士後期課程
    開講学部 : 情報科学研究科
    キーワード : 大規模データ（ビッグデータ）処理アルゴリズム，離散アルゴリズム，データマイニング，情報検索，半構造データ，グラフ，木，系列処理，列挙，照合，最適化
  • 情報知識ネットワーク特論
    開講年度 : 2021年
    課程区分 : 博士後期課程
    開講学部 : 情報科学院
    キーワード : 大規模データ（ビッグデータ）処理アルゴリズム，離散アルゴリズム，データマイニング，情報検索，半構造データ，グラフ，木，系列処理，列挙，照合，最適化
  • Introduction to Artificial Intelligence, Big Data, and Cybersecurity for Graduate Students
    開講年度 : 2021年
    課程区分 : 博士後期課程
    開講学部 : 情報科学院
    キーワード : artificial intelligence, big data, cryptography, information retrieval, machine learning
  • 情報理論
    開講年度 : 2021年
    課程区分 : 学士課程
    開講学部 : 工学部
    キーワード : 情報量、エントロピー、情報源、通信路、符号化、データ圧縮
  • アルゴリズムとデータ構造
    開講年度 : 2021年
    課程区分 : 学士課程
    開講学部 : 工学部
    キーワード : 計算量，ソート，探索，グラフ，文字列照合
  • プログラム理論と言語
    開講年度 : 2021年
    課程区分 : 学士課程
    開講学部 : 工学部
    キーワード : プログラミング、プログラム言語、プログラム意味論，構文と意味
  • 情報理工学実験Ⅰ
    開講年度 : 2021年
    課程区分 : 学士課程
    開講学部 : 工学部
    キーワード : プログラミング、計算機システム、データ解析技法
  • 情報理工学演習Ⅲ
    開講年度 : 2021年
    課程区分 : 学士課程
    開講学部 : 工学部
    キーワード : データ構造，アルゴリズム，ソート，再帰，線形代数, 音声音響信号処理，画像信号処理，画像認識，コンピュータグラフィクス

大学運営

学内役職歴

  • 2013年4月1日 - 2015年3月31日 知識メディア・ラボラトリー長

委員歴

  • 2023年10月 - 現在   日本学術会議   会員 (第三部会情報学委員会)
  • 2020年10月 - 2023年09月   日本学術会議   連携会員 (第三部会情報学委員会)
  • 2018年04月 - 2020年03月   日本学術振興会   先端科学シンポジウム事業委員会委員 (Frontiers of Science Symposia)
  • 2017年06月 - 2019年05月   人工知能学会   代議員
  • 2017年06月 - 2019年03月   文部科学省   科学技術・学術審議会専門委員（情報科学技術委員会委員）
  • 2011年04月 - 2018年03月   日本学術振興会   先端科学シンポジウム専門委員(Frontiers of Science Symposia)
  • 2015年06月 - 2016年05月   人工知能学会   2016年度全国大会 プログラム委員長
  • 2014年06月 - 2016年05月   人工知能学会   理事
  • 2008年05月 - 2014年04月   電子情報通信学会コンピュテーション研究専門委員会   専門委員
  • 2008年 - 2014年   JSTさきがけ「知の創生と情報社会」,領域（領域統括:中島秀之)   アドバイザー
  • 2007年 - 2013年09月   発見科学国際会議(International Conference on Discovery Science)   運営委員会委員(Steering committee member, International Conference on Discovery Science)
  • 2006年05月 - 2008年04月   電子情報通信学会コンピュテーション研究専門委員会   副委員長   電子情報通信学会コンピュテーション研究会
  • 2006年04月 - 2008年03月   人工知能学会 人工知能基礎問題研究会   主査
  • 2008年 - 2008年   日本学術振興会先端科学シンポジウム   PGM (UJFoS2008)   Frontiers of Science Symposia, Planning Group Member.
  • 2006年 - 2007年   JST CRDS 科学技術未来戦略ワークショップ「予測と発見」   分科会Bリーダー
  • 2006年 - 2007年   人工知能学会   人工知能基礎問題研究会主査(H18-H19)   人工知能学会
  • 2006年 - 2006年   1st Int'l Workshop on Data Mining and Statistical Science (DMSS-2006), Sapporo   Chair
  • 2004年 - 2006年   人工知能学会   評議員（Ｈ16－Ｈ17）   人工知能学会
  • 2004年 - 2006年   情報処理学会   データベース研究会研究運営委員   情報処理学会
  • 2004年 - 2006年   人工知能学会人工知能基礎問題研究会   幹事   人工知能学会人工知能基礎問題研究会
  • 2003年 - 2005年   日本学術振興会先端科学シンポジウム   PGM (JGFoS'04, JGFoS'05)
  • 1999年 - 2000年   the 11th International Conference on Algorithmic Learning Theory (ALT'00, Sydney)   PC co-chair

社会貢献活動

  • 公開講座（一部は道民カレッジと連携）
    期間 : 2009年09月 - 2011年11月
    役割 : 講師
    主催者・発行元 : 北海道大学 大学院情報科学研究科
    イベント・番組・新聞雑誌名 : COE公開講座「くらしの中の情報科学」ー ネットワークからナノテク・ゲノムまで ー

メディア報道

  • 望む結果までの手順を導くことができる「説明可能な AI」を 世界で初めて開発 ー 人と協働する AI の信頼性と透明性の向上を実現 ー
    報道 : 2021年02月04日
    発行元・放送局 : 北海道大学 / 富士通
    北海道大学，プレスリリース：https://www.global.hokudai.ac.jp/blog/fujitsu-and-hokkaido-university-develop-explainable-ai-technology-providing-users-with-concrete-steps-to-achieve-desired-outcomes/　その他
  • 富士通研究所と北大、望む結果を得るための手順を導くことができるAIを開発
    報道 : 2021年02月04日
    執筆者 : 本人以外
    番組・新聞雑誌 : 日本経済新聞
    日経新聞: https://www.nikkei.com/article/DGXLRSP604512_U1A200C2000000/　新聞・雑誌

Copyright © MEDIA FUSION Co.,Ltd. All rights reserved.