東北大学研究者紹介

研究者詳細

ホーム

日本語 English

シノハラ　アユミ

篠原　歩

Ayumi Shinohara

所属

大学院情報科学研究科　システム情報科学専攻　知能情報科学講座（知能システム科学分野）

職名

教授

学位

博士（理学）九州大学

researchmap

https://researchmap.jp/read0121310

J-GLOBAL ID

200901055094177640

経歴 5

2005年3月～継続中

東北大学大学院情報科学研究科　教授
2000年4月～ 2005年2月

九州大学大学院システム情報科学研究院　助教授
1996年4月～ 2000年3月

九州大学大学院システム情報科学研究科　助教授
1994年10月～ 1996年3月

九州大学理学部　助教授
1990年4月～ 1994年9月

九州大学理学部　助手

学歴 2

九州大学　総合理工学研究科　情報システム学専攻

1988年4月～ 1990年3月
九州大学　理学部　数学科

1984年4月～ 1988年3月

委員歴 34

Member of Program Commitee of CPM2017　Program Commitee

2017年1月～ 2017年7月
国際会議CPM2017 プログラム委員　プログラム委員

2017年1月～ 2017年7月
Member of Program Commitee of LATA2015　Program Commitee

2014年10月～ 2015年3月
国際会議LATA2015 プログラム委員　プログラム委員

2014年10月～ 2015年3月
Member of Program Commitee of LATA2011　Program Commitee

2010年10月～ 2011年3月
国際会議LATA2011 プログラム委員　プログラム委員

2010年10月～ 2011年3月
電子情報通信学会コンピュテーション研究専門委員会　委員

2003年4月～ 2009年5月
電子情報通信学会コンピュテーション研究専門委員会　委員

2003年4月～ 2009年5月
The 10th International Conference on Discovery Science　Conference Chair

2006年11月～ 2007年10月
The 10th International Conference on Discovery Science　Conference Chair

2006年11月～ 2007年10月
Member of Program Commitee of CPM2006　プログラム委員

2006年1月～ 2006年7月
国際会議CPM2006 プログラム委員　プログラム委員

2006年1月～ 2006年7月
Member of Program Commitee of SPIRE2005　プログラム委員

2005年4月～ 2005年10月
国際会議SPIRE2005 プログラム委員　プログラム委員

2005年4月～ 2005年10月
Member of Program Commitee of ALT2004　プログラム委員

2004年4月～ 2004年11月
国際会議ALT2004 プログラム委員　プログラム委員

2004年4月～ 2004年11月
Member of Program Commitee of SPIRE2004　プログラム委員

2004年4月～ 2004年10月
国際会議SPIRE2004 プログラム委員　プログラム委員

2004年4月～ 2004年10月
Member of Program Commitee of SPIRE2003　プログラム委員

2003年4月～ 2003年10月
国際会議SPIRE2003 プログラム委員　プログラム委員

2003年4月～ 2003年10月
Member of Program Commitee of CPM2003　プログラム委員

2003年1月～ 2003年7月
国際会議CPM2003 プログラム委員　プログラム委員

2003年1月～ 2003年7月
Member of Program Commitee of DS2002　プログラム委員

2002年4月～ 2002年11月
国際会議DS2002 プログラム委員　プログラム委員

2002年4月～ 2002年11月
Member of Program Commitee of SPIRE2002　プログラム委員

2002年4月～ 2002年10月
国際会議SPIRE2002 プログラム委員　プログラム委員

2002年4月～ 2002年10月
Co-chair of Program Commitee of DS2001　プログラム委員

2001年4月～ 2001年11月
国際会議DS2001 プログラム副委員長　プログラム委員

2001年4月～ 2001年11月
Member of Program Commitee of DS2000　プログラム委員

2000年4月～ 2000年11月
国際会議DS2000 プログラム委員　プログラム委員

2000年4月～ 2000年11月
Member of Program Commitee of ALT'99　プログラム委員

1999年4月～ 1999年11月
国際会議ALT'99 プログラム委員　プログラム委員

1999年4月～ 1999年11月
Member of Program Commitee of ALT'97　プログラム委員

1997年4月～ 1997年11月
国際会議ALT'97 プログラム委員　プログラム委員

1997年4月～ 1997年11月

︎全件表示 ︎最初の5件までを表示

所属学協会 3

日本ソフトウエア科学会
人工知能学会
情報処理学会

研究キーワード 3

人工知能
機械学習
文字列処理アルゴリズム

研究分野 2

情報通信 / 知能情報学 /
情報通信 / 情報学基礎論 /

受賞 3

2006年度ロボカップ研究賞

2007年3月31日　日本ロボカップ委員会
日本ロボット学会最優秀賞

2004年5月　日本ロボット学会　ロボカップジャパンオープン2004 大阪４足ロボットリーグ
情報処理学会創立４０周年記念論文賞

2001年10月　情報処理学会

論文 244

Query Learning of Context-Deterministic and Congruential Context-Free Languages over Infinite Alphabets.

Yutaro Numaya, Yoshito Kawasaki, Ryo Yoshinaka, Ayumi Shinohara

SOFSEM (2)　211-224　2025年

DOI： 10.1007/978-3-031-82697-9_16 　
Serial and parallel algorithms for order-preserving pattern matching based on the duel-and-sweep paradigm

Davaajav Jargalsaikhan, Diptarama Hendrian, Yohei Ueki, Ryo Yoshinaka, Ayumi Shinohara

Acta Informatica　2024年8月31日
出版者・発行元： Springer Science and Business Media LLC
DOI： 10.1007/s00236-024-00464-w 　

ISSN：0001-5903

eISSN：1432-0525
Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching 査読有り

Kento Iseri, Tomohiro I, Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka, Ayumi Shinohara

Proceedings of the 51st International Colloquium on Automata, Languages and Programming (ICALP 2024)　89:1-89:19　2024年7月

DOI： 10.4230/LIPIcs.ICALP.2024.89 　
Algorithms for Galois Words: Detection, Factorization, and Rotation 査読有り

Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka, Ayumi Shinohara

Proceedings of the 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)　18:1-18:16　2024年6月

DOI： 10.4230/LIPIcs.CPM.2024.18 　
Query Learning of Minimal Deterministic Symbolic Finite Automata Separating Regular Languages

Yoshito Kawasaki, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

Lecture Notes in Computer Science　340-354　2024年2月7日
出版者・発行元： Springer Nature Switzerland
DOI： 10.1007/978-3-031-52113-3_24 　

ISSN：0302-9743

eISSN：1611-3349
Efficient Parameterized Pattern Matching in Sublinear Space

Haruki Ideguchi, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

String Processing and Information Retrieval　271-283　2023年9月20日
出版者・発行元： Springer Nature Switzerland
DOI： 10.1007/978-3-031-43980-3_22 　

ISSN：0302-9743

eISSN：1611-3349
Inferring Strings from Position Heaps in Linear Time

Koshiro Kumagai, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

WALCOM: Algorithms and Computation　115-126　2023年3月13日
出版者・発行元： Springer Nature Switzerland
DOI： 10.1007/978-3-031-27051-2_11 　

ISSN：0302-9743

eISSN：1611-3349
Identification of Substitutable Context-Free Languages over Infinite Alphabets from Positive Data.

Yutaro Numaya, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

International Conference on Grammatical Inference(ICGI)　23-34　2023年
出版者・発行元： PMLR
Parameterized DAWGs: Efficient constructions and bidirectional pattern searches

Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian, Yuto Nakashima, Ryo Yoshinaka, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Masayuki Takeda

Theoretical Computer Science　933　21-42　2022年10月
出版者・発行元： Elsevier BV
DOI： 10.1016/j.tcs.2022.09.008 　

ISSN：0304-3975
Parallel Algorithm for Pattern Matching Problems Under Substring Consistent Equivalence Relations 査読有り

Davaajav Jargalsaikhan, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

Proceedings of the 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)　28:1-28:21　2022年6月

DOI： 10.4230/LIPIcs.CPM.2022.28 　
Computing the Parameterized Burrows–Wheeler Transform Online

Daiki Hashimoto, Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka, Ayumi Shinohara

String Processing and Information Retrieval　70-85　2022年
出版者・発行元： Springer International Publishing
DOI： 10.1007/978-3-031-20643-6_6 　

ISSN：0302-9743

eISSN：1611-3349
Inside-Outside Algorithm for Macro Grammars.

Ryuta Kambe, Naoki Kobayashi 0001, Ryosuke Sato 0001, Ayumi Shinohara, Ryo Yoshinaka

Proceedings of the 15th International Conference on Grammatical Inference(ICGI)　32-46　2021年
出版者・発行元： PMLR
Fast and Linear-Time String Matching Algorithms Based on the Distances of q-Gram Occurrences

Satoshi Kobayashi, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

Leibniz International Proceedings in Informatics, LIPIcs　160　2020年6月1日
出版者・発行元： Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
DOI： 10.4230/LIPIcs.SEA.2020.13 　

ISSN：1868-8969
Linear-Time Online Algorithm for Inferring the Shortest Path Graph from a Walk 査読有り

Shintaro Narisada, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

Theoretical Computer Science　812　187-202　2020年4月

DOI： 10.1016/j.tcs.2019.10.029 　
Grammar compression with probabilistic context-free grammar

Hiroaki Naganuma, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara, Naoki Kobayashi

Data Compression Conference Proceedings　2020-　386　2020年3月1日
出版者・発行元： Institute of Electrical and Electronics Engineers Inc.
DOI： 10.1109/DCC47342.2020.00093 　

ISSN：1068-0314
AOBA: An Online Benchmark tool for Algorithms in stringology

Ryu Wakimoto, Satoshi Kobayashi, Yuki Igarashi, Davaajav Jargalsaikhan, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

CEUR Workshop Proceedings　2568　1-12　2020年
出版者・発行元： CEUR-WS
ISSN：1613-0073
An extension of linear-size suffix tries for parameterized strings

Katsuhito Nakashima, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

CEUR Workshop Proceedings　2568　97-108　2020年
出版者・発行元： CEUR-WS
ISSN：1613-0073
Parallel duel-and-sweep algorithm for the order-preserving pattern matching 査読有り

Davaajav Jargalsaikhan, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

The 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2020)　211-222　2020年1月

DOI： 10.1007/978-3-030-38919-2_18 　
DAWGs for Parameterized Matching: Online Construction and Related Indexing Structures.

Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian, Yuto Nakashima, Ryo Yoshinaka, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Masayuki Takeda

31st Annual Symposium on Combinatorial Pattern Matching(CPM)　26-14　2020年
出版者・発行元： Schloss Dagstuhl - Leibniz-Zentrum für Informatik
DOI： 10.4230/LIPIcs.CPM.2020.26 　
Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences.

Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Ayumi Shinohara

31st Annual Symposium on Combinatorial Pattern Matching(CPM)　12-11　2020年
出版者・発行元： Schloss Dagstuhl - Leibniz-Zentrum für Informatik
DOI： 10.4230/LIPIcs.CPM.2020.12 　
Efficient computation of longest single-arm-gapped palindromes in a string.

Shintaro Narisada, Diptarama Hendrian, Kazuyuki Narisawa, Shunsuke Inenaga, Ayumi Shinohara

Theor. Comput. Sci.　812　160-173　2020年

DOI： 10.1016/j.tcs.2019.10.025 　
In-Place Bijective Burrows-Wheeler Transforms.

Dominik Köppl, Daiki Hashimoto, Diptarama Hendrian, Ayumi Shinohara

31st Annual Symposium on Combinatorial Pattern Matching(CPM)　21-15　2020年
出版者・発行元： Schloss Dagstuhl - Leibniz-Zentrum für Informatik
DOI： 10.4230/LIPIcs.CPM.2020.21 　
Computing Covers Under Substring Consistent Equivalence Relations

Natsumi Kikuchi, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

String Processing and Information Retrieval　131-146　2020年
出版者・発行元： Springer International Publishing
DOI： 10.1007/978-3-030-59212-7_10 　

ISSN：0302-9743

eISSN：1611-3349
Query Learning Algorithm for Residual Symbolic Finite Automata 査読有り

Kaizaburo Chubachi, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

The Tenth International Symposium on Games, Automata, Logics, and Formal Verification, GandALF 2019　140-153　2019年9月

DOI： 10.4204/EPTCS.305.10 　
Development of a Lightweight Cyber-enhanced Rescue Canine Suit with Heat Protection and Anti-slip Countermeasures

Hiroyuki Nishinoma, Beokhaimook Chayapol, Kazunori Ohno, Ayumi Shinohara, Satoshi Tadokoro

2019 IEEE International Symposium on Safety, Security, and Rescue Robotics, SSRR 2019　74-80　2019年9月

DOI： 10.1109/SSRR.2019.8848938 　
An improvement of the franek-jennings-smyth pattern matching algorithm

Satoshi Kobayashi, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

Proceedings of the Prague Stringology Conference, PSC 2019　56-68　2019年8月26日
出版者・発行元： Prague Stringology Club
Permuted Pattern Matching Algorithms on Multi-Track Strings. 査読有り

Diptarama Hendrian, Yohei Ueki, Kazuyuki Narisawa, Ryo Yoshinaka, Ayumi Shinohara

Algorithms　12　(4)　73:1-73:20　2019年4月

DOI： 10.3390/a12040073 　
Cyber-enhanced rescue canine

Kazunori Ohno, Ryunosuke Hamada, Tatsuya Hoshi, Hiroyuki Nishinoma, Shumpei Yamaguchi, Solvi Arnold, Kimitoshi Yamazaki, Takefumi Kikusui, Satoko Matsubara, Miho Nagasawa, Takatomi Kubo, Eri Nakahara, Yuki Maruno, Kazushi Ikeda, Toshitaka Yamakawa, Takeshi Tokuyama, Ayumi Shinohara, Ryo Yoshinaka, Diptarama Hendrian, Kaizaburo Chubachi, Satoshi Kobayashi, Katsuhito Nakashima, Hiroaki Naganuma, Ryu Wakimoto, Shu Ishikawa, Tatsuki Miura, Satoshi Tadokoro

Springer Tracts in Advanced Robotics　128　143-193　2019年

DOI： 10.1007/978-3-030-05321-5_4 　

ISSN：1610-7438

eISSN：1610-742X
Efficient dynamic dictionary matching with DAWGs and AC-automata 査読有り

Diptarama Hendrian, Shunsuke Inenaga, Ryo Yoshinaka, Ayumi Shinohara

Theoretical Computer Science　2018年
出版者・発行元： Elsevier B.V.
DOI： 10.1016/j.tcs.2018.04.016 　

ISSN：0304-3975
Linear-Time Online Algorithm Inferring the Shortest Path from a Walk. 査読有り

Shintaro Narisada, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Lima, Peru, October 9-11, 2018, Proceedings　311-324　2018年
出版者・発行元： Springer
DOI： 10.1007/978-3-030-00479-8_25 　
Enumeration of Cryptarithms Using Deterministic Finite Automata. 査読有り

Yuki Nozaki, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

Implementation and Application of Automata - 23rd International Conference, CIAA 2018, Charlottetown, PE, Canada, July 30 - August 2, 2018, Proceedings　286-298　2018年
出版者・発行元： Springer
DOI： 10.1007/978-3-319-94812-6_24 　
Duel and sweep algorithm for order-preserving pattern matching 査読有り

Davaajav Jargalsaikhan, Diptarama, Yohei Ueki, Ryo Yoshinaka, Ayumi Shinohara

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　10706　624-635　2018年
出版者・発行元： Springer Verlag
DOI： 10.1007/978-3-319-73117-9_44 　

ISSN：1611-3349 0302-9743
New variants of pattern matching with constants and variables 査読有り

Yuki Igarashi, Diptarama, Ryo Yoshinaka, Ayumi Shinohara

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　10706　611-623　2018年
出版者・発行元： Springer Verlag
DOI： 10.1007/978-3-319-73117-9_43 　

ISSN：1611-3349 0302-9743
Renewal of the Major Fields from New Generation Computing Vol. 36 (2018). 査読有り

Masayuki Numao, Yutaka Matsuo, Ayumi Shinohara, Masaki Suwa

New Generation Comput.　36　(2)　91-93　2018年

DOI： 10.1007/s00354-018-0032-8 　
Computing Longest Single-arm-gapped Palindromes in a String 査読有り

Shintaro Narisada, Diptarama, Kazuyuki Narisawa, Shunsuke Inenaga, Ayumi Shinohara

SOFSEM 2017: THEORY AND PRACTICE OF COMPUTER SCIENCE　10139　375-386　2017年

DOI： 10.1007/978-3-319-51963-0_29 　

ISSN：0302-9743

eISSN：1611-3349
Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings 査読有り

Yohei Ueki, Diptarama, Masatoshi Kurihara, Yoshiaki Matsuoka, Kazuyuki Narisawa, Ryo Yoshinaka, Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara

SOFSEM 2017: THEORY AND PRACTICE OF COMPUTER SCIENCE　10139　363-374　2017年

DOI： 10.1007/978-3-319-51963-0_28 　

ISSN：0302-9743

eISSN：1611-3349
Position Heaps for Parameterized Strings. 査読有り

Diptarama, Takashi Katsura, Yuhei Otomo, Kazuyuki Narisawa, Ayumi Shinohara

28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017, July 4-6, 2017, Warsaw, Poland　8:1-8:13　2017年
出版者・発行元： Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
An efficient query learning algorithm for zero-suppressed binary decision diagrams. 査読有り

Hayato Mizumoto, Shota Todoroki, Diptarama, Ryo Yoshinaka, Ayumi Shinohara

International Conference on Algorithmic Learning Theory, ALT 2017, 15-17 October 2017, Kyoto University, Kyoto, Japan　360-371　2017年
出版者・発行元： PMLR
Compact Bit Encoding Schemes for Simply-Typed Lambda-Terms 査読有り

Kotaro Takeda, Naoki Kobayashi, Kazuya Yaguchi, Ayumi Shinohara

ACM SIGPLAN NOTICES　51　(9)　146-157　2016年9月

DOI： 10.1145/2951913.2951918 　

ISSN：0362-1340

eISSN：1558-1160
Drawing Strategies for Generalized Tic-Tac-Toe (p, q) 査読有り

Diptarama, Kazuyuki Narisawa, Ayumi Shinohara

PROGRESS IN APPLIED MATHEMATICS IN SCIENCE AND ENGINEERING PROCEEDINGS　1705　(020021)　2016年

DOI： 10.1063/1.4940269 　

ISSN：0094-243X
Generalization of Efficient Implementation of Compression by Substring Enumeration 査読有り

Shumpei Sakuma, Kazuyuki Narisawa, Ayumi Shinohara

2016 DATA COMPRESSION CONFERENCE (DCC)　630-630　2016年

DOI： 10.1109/DCC.2016.86 　

ISSN：1068-0314
Visualization and analysis of electrical energy consumption in laboratories 査読有り

Ichinari Sato, Diptarama, Ayumi Shinohara

PROCEEDINGS 2016 5TH IIAI INTERNATIONAL CONGRESS ON ADVANCED APPLIED INFORMATICS IIAI-AAI 2016　509-512　2016年

DOI： 10.1109/IIAI-AAI.2016.194 　
AC-Automaton Update Algorithm for Semi-dynamic Dictionary Matching 査読有り

Diptarama, Ryo Yoshinaka, Ayumi Shinohara

STRING PROCESSING AND INFORMATION RETRIEVAL, SPIRE 2016　9954　110-121　2016年

DOI： 10.1007/978-3-319-46049-9_11 　

ISSN：0302-9743
Pattern Matching on Compressed Text. 査読有り

Masayuki Takeda, Ayumi Shinohara

Encyclopedia of Algorithms 2016　1538-1542　2016年

DOI： 10.1007/978-1-4939-2864-4_81 　
Fast Full Permuted Pattern Matching Algorithms on Multi-track Strings 査読有り

Diptarama, Ryo Yoshinaka, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2016　7-21　2016年
AC-Automaton Update Algorithm for Semi-dynamic Dictionary Matching 査読有り

Diptarama, Ryo Yoshinaka, Ayumi Shinohara

STRING PROCESSING AND INFORMATION RETRIEVAL, SPIRE 2016　9954　110-121　2016年

DOI： 10.1007/978-3-319-46049-9_11 　

ISSN：0302-9743
A Fast Order-Preserving Matching with q-neighborhood Filtration Using SIMD Instructions. 査読有り

Yohei Ueki, Kazuyuki Narisawa, Ayumi Shinohara

Proceedings of Student Research Forum Papers and Posters at SOFSEM 2016 co-located with 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016), Harrachov, Czech Republic, January 23-28, 2016.　108-115　2016年
出版者・発行元： CEUR-WS.org
KMP Based Pattern Matching Algorithms for Multi-Track Strings. 査読有り

Diptarama, Yohei Ueki, Kazuyuki Narisawa, Ayumi Shinohara

Proceedings of Student Research Forum Papers and Posters at SOFSEM 2016 co-located with 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016), Harrachov, Czech Republic, January 23-28, 2016.　100-107　2016年
出版者・発行元： CEUR-WS.org
QBF Encoding of Generalized Tic-Tac-Toe. 査読有り

Diptarama,Ryo Yoshinaka, Ayumi Shinohara

Proceedings of the 4th International Workshop on Quantified Boolean Formulas (QBF 2016) co-located with 19th International Conference on Theory and Applications of Satisfiability Testing (SAT 2016), Bordeaux, France, July 4, 2016.　14-26　2016年
出版者・発行元： CEUR-WS.org
Visualization and analysis of electrical energy consumption in laboratories 査読有り

Ichinari Sato, Diptarama, Ayumi Shinohara

PROCEEDINGS 2016 5TH IIAI INTERNATIONAL CONGRESS ON ADVANCED APPLIED INFORMATICS IIAI-AAI 2016　509-512　2016年

DOI： 10.1109/IIAI-AAI.2016.194 　
Generalization of Efficient Implementation of Compression by Substring Enumeration 査読有り

Shumpei Sakuma, Kazuyuki Narisawa, Ayumi Shinohara

2016 DATA COMPRESSION CONFERENCE (DCC)　630-630　2016年

DOI： 10.1109/DCC.2016.86 　

ISSN：1068-0314
Filtering Multi-set Tree: Data Structure for Flexible Matching Using Multi-track Data 査読有り

Kazuyuki Narisawa, Takashi Katsura, Hiroyuki Ota, Ayumi Shinohara

Interdisciplinary Information Sciences　21　(1)　37-47　2015年3月
出版者・発行元：東北大学
DOI： 10.4036/iis.2015.37 　

ISSN：1340-9050

詳細を見る詳細を閉じる

Multi-track data are multi-set sequences that are suitable for representing time series data, such as multi-sensor data, polyphonic music data and traffic data. The permuted pattern matching problem aims to determine the occurrences of multi-track patterns in multi-track text by allowing the order of the pattern tracks to be permuted. In this study, we address permuted pattern matching by proposing a new data structure called a filtering multi-set tree (FILM tree). The FILM tree is a complete binary tree based on a spectral Bloom filter (SBF) with hash functions. This data structure is very simple but powerful, and it can be applied to both exact and approximate matching problems. We present experimental results that demonstrate the efficiency of our FILM tree-based approach.
Detecting regularities on grammar-compressed strings 査読有り

Tomohiro, I, Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara

INFORMATION AND COMPUTATION　240　74-89　2015年2月

DOI： 10.1016/j.ic.2014.09.009 　

ISSN：0890-5401

eISSN：1090-2651
Detecting regularities on grammar-compressed strings 査読有り

Tomohiro, I, Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara

INFORMATION AND COMPUTATION　240　74-89　2015年2月

DOI： 10.1016/j.ic.2014.09.009 　

ISSN：0890-5401

eISSN：1090-2651
Position Heaps for Permuted Pattern Matching on Multi-Track String 査読有り

Takashi Katsura, Yuhei Otomo, Kazuyuki Narisawa, Ayumi Shinohara

Proceedings of Student Research Forum Papers and Posters at SOFSEM 2015, the 41st International Conference on Current Trends in Theory and Practice of Computer Science　41-53　2015年1月26日
Position Heaps for Permuted Pattern Matching on Multi-Track String. 査読有り

Takashi Katsura, Yuhei Otomo, Kazuyuki Narisawa, Ayumi Shinohara

Proceedings of Student Research Forum Papers and Posters at SOFSEM 2015, the 41st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2015) , Pec pod Snezkou, Czech Republic, January 24-29, 2015.　41-53　2015年
出版者・発行元： CEUR-WS.org
一般化三並べの拡張：目標動物の組合せ査読有り

本田耕一, 八鍬友貴, 成澤和志, 篠原歩

情報処理学会論文誌　55　(11)　2336-2343　2014年11月
出版者・発行元：一般社団法人情報処理学会
ISSN：1882-7764

詳細を見る詳細を閉じる

一般化三並べは，Frank Hararyによって提案された2人完全情報ゲームであり，碁盤目状の盤面に先手後手が交互に石を1つずつ置いていき，あらかじめ定められた動物（連結した石で定義される形）を先に作ったプレイヤが勝ちとなるゲームである．本論文は，これを拡張し，目標動物の組を目標とする4種類の新たなゲーム（OR，n細胞OR，AND，NOTAND）を提案する．そしてこれらのゲームにおける性質を解析し，各動物に対して勝ち型と負け型の分類を行う．Frank Harary introduced achievement games for polyominoes as generalized Tic-Tac-Toe. Two players alternately mark cells on a board, and the player who first achieves a given polyomino wins. In this paper, we propose four new games: Game OR, Game nCellsOR, Game AND and Game NOTAND. The target of each game is a combination of polyominoes. We analyze the proposed games, and decide whether polyominoes are winners or losers.
一般化三並べの拡張：一手p石査読有り

ディプタラマ, 成澤和志, 篠原歩

情報処理学会論文誌　55　(11)　2344-2352　2014年11月
A Simple Classification Method for Class Imbalanced Data using the Kernel Mean 査読有り

Yusuke Sato, Kazuyuki Narisawa, Ayumi Shinohara

Proceedings of the 6th International Conference on Knowledge Discovery and Information Retrieval (KDIR 2014)　327-334　2014年10月21日

DOI： 10.5220/0005130103270334 　
Reducing Sample Complexity in Reinforcement Learning by Transferring Transition and Reward Probabilities 査読有り

Kouta Oguni, Kazuyuki Narisawa, Ayumi Shinohara

Proceedings of the 6th International Conference on Agents and Artificial Intelligence (ICAART 2014)　632-638　2014年3月7日

DOI： 10.5220/0004915606320638 　
Bounded Occurrence Edit Distance: A New Metric for String Similarity Joins with Edit Distance Constraints 査読有り

Tomoki Komatsu, Ryosuke Okuta, Kazuyuki Narisawa, Ayumi Shinohara

SOFSEM 2014: THEORY AND PRACTICE OF COMPUTER SCIENCE　8327　(Springer-Verlag)　363-374　2014年

DOI： 10.1007/978-3-319-04298-5_32 　

ISSN：0302-9743
Efficient algorithm and coding for higher-order compression 査読有り

Kazuya Yaguchi, Naoki Kobayashi, Ayumi Shinohara

Data Compression Conference Proceedings　434-434　2014年
出版者・発行元： Institute of Electrical and Electronics Engineers Inc.
DOI： 10.1109/DCC.2014.63 　

ISSN：1068-0314
Bounded Occurrence Edit Distance: A New Metric for String Similarity Joins with Edit Distance Constraints 査読有り

Tomoki Komatsu, Ryosuke Okuta, Kazuyuki Narisawa, Ayumi Shinohara

SOFSEM 2014: THEORY AND PRACTICE OF COMPUTER SCIENCE　8327　363-374　2014年

DOI： 10.1007/978-3-319-04298-5_32 　

ISSN：0302-9743
Reducing Sample Complexity in Reinforcement Learning by Transferring Transition and Reward Probabilities. 査読有り

Kouta Oguni, Kazuyuki Narisawa, Ayumi Shinohara

ICAART 2014 - Proceedings of the 6th International Conference on Agents and Artificial Intelligence, Volume 1, ESEO, Angers, Loire Valley, France, 6-8 March, 2014　632-638　2014年
出版者・発行元： SciTePress
DOI： 10.5220/0004915606320638 　
A Simple Classification Method for Class Imbalanced Data using the Kernel Mean. 査読有り

Yusuke Sato, Kazuyuki Narisawa, Ayumi Shinohara

KDIR 2014 - Proceedings of the International Conference on Knowledge Discovery and Information Retrieval, Rome, Italy, 21 - 24 October, 2014　327-334　2014年
出版者・発行元： SciTePress
DOI： 10.5220/0005130103270334 　
Efficient algorithm and coding for higher-order compression 査読有り

Kazuya Yaguchi, Naoki Kobayashi, Ayumi Shinohara

Data Compression Conference Proceedings　434　2014年
出版者・発行元： Institute of Electrical and Electronics Engineers Inc.
DOI： 10.1109/DCC.2014.63 　

ISSN：1068-0314
Average number of occurrences of repetitions in a necklace 査読有り

Kazuhiko Kusano, Ayumi Shinohara

DISCRETE APPLIED MATHEMATICS　163　334-342　2014年1月

DOI： 10.1016/j.dam.2013.05.019 　

ISSN：0166-218X

eISSN：1872-6771
On Morphisms Generating Run-Rich Strings 査読有り

Kazuhiko Kusano, Kazuyuki Narisawa, Ayumi Shinohara

Proc. The Prague Stringology Conference 2013 (PSC2013)　35-47　2013年9月3日
On the hardness of approximating the minimum consistent DFA from prefix samples 査読有り

Kaori Ueno, Shinichi Shimozono, Kazuyuki Narisawa, Ayumi Shinohara

ICALP 2013 Satellite Workshop on Learning Theory and ComplexityLearning Theory and Complexity (LTC 2013), (post-proceedings will be published later)　2013年7月7日
Permuted pattern matching on multi-track strings 査読有り

Takashi Katsura, Kazuyuki Narisawa, Ayumi Shinohara, Hideo Bannai, Shunsuke Inenaga

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　7741　(Springer-Verlag)　280-291　2013年

DOI： 10.1007/978-3-642-35843-2_25 　

ISSN：0302-9743 1611-3349
Detecting Regularities on Grammar-Compressed Strings 査読有り

Tomohiro, I, Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2013　8087　(Springer-Verlag)　571-582　2013年

DOI： 10.1007/978-3-642-40313-2_51 　

ISSN：0302-9743
On Morphisms Generating Run-Rich Strings. 査読有り

Kazuhiko Kusano, Kazuyuki Narisawa, Ayumi Shinohara

Proceedings of the Prague Stringology Conference 2013, Prague, Czech Republic, September 2-4, 2013　35-47　2013年
出版者・発行元： Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague
Permuted pattern matching on multi-track strings 査読有り

Takashi Katsura, Kazuyuki Narisawa, Ayumi Shinohara, Hideo Bannai, Shunsuke Inenaga

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　7741　280-291　2013年
出版者・発行元： Springer
DOI： 10.1007/978-3-642-35843-2_25 　

ISSN：0302-9743 1611-3349
Detecting Regularities on Grammar-Compressed Strings 査読有り

Tomohiro, I, Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2013　8087　571-582　2013年

DOI： 10.1007/978-3-642-40313-2_51 　

ISSN：0302-9743
Functional programs as compressed data 査読有り

Naoki Kobayashi, Kazutaka Matsuda, Ayumi Shinohara, Kazuya Yaguchi

Higher-Order and Symbolic Computation　25　(1)　39-84　2012年3月1日
出版者・発行元： Kluwer Academic Publishers
DOI： 10.1007/s10990-013-9093-z 　

ISSN：1388-3690
Functional programs as compressed data 査読有り

Naoki Kobayashi, Kazutaka Matsuda, Ayumi Shinohara, Kazuya Yaguchi

Higher-Order and Symbolic Computation　25　(1)　39-84　2012年3月1日
出版者・発行元： Kluwer Academic Publishers
DOI： 10.1007/s10990-013-9093-z 　

ISSN：1388-3690
Functional programs as compressed data 査読有り

Naoki Kobayashi, Kazutaka Matsuda, Ayumi Shinohara, Kazuya Yaguchi

ACM SIGPLAN 2012 Workshop on Partial Evaluation and Program Manipulation (PEPM 2012)　121-130　2012年2月1日

DOI： 10.1145/2103746.2103770 　
PREDICTION FOR CONTROL DELAY ON REINFORCEMENT LEARING 査読有り

Junya Saito, Kazuyuki Narisawa, Ayumi Shinohara

ICAART: PROCEEDINGS OF THE 4TH INTERNATIONAL CONFERENCE ON AGENTS AND ARTIFICIAL INTELLIGENCE, VOL 1　579-586　2012年

DOI： 10.5220/0003888405790586 　
Computing Maximum Number of Runs in Strings 査読有り

Kazuhiko Kusano, Kazuyuki Narisawa, Ayumi Shinohara

STRING PROCESSING AND INFORMATION RETRIEVAL　7608　(Springer-Verlag)　318-329　2012年

DOI： 10.1007/978-3-642-34109-0_33 　

ISSN：0302-9743
Computing Maximum Number of Runs in Strings 査読有り

Kazuhiko Kusano, Kazuyuki Narisawa, Ayumi Shinohara

STRING PROCESSING AND INFORMATION RETRIEVAL　7608　318-329　2012年

DOI： 10.1007/978-3-642-34109-0_33 　

ISSN：0302-9743
Functional programs as compressed data. 査読有り

Naoki Kobayashi, Kazutaka Matsuda, Ayumi Shinohara

Proceedings of the ACM SIGPLAN 2012 Workshop on Partial Evaluation and Program Manipulation, PEPM 2012, Philadelphia, Pennsylvania, USA, January 23-24, 2012　121-130　2012年
出版者・発行元： ACM
PREDICTION FOR CONTROL DELAY ON REINFORCEMENT LEARING 査読有り

Junya Saito, Kazuyuki Narisawa, Ayumi Shinohara

ICAART: PROCEEDINGS OF THE 4TH INTERNATIONAL CONFERENCE ON AGENTS AND ARTIFICIAL INTELLIGENCE, VOL 1　579-586　2012年

DOI： 10.5220/0003888405790586 　
Similarity Measure using Lossy Compression and its Application to Image Retrieval 査読有り

Kosuke Bannai, Kazuyuki Narisawa, Ayumi Shinohara

The GSTF International Journal on Computing (JoC)　1　(3)　45-50　2011年8月1日
Similarity Measure using Lossy Compression and its Application to Image Retrieval 査読有り

Kosuke Bannai, Kazuyuki Narisawa, Ayumi Shinohara

Annual International Conference on Information Theory and Application (ITA 2011)　14　(19)　2011年2月1日
半導体歩留り解析のための回帰木に基づく仮説検証手法の提案査読有り

津田英隆, 白井英大, 寺邊正大, 橋本和夫, 篠原歩

電気学会論文誌D　131　(10)　1232-1239　2011年

DOI： 10.1541/ieejias.131.1232 　

ISSN：0913-6339 1348-8163
An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Programs 査読有り

Wataru Matsubara, Shunsuke Inenaga, Ayumi Shinohara

Chicago Journal of Theoretical Computer Science　Article 7　1-20　2010年6月22日

DOI： 10.4086/cjtcs.2010.007 　
Inferring Strings from Runs 査読有り

Wataru Matsubara, Akira Ishino, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2010　150-160　2010年
The Number of Runs in a Ternary Word 査読有り

Hideo Bannai, Mathieu Giraud, Kazuhiko Kusano, Wataru Matsubara, Ayumi Shinohara, Jamie Simpson

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2010　178-181　2010年
The Number of Runs in a Ternary Word 査読有り

Hideo Bannai, Mathieu Giraud, Kazuhiko Kusano, Wataru Matsubara, Ayumi Shinohara, Jamie Simpson

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2010　178-181　2010年
Average Number of Runs and Squares in Necklace 査読有り

Kazuhiko Kusano, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2010　167-177　2010年
Inferring Strings from Runs 査読有り

Wataru Matsubara, Akira Ishino, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2010　150-160　2010年
Multi-target adaptive A*. 査読有り

Kengo Matsuta, Hayato Kobayashi, Ayumi Shinohara

9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), Toronto, Canada, May 10-14, 2010, Volume 1-3　1065-1072　2010年
出版者・発行元： IFAAMAS
An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Programs. 査読有り

Wataru Matsubara, Shunsuke Inenaga, Ayumi Shinohara

Chicago J. Theor. Comput. Sci.　2010　2010年
The Size of Message Set Needed for the Optimal Communication Policy 査読有り

Tatsuya Kasai, Hayato Kobayashi, Ayumi Shinohara

Proceedings of the 7th European Workshop on Multi-Agent Systems　S40　2009年12月18日
Linear-Time text compression by longest-first substitution 査読有り

Ryosuke Nakamura, Shunsuke Inenaga, Hideo Bannai, Takashi Funamoto, Masayuki Takeda, Ayumi Shinohara

Algorithms　2　(4)　1429-1448　2009年12月

DOI： 10.3390/a2041429 　

ISSN：1999-4893
AVERAGE VALUE OF SUM OF EXPONENTS OF RUNS IN A STRING 査読有り

Kazuhiko Kusano, Wataru Matsubara, Akira Ishino, Ayumi Shinohara

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE　20　(6)　1135-1146　2009年12月

DOI： 10.1142/S0129054109007078 　

ISSN：0129-0541
AVERAGE VALUE OF SUM OF EXPONENTS OF RUNS IN A STRING 査読有り

Kazuhiko Kusano, Wataru Matsubara, Akira Ishino, Ayumi Shinohara

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE　20　(6)　1135-1146　2009年12月

DOI： 10.1142/S0129054109007078 　

ISSN：0129-0541
Linear-Time text compression by longest-first substitution 査読有り

Ryosuke Nakamura, Shunsuke Inenaga, Hideo Bannai, Takashi Funamoto, Masayuki Takeda, Ayumi Shinohara

Algorithms　2　(4)　1429-1448　2009年12月

DOI： 10.3390/a2041429 　

ISSN：1999-4893
Development of an Interactive Augmented Environment and Its Application to Autonomous Learning for Quadruped Robots 査読有り

Hayato Kobayashi, Tsugutoyo Osaki, Tetsuro Okuyama, Joshua Gramm, Akira Ishino, Ayumi Shinohara

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS　E92D　(9)　1752-1761　2009年9月

DOI： 10.1587/transinf.E92.D.1752 　

ISSN：0916-8532
Complexity of Teaching by a Restricted Number of Examples 査読有り

Hayato Kobayashi, Ayumi Shinohara

The 22nd Conference on Learning Theory　2009年6月18日
Improvement of the performance using received message on learning of communication codes 査読有り

Tatsuya Kasai, Hayato Kobayashi, Ayumi Shinohara

8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009)　2　2009年5月10日
Efficient algorithms to compute compressed longest common substrings and compressed palindromes 査読有り

Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, Kazuo Hashimoto

THEORETICAL COMPUTER SCIENCE　410　(8-10)　900-913　2009年3月

DOI： 10.1016/j.tcs.2008.12.016 　

ISSN：0304-3975
Efficient algorithms to compute compressed longest common substrings and compressed palindromes 査読有り

Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, Kazuo Hashimoto

THEORETICAL COMPUTER SCIENCE　410　(8-10)　900-913　2009年3月

DOI： 10.1016/j.tcs.2008.12.016 　

ISSN：0304-3975
Testing Square-Freeness of Strings Compressed by Balanced Straight Line Program 査読有り

Wataru Matsubara, Shunsuke Inenaga, Ayumi Shinohara

Proc. 15th Computing: The Australasian Theory Symposium　94　21-30　2009年1月20日
Development of an Augmented Environment and Autonomous Learning for Quadruped Robots 査読有り

Hayato Kobayashi, Tsugutoyo Osaki, Tetsuro Okuyama, Akira Ishino, Ayumi Shinohara

ROBOCUP 2008: ROBOT SOCCER WORLD CUP XII　5399　109-120　2009年

DOI： 10.1007/978-3-642-02921-9_10 　

ISSN：0302-9743
間引き：ロボットのスキル発見における評価の削減手法査読有り

小林隼人, 畑埜晃平, 石野明, 篠原歩

人工知能学会論文誌　24　(1)　191-202　2009年
出版者・発行元：
DOI： 10.1527/tjsai.24.191 　

ISSN：1346-8030 1346-0714
A Series of Run-Rich Strings 査読有り

Wataru Matsubara, Kazuhiko Kusano, Hideo Bannai, Ayumi Shinohara

LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS　5457　578-+　2009年

DOI： 10.1007/978-3-642-00982-2_49 　

ISSN：0302-9743
半導体歩留り解析へのデータマイニング適用手法の提案査読有り

津田英隆, 白井英大, 寺邊正大, 橋本和夫, 篠原歩

電気学会論文誌D　129　(12)　9-1211　2009年

DOI： 10.1541/ieejias.129.1201 　

ISSN：0913-6339 1348-8163
Development of an Augmented Environment and Autonomous Learning for Quadruped Robots 査読有り

Hayato Kobayashi, Tsugutoyo Osaki, Tetsuro Okuyama, Akira Ishino, Ayumi Shinohara

ROBOCUP 2008: ROBOT SOCCER WORLD CUP XII　5399　109-120　2009年

DOI： 10.1007/978-3-642-02921-9_10 　

ISSN：0302-9743
Bit-parallel algorithms for computing all the runs in a string 査読有り

Kazunori Hirashima, Hideo Bannai, Wataru Matsubara, Akira Ishino, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2009　203-213　2009年
A Series of Run-Rich Strings 査読有り

Wataru Matsubara, Kazuhiko Kusano, Hideo Bannai, Ayumi Shinohara

LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS　5457　578-+　2009年

DOI： 10.1007/978-3-642-00982-2_49 　

ISSN：0302-9743
Complexity of Teaching by a Restricted Number of Examples. 査読有り

Hayato Kobayashi, Ayumi Shinohara

COLT 2009 - The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009　2009年
Testing Square-Freeness of Strings Compressed by Balanced Straight Line Program. 査読有り

Wataru Matsubara, Shunsuke Inenaga, Ayumi Shinohara

Theory of Computing 2009, Fifteenth Computing: The Australasian Theory Symposium, CATS 2009, Wellington, New Zealand, January 2009　19-28　2009年
出版者・発行元： Australian Computer Society
Improvement of the performance using received message on learning of communication codes. 査読有り

Tatsuya Kasai, Hayato Kobayashi, Ayumi Shinohara

8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009), Budapest, Hungary, May 10-15, 2009, Volume 2　1229-1230　2009年
出版者・発行元： IFAAMAS
A trend mining method for yield improvement based on trend in time series

Hidetaka Tsuda, Hidehiro Shirai, Masahiro Terabe, Kazuo Hashimoto, Ayumi Shinohara

IEEE International Symposium on Semiconductor Manufacturing Conference Proceedings　247-250　2008年

ISSN：1523-553X
Computing longest common substring and all palindromes from compressed strings 査読有り

Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, Kazuo Hashimoto

SOFSEM 2008: THEORY AND PRACTICE OF COMPUTER SCIENCE　4910　364-+　2008年

DOI： 10.1007/978-3-540-77566-9_31 　

ISSN：0302-9743
Autonomous Learning of Ball Passing by Four-legged Robots and Trial Reduction by Thinning-out and Surrogate Functions 査読有り

Hayato Kobayashi, Kohei Hatano, Akira Ishino, Ayumi Shinohara

IAS-10: INTELLIGENT AUTONOMOUS SYSTEMS 10　145-154　2008年

DOI： 10.3233/978-1-58603-887-8-145 　
New Lower Bounds for the Maximum Number of Runs in a String 査読有り

Wataru Matsubara, Kazuhiko Kusano, Akira Ishino, Hideo Bannai, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2008　140-145　2008年
Average Value of Sum of Exponents of Runs in Strings 査読有り

Kazuhiko Kusano, Wataru Matsubara, Akira Ishino, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2008　185-192　2008年
New Lower Bounds for the Maximum Number of Runs in a String 査読有り

Wataru Matsubara, Kazuhiko Kusano, Akira Ishino, Hideo Bannai, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2008　abs/0804.1214　140-145　2008年
An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Program. 査読有り

Wataru Matsubara, Shunsuke Inenaga, Ayumi Shinohara

Structure-Based Compression of Complex Massive Data, 22.06. - 27.06.2008　2008年
出版者・発行元： Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany
Average Value of Sum of Exponents of Runs in Strings 査読有り

Kazuhiko Kusano, Wataru Matsubara, Akira Ishino, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2008　185-192　2008年
New Lower Bounds for the Maximum Number of Runs in a String 査読有り

Wataru Matsubara, Kazuhiko Kusano, Akira Ishino, Hideo Bannai, Ayumi Shinohara

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2008　140-145　2008年
Computing longest common substring and all palindromes from compressed strings 査読有り

Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, Kazuo Hashimoto

SOFSEM 2008: THEORY AND PRACTICE OF COMPUTER SCIENCE　4910　364-+　2008年

DOI： 10.1007/978-3-540-77566-9_31 　

ISSN：0302-9743
Autonomous learning of ball trapping in the four-legged robot league 査読有り

Hayato Kobayashi, Tsugutoyo Osaki, Eric Williams, Akira Ishino, Ayumi Shinohara

ROBOCUP 2006: ROBOT SOCCER WORLD CUP X　4434　86-+　2007年

DOI： 10.1007/978-3-540-74024-7_8 　

ISSN：0302-9743
Reducing trials by thinning-out in skill discovery 査読有り

Hayato Kobayashi, Kohei Hatano, Akira Ishino, Ayumi Shinohara

DISCOVERY SCIENCE, PROCEEDINGS　4755　127-+　2007年

DOI： 10.1007/978-3-540-75488-6_13 　

ISSN：0302-9743
Autonomous learning of ball trapping in the four-legged robot league 査読有り

Hayato Kobayashi, Tsugutoyo Osaki, Eric Williams, Akira Ishino, Ayumi Shinohara

ROBOCUP 2006: ROBOT SOCCER WORLD CUP X　4434　86-+　2007年

DOI： 10.1007/978-3-540-74024-7_8 　

ISSN：0302-9743
Reducing trials by thinning-out in skill discovery 査読有り

Hayato Kobayashi, Kohei Hatano, Akira Ishino, Ayumi Shinohara

DISCOVERY SCIENCE, PROCEEDINGS　4755　127-+　2007年

DOI： 10.1007/978-3-540-75488-6_13 　

ISSN：0302-9743
A Framework for Advanced Robot Programming in the RoboCup Domain - Using Plug-in System and Scripting Language 査読有り

Hayato Kobayashi, Akira Ishino, Ayumi Shinohara

INTELLIGENT AUTONOMOUS SYSTEMS 9　660-+　2006年
Ball tracking with velocity based on Monte-Carlo localization 査読有り

Jun Inoue, Akira Ishino, Ayumi Shinohara

INTELLIGENT AUTONOMOUS SYSTEMS 9　686-+　2006年
Ball tracking with velocity based on Monte-Carlo localization 査読有り

Jun Inoue, Akira Ishino, Ayumi Shinohara

INTELLIGENT AUTONOMOUS SYSTEMS 9　686-+　2006年
A Framework for Advanced Robot Programming in the RoboCup Domain - Using Plug-in System and Scripting Language 査読有り

Hayato Kobayashi, Akira Ishino, Ayumi Shinohara

INTELLIGENT AUTONOMOUS SYSTEMS 9　660-+　2006年
A fully compressed pattern matching algorithm for simple collage systems 査読有り

S Inenaga, A Shinohara, M Takeda

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE　16　(6)　1155-1166　2005年12月

DOI： 10.1142/S0129054105003728 　

ISSN：0129-0541

eISSN：1793-6373
The size of subsequence automaton 査読有り

Z Tronicek, A Shinohara

THEORETICAL COMPUTER SCIENCE　341　(1-3)　379-384　2005年9月

DOI： 10.1016/j.tcs.2005.03.027 　

ISSN：0304-3975
The size of subsequence automaton 査読有り

Z Tronicek, A Shinohara

THEORETICAL COMPUTER SCIENCE　341　(1-3)　379-384　2005年9月

DOI： 10.1016/j.tcs.2005.03.027 　

ISSN：0304-3975
On-line construction of compact directed acyclic word graphs 査読有り

Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Giancarlo Mauri, Giulio Pavesi

Discrete Applied Mathematics　146　(2)　156-179　2005年3月1日

DOI： 10.1016/j.dam.2004.04.012 　

ISSN：0166-218X
On-line construction of compact directed acyclic word graphs 査読有り

S Inenaga, H Hoshino, A Shinohara, M Takeda, S Arikawa, G Mauri, G Pavesi

DISCRETE APPLIED MATHEMATICS　146　(2)　156-179　2005年3月

DOI： 10.1016/dam.2004.04.012 　

ISSN：0166-218X
On bit-parallel processing of multi-byte text 査読有り

H Hyyro, J Takaba, A Shinohara, M Takeda

INFORMATION RETRIEVAL TECHNOLOGY　3411　289-300　2005年

ISSN：0302-9743
Fast bit-vector algorithms for approximate string matching under indel distance 査読有り

H Hyyro, Y Pinzon, A Shinohara

SOFSEM 2005:THEORY AND PRACTICE OF COMPUTER SCIENCE　3381　380-384　2005年

DOI： 10.1007/b105088 　

ISSN：0302-9743
New bit-parallel Indel-distance algorithm 査読有り

H Hyyro, Y Pinzon, A Shinohara

EXPERIMENTAL AND EFFICIENT ALGORITHMS, PROCEEDINGS　3503　380-390　2005年

DOI： 10.1007/11427186_33 　

ISSN：0302-9743
Fully incremental LCS computation 査読有り

Y Ishida, S Inenaga, A Shinohara, M Takeda

FUNDAMENTALS OF COMPUTATIONAL THEORY, PROCEEDINGS　3623　563-574　2005年

DOI： 10.1007/11537311_49 　

ISSN：0302-9743
On bit-parallel processing of multi-byte text 査読有り

H Hyyro, J Takaba, A Shinohara, M Takeda

INFORMATION RETRIEVAL TECHNOLOGY　3411　289-300　2005年

DOI： 10.1007/978-3-540-31871-2_25 　

ISSN：0302-9743
New bit-parallel Indel-distance algorithm 査読有り

H Hyyro, Y Pinzon, A Shinohara

EXPERIMENTAL AND EFFICIENT ALGORITHMS, PROCEEDINGS　3503　380-390　2005年

DOI： 10.1007/11427186_33 　

ISSN：0302-9743
Fast bit-vector algorithms for approximate string matching under indel distance 査読有り

H Hyyro, Y Pinzon, A Shinohara

SOFSEM 2005:THEORY AND PRACTICE OF COMPUTER SCIENCE　3381　380-384　2005年

DOI： 10.1007/978-3-540-30577-4_44 　

ISSN：0302-9743
Fully incremental LCS computation 査読有り

Y Ishida, S Inenaga, A Shinohara, M Takeda

FUNDAMENTALS OF COMPUTATIONAL THEORY, PROCEEDINGS　3623　563-574　2005年

DOI： 10.1007/11537311_49 　

ISSN：0302-9743
Ternary directed acyclic word graphs 査読有り

S Miyamoto, S Inenaga, M Takeda, A Shinohara

THEORETICAL COMPUTER SCIENCE　328　(1-2)　97-111　2004年11月

DOI： 10.1016/j.tcs.2004.07.008 　

ISSN：0304-3975
Ternary directed acyclic word graphs 査読有り

S Miyamoto, S Inenaga, M Takeda, A Shinohara

THEORETICAL COMPUTER SCIENCE　328　(1-2)　97-111　2004年11月

DOI： 10.1016/j.tcs.2004.07.008 　

ISSN：0304-3975
An O(N-2) algorithm for discovering optimal boolean pattern pairs 査読有り

H Bannai, H Hyyro, A Shinohara, M Takeda, K Nakai, S Miyano

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS　1　(4)　159-170　2004年10月

DOI： 10.1109/TCBB.2004.36 　

ISSN：1545-5963
An O(N-2) algorithm for discovering optimal boolean pattern pairs 査読有り

H Bannai, H Hyyro, A Shinohara, M Takeda, K Nakai, S Miyano

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS　1　(4)　159-170　2004年10月

DOI： 10.1109/TCBB.2004.36 　

ISSN：1545-5963
Expression profiling of gene with upstream AML I recognition sequence in hematopoietic stem cell-like fractions from individuals with the M2 subtype of human acute myeloid leukemia 査読有り

Y Oshima, Y Ishida, A Shinohara, H Mano, A Fujimura

EXPERIMENTAL HEMATOLOGY　32　(7)　34-34　2004年7月

ISSN：0301-472X
Efficiently finding regulatory elements using correlation with gene expression 査読有り

Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Satoru Miyano

Journal of Bioinformatics and Computational Biology　2　(2)　273-288　2004年6月

DOI： 10.1142/S0219720004000612 　

ISSN：0219-7200
Efficiently finding regulatory elements using correlation with gene expression 査読有り

Hideo Bannai, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Satoru Miyano

Journal of Bioinformatics and Computational Biology　2　(2)　273-288　2004年6月

DOI： 10.1142/S0219720004000612 　

ISSN：0219-7200
Compact directed acyclic word graphs for a sliding window 査読有り

Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa

Journal of Discrete Algorithms　2　(1)　33-51　2004年3月

DOI： 10.1016/S1570-8667(03)00064-9 　

ISSN：1570-8667
Compact directed acyclic word graphs for a sliding window 査読有り

Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa

Journal of Discrete Algorithms　2　(1)　33-51　2004年3月

DOI： 10.1016/S1570-8667(03)00064-9 　

ISSN：1570-8667
An efficient pattern matching algorithm on a subclass of context free grammars 査読有り

S Inenaga, A Shinohara, M Takeda

DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS　3340　225-236　2004年

DOI： 10.1007/b103739 　

ISSN：0302-9743
Finding optimal pairs of patterns 査読有り

H Bannai, H Hyyro, A Shinohara, M Takeda, K Nakai, S Miyano

ALGORITHMS IN BIOINFORMATICS, PROCEEDINGS　3240　450-462　2004年

DOI： 10.1007/978-3-540-30219-3_38 　

ISSN：0302-9743
A Fully Compressed Pattern Matching Algorithm for Simple Collage Systems. 査読有り

Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda

Proceedings of the Prague Stringology Conference 2004, Prague, Czech Republic, August 30 - September 1, 2004　98-113　2004年
出版者・発行元： Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University
An efficient pattern matching algorithm on a subclass of context free grammars 査読有り

S Inenaga, A Shinohara, M Takeda

DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS　3340　225-236　2004年

DOI： 10.1007/978-3-540-30550-7_19 　

ISSN：0302-9743
Finding optimal pairs of cooperative and competing patterns with bounded distance 査読有り

S Inenaga, H Bannai, H Hyyro, A Shinohara, M Takeda, K Nakai, S Miyano

DISCOVERY SCIENCE, PROCEEDINGS　3245　32-46　2004年

DOI： 10.1007/978-3-540-30214-8_3 　

ISSN：0302-9743
String pattern discovery 査読有り

A Shinohara

ALGORITHMIC LEARNING THEORY, PROCEEDINGS　3244　1-13　2004年

DOI： 10.1007/978-3-540-30215-5_1 　

ISSN：0302-9743
A Note on Randomized Algorithm for String Matching with Mismatches 査読有り

Kensuke Baba, Ayumi Shinohara, Masayuki Takeda, Shunsuke Inenaga, Setsuo Arikawa

Nordic Journal of Computing　10　(1)　2-12　2003年4月
Collage system: a unifying framework for compressed pattern matching 査読有り

T Kida, T Matsumoto, Y Shibata, M Takeda, A Shinohara, S Arikawa

THEORETICAL COMPUTER SCIENCE　298　(1)　253-272　2003年4月

DOI： 10.1016/S0304-3975(02)00426-7 　

ISSN：0304-3975

eISSN：1879-2294
Collage system: a unifying framework for compressed pattern matching 査読有り

T Kida, T Matsumoto, Y Shibata, M Takeda, A Shinohara, S Arikawa

THEORETICAL COMPUTER SCIENCE　298　(1)　253-272　2003年4月

DOI： 10.1016/S0304-3975(02)00426-7 　

ISSN：0304-3975

eISSN：1879-2294
A generalization of FFT algorithms for string matching 査読有り

Baba Kensuke, Tanaka Yoshihito, Nakatoh Tetsuya, Shinohara Ayumi, 馬場謙介, 田中義人, 中藤哲也, 篠原歩

Proceedings of the International Symposium on Information Science and Electrical Engineering　2003　191　2003年
Uniform characterizations of polynomial-query learnabilities 査読有り

Y Hayashi, S Matsumoto, A Shinohara, M Takeda

THEORETICAL COMPUTER SCIENCE　292　(2)　377-385　2003年1月

DOI： 10.1016/S0304-3975(02)00177-9 　

ISSN：0304-3975

eISSN：1879-2294
A practical algorithm to find the best subsequence patterns 査読有り

M Hirao, H Hoshino, A Shinohara, M Takeda, S Arikawa

THEORETICAL COMPUTER SCIENCE　292　(2)　465-479　2003年1月

DOI： 10.1016/S0304-3975(02)00182-2 　

ISSN：0304-3975

eISSN：1879-2294
Ternary directed acyclic word graphs 査読有り

S Miyamoto, S Inenaga, M Takeda, A Shinohara

IMPLEMENTATION AND APPLICATION OF AUTOMATA, PROCEEDINGS　2759　120-130　2003年

DOI： 10.1007/3-540-45089-0_12 　

ISSN：0302-9743
The size of subsequence automaton 査読有り

Z Tronicek, A Shinohara

STRING PROCESSING AND INFORMATION RETRIEVAL, PROCEEDINGS　2857　304-310　2003年

DOI： 10.1007/978-3-540-39984-1_23 　

ISSN：0302-9743
Linear-time off-line text compression by longest-first substitution 査読有り

S Inenaga, T Funamoto, M Takeda, A Shinohara

STRING PROCESSING AND INFORMATION RETRIEVAL, PROCEEDINGS　2857　137-152　2003年

DOI： 10.1007/978-3-540-39984-1_11 　

ISSN：0302-9743
Inferring strings from graphs and arrays 査読有り

H Bannai, S Inenaga, A Shinohara, M Takeda

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2003, PROCEEDINGS　2747　208-217　2003年

DOI： 10.1007/978-3-540-45138-9_15 　

ISSN：0302-9743
On the length of the minimum solution of word equations in one variable 査読有り

K Baba, S Tsuruta, A Shinohara, M Takeda

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2003, PROCEEDINGS　2747　189-197　2003年

DOI： 10.1007/978-3-540-45138-9_13 　

ISSN：0302-9743
Discovering most classificatory patterns for very expressive pattern classes 査読有り

M Takeda, S Inenaga, H Bannai, A Shinohara, S Arikawa

DISCOVERY SCIENCE, PROCEEDINGS　2843　486-493　2003年

DOI： 10.1007/978-3-540-39644-4_50 　

ISSN：0302-9743
A practical algorithm to find the best subsequence patterns 査読有り

M Hirao, H Hoshino, A Shinohara, M Takeda, S Arikawa

THEORETICAL COMPUTER SCIENCE　292　(2)　465-479　2003年1月

DOI： 10.1016/S0304-3975(02)00182-2 　

ISSN：0304-3975

eISSN：1879-2294
Uniform characterizations of polynomial-query learnabilities 査読有り

Y Hayashi, S Matsumoto, A Shinohara, M Takeda

THEORETICAL COMPUTER SCIENCE　292　(2)　377-385　2003年1月

DOI： 10.1016/S0304-3975(02)00177-9 　

ISSN：0304-3975

eISSN：1879-2294
A Note on Randomized Algorithm for String Matching with Mismatches. 査読有り

Kensuke Baba, Ayumi Shinohara, Masayuki Takeda, Shunsuke Inenaga, Setsuo Arikawa

Nord. J. Comput.　10　(1)　2-12　2003年
A string pattern regression algorithm and its application to pattern discovery in long introns 査読有り

BANNAI H.

Genome Informatics 2002 (GIW2002)　13　3-11　2002年12月

DOI： 10.11234/gi1990.13.3 　
Progress in Discovery Science, Final Report of the Japanese Discovery Science Project 査読有り

Progress in Discovery Science 2002　2281　2002年
出版者・発行元： Springer
DOI： 10.1007/3-540-45884-0 　
A Note on Randomized Algorithm for String Matching with Mismatches. 査読有り

Kensuke Baba, Ayumi Shinohara, Masayuki Takeda, Shunsuke Inenaga, Setsuo Arikawa

Proceedings of the Prague Stringology Conference 2002, Prague, Czech Republic, September 23-24, 2002　9-17　2002年
出版者・発行元： Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University
Compact directed acyclic word graphs for a sliding window 査読有り

Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　2476　310-324　2002年
出版者・発行元： Springer Verlag
DOI： 10.1007/3-540-45735-6_27 　

ISSN：1611-3349 0302-9743
Processing text files as is: Pattern matching over compressed texts, multi-byte character texts, and semi-structured texts 査読有り

Masayuki Takeda, Satoru Miyamoto, Takuya Kida, Ayumi Shinohara, Shuichi Fukamachi, Takeshi Shinohara, Setsuo Arikawa

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　2476　170-186　2002年
出版者・発行元： Springer Verlag
DOI： 10.1007/3-540-45735-6_16 　

ISSN：1611-3349 0302-9743
Space-economical construction of index structures for all suffixes of a string 査読有り

S Inenaga, A Shinohara, M Takeda, H Bannai, S Arikawa

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2002　2420　341-352　2002年

DOI： 10.1007/3-540-45687-2_28 　

ISSN：0302-9743
Finding Best Patterns Practically. 査読有り

Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Masahiro Hirao, Hiromasa Hoshino, Shunsuke Inenaga

Progress in Discovery Science, Final Report of the Japanese Discovery Science Project　307-317　2002年
出版者・発行元： Springer
DOI： 10.1007/3-540-45884-0_21 　
Discovering best variable-length-don't-care patterns 査読有り

S Inenaga, H Bannai, A Shmohara, M Takeda, S Arikawa

DISCOVERY SCIENCE, PROCEEDINGS　2534　86-97　2002年

DOI： 10.1007/3-540-36182-0_10 　

ISSN：0302-9743
The minimum DAWG for all suffixes of a string and its applications 査読有り

S Inenaga, M Takeda, A Shinohara, H Hoshino, S Arikawa

COMBINATORIAL PATTERN MATCHING　2373　153-167　2002年

DOI： 10.1007/3-540-45452-7_14 　

ISSN：0302-9743
平衡直線的プログラムに対するパターン照合アルゴリズム査読有り

平尾昌啓, 篠原歩, 竹田正幸, 有川節夫

電子情報通信学会和文論文誌　J84-A　(6)　722-730　2001年6月
出版者・発行元：一般社団法人電子情報通信学会
ISSN：0913-5707

詳細を見る詳細を閉じる

テキストとパターンが直線的プログラムとその変種で記述された文字列の照合問題を扱う.直線的プログラムによって表される文字列の長さは, その記述長に対して指数的に長くなる可能性があるので, 展開することなしに, いかに高速な照合を行うかが問題となる.直線的プログラムに対する既存の最も良い圧縮パターン照合アルゴリズムはO(n^2m^2)時間O(mn)領域で動作する.ここで, nは圧縮テキストのサイズで, mは圧縮パターンのサイズである.本論文では, 平衡直線的プログラムという直線的プログラムの変種を提案し, それに対する高速な圧縮パターン照合アルゴリズムを示す.平衡直線的プログラムは直線的プログラムに比べ圧縮率では劣るが, 直線的プログラムと同様に指数長の表現力をもつ.提案アルゴリズムはO(nm)時間O(nm)領域で動作する.
Speeding up string pattern matching by text compression 査読有り

Masayuki Takeda, Yusuke Shibata, Tetsuya Matsumoto, Takuya Kida, Ayumi Shinohara, Shuichi Fukamachi, Takeshi Shinohara, Setsuo Arikawa

Trans. Information Processing Society of Japan　42　(3)　370-384　2001年3月
出版者・発行元：一般社団法人情報処理学会
ISSN：1882-7764

詳細を見る詳細を閉じる

This paper describes our recent studies onstring pattern matching in compressed textsmainly from practical viewpoints.The aim is to speed up the string pattern matching task in comparison with an ordinary search over the original texts.We have successfully developed (1) an AC type algorithmfor searching in Huffman encoded files and (2) a KMP typealgorithm and (3) a BM type algorithm for searchingin files compressed by the so-called byte pair encoding (BPE).Each of the algorithms reduces the search timeat nearly the same rate as the compression ratio.Surprisingly the BM type algorithm runs over BPE compressed filesabout $1.2$--$3.0$ times faster thanthe exact match routines of the software package {?tt agrep} which is known as the fastest pattern matching tool.This paper describes our recent studies onstring pattern matching in compressed textsmainly from practical viewpoints.The aim is to speed up the string pattern matching task,in comparison with an ordinary search over the original texts.We have successfully developed (1) an AC type algorithmfor searching in Huffman encoded files, and (2) a KMP typealgorithm and (3) a BM type algorithm for searchingin files compressed by the so-called byte pair encoding (BPE).Each of the algorithms reduces the search timeat nearly the same rate as the compression ratio.Surprisingly, the BM type algorithm runs over BPE compressed filesabout $1.2$--$3.0$ times faster thanthe exact match routines of the software package {\tt agrep}, which is known as the fastest pattern matching tool.
More Speed and More Pattern Variations for Knowledge Discovery System BONSAI

Bannai Hideo, Iida Keisuke, Shinohara Ayumi, Takeda Masayuki, Miyano Satoru

Genome Informatics　12　454-455　2001年
出版者・発行元： Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.12.454 　

ISSN：0919-9454
Discovery Science, 4th International Conference, DS 2001, Washington, DC, USA, November 25-28, 2001, Proceedings 査読有り

Discovery Science 2001　2226　2001年
出版者・発行元： Springer
DOI： 10.1007/3-540-45650-3 　
Construction of the CDAWG for a Trie. 査読有り

Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa

Proceedings of the Prague Stringology Conference 2001, Prague, Czech Republic, September 4, 2001　37-48　2001年
出版者・発行元： Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University
Musical sequence comparison for melodic and rhythmic similarities 査読有り

T Kadota, M Hirao, A Ishino, M Takeda, A Shinohara, F Matsuo

EIGHTH SYMPOSIUM ON STRING PROCESSING AND INFORMATION RETRIEVAL, PROCEEDINGS　111-122　2001年

DOI： 10.1109/SPIRE.2001.989744 　
On-line construction of symmetric Compact Directed Acyclic Word Graphs 査読有り

S Inenaga, H Hoshino, A Shinohara, M Takeda, S Arikawa

EIGHTH SYMPOSIUM ON STRING PROCESSING AND INFORMATION RETRIEVAL, PROCEEDINGS　96-110　2001年

DOI： 10.1109/SPIRE.2001.989743 　
Fragmentary pattern matching: Complexity, algorithms and applications for analyzing classic literary works 査読有り

H Hori, S Shimozono, M Takeda, A Shinohara

ALGORITHMS AND COMPUTATION, PROCEEDINGS　2223　719-730　2001年

DOI： 10.1007/3-540-45678-3_61 　

ISSN：0302-9743
A Practical Algorithm to Find the Best Episode Patterns. 査読有り

Masahiro Hirao, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa

Discovery Science, 4th International Conference, DS 2001, Washington, DC, USA, November 25-28, 2001, Proceedings　435-440　2001年
出版者・発行元： Springer
DOI： 10.1007/3-540-45650-3_37 　
Discovering Repetitive Expressions and Affinities from Anthologies of Classical Japanese Poems. 査読有り

Koichiro Yamamoto, Masayuki Takeda, Ayumi Shinohara, Tomoko Fukuda, Ichiro Nanri

Discovery Science, 4th International Conference, DS 2001, Washington, DC, USA, November 25-28, 2001, Proceedings　416-428　2001年
出版者・発行元： Springer
DOI： 10.1007/3-540-45650-3_35 　
Compressed pattern matching for SEQUITUR 査読有り

S Mitarai, M Hirao, T Matsumoto, A Shinohara, M Takeda, S Arikawa

DCC 2001: DATA COMPRESSION CONFERENCE, PROCEEDINGS　469-478　2001年

DOI： 10.1109/DCC.2001.917178 　

ISSN：1068-0314
Faster approximate string matching over compressed text 査読有り

G Navarro, T Kida, M Takeda, A Shinohara, S Arikawa

DCC 2001: DATA COMPRESSION CONFERENCE, PROCEEDINGS　459-468　2001年

DOI： 10.1109/DCC.2001.917177 　

ISSN：1068-0314
Multiple Pattern Matching Algorithms on Collage System. 査読有り

Takuya Kida, Tetsuya Matsumoto, Masayuki Takeda, Ayumi Shinohara, Setsuo Arikawa

Combinatorial Pattern Matching, 12th Annual Symposium, CPM 2001 Jerusalem, Israel, July 1-4, 2001 Proceedings　193-206　2001年
出版者・発行元： Springer
DOI： 10.1007/3-540-48194-X_18 　
On-Line Construction of Compact Directed Acyclic Word Graphs. 査読有り

Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Giancarlo Mauri, Giulio Pavesi

Combinatorial Pattern Matching, 12th Annual Symposium, CPM 2001 Jerusalem, Israel, July 1-4, 2001 Proceedings　169-180　2001年
出版者・発行元： Springer
DOI： 10.1007/3-540-48194-X_16 　
Finding Sparse Gene Networks

Shinohara Ayumi, Iida Keisuke, Takeda Masayuki, Maruyama Osamu, Miyano Satoru, Kuhara Satoru

Genome Informatics　11　249-250　2000年
出版者・発行元： Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.11.249 　

ISSN：0919-9454
Bit-parallel approach to approximate string matching in compressed texts 査読有り

T Matsumoto, T Kida, M Takeda, A Shinohara, S Arikawa

SPIRE 2000: SEVENTH INTERNATIONAL SYMPOSIUM ON STRING PROCESSING AND INFORMATION RETRIEVAL - PROCEEDINGS　221-228　2000年

DOI： 10.1109/SPIRE.2000.878198 　
Online construction of subsequence automata for multiple texts 査読有り

H Hoshino, A Shinohara, M Takeda, S Arikawa

SPIRE 2000: SEVENTH INTERNATIONAL SYMPOSIUM ON STRING PROCESSING AND INFORMATION RETRIEVAL - PROCEEDINGS　146-152　2000年

DOI： 10.1109/SPIRE.2000.878190 　
Fully compressed pattern matching algorithm for balanced straight-line programs 査読有り

M Hirao, A Shinohara, M Takeda, S Arikawa

SPIRE 2000: SEVENTH INTERNATIONAL SYMPOSIUM ON STRING PROCESSING AND INFORMATION RETRIEVAL - PROCEEDINGS　132-138　2000年

DOI： 10.1109/SPIRE.2000.878188 　
A Practical Algorithm to Find the Best Subsequence Patterns. 査読有り

Masahiro Hirao, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa

Discovery Science, Third International Conference, DS 2000, Kyoto, Japan, December 4-6, 2000, Proceedings　141-154　2000年
出版者・発行元： Springer
DOI： 10.1007/3-540-44418-1_12 　
A Boyer-Moore type algorithm for compressed pattern matching 査読有り

Y Shibata, T Matsumoto, M Takeda, A Shinohara, S Arikawa

COMBINATORIAL PATTERN MATCHING　1848　181-194　2000年

DOI： 10.1007/3-540-45123-4_17 　

ISSN：0302-9743
Speeding up pattern matching by text compression 査読有り

Y Shibata, T Kida, S Fukamachi, M Takeda, A Shinohara, T Shinohara, S Arikawa

ALGORITHMS AND COMPLEXITY　1767　306-315　2000年

DOI： 10.1007/3-540-46521-9_25 　

ISSN：0302-9743
Polynomial-time learning of elementary formal systems 査読有り

S Miyano, A Shinohara, T Shinohara

NEW GENERATION COMPUTING　18　(3)　217-242　2000年

DOI： 10.1007/BF03037530 　

ISSN：0288-3635
A System to Find Genetic Networks Using Weighted Network Model

Moriyama Tomohiro, Shinohara Ayumi, Takeda Masayuki, Maruyama Osamu, Goto Takao, Miyano Satoru, Kuhara Satoru

Genome Informatics　10　186-195　1999年
出版者・発行元： Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.10.186 　

ISSN：0919-9454

詳細を見る詳細を閉じる

We are developing a system which finds a genetic network from data obtained by multiple gene disruptions and overexpressions. We deal with a genetic network as a weighted graph, where each weight represents the strength of activation from a gene to another gene. In this paper, we explain the overview of our system, and our strategy to visualize the weighted network. Wealso study the computational complexity related to the visualization.
A unifying framework for compressed pattern matching 査読有り

Takuya Kida, Yusuke Shibata, Masayuki Takeda, Ayumi Shinohara, Setsuo Arikawa

String Processing and Information Retrieval Symposium and International Workshop on Groupware, SPIRE 1999 and CRIWG 1999　89-96　1999年
出版者・発行元： Institute of Electrical and Electronics Engineers Inc.
DOI： 10.1109/SPIRE.1999.796582 　
Knowledge discovery from health data using weighted aggregation classifier 査読有り

T Takae, M Chikamune, H Arimura, A Shinohara, H Inoue, S Takeya, K Uezono, T Kawasaki

DISCOVERY SCIENCE, PROCEEDINGS　1721　359-361　1999年

DOI： 10.1007/3-540-46846-3_48 　

ISSN：0302-9743
Pattern matching in text compressed by using antidictionaries 査読有り

Yusuke Shibata, Masayuki Takeda, Ayumi Shinohara, Setsuo Arikawa

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　1645　37-49　1999年
出版者・発行元： Springer Verlag
DOI： 10.1007/3-540-48452-3_3 　

ISSN：1611-3349 0302-9743
Shift-and approach to pattern matching in LZW compressed text 査読有り

Takuya Kida, Masayuki Takeda, Ayumi Shinohara, Setsuo Arikawa

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　1645　1-13　1999年
出版者・発行元： Springer Verlag
DOI： 10.1007/3-540-48452-3_1 　

ISSN：1611-3349 0302-9743
On the hardness of approximating the minimum consistent acyclic DFA and decision diagram 査読有り

S Shimozono, K Hirata, A Shinohara

INFORMATION PROCESSING LETTERS　66　(4)　165-170　1998年5月

DOI： 10.1016/S0020-0190(98)00065-9 　

ISSN：0020-0190

eISSN：1872-6119
Finding tree patterns consistent with positive and negative examples using queries 査読有り

H Ishizaka, H Arimura, T Shinohara

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE　23　(1-2)　101-115　1998年

ISSN：1012-2443

eISSN：1573-7470
Finding Genetic Network from Experiments by Weighted Network Model

Noda Kiyoshi, Shinohara Ayumi, Takeda Masayuki, Matsumoto Satoshi, Miyano Satoru, Kuhara Satoru

Genome Informatics　9　141-150　1998年
出版者・発行元： Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.9.141 　

ISSN：0919-9454

詳細を見る詳細を閉じる

We study the problem of finding a genetic network from data obtained by multiple gene disruptions and overexpressions. We define a genetic network as a weighted graph, and analyze the computational complexity of the problem. We show that if there exists a weighted network which is consistent with given data, we can find it in polynomial time. Moreover, we also consider the optimization problem, where we try to find an optimally consistent weighted network with given data. We show that the problem is NP-hard. On the other hand, we give a polynomial-time approximation algorithm to solve it with approximation ratio 2. We report some simulation results on experiments.
Uniform characterizations of polynomial-query learnabilities 査読有り

Y Hayashi, S Matsumoto, A Shinohara, M Takeda

DISCOVERY SCIENCE　1532　84-92　1998年

DOI： 10.1007/3-540-49292-5_8 　

ISSN：0302-9743
Multiple pattern matching in LZW compressed text 査読有り

T Kida, M Takeda, A Shinohara, M Miyazaki, S Arikawa

DCC '98 - DATA COMPRESSION CONFERENCE　103-112　1998年

DOI： 10.1109/DCC.1998.672136 　

ISSN：1068-0314
Learning Pattern Languages Using Queries. 査読有り

Satoshi Matsumoto, Ayumi Shinohara

Computational Learning Theory, Third European Conference, EuroCOLT '97, Jerusalem, Israel, March 17-19, 1997, Proceedings　185-197　1997年
出版者・発行元： Springer
DOI： 10.1007/3-540-62685-9_16 　
An improved pattern matching algorithm for strings in terms of straight-line programs 査読有り

M Miyazaki, A Shinohara, M Takeda

COMBINATORIAL PATTERN MATCHING, PROCEEDINGS　1264　1-11　1997年

DOI： 10.1007/3-540-63220-4_45 　

ISSN：0302-9743
An Efficient Pattern-Matching Algorithm for Strings with Short Descriptions. 査読有り

Marek Karpinski, Wojciech Rytter, Ayumi Shinohara

Nord. J. Comput.　4　(2)　172-186　1997年
HAKKE: A Multi-Strategy Prediction System for Sequences

Furukawa Naohiro, Matsumoto Satoshi, Shinohara Ayumi, Shoudai Takayoshi, Miyano Satoru

Genome Informatics　7　98-107　1996年
出版者・発行元： Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.7.98 　

ISSN：0919-9454

詳細を見る詳細を閉じる

We developed a machine learning system HAKKE which is suitable for predicting functional regions from sequences, such as protein-coding region prediction, and transmembrane domain prediction. HAKKE is a hybrid system cooperated by a number of algorithms of a pool to make an accurate prediction. The system uses an extension of the weighted majority algorithm in order to fit the strength of each algorithm into given training examples. In this paper, we describe the core of the system and show some experimental results on transmembrane domain and a-helix predictions.
On the Hardness of Approximating the Minimum Consistent OBDD Problem. 査読有り

Kouichi Hirata, Shinichi Shimozono, Ayumi Shinohara

Algorithm Theory - SWAT '96, 5th Scandinavian Workshop on Algorithm Theory, Reykjavík, Iceland, July 3-5, 1996, Proceedings　96　(45)　112-123　1996年
出版者・発行元： Springer
DOI： 10.1007/3-540-61422-2_125 　

詳細を見る詳細を閉じる

順序付き二分決定グラフ(OBDD)は, 論理関数の有向グラフによる効果的な表現である. 無矛盾最小OBDD問題とは, ある論理関数について与えられた不完全な真偽値表から, その表に無矛盾かつ最小のOBDDを求める問題である. 本稿では, 任意に固定された変数順序について, この問題が計算量的に困難なことを示す. また, P≠NPの仮定の下では, n変数のとき常に最小サイズのn^ε倍以下のOBDDを出力するような多項式時間近似アルゴリズムがこの問題に対して存在しない, そのような定数ε>0があることを示す.
Pattern-matching for strings with short descriptions 査読有り

M Karpinski, W Rytter, A Shinohara

COMBINATORIAL PATTERN MATCHING　937　(22)　205-214　1995年

ISSN：0302-9743
Developments in Computational Learning and Discovery Theory within the Framework of Elementary Formal Systems. 査読有り

Setsuo Arikawa, Masako Sato, Ayumi Shinohara, Takeshi Shinohara

Machine Intelligence 15, Intelligent Agents [St. Catherine's College, Oxford, UK, July 1995]　15　227-247　1995年
出版者・発行元： Oxford University Press
BONSAI Garden: Parallel Knowledge Discovery System for Amino Acid Sequences. 査読有り

Takayoshi Shoudai, Michael Lappe, Satoru Miyano, Ayumi Shinohara, Takeo Okazaki, Setsuo Arikawa, Tomoyuki Uchida, Shinichi Shimozono, Takeshi Shinohara, Satoru Kuhara

Proceedings of the Third International Conference on Intelligent Systems for Molecular Biology, Cambridge, United Kingdom, July 16-19, 1995　359-366　1995年
出版者・発行元： AAAI
Pattern-matching for strings with short descriptions 査読有り

M Karpinski, W Rytter, A Shinohara

COMBINATORIAL PATTERN MATCHING　937　205-214　1995年

DOI： 10.1007/3-540-60044-2_44 　

ISSN：0302-9743
COMPLEXITY OF COMPUTING VAPNIK-CHERVONENKIS DIMENSION AND SOME GENERALIZED DIMENSIONS 査読有り

A SHINOHARA

THEORETICAL COMPUTER SCIENCE　137　(1)　129-144　1995年1月

DOI： 10.1016/0304-3975(94)00164-E 　

ISSN：0304-3975
学位論文審査報告

有村博紀, 篠原歩, 宮川英明, 沖田茂, 松野浩嗣

九州大学大学院総合理工学報告　16　(3)　359-368　1994年12月1日
出版者・発行元：九州大学大学院総合理工学研究科
DOI： 10.15017/17351 　

ISSN：0388-1717
Assignment of Certainty-Factor Parameters with a Given Reasoning Tree for the Prediction of Protein Localization Sites

中井謙太, 篠原歩, 宮野悟

Genome Informatics　5　170-171　1994年
出版者・発行元： Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.5.170 　

ISSN：0919-9454

詳細を見る詳細を閉じる

In this age of large-scale sequencing, we have many "potentially expressed" amino acidsequences of unknown function. Characterization of such sequences by computers is undoubtedlyuseful for further experimental analyses. We have developed a knowledge-based system PSORT for characterizing various sorting signals potentially coded in amino acid sequences andfor predicting their final localization sites in cells [1, 2]. The system calculates the probability (certainty factor) of an input protein to be localized at each candidate site. One of the difficultiesof our system is that, since it has many adjustable parameters, optimization of them toa given training data is difficult. Therefore, incorporation of recent knowledge into the systemhas not been easy. We present here a simple scheme for assigning certainty-factor parameters with a given reasoning tree. Since the size of training data, i. e., sequences of known localization sites, is not large inmost cases, we must suppress the number of parameters as possible. In this case, use of ourknowledge on the reasoning flow is favorable. Such a flow can be organized into a reasoningtree, in which an input flux is divided into thinner flows on a step-by-step basis according tosome characteristic values calculated from the input sequence (Fig. 1). Its final outputs areflows corresponding to candidate localization sites. In this stage, the amount of each flow can beinterpreted as the corresponding certainty factor. Thus, the problem is how to find appropriate functions that transform a characteristic value at each step in an optimized performance forthe classification of training data. We used the following formula for that function: F_p (x_p (i)) =1/1+exp (-10×(x_p (i)-b_p)) where x_p (i) represents a characteristic value of a sequence i at the step p, e.g., propensitythat the input sequence i encodes a membrane protein, and b_p is a threshold value which isobtained by the criterion that can classify the training data at step p with least mistakes.The certainty factor for localizing a candidate site is thus calculated as a probability to choosethe corresponding path, e.g., the certainty factor for a protein i to localize at the site #3 isF₁ (i)×F₂ (i)×(1-F₄ (i)) in Fig. 1. To test the validity of our model, we prepared 156 sequences of Bacillus subtilis whoselocalization sites are the prediction results of PSORT. The cross-validation test showed rathergood result. Thus, although there is no theoretical proof that our model always gives goodresults, it will be hopefully used for future improvement of PSORT. Moreover, because of itssimplicity, this method may be generally used to interpret unknown sequence data with the latest knowledge of molecular cell biology.
Machine Learning and Discovery for Bloinformatics: Introduction. 査読有り

Satoru Miyano, Ayumi Shinohara

27th Annual Hawaii International Conference on System Sciences (HICSS-27), January 4-7, 1994, Maui, Hawaii, USA　111-112　1994年
出版者・発行元： IEEE Computer Society
Complexity of Computing Generalized VC-Dimensions. 査読有り

Ayumi Shinohara

Machine Learning: ECML-94, European Conference on Machine Learning, Catania, Italy, April 6-8, 1994, Proceedings　415-418　1994年
出版者・発行元： Springer
DOI： 10.1007/3-540-57868-4_87 　
Refutably Probably Approximately Correct Learning. 査読有り

Satoshi Matsumoto, Ayumi Shinohara

Algorithmic Learning Theory, 4th International Workshop on Analogical and Inductive Inference, AII '94, 5th International Workshop on Algorithmic Learning Theory, ALT '94, Reinhardsbrunn Castle, Germany, October 10-15, 1994, Proceedings　469-483　1994年
出版者・発行元： Springer
DOI： 10.1007/3-540-58520-6_84 　
Finding alphabet indexing for decision trees over regular patterns: An approach to bioinformatical knowledge acquisition

Shinichi Shimozono, Ayumi Shinohara, Takeshi Shinohara, Satoru Miyano, Satoru Kuhara, Setsuo Arikawa

Proceedings of the Annual Hawaii International Conference on System Sciences　1　763-772　1993年
出版者・発行元： IEEE Computer Society
DOI： 10.1109/HICSS.1993.270664 　

ISSN：1530-1605
Running Learning Systems in Parallel for Machine Discovery from Sequences

篠原歩, 宮野悟, 有川節夫, 下薗真一, 内田智之, 久原哲

Genome Informatics　4　74-83　1993年
出版者・発行元： Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.4.74 　

ISSN：0919-9454

詳細を見る詳細を閉じる

We have developed a machine learning system BONSAI which gets positive and negative examples as inputs and produces a pair of a decision tree over regular patterns and an alphabet indexing as a hypothesis. This paper proposes two applications of BONSAI when we can run multiple BONSAI systems in parallel. The one is to classify given examples which are coming from several different unknown classes. The process of solving the problem consists of multiply spawned BONSAI systems, each of which tries to find a decision tree, an alphabet indexing and a group of examples. It will finally partition a hodgepodge of sequences into a small number of disjoint classes together with hypotheses explaining these classes accurately. The other is to find a good sample of a concept. Though the main interest of applying the BONSAI system is to discover good hypotheses, it is equally interesting to find a small set of examples from which a good hypothesis is made. We present a method for solving this problem by combining a strategy in genetic algorithms with multiply running BONSAI systems.
Complexity of Computing Vapnik-Chervonenkis Dimension. 査読有り

Ayumi Shinohara

Algorithmic Learning Theory, 4th International Workshop, ALT '93, Tokyo, Japan, November 8-10, 1993, Proceedings　279-287　1993年
出版者・発行元： Springer
DOI： 10.1007/3-540-57370-4_54 　
A MACHINE DISCOVERY FROM AMINO-ACID-SEQUENCES BY DECISION TREES OVER REGULAR PATTERNS 査読有り

S ARIKAWA, S MIYANO, A SHINOHARA, S KUHARA, Y MUKOUCHI, T SHINOHARA

NEW GENERATION COMPUTING　11　(3-4)　361-375　1993年

DOI： 10.1007/BF03037183 　

ISSN：0288-3635
ALGORITHMIC LEARNING-THEORY WITH ELEMENTARY FORMAL SYSTEMS 査読有り

S ARIKAWA, S MIYANO, A SHINOHARA, T SHINOHARA, A YAMAMOTO

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS　E75D　(4)　405-414　1992年7月

ISSN：0916-8532
Knowledge Acquisition from Amino Acid Sequences by Decision Trees and Indexing

宮野悟, 篠原歩, 有川節夫, 下薗真一, 篠原武, 久原哲

Genome Informatics　3　69-72　1992年
出版者・発行元： Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.3.69 　

ISSN：0919-9454

詳細を見る詳細を閉じる

We present a machine learning system for knowledge acquisition that produces hypotheses from positive and negative examples, and report some experiments on protein data using the PIR and Gen Bank databases. This learning system is developed with an algorithmic learning theory for decision trees over regular patterns, which we newly devised for this research. In the experiments on transmembrane domain identification, the system discovered very simple hypotheses with very high accuracy from a small number of positive and negative examples. These hypotheses show that negative motifs, namely, motifs of negative data, play a key role in such classification. In these experiments, we classified 20 symbols of amino acid residues into 3 categories according to the hydropathy indices due to Kyte and Doolittle. We call such transformation of symbols an indexing. We observed that the indexing by the hydropathy indices is important in making the learning algorithm efficient and accurate. This observation inspired us with a desire to discover such an indexing itself just by a learning algorithm. We succeeded in it by combining the above learning algorithm and the local search technique for finding good indexings. We also report some experiments on signal peptides. We have implemented this learning system, called BONSAI, which shall be presented at the Computer Demonstration Session during this workshop.
A MACHINE DISCOVERY FROM AMINO-ACID-SEQUENCES BY DECISION TREES OVER REGULAR PATTERNS 査読有り

S ARIKAWA, S KUHARA, S MIYANO, Y MUKOUCHI, A SHINOHARA, T SHINOHARA

FIFTH GENERATION COMPUTER SYSTEMS 1992, VOLS 1 AND 2　618-625　1992年
Which classes of elementary formal systems are polynomial-time learnable.

Satoru Miyano, Ayumi Shinohara, Takeshi Shinohara

Algorithmic Learning Theory(ALT)　139-150　1991年
出版者・発行元： Ohmsha
Machine Discovery of a Negative Motif

有川節夫, 久原哲, 宮野悟, 篠原歩, 篠原武

Genome Informatics　2　62-65　1991年
出版者・発行元： Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.2.62 　

ISSN：0919-9454
A Text Database Management System SIGMA and Its Applications to Analyzing the Genetic Information

篠原武, 有川節夫, 久原哲, 宮原哲浩, 井上仁, 篠原歩, 内田智之

Genome Informatics　2　28-32　1991年
出版者・発行元： Japanese Society for Bioinformatics
DOI： 10.11234/gi1990.2.28 　

ISSN：0919-9454

詳細を見る詳細を閉じる

SIGMAは, 著者らが開発し九州大学大型計算機センターで1981年から公開しているテキストデータペース管理システムであり, フルテキストデータベースの高速検索に活用されている. ゲノムデータベースは, 複雑なフォーマットを有し, 長大な配列情報を含むため, テキストデータペース化しフルテキストサーテを行うことは, ゲノム解析に有効である. 簡単なデータ変換を行うことにより, 遺伝子塩基配列データベースGen Bank, タンパク質アミノ酸配列データベースPIRを, SIGMAで管理・検索できることを確認したので報告する.
More About Learning Elementary Formal Systems. 査読有り

Setsuo Arikawa, Takeshi Shinohara, Satoru Miyano, Ayumi Shinohara

Nonmonotonic and Inductive Logic, Second International Workshop, Reinhardsbrunn Castle, Germany, December 2-6, 1991, Proceedings　107-117　1991年
出版者・発行元： Springer
DOI： 10.1007/BFb0030388 　
Teachability in Computational Learning. 査読有り

Ayumi Shinohara, Satoru Miyano

Algorithmic Learning Theory, First International Workshop, ALT '90, Tokyo, Japan, October 8-10, 1990, Proceedings　247-255　1990年
出版者・発行元： Springer/Ohmsha
TEACHABILITY IN COMPUTATIONAL LEARNING 査読有り

A SHINOHARA, S MIYANO

NEW GENERATION COMPUTING　8　(4)　337-347　1990年

DOI： 10.1007/BF03037091 　

ISSN：0288-3635

︎全件表示 ︎最初の5件までを表示

MISC 93

実用的なサイバー救助犬スーツの開発-サイバー救助犬スーツの熱対策・傾き対策・軽量化・小型化-

西野間洋之, 大野和則, 大野和則, 濱田龍之介, 星達也, BEOKHAIMOOK Chayapol, 篠原歩, 田所諭

日本機械学会ロボティクス・メカトロニクス講演会講演論文集(CD-ROM)　2019　2019年

ISSN： 2424-3124
慣性センサに基づく災害救助犬の行動推定・可視化システムの開発

三浦樹, 川又周, 清水俊汰, 五十嵐祐貴, 中鉢魁三郎, 成定真太郎, 益子直, 山口竣平, 星達也, 濱田龍之介, 吉仲亮, 大野和則, 篠原歩, 徳山豪

日本機械学会ロボティクス・メカトロニクス講演会講演論文集(CD-ROM)　2018　ROMBUNNO.2A2‐K01　2018年6月1日
「手応え関数」の自動生成に基づく自律分散制御則の設計~一次元這行運動を用いた検証~

佐藤光暁, 脇本竜, 加納剛史, 篠原歩, 石黒章夫

日本機械学会ロボティクス・メカトロニクス講演会講演論文集(CD-ROM)　2018　ROMBUNNO.1P1‐D18　2018年6月1日
Query Learning of Residual Symbolic Automata

Chubachi, K, Diptarama, H, Yoshinaka, R, Shinohara, A

Work in Progress Track, ICGI 2018　2018年
慣性センサに基づく災害救助犬の行動推定

成定真太郎, 益子直, 清水俊汰, 大堀優, 菅原啓介, 佐久間俊平, 佐藤市也, 上木庸平, 濱田龍之介, 山口竣平, 星達也, 大野和則, 吉仲亮, 篠原歩, 徳山豪

日本機械学会ロボティクス・メカトロニクス講演会講演論文集(CD-ROM)　2017　ROMBUNNO.2A1‐Q04-Q04　2017年5月9日
出版者・発行元：一般社団法人日本機械学会
DOI： 10.1299/jsmermd.2017.2A1-Q04 　

詳細を見る詳細を閉じる

We propose an underlying system that can infer and visualize search and rescue (SAR) dogs' behavior. The system is aimed at identifying "run", "walk", "stop", "sniff" and "bark" behaviors of SAR dogs robustly from inertial sensors data, and visualizing the results for the users. In the system, we apply Short-Time Fourier Transform (STFT) to the sensors data, and use a random forest algorithm for learning investigation activities of SAR dogs. We performed an experiment on our system and got the results that some behaviors can be identified precisely. We also developed an on-line visualization system for streaming data of behavior probabilities.
順序同型な部分系列を用いた数値列に対する最長共通部分列問題

栗原理聡, 成澤和志, 篠原歩

電子情報通信学会技術研究報告　115　(510(COMP2015 37-39))　11‐20-20　2016年3月7日
出版者・発行元：電子情報通信学会
ISSN： 0913-5685
順序保存カーネルを用いた時系列データ分類

柏葉祐輝, 成澤和志, 篠原歩

人工知能学会人工知能基本問題研究会資料　99th　1‐6　2016年1月20日
部分文字列数え上げ圧縮法の効率的な実現の一般化多値化とフェーズの導入

佐久間俊平, 成澤和志, 篠原歩

電子情報通信学会技術研究報告　115　(205(COMP2015 16-21))　13-20　2015年8月25日

ISSN： 0913-5685
順序保存符号化n‐gramの高速な出現頻度計算手法

佐藤雄介, 成澤和志, 篠原歩

情報処理学会研究報告(Web)　2015　(AL-151)　VOL.2015-AL-151,NO.1 (WEB ONLY)-8　2015年1月6日
出版者・発行元：一般社団法人情報処理学会
ISSN： 0919-6072

詳細を見る詳細を閉じる

順序保存照合問題とは，与えられた系列に対し順序関係を保存する符号化を施し，等しい順序関係をもつ部分系列を照合する問題である．本論文では，順序保存符号化 n-gram の出現頻度を高速に計算するアルゴリズムを提案する．また，系列や n-gram の長さに対する依存が少ない文字オラクルとして，ウェーブレット木を用いた O(logσ) 時間文字オラクルを提案する．さらに計算機実験によって提案アルゴリズムの優位性を確認する．
マルチトラック文字列上の順列パターン照合のための省メモリな索引構造

桂敬史, 大友雄平, 成澤和志, 篠原歩

電子情報通信学会技術研究報告　114　(199(COMP2014 15-24))　1-8　2014年8月26日

ISSN： 0913-5685
接頭辞集合に対する決定性有限オートマトンの最小無矛盾問題について

上埜かおり, 下薗真一, 成澤和志, 篠原歩

電子情報通信学会技術研究報告　113　(371(COMP2013 38-59))　115-122　2013年12月13日

ISSN： 0913-5685
状態遷移確率と報酬確率の転移による強化学習のサンプル量削減

小國晃太, 成澤和志, 篠原歩

電子情報通信学会技術研究報告　113　(286(IBISML2013 36-66))　139-146　2013年11月5日

ISSN： 0913-5685
一般化三並べの拡張: 一手p石

ディプタラマ, 成澤和志, 篠原歩

ゲームプログラミングワークショップ2013論文集　19-26　2013年11月1日
高階圧縮の高速化と効率の良い符号化

矢口和也, 小林直樹, 篠原歩

電子情報通信学会技術研究報告　113　(252(COMP2013 32-37))　13-20　2013年10月11日
出版者・発行元：一般社団法人電子情報通信学会
ISSN： 0913-5685

詳細を見る詳細を閉じる

高階圧縮とは,与えられたデータを生成する高階関数型プログラムを構成する圧縮法であり,圧縮したままのデータ操作が可能であるという文法圧縮の利点を持つと同時に,従来手法では扱えないパターンの発見や高い圧縮率が期待される.本論文では、高階圧縮の既存研究では未解決であった(1)高速な圧縮アルゴリズムおよび(2)高階関数型プログラムのビット列への簡潔な符号化方法を提案し,その有効性を実験的に示す.
SATソルバを用いた学位論文審査の時間割作成システムの試作

奥田遼介, 小松智希, 石黒裕也, 柏葉祐輝, 成澤和志, 篠原歩

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集　2013　232-233　2013年9月11日
出版者・発行元：公益社団法人日本オペレーションズ・リサーチ学会
ISSN： 1883-1893
文字列に含まれる連の最大指数和の解析 n=57までの厳密値と新たな下界2.03696の発見

草野一彦, 奥田遼介, 成澤和志, 篠原歩

電子情報通信学会技術研究報告　113　(14(COMP2013 1-8))　17-24　2013年4月17日
出版者・発行元：一般社団法人電子情報通信学会
ISSN： 0913-5685

詳細を見る詳細を閉じる

連とは,文字列に含まれる周期的な部分文字列であり,その周期性が左右に延長不可能なものをいう.近年,長さnの文字列に含まれる連の最大数についての研究が活発になされている.本論文では,連の数え方の一つである指数和に着目し,長さnのバイナリ文字列に含まれる連の指数和の最大値σ_2(n)について,枝刈りを用いて計算を高速化することにより得られたn=57までの計算結果を示す.また,連の指数和の最大値σ(n)について,これまでに知られている最良の下界は2.03525nであったが,我々は文字列を生成する準同型写像を探索することにより,新たな下界2.03696nを発見した.
マルチトラックデータ上の近似順列パターン照合と索引構造

大田裕之, 桂敬史, 成澤和志, 篠原歩

電子情報通信学会技術研究報告　113　(14(COMP2013 1-8))　9-16　2013年4月17日
出版者・発行元：一般社団法人電子情報通信学会
ISSN： 0913-5685

詳細を見る詳細を閉じる

複数の系列からなるデータをマルチトラックと呼び,マルチトラック上で,各系列の入れ替えを許して行うパターン照合を順列パターン照合と呼ぶ.数値列で表されるトラック長n,トラック数Nのマルチトラックテキストに対し,トラック長m,トラック数Mのマルチトラックパターンが与えられたとき,トラック間のユークリッド距離が閾値以下のとき一致するとみなす近似順列パターン照合問題を考える.本論文では,近似順列パターン照合問題を高速に解くためのデータ構造であるLoFT,およびLoFTを用いた近似順列パターン照合問題に対する確率的パターン照合アルゴリズムを提案する.また,LoFTの性能および精度を実験的に評価する.
種々のパターン照合問題に対するポジションヒープの構築

大友雄平, 成澤和志, 篠原歩

電子情報通信学会技術研究報告　112　(340(COMP2012 43-51))　7-14　2012年12月3日

ISSN： 0913-5685
組込環境用プロセス仮想マシンの実装とETロボコンへの適用

奥田遼介, 成澤和志, 篠原歩

電気学会制御研究会資料　CT-12　(24.26-29)　9-14　2012年12月1日
出版者・発行元：電気学会
実ロボット自動テストシステムSATORI2を用いた難所戦略の妥当性の検証

大井雄介, DIPTARAMA, 奥田遼介, 桂敬史, 成澤和志, 篠原歩

電気学会制御研究会資料　CT-12　(24.26-29)　15-20　2012年12月1日
出版者・発行元：電気学会
圧縮文字列に対する省メモリなパターンマッチアルゴリズム

相原高雄, 篠原歩, 成澤和志

電子情報通信学会技術研究報告　112　(272(COMP2012 34-42))　17-24　2012年10月24日
出版者・発行元：一般社団法人電子情報通信学会
ISSN： 0913-5685

詳細を見る詳細を閉じる

本論文では,テキストとパターンがいずれも直線的プログラム(Straight-Line Program:SLP)を用いて圧縮されているとき,それらに対しパターンマッチを行う確率的アルゴリズムを提案する.我々はまずSchmidt-Schaussらの確率的等価性判定法を拡張することにより,関数FirstMismatchを新しい方法で確率的に実現する.FirstMismatchとは,テキストの非終端記号とパターンの非終端記号を与えられた位置から照合したときの最初の相違位置を返す関数である.FirstMismatchの新しい実現法をMiyazakiらのパターンマッチ手法と組み合わせることで,計算時間O(n(n log N+m log M)log M),計算領域O(n log N+m log M)でのパターンマッチを実現する.ここでn,mはテキストとパターンを表すSLPのサイズであり,N,Mはテキストとパターンの文字列長である.Jezらに提案されたアルゴリズムと比較すると,計算時間は劣るが計算領域が小さいため,使用できる領域が限られている場合に有効な手法である.
マルチトラック文字列の順列パターン照合と索引構造

桂敬史, 成澤和志, 篠原歩, 坂内英夫, 稲永俊介

電子情報通信学会技術研究報告　112　(199(COMP2012 26-33))　1-8　2012年8月27日

ISSN： 0913-5685
役を構成するゲームに対する効率的な行動決定アルゴリズムの提案

小松智希, 成澤和志, 篠原歩

情報処理学会研究報告(CD-ROM)　2012　(2)　ROMBUNNO.GI-28,NO.8　2012年8月15日

ISSN： 2186-2583
覆面算を解析するためのオートマトン理論的アプローチ

遠藤洋, 成澤和志, 篠原歩

情報処理学会シンポジウム論文集　2011　(6)　54-61　2011年10月28日

ISSN： 1344-0640
イベント列データにおけるVLDCエピソード生成モデル

棚橋広亮, 成澤和志, 篠原歩

人工知能学会人工知能基本問題研究会資料　82nd　63-68　2011年7月25日
実ロボットの自律学習を支援する統合分析環境:SATORI

斎藤淳哉, 桂敬史, 一井宏次, 伊東裕二, 可児輝之, 棚橋広亮, 成澤和志, 篠原歩

人工知能学会人工知能基本問題研究会資料　82nd　37-42　2011年7月25日
DS-1-12 文字列に含まれる連構造(DS-1.COMP学生シンポジウム,シンポジウムセッション)

松原渉, 篠原歩

電子情報通信学会総合大会講演論文集　2011　(1)　"S-23"-"S-24"　2011年2月28日
出版者・発行元：一般社団法人電子情報通信学会
文字列に含まれる連構造

松原渉, 篠原歩

電子情報通信学会大会講演論文集　2011　S.23-S.24　2011年2月28日

ISSN： 1349-1369
半導体歩留り解析に回帰木分析を適用するための仮説検証手法の提案

津田英隆, 白井英大, 寺邊正大, 橋本和夫, 篠原歩

電気学会情報システム研究会資料　IS-10　(73-75.77-82)　11-17　2010年11月26日
立体ピクロスはNP完全

草野一彦, 成澤和志, 篠原歩

ゲームプログラミングワークショップ2010論文集　2010　(12)　108-113　2010年11月12日

詳細を見る詳細を閉じる

立体ピクロスとは任天堂が2009年に発売した同名のゲームに収録されているパズルである.問題として立方体のブロックが積み重なった直方体が与えられ,ブロックに描かれたヒントに従って不要なブロックを削り,隠されたカタチを取り出すのが目的である.本稿では,3SATからの帰着により,立体ピクロスの解の存在判定がNP完全であることを示す.また,立体ピクロスの高さを1に制限し,普通数字・丸数字・四角数字を区別しない場合には,解の存在判定が多項式時間で行えることを示す.Picross 3D is a puzzle which is included in the video game with the same title, Nintendo released on 2009. Players are given a rectangular parallelepiped made of cubic blocks and try to take out the hidden object from it breaking unwanted blocks. In this paper, we show that it is NP-complete to decide whether a given Picross 3D has solutions by reducing 3SAT to Picross 3D. We also show that we can decide exsistence of solutions in polynomial time if height of Picross 3D is restricted to 1 and condition of hint numbers is ignored.
信頼区間上限の不確実性サンプリングへの応用

斎藤淳哉, 篠原歩

情報科学技術フォーラム講演論文集　9th　(1)　209-214　2010年8月20日
出版者・発行元： FIT(電子情報通信学会・情報処理学会)運営委員会
非可逆圧縮を用いた類似性指標と画像検索への応用

坂内恒介, 成澤和志, BRODKORB Felix, 篠原歩

情報科学技術フォーラム講演論文集　9th　(1)　215-220　2010年8月20日
出版者・発行元： FIT(電子情報通信学会・情報処理学会)運営委員会

詳細を見る詳細を閉じる

本論文では,非可逆圧縮を用いた類似性指標を提案する.これまでは可逆圧縮を用いた正規圧縮距離(NCD))を類似性指標とする研究が行われてきた.これは,二つの情報が似ていればそれらを連結して圧縮したサイズがそれぞれ単独で圧縮したサイズの合計よりも小さくなるというコルモゴロフ複雑性の定理に基づいている.計算不可能なコルモゴロフ複雑性の代用として可逆圧縮が用いられてきたが,本研究では非可逆圧縮を用いた正規非可逆圧縮距離(NLCD)を定義する.また,フラクタル圧縮がNLCDに最適な非可逆圧縮であることを実験的に確かめ,画像類似検索へ応用する.
2GPUによるCubicセミ・ラグランジュ法の高速化

須藤郁弥, 坂内恒介, 本田耕一, 松田健護, 篠原歩

情報処理学会シンポジウム論文集　2010　(5)　135-136　2010年5月20日

ISSN： 1344-0640
移調を許した圧縮文字列照合アルゴリズム

松原渉, 篠原歩

電子情報通信学会技術研究報告　110　(12(COMP2010 1-9))　39-45　2010年4月15日
出版者・発行元：一般社団法人電子情報通信学会
ISSN： 0913-5685

詳細を見る詳細を閉じる

移調を許したマッチングとは,与えられたテキストとパタンに対して,任意のオフセットを許した移調パタンの出現を発見する問題であり,例として音楽検索が挙げられる.本研究では,移調を一般に文字の置き換え関数としてとらえ,任意の置換が与えられたとき,すべてのパタンを検出する問題について取り組む.入力のテキストとパタンは,文法圧縮の一種である直線的プログラム(SLP)で与えられるものとし,文字列を陽に展開することなく処理を完了する効率の良いアルゴリズムを与える.
基本形式体系に対する非終端記号の導入

小出智彦, 篠原歩

電子情報通信学会技術研究報告　110　(12(COMP2010 1-9))　47-54　2010年4月15日
出版者・発行元：一般社団法人電子情報通信学会
ISSN： 0913-5685

詳細を見る詳細を閉じる

基本形式体系は,文字列を対象した一種の論理プログラムであり,形式言語理論において種々の言語クラスを簡潔に記述することができる.本論文では,基本形式体系に非終端記号を導入することによって生じる言語の記述力についての解析を行う.
文字列に含まれる繰り返し構造の頻度について

草野一彦, 篠原歩

情報処理学会全国大会講演論文集　72nd　(1)　1.409-1.410-410　2010年3月8日
DS-1-6 例数制限付き教示の複雑さ(DS-1.計算理論における学生の研究パワー:COMP学生シンポジウム,シンポジウムセッション)

小林隼人, 篠原歩

電子情報通信学会総合大会講演論文集　2010　(1)　"S-11"-"S-12"　2010年3月2日
出版者・発行元：一般社団法人電子情報通信学会
非終端記号を導入した基本形式体系の言語記述力について

小出智彦, 篠原歩

電子情報通信学会大会講演論文集　2010　(1)　S.9-S.10-9"-"S-10"　2010年3月2日
出版者・発行元：一般社団法人電子情報通信学会
ISSN： 1349-1369
例数制限付き教示の複雑さ

小林隼人, 篠原歩

電子情報通信学会大会講演論文集　2010　S.11-S.12　2010年3月2日

ISSN： 1349-1369
Cell BEを用いた文字列の編集距離計算の高速化

須藤郁弥, 篠原歩

情報処理学会シンポジウム論文集　2009　(5)　98-99　2009年5月21日

ISSN： 1344-0640
文字列の繰り返し構造の平均解析 (理論計算機科学の深化と応用)

草野一彦, 松原渉, 石野明, 篠原歩

数理解析研究所講究録　1649　181-188　2009年5月
出版者・発行元：京都大学
ISSN： 1880-2818
例数制限付き教示の複雑さ (理論計算機科学の深化と応用)

小林隼人, 篠原歩

数理解析研究所講究録　1649　165-172　2009年5月
出版者・発行元：京都大学
ISSN： 1880-2818
置換のランク付けに対する$O$($n$log log$n$)ビット領域の線形時間アルゴリズム (理論計算機科学の深化と応用)

須藤郁弥, 篠原歩

数理解析研究所講究録　1649　173-180　2009年5月
出版者・発行元：京都大学
ISSN： 1880-2818
連を多く含む文字列発見のための探索的手法 (理論計算機科学の深化と応用)

松原渉, 草野一彦, 坂内英夫, 石野明, 篠原歩

数理解析研究所講究録　1649　81-88　2009年5月
出版者・発行元：京都大学
ISSN： 1880-2818
通信規約学習の拡張による協調精度の向上

葛西達也, 小林隼人, 篠原歩

情報処理学会全国大会講演論文集　71st　(2)　2.201-2.202-202　2009年3月10日
平衡直線的プログラムで圧縮された文字列の非反復性検証アルゴリズム

松原渉, 稲永俊介, 篠原歩

電子情報通信学会技術研究報告　108　(443(COMP2008 54-62))　9-16　2009年2月23日
出版者・発行元：一般社団法人電子情報通信学会
ISSN： 0913-5685

詳細を見る詳細を閉じる

平衡直線的プログラム(Balanced Straight line program,BSLP)は単元集合を生成する文脈自由文法とみなすことができ,そこで生成される文字列の長さNは,変数の個数nに対して指数的に長くなりうる.そのため,BSLPによって圧縮表現された文字列に対してnの多項式時間で効率よく処理を行うには,陽に展開することなく処理を行うことが必要不可欠となる.本研究では,BSLPとして表現された文字列の非反復性判定をO(max(n^2,nlog^2N))時間,O(n^2)領域で解くアルゴリズムを示す.
Cellスピードチャレンジ2008規定課題部門で用いた高速化手法

須藤郁弥, 本田耕一, 松田健護, 坂内恒介, 柴田悠希, 小林隼人, 石野明, 篠原歩

情報処理学会シンポジウム論文集　2008　(5)　13-14　2008年6月4日

ISSN： 1344-0640
間引きを用いたパス技術の自律学習

小林隼人, 畑埜晃平, 石野明, 篠原歩

情報処理学会全国大会講演論文集　70th　(2)　2.209-2.210-210　2008年3月13日
圧縮文字列における最長共通部分文字列および回文を求める多項式時間アルゴリズム

松原渉, 稲永俊介, 石野明, 篠原歩, 中村智将, 橋本和夫

電子情報通信学会技術研究報告　107　(537(COMP2007 55-67))　55-62　2008年3月3日
出版者・発行元：一般社団法人電子情報通信学会
ISSN： 0913-5685

詳細を見る詳細を閉じる

直線的プログラム(Straight line program, SLP)は単元集合を生成する文脈自由文法の部分クラスとみなすことができ,そこで生成される文字列の長さは,変数の個数nに対して指数的に長くなりうる.そのため,SLPによって圧縮表現された文字列に対してnの多項式時間で効率よく処理を行うには,陽に展開することなく処理を行うことが必要不可欠となる.本研究では,SLPとして表現された2つの文字列の最長共通部分文字列の長さを求める問題をO(n^4log n)時間,O(n^4)領域で解くアルゴリズムを示す.またSLPとして表現された文字列に含まれるすべての回文を検出する問題に対して,O(n^4)時間,O(n^2)領域で解くアルゴリズムを示す.
無限n‐ボナッチ文字列の繰り返し構造について

佐々木崇人, 大崎嗣豊, 石野明, 篠原歩

電子情報通信学会技術研究報告　107　(24(COMP2007 1-10))　55-61　2007年4月19日

ISSN： 0913-5685
間引きを用いたシュートモーション学習

小林隼人, 畑埜晃平, 石野明, 篠原歩

人工知能学会AIチャレンジ研究会　25th　52-57　2007年
実ロボットによる揺動運動のスキル獲得

柳町修平, 大崎嗣豊, 小林隼人, 石野明, 篠原歩

人工知能学会人工知能基本問題研究会資料　62nd　17-22　2006年3月27日
出版者・発行元：人工知能学会
スクリプト言語Luaを用いたロボカップ四足ロボットリーグシミュレータ

小林隼人, 井上淳, 石野明, 篠原歩

人工知能学会AIチャレンジ研究会　21st　20-25　2005年
薬剤取り違え防止のための医薬品名類似性指標

今田結城, 竹田正幸, 篠原歩, 大谷寿一, 沢田康文

人工知能学会知識ベースシステム研究会資料　64th　165-170　2004年3月1日
出版者・発行元：人工知能学会
長さ優先置換による文字列圧縮の線形時間アルゴリズム

稲永俊介, 船本崇, 竹田正幸, 篠原歩

電子情報通信学会技術研究報告　103　(622(COMP2003 69-80))　29-36　2004年1月29日

ISSN： 0913-5685
1変数文字列方程式の最小解の長さの上限

馬場謙介, 鶴田聡士, 篠原歩, 竹田正幸

電子情報通信学会技術研究報告　103　(394(COMP2003 44-53))　65-69　2003年10月27日

ISSN： 0913-5685
圧縮されたテキスト上のパターン照合データ圧縮とパターン照合の新展開

竹田正幸, 篠原歩

情報処理　43　(7)　763-769　2002年7月15日
出版者・発行元：一般社団法人情報処理学会
ISSN： 0447-8053

詳細を見る詳細を閉じる

テキストデータを圧縮したままパターン照合を行う「圧縮テキスト上でのパターン照合」が新しい研究課題として脚光を浴びるようになった．本稿では，この課題に関する最新の研究成果について，理論と実用の両面から解説する．
圧縮されたテキスト上のパターン照合－データ圧縮とパターン照合の新展開－

竹田正幸, 篠原歩

情報処理学会学会誌　43　(7)　763-769　2002年7月
出版者・発行元：一般社団法人情報処理学会
ISSN： 0447-8053

詳細を見る詳細を閉じる

テキストデータを圧縮したままパターン照合を行う「圧縮テキスト上でのパターン照合」が新しい研究課題として脚光を浴びるようになった．本稿では，この課題に関する最新の研究成果について，理論と実用の両面から解説する．
断片パターンマッチングの計算量的困難性と近似アルゴリズムについて

堀英彰, 下薗真一, 竹田正幸, 篠原歩

電子情報通信学会技術研究報告. COMP, コンピュテーション　101　(431)　23-30　2001年11月9日
出版者・発行元：一般社団法人電子情報通信学会
ISSN： 0913-5685

詳細を見る詳細を閉じる

断片パターンとは空でない文字列のマルチセットであり, 断片パターンの文字列すべてが文字列w中に重なりなく出現するとき, 断片パターンはwにマッチするという.本論文では断片パターンの照合に関連した基本的な問題の計算量的困難性を考察する.まず断片パターンマッチング問題がNP完全であること, 二つの文字列に対しスコアが最大となる共通の断片パターンを発見する問題がNP困難であることを示す.さらに断片パターンマッチングの多項式時間近似アルゴリズムを提案し, パターン中の文字列が全て同じ長さであるか, またはパターン中の文字列の重み付けが文字列の長さに比例する場合には, このアルゴリズムが定数近似率を達成することを示す.
平衡直線的プログラムに対するパターン照合アルゴリズム

平尾昌啓, 篠原歩, 竹田正幸, 有川節夫

電子情報通信学会論文誌 A　J84-A　(6)　722-730　2001年6月1日
出版者・発行元：一般社団法人電子情報通信学会
ISSN： 0913-5707

詳細を見る詳細を閉じる

テキストとパターンが直線的プログラムとその変種で記述された文字列の照合問題を扱う.直線的プログラムによって表される文字列の長さは, その記述長に対して指数的に長くなる可能性があるので, 展開することなしに, いかに高速な照合を行うかが問題となる.直線的プログラムに対する既存の最も良い圧縮パターン照合アルゴリズムはO(n^2m^2)時間O(mn)領域で動作する.ここで, nは圧縮テキストのサイズで, mは圧縮パターンのサイズである.本論文では, 平衡直線的プログラムという直線的プログラムの変種を提案し, それに対する高速な圧縮パターン照合アルゴリズムを示す.平衡直線的プログラムは直線的プログラムに比べ圧縮率では劣るが, 直線的プログラムと同様に指数長の表現力をもつ.提案アルゴリズムはO(nm)時間O(nm)領域で動作する.
バイオテクノロジー分野におけるサーチ手法に関する調査研究報告書平成12年度 (特許庁S)

熊谷健一, 塩原立也, 篠原歩, 菅原秀明, 高木利久, 中村春木, 深川正夫

バイオテクノロジー分野におけるサーチ手法に関する調査研究報告書平成12年度特許庁工業所有権制度問題調査報告書　114P　2001年
ゲノムデータベース計算機に格納された生命の姿第5回配列データからの知識発見

篠原歩, 宮野悟

BIT (Tokyo)　31　(11)　76-83　1999年11月1日
出版者・発行元：共立出版
ISSN： 0385-6984
データ圧縮による文字列照合の高速化

柴田裕介, 喜田拓也, 竹田正幸, 篠原歩, 有川節夫

情報処理学会全国大会講演論文集　59th　(1)　1.175-1.176-176　1999年9月28日
圧縮テキストに対する文字列照合のための統一的枠組み

喜田拓也, 柴田裕介, 竹田正幸, 篠原歩, 有川節夫

情報処理学会全国大会講演論文集　59th　(1)　1.177-1.178　1999年9月28日
重み付き分類規則による保健データからのデータマイニング

高江徹, 近棟稔, 有村博紀, 篠原歩, 井上仁, 武谷俊一, 上園慶子, 川崎晃一

情報処理学会全国大会講演論文集　59th　(4)　4.311-4.312　1999年9月28日
重み付きネットワークを用いた遺伝子発現ネットワークの発見 (文部省S)

篠原歩, 竹田正幸, 野田清志

ゲノムサイエンス:ヒトゲノム解析に基づくバイオサイエンスの新展開平成10年度 No.08283101　290-293　1999年
質問学習における学習可能性の統一的特徴づけ

林洋祐, 松本哲志, 篠原歩, 竹田正幸

情報処理学会全国大会講演論文集　57th　(2)　2.341-2.342　1998年10月
LZW圧縮テキストに対する高速文字列照合アルゴリズム

喜田拓也, 竹田正幸, 篠原歩

情報処理学会全国大会講演論文集　57th　(1)　1.143-1.144　1998年10月
領域予測のための機械発見システムの研究 (文部省S)

篠原歩

ゲノムサイエンス:ヒトゲノム解析に基づくバイオサイエンスの新展開平成9年度 No.08283101　301-303　1998年
日本におけるヒト・ゲノム研究の最前線 [4] 情報コンピュータの推論による知識発見の支援

宮野悟, 篠原歩

蛋白質核酸酵素　42　(17)　3008-3013　1997年12月

ISSN： 0039-9450
局面検索方式将棋棋譜データベースの開発

林洋祐, 石坂裕毅, 篠原歩

電気関係学会九州支部連合大会講演論文集　50th　222　1997年10月
Z圧縮テキストに対する文字列照合アルゴリズムの実働化

喜田拓也, 竹田正幸, 宮崎正路, 篠原歩

電気関係学会九州支部連合大会講演論文集　50th　275　1997年10月
直線的プログラムによって記述された文字列に対する照合アルゴリズムの高速化

宮崎正路, 篠原歩, 竹田正幸

電気関係学会九州支部連合大会講演論文集　50th　274　1997年10月
九州大学における一般情報処理教育支援システムについて

峯恒憲, 佐藤周行, 正代隆義, 広川佐千男, 有村博紀, 森雅生, 篠原歩, 竹田正幸

情報処理学会研究報告　97　(49(DD-7))　39-46　1997年5月23日
出版者・発行元：一般社団法人情報処理学会
ISSN： 0919-6072

詳細を見る詳細を閉じる

九州大学では、毎年およそ2，300人の新入生が情報処理の入門教育を受講する。これらの学生は、Windows95の動くパソコン上で、プログラミングを始めとする情報処理の基礎を学ぶ。個人差が大きくなりがちな情報処理を学ぶ学生の習熟度に対処するため、講義をサポートし、かつ、講義時間外に利用できる自学自習用のホームページを用意した。このページでは、我々のこれまでの情報処理教育の経験から得た講義のエッセンスを再現(ecture Captur)している。しかし、プログラムが如何に動作するかを理解させることは難しかった。そこで、我々は、プログラムの動作の理解を助ける機能として、「プログラムアニメーションコンパイラ」と呼ぶPascalプログラムをJava Appletに変換するシミュレータを開発した。これにより、Webのブラウザを通してプログラムの動きを体験し、実感してもらえるもらえるようになった。本稿では、本システムのアイデアと概要、並びに今後の開発予定について報告する。We are developing a Web system for the introductory course: of programming and computer literacy. 2300 students take the course with this Web system at Kyushu University. Our main object of this system is to reappear our lecture in front of students in their private studies. Teaching how programs run is a hard problem to deal with in information processing educations. In order to deal with such a difficult subject easily, we propose a program animation compiler for assisting students to understand a motion of programs. This compiler systematically translates tiny Pascal programs into Java Applets. In this paper, we state our idea and future plans of the system.
圧縮テキスト上での文字列照合アルゴリズム

篠原歩

電子情報通信学会大会講演論文集　1997　(Sogo Pt 6)　361-362　1997年3月

ISSN： 1349-1369
機械学習と機械発見による生物情報の概念形成

篠原歩, 正代隆義

ゲノムサイエンス:ヒトゲノム解析に基づくバイオサイエンスの新展開平成8年度 No.08283101　281-283　1997年
短縮記述された文字列上での照合アルゴリズムの実働化

宮崎正路, 篠原歩, 竹田正幸

電気関係学会九州支部連合大会講演論文集　49th　676　1996年10月
Learnability of Subsequence Languages

松本哲志, 篠原歩

数理解析研究所講究録　950　250-256　1996年5月
出版者・発行元：京都大学
ISSN： 1880-2818
順序付き二分決定グラフの学習可能性

平田耕一, 篠原歩, 松本哲志

電子情報通信学会技術研究報告. COMP, コンピュテーション　95　(374)　37-44　1995年11月17日
出版者・発行元：一般社団法人電子情報通信学会

詳細を見る詳細を閉じる

順序付き二分決定グラフ(ordered binary decision diagrams, OBDD)は,プール関数を有向非巡回グラフで表現する.本論文では,このOBDDの学習可能性について議論する.まず,n変数全対称対称関数を表現するOBDDは,高々n+1回の等価性質問,もしくはちょうどn+1回の所属性質問を用いて多項式時間学習可能であることを示す.また,n変数のリテラルの連言,選言を表現するOBDDは,高々n回の等価性質問を用いて多項式時間学習可能であることを示す.したがって,これらはすべて多項式時間PAC学習可能となる.
大規模データベースからの知識発見短縮記述された文字列上での多項式時間照合アルゴリズム

篠原歩, RYTTER W, KARPINSKI M

情報処理学会研究報告　95　(76(FI-38))　25-32　1995年7月28日
出版者・発行元：一般社団法人情報処理学会
ISSN： 0919-6072

詳細を見る詳細を閉じる

直線的プログラムによって短縮記述された文字列についての照合問題を考察する．通常，このようにして表される文字列の真の長さは，その記述長nに対して指数的に長い．この問題に対して我々は，文献[6]において，O(^)時間照合アルゴリズムを与えた．本稿では，これを改良し，O(^4 log )時間アルゴリズムを実現する．We investigate the time complexity of the pattern matching problem for strings which are succinctly described in terms of straight-line programs. Usually the strings of descriptive size n are of exponential length with respect to n. In our former work [6], we have developed O(n^7) time pattern matching algorithm for strings with short descriptions. In this paper, we improve the time complexity: our new algorithm runs in O(n^4 log n) time.
反駁PAC学習可能性

松本哲志, 篠原歩

人工知能学会全国大会論文集　9th　81-84　1995年7月
並列知識獲得システムBONSAI Garden

正代隆義, 宮野悟, LAPPE M, 内田智之, 岡崎威生, 篠原歩

情報処理学会全国大会講演論文集　50th　(3)　3.31-3.32　1995年3月
人工知能

Shinichi Shimozono, Ayumi Shinohara, Takeshi Shinohara, Satoru Miyano, Satoru Kuhara, Setsuo Arikawa

情報処理学会論文誌　35　(10)　2009-2018　1994年10月15日
出版者・発行元：一般社団法人情報処理学会
ISSN： 1882-7764

詳細を見る詳細を閉じる

We present a machine learning system called BONSAI for knowledge acquisition from positive and negative examples of strings and report some experiments on protein data using the PIR and GenBank databases. This learning system is constructed with an algorithmic learning theory for decision trees over regular patterns which is newly developed for this work. As a hypothesis the system trles to find a pair of a classification of symbols called an alphabet indexing and a decision tree over regular patterns which classifies given examples with high accuracy. Through the experiments the system discovered very simple hypotheses that exhibit important knowledge about transmembrane domains and signal peptides.We present a machine learning system, called BONSAI, for knowledge acquisition from positive and negative examples of strings, and report some experiments on protein data using the PIR and GenBank databases. This learning system is constructed with an algorithmic learning theory for decision trees over regular patterns, which is newly developed for this work. As a hypothesis, the system trles to find a pair of a classification of symbols called an alphabet indexing and a decision tree over regular patterns, which classifies given examples with high accuracy. Through the experiments, the system discovered very simple hypotheses that exhibit important knowledge about transmembrane domains and signal peptides.
BONSAI Garden:学習アルゴリズムによるアミノ酸配列からの並列知識獲得システム

宮野悟, 篠原歩, 内田智之, 久原哲, 下薗真一, 篠原武, 正代隆義, 有川節夫

情報処理学会研究報告　94　(69(AL-40))　41-47　1994年7月22日
出版者・発行元：一般社団法人情報処理学会
ISSN： 0919-6072

詳細を見る詳細を閉じる

これまでに，我々は，学習アルゴリズムによる知識獲得システムBONSAIを開発し，主にアミノ酸配列からの知識獲得実験を行なってきた．このシステムは，正の例と負の例からそれらを説明する仮説を学習するもので，これまでの実験で，膜貫通領域とシグナルペプチッド配列に対して，非常に精度の高い小さな仮説を発見し，BONSAIがその能力において大きなポテンシャルをもっていることが判明した．このBONSAIを基本プロセスとして，これを複数個走らせる並列知識獲得システムBONSAI Gardenのプロトタイプを作成し，これまでBONSAIで実験を行なってきたものと同じデータを用いて，比較・検討し，その有効性を確認した．We have developed a machine learning system BONSAI which gets positive and negative examples as inputs and produces a pair of a decision tree over regular patterns and an alphabet indexing as a hypothesis. We observed that the indexing by the hydropathy indices is important in making the learning algorithms efficient and accurate. We are also implementing a system BONSAI Garden, which runs several BONSAI systems in parallel, to acquire knowledge from a hodgepodge of data. Some experiments on the prototype shall be presented.
特集「人工知能技術における計算量」ゲノム情報における機械学習の計算量理論と実際

宮野悟, 篠原歩, 有川節夫

人工知能学会誌　9　(3)　350-357　1994年5月

ISSN： 0912-8085
BONSAI Gardenによるアミノ酸配列データからの並列知識獲得

宮野悟, 正代隆義, LAPPE M, 内田智之, 岡崎威生, 篠原歩, 久原哲, 有川節夫

蛋白質の構造・機能予測　17-21　1994年
BONSAI: ゲノムデータからの機械発見システム

宮野悟, 篠原歩, 有川節夫, 久原哲, 下薗真一, 篠原武

日本生物物理学会年会講演予稿集　31st　S48　1993年9月

ISSN： 0582-4052
BONSAI: 決定木とインデックス化による文字列からの機械発見システム

宮野悟, 篠原歩, 有川節夫, 下薗真一, 篠原武, 久原哲

人工知能学会全国大会論文集　7th　119-122　1993年7月
学習アルゴリズムによるアミノ酸のインデックス化とタンパク質データからの知識獲得実験

宮野悟, 篠原歩, 有川節夫, 下薗真一, 篠原武, 久原哲

計算機科学研究報告　10　(10)　47-52　1993年3月
出版者・発行元：九州大学
ISSN： 0910-352X
Natarajan, B. K. : MACHINE LEARNING - A Theoretical Approach, Morgan Kaufmann Publishers (1991).

篠原歩, 九州大学理学部附属基礎情報学研究施設

人工知能学会誌 = Journal of Japanese Society for Artificial Intelligence　7　(6)　1118-1118　1992年11月1日

ISSN： 0912-8085
EFSの学習可能性と膜蛋白領域予測への応用

有川節夫, 久原哲, 宮野悟, 篠原歩, 篠原武

情報処理学会研究報告　91　(74(FI-23))　23.1,1-8-8　1991年9月10日

ISSN： 0919-6072

詳細を見る詳細を閉じる

EFS(ementary formal syst) を用いた膜蛋白領域の学習について論じる．EFSは if?then 規則からなる論理プログラムの一種である．この枠組を用いてアミノ酸配列の中から膜蛋白領域を予測するアルゴリズムを実働化した．計算資源の制約のため，我々は仮説の候補として用いる EFS を正則パターンに制限した．しかし我々のアルゴリズムは70個の膜蛋白データから膜蛋白領域を同定するいくつかの妥当な仮説を生成した．各仮説は高々10個の正則パターンで表されている．PIRデータベースを利用した検証から，これらの仮説は膜蛋白領域のうちの90%をカバーし，またそれ以外の部分の80%を排除することが確かめられた．We propose a method for algorithmic learning of transmembrane domains based on EFS(elementary formal systems). An EFS is a kind of alogic program consisting of if-then rules. With this framework, we have implemented the algorithm for identifying transmembrane domains in amino acid sequences. Because of the limitations on computational resources, we restrict candidate hypotheses to EFSs defined by collections of regular patterns. However, from 70 sequences of transmembrane domain data, our algorithm has produced several reasonable hypotheses that can identify transmembrane domains. Each of the hypotheses consists of at most ten regular patterns. Experiments with the database PIR show that most of these hypotheses can cover 90% transmembrane domain sequences and exclude 80% negative data.
特集:「計算論的学習理論とその応用」 PAC学習確率的で近似的に正しい学習

篠原歩, 宮野悟

情報処理　32　(3)　257-263　1991年3月
出版者・発行元：オーム社
ISSN： 0447-8053
アルゴリズム論的教示の理論

篠原歩, 宮野悟

人工知能学会人工知能基礎論研究会資料　9th　61-70　1990年1月

︎全件表示 ︎最初の5件までを表示

書籍等出版物 4

バイオインフォマティクス事典

日本バイオインフォマティクス学会編

共立出版　2006年7月
人工知能学事典

人工知能学会

共立出版　2005年12月
Progress in Discovery Science : Final Report of the Japanese Discovery Science Project

Setsuo Arikawa, Ayumi Shinohara

Springer-Verlag　2002年4月8日
Discovery Science : 4th International Conference, DS 2001

Klaus P. Jantke, Ayumi Shinohara

Springer-Verlag　2001年12月12日

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

データ圧縮：最小文法問題に対する理論と応用の両面アプローチ

篠原歩

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (C)

研究機関：Tohoku University

2021年4月1日～ 2025年3月31日

詳細を見る詳細を閉じる

本研究では，可逆的データ圧縮の代表例である文法圧縮に対して，理論と応用の両面から取り組んでいる．初年度として，まず，確率マクロ文法に対する学習アルゴリズムの開発に力を注いだ．既存研究として，文法圧縮に確率文脈自由文法を用いるものが知られているが，マクロ文法は文脈自由文法を真に超える表現力を持つため，より強力な圧縮器を構成する候補となりうる．我々は，確率文脈自由文法のパラメータ推定によく用いられているInside-Outsideアルゴリズムを土台として，高階文法における型導出の技術を用いることで，確率マクロ文法への自然な拡張を行うことに成功した．そしてその効果を計算機実験によって検証した．また，重み付きシンボリックオートマトン(SWFA)の学習可能性に関する研究成果を得た．SWFAは，古典的な有限オートマトンの2つの方向への拡張である重み付きオートマトン(WFA)とシンボリックオートマトン(SFA)を融合したものである． WFAは0/1だけではなく一般の数値を扱うための拡張であり，一方SFAは状態遷移に述語を用いることで入力の対象とする記号の数が極めて大きい場合や無限の場合でも簡潔に定義し表現できるようにするための拡張である．SWFAは，これら双方の利点を併せ持つため，応用範囲の広がりが期待できる．既存研究において，所属性質問と等価性質問を用いる厳密学習の枠組みでWFAとSFAそれぞれに対する学習アルゴリズムが示されていたが，本研究ではそれらを一般化することでSWFAに対する効率のよい質問学習アルゴリズムを開発することに成功した．また計算機実験によって，このアルゴリズムの挙動を評価した．
高階モデル検査の深化と発展

小林直樹, 篠原歩, 佐藤亮介, 五十嵐淳, 海野広志

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (S)

研究機関：The University of Tokyo

2015年5月29日～ 2020年3月31日

詳細を見る詳細を閉じる

本研究では、代表者らがこれまで発展させてきた高階モデル検査の理論およびプログラム検証等への応用を発展させることを目的とした。理論面では、高階文法の反復補題についての40年以上ぶりの進展を得るとともに、異なる2種類の高階モデル検査であるHORSモデル検査とHFLモデル検査の間の関係を明らかにするなど、大きな進展が得られた。また応用面でも、高階モデル検査器およびプログラム自動検証器の大幅な高速化、検証できる性質の拡大、高階データ圧縮のための算術符号化などの成果が得られた。
学習理論からの計算限界解明へのアプローチ

瀧本英二, 篠原歩, 正代隆義, 畑埜晃平, 吉仲亮, 内沢啓, 津田宏治

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area)

研究機関：Kyushu University

2012年6月28日～ 2017年3月31日

詳細を見る詳細を閉じる

学習問題の複雑さ解析を通して，計算に対する新しい解釈，理解をもたらす多くの成果を得た．オンライン予測の解析では，通常の最適化問題の複雑さとの等価性に関する重要な未解決問題を部分的に解決した．仮説表現の複雑さ解析では，閉路のあるニューラルネットを一般化した離散力学系と呼ばれるモデル上のいくつかの決定問題が，NP中間層に属することを示唆する結果を得た．文法学習の解析では，部分文字列／部分グラフとその周囲の構造との関係に注目する分布学習という考え方を用いて，形式文法／形式グラフ文法の学習可能性を大きく進展させる結果を得た．
高等教育に適した自学自習システムの開発

篠原歩

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Challenging Exploratory Research

研究機関：Tohoku University

2013年4月1日～ 2016年3月31日

詳細を見る詳細を閉じる

タブレットPC，スマートフォンなどの携帯端末でも容易に利用可能な大学生向けのe-learningシステムの構築を目指し，オートマトン・言語理論を題材として，各種端末の利点を活かしたシステムのプロトタイプを作成した．正規言語の反復補題を理解しやすいように対話的にユーザに提示するシステムや，オートマトンを題材としたパズルゲームを設計して実装した．また，これに関連した，入力に矛盾しない最小のオートマトンを求める問題の計算複雑さを解析した．
高階モデル検査とその応用

小林直樹, 篠原歩, 五十嵐淳, 海野広志, 寺内多智弘, 住井英二郎, 松田一孝

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (S)

2011年5月31日～ 2016年3月31日

詳細を見る詳細を閉じる

本研究の中心テーマである高階モデル検査とは、代表的なシステム検証手法であるモデル検査の拡張であり、2009年に研究代表者の小林によって初めて現実的な高階モデル検査アルゴリズムおよびプログラム検証への応用が見出された。本研究課題はその結果を受けて行った研究であり、高階モデル検査器の大幅な高速化、高階モデル検査に基づく全自動プログラム検証器の構築、高階モデル検査のデータ圧縮への応用（データをそれを生成する関数型プログラムの形に圧縮し、圧縮したままのデータ操作を実現）などの成果を得た。
データ圧縮に基づく知識発見の理論と応用に関する研究

篠原歩, 成澤和志

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (B)

研究機関：Tohoku University

2011年4月1日～ 2015年3月31日

詳細を見る詳細を閉じる

知識発見の原理の究明と実働化を目指して，データ圧縮技術の関連に着目しながら，理論と応用の両面から研究を展開した．圧縮したままのデータ処理，文字列照合，文字列の繰り返し構造に関する組み合わせ論，マルチエージェントシステム，例から概念を同定する問題の計算量，強化学習，ゲームの解析，実問題への応用などに関する一連の成果を得た．
文字列学のための研究支援システムの開発

篠原歩

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Challenging Exploratory Research

研究機関：Tohoku University

2011年～ 2012年

詳細を見る詳細を閉じる

文字列の持つ離散構造や組み合わせ的性質の解明とその活用を効果的に行うための研究支援システムの開発を目指して研究を展開した.まず,種々の文字列の基本的性質や代表的アルゴリズムと索引構造を記載したオンラインシステムのプロトタイプを作成した.また,文字の置換を許した検索をサポートするための索引構造を開発した.さらに,極大な繰り返し構造である連を最も多く含む文字列を効率よく探索するアルゴリズムを実装した.
超高速圧縮データストリーム処理に基づく軽量XMLデータベース管理システム基盤技術

竹田正幸, 篠原歩, 坂内英夫, 瀧本英二, 坂本比呂志, 畑埜晃平, 稲永俊介

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (B)

研究機関：Kyushu University

2010年～ 2012年

詳細を見る詳細を閉じる

本研究では,圧縮データ処理に基づいて軽量XMLデータベース管理システム(DBMS)のための基盤技術を確立することを目標とし,主として以下の成果を得た.(1) 高速で軽量なオンライン文法圧縮アルゴリズムの開発. (2) 圧縮データ上で動作するq-グラム頻度計算アルゴリズムの開発. (3) 高速XMLデータストリームフィルタリング技術の開発. この他,DBMSの備えるべき知的データ処理機能として,パターンの効率的な枚挙,分類,オンライン予測等に関する研究を行い,多くの成果を得ている.
データ圧縮に基づく知識発見の研究

篠原歩, 石野明

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (B)

研究機関：Tohoku University

2008年～ 2010年

詳細を見る詳細を閉じる

知識発見の原理の究明と実働化を目指して,データ圧縮技術との関連に着目しなェら,理論と応用の両面から研究を展開した.知識発見を非可逆的なデータ圧縮としてとらえて新たな類似性の指標を導入し,その性質を調べた.また,圧縮したままのデータ処理,文字列の連の数に関する組み合わせ論,形式言語理論,マルチエージェントシステム,計算学習理論,ゲームの解析,実問題への応用などに関する一連の成果を得た.
高速圧縮パターン照合に基づく組込み機器向けXMLデータベース基盤技術

竹田正幸, 坂本比呂志, 坂内英夫, 馬場謙介, 稲永俊介, 篠原歩, 石野明

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (B)

研究機関：Kyushu University

2007年～ 2009年

詳細を見る詳細を閉じる

組込み機器では,メモリやストレージ等の計算資源が乏しいため,従来型のDB技術では,ローカルなDBをもたせることが難しい.そこで本研究では,独自の高速圧縮パターン照合技術に基づき,組込み機器向けのXML-DB基盤技術を開発した.
トランスクリプトーム解析と生体イメージングによる心不全に対する新しい治療法の開発

中山雅晴, 篠原歩, 根東義明

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (C)

研究機関：Tohoku University

2007年～ 2008年

詳細を見る詳細を閉じる

1) 心不全の形成過程で要因特異的な転写因子をトランスクリプトーム解析により同定した。 (1) 大動脈結紮による圧負荷モデルとアンジオテンシンII 持続注入による液性因子負荷モデルをそれぞれ作成し、負荷開始後1 週間目で左心室を回収した。 (2) 有意に発現上昇が認められる遺伝子群を同定し、それらの遺伝子上流1kbにわたる塩基配列を、他の遺伝子上流情報とともにデータベースから情報収集した。 (3) その遺伝子上流域に含まれる転写因子結合配列の出現頻度を調べ、全体の遺伝子上流配列のなかで出現頻度が統計学的に有意に高くなるものを同定した。それらは両負荷モデル共通のものと、それぞれのモデルにのみ出現する配列とが認められ、圧負荷・液性因子負荷ともに共通して働く転写因子と、個別のモデル特有に関与する転写因子とに分けられた。 2) 対象とする転写因子の活性を生体の心臓においてリアルタイムに可視化することに成功した。 (1) 上記1)で求めた転写因子の結合配列とルシフェラーゼ発現部位とを含んだプラスミドベクターを作成し、マウスの左心室に発現させたのち、基質であるルシフェリンを腹腔内に注入した上で、In vivo imaging systemで観察、発光を定量化することにより各々の転写因子による転写活性を生体で確認する方法を確立した。 (2) 転写因子結合配列を含む発現ベクターを左心室に発現させたマウスを上記2つの負荷により左室肥大を形成させた。負荷開始翌日より血圧・体重・脈拍とともに転写因子活性を測定し、2日ごと2週間まで測定を繰り返すことで、心不全形成過程における各々の転写活性の程度を生体で連続観測することに成功した。 3) 上記実験により、解析結果同様、要因特異的な転写因子の介在を示した。今後、同様の手法で知見を積み重ねることにより、多因子疾患である心不全の診断・治療法開発の新しいアプローチになるものと期待される。
大規模半構造データからの高速知識発見システムの開発

岡本青史, 竹田正幸, 篠原歩, 喜田拓也, 坂本比呂志, 平田耕一, 有川節夫

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (A)

研究機関：FUJITSU LABORATORIES LTD.

2005年～ 2007年

詳細を見る詳細を閉じる

インターネットとWebサービス技術の急速な発展を背景として,WebページやXMLデータに代表される半構造データが,大量に流通・蓄積されるようになってきた.我々は,このような大規模半構造データに対する学習と発見の理論的基盤,及び効率的なパターン照合,データ圧縮,索引構造などの実用的処理基盤を構築し,これらの成果を高速知識発見システムに応用することを目的として研究を遂行した. 半構造データに対するパターン発見の理論研究では,木構造データのためのカーネル関数の設計と解析を行い,一般的な木構造の学習困難性が#P-完全であることを理論的に示した.本研究は,2006年度人工知能学会論文賞を受賞した.また,ストリームデータからの知識発見の理論研究としてエピソードマイニングに取り組み,直列エピソードのみから構成できるエピソードと非並列エピソードが等価になることを理論的に示した.本手法を細菌感受性検査データに適用し,効果を検証した. 半構造データ処理基盤の研究として,一方向逐次処理に基づくパスパターンの高速照合技術を開発した.本手法は,数千〜数万クエリの同時処理が可能であり,既存手法と比較して実行速度で約4〜6倍,メモリ使用量で約6倍以上の圧倒的な性能を達成した.さらに,この技術を応用し,高速かつ省メモリなXMLストリーム処理システムの開発に成功した.本システムは,一般的なXMLデータベース管理システムとは異なり,クエリ種別に対する性能依存性が極めて小さいという特徴を有する.半構造データに対する索引技術としては,グラフ上の高速な到達可能性判定を実現する効率よい索引構造を提案・実装した.本研究は第18回データ工学ワークショップ(DEWS2007)の優秀論文賞を受賞した.テキスト圧縮の研究においては,ASCIIテキストを主対象とした従来のBPE圧縮技術を日本語テキストに拡張した.さらに,圧縮パターン照合の観点からも有効な新たな圧縮法の開発に成功した.
非明示的表現に対するアルゴリズムの開発

篠原歩, 竹田正幸, 下薗真一, 坂本比呂志, 石野明

2004年～ 2007年

詳細を見る詳細を閉じる

本研究は,非明示的に表現されたオブジェクトに対するアルゴリズムの開発とその計算量の解析を行うことを目的し,また同時に,効率のよいアルゴリズムの開発に適した非明示的な表現法を文字列やグラフなどの離散構造を対象として研究を展開してきた. 具体的には,直線的プログラムとして圧縮表現された文字列を対象として,繰り返し構造や共通部分を検出する問題に取り組んだ.直線的プログラムは,文字列の連結を基本命令とした代入式の列であり,種々の文法圧縮,辞書式圧縮を抽象化したものである.もしもこの直線的プログラムからもとの文字列を陽に展開してしまうと,その長さは指数的に長くなりうるため,決して多項式時間で処理を行うことができない.我々は文字列に内在する組み合わせ構造や周期に着目することにより,圧縮文字列に含まれる回文構造の検出や,最大共通部分文字列の計算を多項式時間で行うアルゴリズムを開発した. また,漸化式として表される文字列の性質を調べた.隣接2項の漸化式で表されるフィボナッチ文字列を一般化し,隣接n項の漸化式でn-ボナッチ文字列を定義した.本研究では,任意のn≧2に対して,無限n-ボナッチ文字列における第k項目の有限n-ボナッチ文字列の最大連続出現数はk→∞のとき2+1/(φ(n)-1)に収束することを証明した.ここに,φ(n)はn-ボナッチ定数であり,特にφ(2)=(1+√<5>)/2は黄金比として知られている.さらに,nを増加させると,最大連続数はちょうど3に近づくことを示した.
アレー解析からの転写制御ネットワークの情報学的解明

久原哲, 田代康介, 小西貞則, 丸山修, 篠原歩, 中野幸二

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research on Priority Areas

研究機関：Kyushu University

2005年～ 2005年

詳細を見る詳細を閉じる

1)発現プロファイルの収集と解析結果としては、酵母について、合計400個の遺伝子欠失変異株における発現プロファイルを作成し、ブーリアンモデリング等による遺伝子発現調節ネットワーク作成を行った。この400個のDNAマイクロアレイデータを用いて、出芽酵母のSET domainを有する遺伝子の制御機構解明を行った。野生株ではストレス応答遺伝子群の発現は浸透圧ストレスに応じて急激に上昇した後,減少する変動を示すのに対し,SET7破壊株では浸透圧ストレスによる急激な発現上昇は起こるが,減少が起こらないことが判明した。この結果は,SET7が浸透圧ストレス応答遺伝子の抑制機構に関与していることが示唆された。 2)近年,遺伝子発現データに基づく癌組織の識別問題において,多くの教師付き機械学習法が応用されている。特にSupport Vector Machines (SVMs)は,最も有効な手法の一つとして主流になっている。しかしながら,他のカーネル識別法の応用に関する研究報告はほとんどなされていない。本年度はカーネル識別法の一つであるカーネル部分空間法を癌組織の多クラス識別問題に適用し,複数のタイプのmulticlass SVMsと識別性能を比較した。7つの癌マイクロアレイデータセットを用いた比較実験の結果,カーネル部分空間法はhigh-dimensional dataに対して,multiclass SVMsに匹敵する高い識別性能を示すことが明らかになった。また,gene selectionと併用することにより,より高い識別性能を得ることができた。さらに本研究では,クラス分離度を測るFisherの基準をカーネル化し,カーネルパラメータの選択基準として応用した。実験の結果,カーネル部分空間法におけるパラメータ選択において有効であることが示された。この基準は他のカーネル識別法においても適用可能であり,識別のためのカーネル設計において有用であると考えられる。
医薬品の商標名類似度と処方関連度に基づく投薬ミス防止システム

竹田正幸, 篠原歩, 澤田康文, 大谷壽一, 坂内英夫, 畑埜晃平

2004年～ 2005年

詳細を見る詳細を閉じる

平成17年度は,以下の4項目について研究した. (1)薬名間の類似性指標の設計(竹田,坂内) 前年度に引き続き,薬名間の類似度を定量化する指標を設計した.各パラメータを決定するため,研究室現有のタキストスコープ装置を用いて視覚および聴覚に関する知覚誤りの実験を行った.得られたデータに機械学習アルゴリズムを適用しパラメータの学習を行った. (2)類似性指標の検証(澤田) 日本薬剤師会などから報告されている「取り違え事例」(日本薬剤師会雑誌53(Sup 4):60-63,2001)や,澤田らがインターネット上に運営している薬剤師間コミュニティーサイト(薬学雑誌122:185-192,2002)に寄せられた事例の医薬品等をもとに,(1)の類似性指標の妥当性を検証した. (3)類似薬名検索方式の開発(篠原,竹田) (1)(2)の成果をもとに,与えられた医薬品名に対して高い類似度を示す医薬品を,医薬品データベース中から高速に検索するためのアルゴリズムを開発した.これを,WS上に実装し,その性能を評価した. (4)処方関連度辞書の構築(大谷,畑埜) 医薬品の処方学的関連の度合を数量化した医薬品処方関連度辞書の構築を目指し,大量の処方箋データからのデータマイニング方式について検討した.
最適パターン発見に基づく大規模半構造データからの知的情報獲得システムの開発

トーマスツォイクマン, 有村博紀, 坂本比呂志, 篠原歩, 下薗真一, 湊真一, 喜田拓也, 竹田正幸

2004年～ 2005年

詳細を見る詳細を閉じる

本研究は,大量のウェブページやXML等の大規模半構造データからのデータマイニング(ウェブマイニング)に基づき,大量のデータ解析を対話的に支援する効率的なツールとして,従来の情報検索システムを超えた新しい情報アクセスシステムの実現方式を明らかにすることを目標としている.その鍵になる技術として,最適パターン発見を木やグラフ構造に拡張し,計算量理論と計算学習理論の最新の成果を援用しながら,半構造データに対する頑健かつ高速な最適化パターン発見アルゴリズムの開発に取り組んだ. 平成17年度は,初年度から昨年度までの研究成果と統合し,最適半構造マイニングのプロトタイプシステム構築を目指した.研究項目としては,有用な情報源の発見,特徴的なパターンの発見,情報の抽出の3つの情報獲得問題に加えて,昨年度から新たに研究を開始した知識索引問題について取り組んだ.今年度得られた具体的な結果のうち主要なものは以下のとおりである. (1)大規模なトランザクションデータによく見られる疎な組み合わせ集合データを効率よく扱うことのできるデータ構造であるZBDD(Zero-suppress BDD)をベースに,その構造の元で重み付き積和集合を計算可能なZBDDパッケージツールVSOP(Valued Sum-Of-Products)の開発を推し進め,頻出するパターン集合を表現するZBDDを単純直交分解する機能を追加した.これにより,そのデータに内包された意味的構造を自動抽出することが可能になった.(湊) (2)パターン発見アルゴリズムによる分類・予測の長期的ふるまいに関する理論保証を与えることに成功した.(ツォイクマン) (3)系列データからの極大モチーフパターンを効率よく枚挙するアルゴリズムを得た.(有村:H13-H16代表) (4)Arc構造付きテキストに対する高速なパターン照合アルゴリズムを得た.(喜田)
データ圧縮とパターン照合に基づく高速機械発見システムの開発

竹田正幸, 篠原歩, 坂本比呂志, 杉本典子, 石野明, 南里智子, 南里一郎

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (B)

研究機関：KYUSHU UNIVERSITY

2003年～ 2005年

詳細を見る詳細を閉じる

本研究では,高速な機械発見システム開発のために以下の3つの項目について研究し,多くの成果を得た。・テキスト圧縮とパターン照合文法変換に基づく圧縮法に焦点をあて,効率的な圧縮アルゴリズムを開発した。これらを基盤技術として用いながら,圧縮文字列照合問題に取り組み,効率的な圧縮文字列照合アルゴリズムの開発に成功した。・テキストと半構造データの高速処理テキストデータの高速処理のために,索引構造の開発を行った。部分文字列パターンに対する索引構造として接尾辞木とDAWGが知られている。そこで,両方の性質を持つCDAWGに着目し,オンライン線形時間CDAWG構築アルゴリズムを開発した。これに基づき,スライド窓に対応したCDAWG構築アルゴリズムを考案し,テキストデータ圧縮に活用した。また,日本語テキストなどアルファベットサイズの大きなテキストデータに適した新たな索引構造を与え,その有用性を示した。一方,部分列パターンの照合のための索引構造である部分列オートマトンについて解析し,部分列パターン発見の高速化に関する知見を得た。さらに,十数年ものあいだ未解決であった語接尾辞木のオンライン線形時間構築アルゴリズムを考案した。半構造データの高速処理のために,ビット並列化技法に基づく高速木パターン照合アルゴリズムを開発した。・パターン発見と情報抽出大量のデータから現実的な時間内に有用な規則を抽出するパターン発見アルゴリズムに関して,様々なパターン族についてそれぞれ独自の高速アルゴリズムを開発した。また,形式的体系(EFS)の質問学習や半構造データからの知識発見に関する研究も行った。これらのアルゴリズムを実働化しそのパフォーマンスを評価した。以上の研究で得られた成果を統合し,計算機上に高速な知識発見システムを構築した。言語データおよび文学作品データに適用し,言語学および文学の専門家の立場から有効性を検証した。
大規模データストリームからの超高速データマイニングの研究

池田大輔, 有村博紀, 竹田正幸, 篠原歩, 喜田拓也, 笠原義晃, 石野明

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (B)

2003年～ 2005年

詳細を見る詳細を閉じる

ネットワーク上を時間的に変化しながら流れる大量半構造データストリームから有用な情報を効率よく獲得する超高速オンライン型データマイニング・システムの研究開発を行った.最終年度である平成17年度は,前年度までに研究開発した基礎理論の深化と,ネットワークデータへの応用の両面から,ストリーム指向パターン照合と半構造データマイニング,さらに,応用としてネットワーク不正侵入検出などの問題について,以下のように研究開発を行った.また,3年間の研究成果の発表・出版を行った. (1)半構造データストリームマイニングの調査と定式化:ネットワーク侵入検出やデータストリームマイニング等の実際のデータストリーム応用を解析し(池田・笠原・喜田),ストリームマイニングに関する最新の技術動向の調査を行った.また,昨年度までの調査結果を出版した(喜田・有村). (2)ストリーム指向半構造パターン照合技術の開発:データストリームを左から右へ一方向逐次走査に基づいた新しいストリーム検索技術について研究した.特に,XMLテキスト高速な木パターン照合処理技術と,シソーラアスやアノテーション等のメタデータを附加したストリームデータ検索技術を開発することに成功した(竹田・篠原・石野・喜田). (3)系列パターン発見に関して,長大な系列データを対象とした効率よいパターン発見アルゴリズムを開発した(篠原・竹田・有村).また,部分文字列の頻度に基づくパターン抽出手法について,そのパターン抽出性能と計算性能の改良を行った(池田・笠原・喜田).さらに,前年度に開発したワイルドカードをもつ極大パターンに対する高速パターンアルゴリズムに関する研究成果が出版された.また,昨年度の研究で開発した系列パターン発見アルゴリズムがH17年6月に,2004年人工知能学会研究会優秀賞を受賞した(篠原・竹田・有村).さらに,前年度までに,研究項目2と3で開発した半構造パターン照合技法とオンライン発見手法を元に開発した,ストリームデータに関する半構造データ族に対する高速半構造パターン発見アルゴリズムの研究成果の論文集への採択が決定した(有村・喜田). (4)応用研究として,現実の大規模高速ネットワークにおいて,実際に大量ネットワークデータに対するオンラインデータ収集と解析を行い,ネットワーク不正侵入検出に関する研究を行った(笠原・池田).
文字列集合からの高速パターン抽出アルゴリズムの開発と実働化

篠原歩

2002年～ 2004年

詳細を見る詳細を閉じる

昨年度まで,入力として与えられた文字列集合から,それを特徴付ける一つのパターンを高速に見つけるアルゴリズムの開発をさまざまなパターン族に対して行ってきた.最終年度にあたる本年度は,それをさらに推し進め,複数のパターンの組み合わせによってより柔軟な表現を可能にすることを目指した.当然のことながらこの拡張を行うと,探索空間がさらに広がるために計算時間の増大が問題となる.我々は,接尾辞木を巧妙に活用することによって,与えられた文字列集合を特徴づけるのに最もよいパターン対を効率よく見つけるアルゴリズムの開発に成功した.接尾辞木は,線形サイズとはいえ領域効率があまりよくないため,大規模な文字列に対しては適用しにくくなる.そこで我々は,より領域効率のよい接尾辞配列を用いて接尾辞木を模倣することによって,実装上の観点からも有効なアルゴリズムを与え,計算機実験によってその効果を実証した.また,2つのパターン対の出現する位置の相対距離に関する条件を自由に与えることによって,より表現力を高めたパターン発見問題についても,効率のよいアルゴリズムを与えることができた.さらに,候補となるパターンが与えられた文字列に合致するかどうかを高速に判定するためのデータ構造として,3分木を活用した有向無閉路文字列グラフや,圧縮無閉路文字列グラフについての考察を行った.そしてこの一連のパターン発見問題に関する我々の研究を関連研究と比較しながら総括した.
最適パターン発見に基づく大規模半構造データからの知的情報獲得システムの開発

有村博紀, 篠原歩, 竹田正幸, 坂本比呂志, 下薗真一

2003年～ 2003年

詳細を見る詳細を閉じる

本研究では,大量のウェブページやXML等の大規模半構造データからのデータマイニング(ウェブマイニング)に基づき,大量のデータ解析を対話的に支援する効率的なツールとして,従来の情報検索システムを超えた新しい情報アクセスシステムの実現方式を明らかにすることを目標としている.鍵になる技術として,最適パターン発見を木やグラフ構造に拡張し,計算量理論と計算学習理論の最新の成果を援用しながら,半構造データに対する頑健かつ高速な最適化パターン発見アルゴリズムの開発に取り組んだ.平成15年度は,前年度の成果に基づき,(a)有用な情報源の発見,(b)特徴的なパターンの発見,(c)情報の抽出の3つの情報獲得問題について,次の研究を行った. (1)前年度開発した最適分類パターンを用いた高精度テキスト自動分類手法を一種の正規表現を扱えるよう一般化した.さらに,近似文字列照合を可能なパターン発見エンジンを開発し,加速学習法を用いて決定木学習システムBONSAIに組み込んだ(竹田・篠原). (2)XPathパターンに対する最適パターン発見アルゴリズムを設計し,半構造データマイニングエンジンを開発した.とくに今回は,より現実の半構造データに近い無順序木モデルに対して,高速なパターン発見エンジンを開発した.パターンの圧縮表現に対する,高速な列挙アルゴリズムを開発した.独自に開発したオンライン化技術を用いて,オンラインパターン発見手法を開発した(有村). (3)情報抽出に関して,現状の技術動向の調査を行い,水平方向制約(Sequence制約)付き半構造データに対するラッパー帰納アルゴリズムの設計を行った(坂本).さらに,半構造データに適した高性能圧縮アルゴリズムを開発し,性能に関する理論的解析を行った.並行して,開発したアルゴリズムの計算量を解析し(下薗,篠原),個々のアルゴリズムの最適化をおこない,性能を向上させた(全員).最後に,ウェブデータとXMLデータに関する評価実験をおこない,この方式の有効性を評価した(有村・篠原).
データ圧縮と高速文字列照合アルゴリズムを用いた知的全文検索システムの開発

篠原歩, 喜田拓也, 坂本比呂志, 竹田正幸, 下薗真一

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (B)

研究機関：Kyushu University

2001年～ 2003年

詳細を見る詳細を閉じる

文字列に対する索引構造として,接尾辞木(suffix tree)や有向無閉路文字列グラフ(DAWG)がよく知られているが,我々はその両方の性質を持つ,よりコンパクトなデータ構造であるコンパクト有向無閉路文字列(CDAWG)に着目し,そのためのオンライン構築アルゴリズムを示した.また,文字列のすべての接頭辞に対するDAWGを合わせた構造に対する構築アルゴリズムを示し,与えられた文字列のすべての部分列を受理するオートマトン(部分列オートマトン)の状態数の下限の証明も行った.これらの結果はいずれも,アプリケーションの高速化の基盤技術として用いられている.また,日本語テキストなど,アルファベットサイズが大きい場合に有効なDAWGの実装技術として,三分木構造を活用したデータ構造を提唱し,その有効性を実証した. 一方,これら文字列に対するデータ構造の性質をより探求するために,グラフ構造からそれに適合する文字列を推論するという逆問題を新たに提案し,DAWG,部分列オートマトン,そして接尾辞配列に対する線形時間アルゴリズムの開発した.さらに,文字列の代数的な性質として,1変数の文字列方程式の解の長さの上限を初めて明示的に証明することに成功した. データ圧縮に関しては,まず我々はテキストに対応したコンパクトな文脈自由文法を出力する枠組みにおいて,出力される文法のサイズの近似率を保証した,領域効率もよいアルゴリズムの開発とその解析に成功した.また,長さ優先で置換を行っていくヒューリスティクスに関しても,全行程を線形時間で行うことを可能にするアルゴリズムを与えた. また、大量のデータから現実的な時間内に有用な規則を抽出しようとするパターン発見アルゴリズムに関しても,より一般化したさまざまなパターンについてそれぞれ独自の高速ナルゴリズムを開発することに成功した.特に,誤りを許した近似パターンについても,効率のよいアルゴリズムを与え,その効果を計算機実験によって検証した.
最適パターン発見に基づく大規模半構造データからの知的情報獲得システムの開発

有村博紀, 下薗真一, 篠原歩, 竹田正幸

2002年～ 2002年

詳細を見る詳細を閉じる

ネットワーク上に分散したウェブページやXML等の半構造データの急速な増大に対して,これらのコンテンツに直接アクセスするための効率良い手法の開発が緊急の課題となっている.本研究では,大規模半構造データからのデータマイニング(ウェブマイニング)に基づき,大量のデータ解析を対話的に支援する効率的なツールとして,従来の情報検索システムを超えた新しい情報アクセスシステムの開発を目指す. そのための鍵となる技術として,最適パターン発見を木やグラフ構造に拡張して,半構造データに対する頑健かつ高速な最適化パターン発見アルゴリズムを開発する.さらに,ウェブマイニングを(a)有用な情報源の発見,および(b)特徴的なパターンの発見,(c)情報抽出の3つの過程ととらえ,これらを有機的に結合して,半構造データを対象とした知識獲得システムの効率良い実現方式を明らかにすることを目標とする.また,計算量理論と計算学習理論の最新成果を援用し,計算量に徹底的に配慮した高速なアルゴリズムの開発を目指すのも特色である. 平成14年度は,次の研究成果を得た. (a)「有用な情報源の発見」に関しては,従来より表現力の高いパターンである可変長変数パターン(VLDCパターン)に対する新しいテキスト索引構造を開発し,これを用いて,効率よい最適化マイニングアルゴリズムを開発した. (b)「特徴的なパターンの発見」に関しては,XML-MessagingとSOAPへの応用を目指して,昨年開発した半構造データマイニング手法FREQTを元に,高速な半構造データストリームマイニングSTREAMTを開発した.これは,非常に少なく資源を使いながらデータストリームを監視し、有用なパターンを逐次報告するアルゴリズムである.また,FREQTの最適化マイニングへの拡張と理論的性能解析を行い,この方式の最適性を示した. (c)「情報抽出」に関しては,XMLデータ処理の基本技術である符号語列上のパターン照合機械技術を開発し,XMLパターン検索への応用を考察した.
cDNAマイクロアレイデータからの知識発見に関する情報科学的基礎付け

宮野悟, 松野浩嗣, 阿久津達也, 久原哲, 丸山修, 篠原歩

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (B)

研究機関：The University of Tokyo

2000年～ 2002年

詳細を見る詳細を閉じる

本研究を開始するころから,cDNAマイクロアレイ技術は急激に実験室で用いられるようになり,ゲノムに関連した大規模プロジェクトが計画され,既存の統計パッケージやデータベース等を利用して,膨大なマイクロアレイデータの計測から結果に至るデータ解析パスが突貫工事的に作られてきた.しかし,そのプロセスには,様々の解析ツールを開発することは強調されているが,情報科学的な基礎をきちんと作るという方向付けは,国内においては特に重要視されていない状況であった. 本研究では,こうした新たな計測技術の登場の初期の段階から,データ及び解析技術について,情報科学的な基礎付けを行うべきであるとの考えから研究を行い,主にcDNAマイクロアレイデータからの遺伝子ネットワークモデル(ブーリアンネットワークモデル,ベイジアンネットワークモデル及び常微分方程式系モデル)及びその推定法についての成果を得た.また,そうしたネットワーク情報に基づいて遺伝子ネットワークをモデリングしシミュレーションを行うための基礎研究(ハイブリッドペトリネットの拡張及びパスウェイのモデル化)及び知識発見を支援するための方式についての研究について成果を得た. マイクロアレイのデータは,大量の数値データであるが,その背景にはゲノムをはじめとする様々の生物知識が存在している.本研究は,そうしたものを総合的に考えながら研究を行い,cDNAマイクロアレイデータの解析について,情報科学の基盤技術を形成に貢献したといえる.
最適パターン発見に基づく大規模半構造データからの知的情報獲得システムの開発

有村博紀, 篠原歩, 竹田正幸, 坂本比呂志, 下薗真一

2001年～ 2001年

詳細を見る詳細を閉じる

ネットワーク上に分散したウェブページやXML等の半構造データの急速な増大に対して,これらのコンテンツに直接アクセスするための効率良い手法の開発が緊急の課題となっている.本研究では,大規模半構造データからのデータマイニング(ウェブマイニング)に基づき,大量のデータ解析を対話的に支援する効率的なツールとして,従来の情報検索システムを超えた新しい情報アクセスシステムの開発を目指す. そのために,鍵となる技術として,最適パターン発見を木やグラフ構造に拡張して,半構造データに対する頑健かつ高速な最適化パターン発見アルゴリズムを開発する.さらに,ウェブマイニングを(a)有用な情報源の発見,および(b)特徴的なパターンの発見,(c)情報抽出の3つの過程からなると考え,これらを有機的に結合して,半構造データを対象とした知識獲得システムの効率良い実現方式を明らかにすることを目標とする,また,計算量理論と計算学習理論の最新の成果を援用して,計算量に徹底的に配慮した高速なアルゴリズムの開発を目指すことも特色である. 平成13年度は,次の研究成果を得た. (a)「有用な情報源の発見」に関しては,部分系列パターンとエピソードパターンと呼ぶ組合せパターンに対する効率よい最適化マイニングアルゴリズムを開発し,これを文字列分類のための決定木学習アルゴリズムBONSAIに組み込んだ. (b)「特徴的なパターンの発見」に関しては,半構造データを最も基本的なラベル付き順序木(labeled ordered trees)のクラスとしてモデル化し,データ中の頻出共通部分構造に対する高速な発見アルゴリズムを開発した.木に関するパターン発見問題は,一般に高い計算量をもつことが多い.そこで,最右枝拡張法という効率よい発見手法を与え,これを複数の最適化手法と組み合わせて,半構造データに対する高速なマイニングアルゴリズムを与えた. (c)「情報抽出」に関しては,ウェブからの情報抽出問題を考察し,HTMLデータから木構造の情報を利用して必要な情報を効率よく切り出すTree-Wrapperアルゴリズムを開発した.
遺伝子ネットワークの解析と可視化システムの開発

篠原歩, 竹田正幸

2001年～ 2001年

詳細を見る詳細を閉じる

本研究は,遺伝子の相互作用を明らかにするために,破壊や過剰発現による実験結果を集めた遺伝子発現プロファイルデータから,そこに内在する相互作用を表現するための規則をユーザとの対話の中で発見するためのシステムを開発することを目的とする.我々の研究グループでは,重み付きネットワークモデルを導入し,発現プロファイルデータから遺伝子間の力関係を辺の重みとして取り出すアルゴリズムを設計し,予備実験を行ってきた.このネットワークを効率よく可視化するための方法論を確立し,それを実装することが目的である. 本年は,グラフィカルモデリングと呼ばれる統計的手法の中で用いられている,共分散選択の技法を応用したシステムを構築し,実データに対して適用を行った.また,遺伝子発現プロファイルデータのみならず,遺伝子の配列情報を合わせてネットワークの同定をより高精度に行うことを目指して,配列データからそこに内在する共通なパターンを抽出する問題について,特に高機能化と高速化に力点をおいて研究を展開した.その結果,部分文字列パターンおよびエピソードパターンに関して,実用的な時間で最も分類精度の高いパターンを見つけだすアルゴリズムの開発に成功した.また,その中で頻繁に用いられる部分に特化したデータ構造を開発し,これらを機械発見システムBONSAIの中に組み込んだ.このことにより,これまでの部分文字列パターンのみを用いた表現方法よりも簡潔でより分類精度のよい決定木が抽出できることを確認した.
大規模半構造化テキストデータからの高速データマイニング・システムの開発

有村博紀, 篠原歩, 竹田正幸, 正代隆義, 平田耕一, 石野明

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (B)

研究機関：Kyushu University

1999年～ 2001年

詳細を見る詳細を閉じる

本研究では,以下の三つの研究項目について研究を展開した. 1.半構造化文書からのデータマイニング方式.大量テキストからのテキストマイニング問題を考察し,これを情報検索の逆問題として定式化し,とくに,雑音の多い不完全なデータにおける頑健なパターン発見のために,統計的尺度を最適化するパターンを発見する最適パターン発見の枠組みを採用した.近接部分語パターンと呼ばれる単純なテキストパターンに対して,ランダムテキスト上できわめて高速にはたらく,最適パターン発見アルゴリズムを開発し,ウェブからのキーワード獲得問題や,対話的文書ブラウジングに適用した.さらに,ウェブやXMLデータなどの大規模半構造化文書を,「半構造化文書=テキスト+構造+属性データ」ととらえて,テキストマイニングの枠組みを木やグラフ構造に拡張した. 2.大量テキストデータに対する高速パターン照合方式.現実の大規模テキストデータベースシステムでは,大量のテキストデータを格納するため,テキストを圧縮して扱うことが多い.そのため,圧縮データ上のパターン照合アルゴリズムに力点をおいて研究した.これは,圧縮されたデータを陽に展開することなくパターン照合を行おうとするものである.本アプローチの独創的な点は,単にデータを圧縮することで記憶領域を削減するだけでなく,さらに,圧縮することでパターン照合そのものを高速化させるという狙いをもつことである.本研究では,一連の研究を通じて,一番目の目標だけでなく,二番目の目標も達成できることを実証した.さらに,既存のさまざまな圧縮方式に対して,その圧縮方式に適した圧縮照合アルゴリズムを開発すると同時に,より高い見地から多様な圧縮照合アルゴリズムを統一的にとらえる枠組みを提案することに成功した. 3.機械学習に基づくデータマイニング方式.一連の半構造化文書からの情報抽出問題を理論的に定式化し,与えられたデータからパターンを発見する問題の学習可能性と限界を理論的に明らかにした.次に,Tree Wrapperや生垣とよばれる木と文字列の双方の性質をもつ木構造パターンに対して,半構造化文書からの情報抽出のための効率よい情報抽出アルゴリズムを開発した.さらに,実際のウェブデータを対象として,さまざまなタイプの半構造化文書から,利用者が必要とする情報を獲得するという情報獲得実験を行い,その有効性を検証した.
遺伝子ネットワークの解析と可視化システムの開発

篠原歩, 竹田正幸

2000年～ 2000年

詳細を見る詳細を閉じる

本研究は、遺伝子の相互作用を明らかにするために、破壊や過剰発現による実験結果を集めた遺伝子発現プロファイルデータから、そこに内在する相互作用を表現するための規則をユーザとの対話の中で発見するためのシステムを開発することを目的とする.我々の研究グループでは,重み付きネットワークモデルを導入し,発現プロファイルデータから遺伝子間の力関係を辺の重みとして取り出すアルゴリズムを設計し,予備実験を行ってきた.この一連の研究の過程で,出力されるネットワークが必ずしも疎ではないという問題点が浮き彫りになってきた.すなわち,出力されるネットワークが密であるために,その関連を直感的にとらえにくく,またそれを可視化するのも容易ではなかった.したがって,疎なネットワークを見つけ出すためには,何らかの指標に基づいて,このネットワークの辺を「間引く」必要がある.そこで,グラフィカルモデリングと呼ばれる統計的手法の中で用いられている共分散選択の技法を応用し,これを疎な遺伝子ネットワークを見つけるために適用した.しかしながら,遺伝子発現プロファイルデータのもつ共線形性によって,この手法をそのまま適用することは実用上,不可能であった.そこで,堀本らの手法と同様に,VIF指標と呼ばれる値を参照しながら,この問題を避けることができた.VIF指標を用いることによって,遺伝子数が40程度のものまでこの手法で取り扱うことができることがわかった.そこで,注目する遺伝子として指定されたものに,ランダムに選んだ他の遺伝子を加えてネットワークを作成し,これを数回繰り返すことによって安定したネットワークを取り出すという実験を行った.この実験結果の生物学的解釈については,現在検討中である
探索アルゴリズムの理論とその実働化に関する研究

篠原歩

1999年～ 2000年

詳細を見る詳細を閉じる

人工知能の問題解決において,探索は常に鍵となる役割を果たしている.実際のアプリケーションにおいては,問題固有の知識を利用しながら探索を制御し,探索経路の組み合わせ的爆発に対する工夫を行うことが必要である.今年度は,情報を表現し保持するための最も基本的なデータ構造である文字列に関する探索問題を設定し,部分文字列の持つ性質を生かして,実用上は多くの場合において全解探索を避けられる枝刈りヒューリスティックを提案し,実験によってその効果を検証した. この問題は,実用的な観点から,与えられた2つの文字列集合SとTを分類するために最良な部分列パターンを見つけ出す方法を示すことを目標としたものであるが,NP困難であることが知られている問題と深い関連があり,最悪時には潜在的に指数的に多い候補パターンを調べあげることを余儀なくされる.すなわち基本的には,それぞれのパターンωに対して,ωを部分文字列として含む文字がSとTにそれぞれいくつ存在するかを数え上げなければならない.そこでまず,文字列集合の部分列をすべて受理する部分列オートマトンを高速に構築するアルゴリズムを開発して実装することで,この数え上げ自身を高速化した.この部分列オートマトンの構築アルゴリズムは,現在知られている中で最も効率のよいものである.さらに,可能な限り候補となる部分列を減らすために,部分列に関する包含関係と,目的関数の性質をうまく組み合わせることによって,探索空間を効率的に枝刈りするヒューリスティクスを2つ提案した.これをアミノ酸配列やDNA配列に対する実験に適用し,それぞれのヒューリスティクスの効果と,部分列オートマトンによる高速化の度合いを確認した.
圧縮データ上の高速パタン照合アルゴリズムを用いた知的全文検索システムの開発

篠原歩, 下薗真一, 坂本比呂志, 竹田正幸, ZEUGMANN Thomas

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (B).

研究機関：KYUSHU UNIVERSITY

1998年～ 2000年

詳細を見る詳細を閉じる

圧縮データ上のパターン照合アルゴリズムの開発に関しては,理論的観点からのアプローチとして,辞書式データ圧縮法の統一的枠組み(Collage system)を開発し,その枠組みの上で,Knuth-Morris-Pratt型(KMP)とBoyer-Moore型(BM)の両方の照合アルゴリズムを開発することに成功した.KMPとBMは,通常のテキストに対する最も基本的な照合アルゴリズムである.これらをByte-Pair-Encoding(BPE)圧縮に適合させることで,実用上,最も高速な圧縮文字列照合アルゴリズムが得られることを実験的に確認した.さらに,このCollage Systemに対して,一般的な複数文字列照合アルゴリズムの開発にも成功した.この手法は,近似文字列照合を行う際にも有用であることも確認できた.この手法を,有望な圧縮プログラムSequiturに対して容易に適用でき,また実用上も有用であることが明らかになった.さらに,テキストのみならずパターンも圧縮された設定において,平衡直線的プログラムに対する圧縮文字列照合アルゴリズムの開発も行った.この平衡直線的プログラムは,圧縮率という観点からは一般の直線的プログラムよりも劣るが,しかしながら圧縮文字列照合の観点からはより有用であることがわかった.また,文字列の部分列を判定するための効率のよいデータ構造である部分列オートマトンを高速に構築するオンラインアルゴリズムの開発を行った.このアルゴリズムは,現在知られている中で最も高速であり,知識発見システムの実行速度を上げるためにも有用であることを確認した.一方,データベースからの知識発見に関しても,例から木の変換規則を学習するアルゴリズムや,大きなテキストデータベースから語の最適な結合規則を見つけるアルゴリズムを開発できた.
計算学習理論に基づく知識発見に関する研究

丸岡章, 篠原歩, 今井浩, 安倍直樹, 渡辺治, 高須淳宏

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research on Priority Areas (A)

研究機関：Tohoku University

1998年～ 2000年

詳細を見る詳細を閉じる

膨大なデータベースから有効な情報を効率良く取り出すための,種々の計算のメカニズムを与えるとともに,特にテキストを対象とした情報抽出のための手法を開発した.代表的な成果は以下のとおりである. 知識発見とブースティング:ブースティングは,複数の性能の劣る予測アルゴリズムを統合して,高い予測性能をもつ予測アルゴリズムを構成する学習法で,実用性も高い手法である.この手法に関連して,状況に応じてサンプル量を適宜自動調整する適応型サンプリング技法を用いた新しいブースティングMadaBoostを開発した.また,学習アルゴリズムが自ら環境に働きかけ,能動的に情報を収集するという視点にたった能動学習アルゴリズムを考案し,従来法を上回る予測精度が得られることを計算機シミュレーションにより示した.さらに,ブースティングのひとつの方式である決定木ブースティングのための見通しの良い理論を構築するとともに,決定木の視点に線形分離関数を割り当てた決定木ブースティングを開発した. テキスト解析における知識発見:遺伝子情報からの機械発見システムBONSAIの核となるアルゴリズムとして,最良の部分列パターンを見つけるアルゴリズムを開発した.また,話者適応するテキスト解析のために,Baum-Welchアルゴリズムからオンライン型アルゴリズムを構成した. 情報圧縮に基づく知識発見:テキストを対応とした文脈木重み付け法により圧縮に基づいた学習アルゴリズムを開発した.また,形態素間の文法的関係を最小記述長のグラフとして表すことにより,辞書知識ベースの作成する方法を提案し,実際の辞書テキストの知識構造化を行い,この方法の妥当性を検証した. 不確実環境における知識発見:現実のテキストデータから情報を効率良く抽出する方法として,誤りを含む文字列データの近似マッチング法を与えた.また,適応型サンプリング手法に基づいて,不確実性をもつ環境における学習アルゴリズムの現実的な評価法を与えた.
二分決定グラフを知識表現に用いたデータマイニングシステムの開発

宮野悟, 篠原歩, 丸山修, 阿久津達也, 下薗真一, 正代隆義, 内田智之

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (B)

研究機関：The University of Tokyo

1997年～ 1999年

詳細を見る詳細を閉じる

発見をすることは科学における最も基本的な活動であり,その発見は新しい彗星の発見であったり,ケプラーの法則のように観測データから導き出された物理法則であったりする.人間の知的活動として重要な位置にあるこうした知識発見は,最近注目されているデータマイニングシステムのように,人間に代わって計算機上のシステムが行うことが強く期待されている. こうした状況に対応するために,本研究は,二分決定グラフ(BDD)を知識表現に用い,データからの高次の知識発見を可能とするシステムの開発を目的として研究を開始した.二分決定グラフは,論理回路設計の分野で重要な概念であり,論理関数の合成,最適化などでその有効性が発揮されているものである.また,こうしたシステムの開発を通して,発見科学の原理や理論の構築の実証的足がかりをつくることも本研究のもう一つの重要な目的である. 本研究では,まず決定グラフを知識表現に用いることにあるが,本研究を展開する中で,計算量に関する研究から,それを直接に取り扱うことには困難が伴うことが様々の観点から判明した.そのため,従来の決定木としてまず仮説を生成し,その後,決定ダイアグラムを編集するという方式をとった.また,仮説生成方式の研究としては,様々の学習方式を検討し,木構造,グラフ構造,ネットワーク構造等を学習するための理論的研究とシステム開発を行った.そしてこうした研究を総括した知識発見システムとしてHypothesisCreatorを開発し,本研究では主に仮説生成エンジンとして,数千万属性に対応できる並列決定木構成方式を実装した.最後に,仮説編集システムDecision Diagram Editorを開発することにより,Human Expertの介入を積極的に支援して,決定木から決定ダイアグラムを作り出すためのシステムを完成させた).
発見的探索アルゴリズムの理論と実働化

篠原歩

1997年～ 1998年

詳細を見る詳細を閉じる

人工知能の問題解決において,探索は常に鍵となる役割を果たしている.実際のアプリケーションにおいては,問題固有の知識を利用しながら探索を制御し,探索経路の組み合わせ的爆発に対する工夫を行うことが必要である.このような経験的な知識を利用した探索は,発見的探索アルゴリズムと呼ばれているが,そのパフォーマンスは個々の問題固有の性質に強く依存し,効率の良い探索技法の統一的な開発,解析が極めて困難である.この発見的アルゴリズムを計算論的学習理論の枠組みでとらえ,さらに具体的な問題を用いてその有効性を実証することを目標として研究を展開した.まず,質問学習のモデルにおいて,概念クラスが多項式回の質問によって学習可能になるための統一的な特徴付けを与えることに成功した.この特徴付けは,これまで等価性質問,所属性質問,およびその組み合わせについてそれぞれ個別に研究されてきたものであるが,我々の成果はそれを包含している.この特徴付けにより,質問による学習可能性の本質は例空間を効率よく絞り込む質問の存在と,絞り込んだ仮説が正しいことを検証できる質問の存在にあるという知見が得られた.次に,実際的によく用いられている決定木の学習アルゴリズムを土台にして,重み付き分類規則を見つけるアルゴリズムを提唱した.計算機実験によってこの方式が時間的にも,また予測精度の点からも決定木のものと同等以上の性能を有することを検証した.さらに,遺伝子の破壊と強制発現によるデータから遺伝子ネットワークを同定する問題を探索問題としてとらえ,この問題の計算量を解明し,理論的な面と実際的な面の両面からそのパフォーマンスを解析し,計算機実験を行った.
テキスト圧縮に基づく高速パターン照合アルゴリズムの研究

竹田正幸, 篠原歩

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (C)

研究機関：KYUSHU UNIVERSITY

1997年～ 1998年

詳細を見る詳細を閉じる

従来,ファイル圧縮の目的は二次記憶領域の効率的利用にあった.したがって,現在広く使われている圧縮法は,圧縮率を第1の基準として選定されたものである.本研究では,この発想を大きく転換し,パターン照合の高速化を図るためにファイル圧縮を行うものと考える.本研究の目標は,以下の二つである. 目標1:展開後照合する方法と比べて,より高速に照合できること. 目標2:非圧縮テキストを照合する方法と比べて,より高速に照合できること. 2年間にわたる本プロジェクトにおいて,上記の二つの目標を達成し,以下の研究成果を得て,プロジェクトを成功裡に終了した. (1) UNIX標準の圧縮プログラムであるCompressで使用されているLZW圧縮法に関して,複数パターン照合アルゴリズムを開発した. (2) 上記(1)のアルゴリズムのより実用的な実現法として,Shift-And法に基づく方法を開発した. (3) 上記(1),(2)のアルゴリズムを実働化し,展開後照合する単純な方式と比べて2倍程度高速であることを示した。すなわち,目標1を達成した. (4) 同様に,二つのアルゴリズムが、非圧縮テキスト上のパターン照合と比べて高速であることを示した.すなわち,目標2を達成した。高速化の度合は,ほぼ圧縮率に等しい. (5) バイト対符号法,ハフマン符号,有限状態符号,否定辞書法などの圧縮法についても,パターン照合アルゴリズムを開発し,その評価を行った.
領域予測のための機械発見システムの研究

篠原歩, 正代隆義

1997年～ 1997年

詳細を見る詳細を閉じる

本研究は,DNA配列データに対して,その中の遺伝子領域予測できるシステムを構築するための体系的な方式を研究し,実用的な領域予測システムを実働化することを目的とする.この目的を達成するために,我々は以下の項目に力点をおいて研究を展開した.(1)領域予測問題の抽象化と定式化.(2)領域予測アルゴリズムの開発.(3)上記アルゴリズムの理論的基礎.(4)計算機実験による上記アルゴリズムの評価.まず,文字列情報の中の特定の機能部位を同定する問題を,文字列の長さを保存する関数のクラスの学習問題として定式化した.そして,その関数の学習アルゴリズムとして,重み付き投票アルゴリズム(WM)を拡張したアルゴリズム(WM^*)を開発した.WMは,複数の予測アルゴリズムを統合して,よりよい精度で予測が行えることを指向するものであり,プールの中の各予測アルゴリズムに予測を投票させ,その投票結果によって全体的な判断を下すものである.我々の拡張によるWM^*は,おのおのの予測アルゴリズムが投票を棄権することを認めるものである.このことにより,直観的には,各予測アルゴリズムは自信のない予測については棄権によって発言権の低下を防ぐことができると期待される.実際に我々は,WM^*による予測の方がWMによる予測よりも原理的に優れていることを理論的に証明した.さらに,このWM^*を組み込んだ領域予測システムHAKKEのプロトタイプを作成し,DNA配列の中から遺伝子領域を予測する実験を行った.また,最も基本的な問題である,パターン照合問題に対して,テキストとパターンが両方とも直線的プログラムで記述されて与えらたときに高速にパターン照合を行うアルゴリズムの開発に成功した。
高速パターン照合アルゴリズムによる知的全文情報処理システムの開発

有川節夫, 井上仁, 竹田正幸, 篠原歩, 篠原武, 松尾文碩

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (A)

研究機関：KYUSHU UNIVERSITY

1995年～ 1997年

詳細を見る詳細を閉じる

本研究は,高速パターン照合アルゴリズムの開発および全文情報処理への構造と機械学習の導入に主眼をおいて,SIGMAシステムの思想を活かしたワークステーションによる新しいテキストデータベース管理システムの開発を目的にしている。本年度は,以下の研究成果を得て,3年間にわたる本研究を成功裡に完了した。 (1)ワークステーション用の知的全文情報処理システムの実現と評価を行い,利用の手引を作成した。 (2)大規模なテキストデータベースのネットワーク上でのやりとりは,データ圧縮をして行われる。したがって,パターン照合アルゴリズムも,圧縮データをそのままの形で扱える方が効率的である。そのための基礎研究を昨年度展開したので,今年度は,その方式の実現と実際のデータを対象にした実験を行った。 (3)6月にデンマークで開催されたこの分野の最も権威ある国際会議(CPM)に出席して,本研究で得られた研究成果を発表し,世界の専門家と討議を行った。 (4)情報圧縮の手法を活用して,ピクチャーとワイルドカードをも扱える新しい高速パターン照合アルゴリズム」の研究開発を行った。 (5)知的全文情報処理システムにおける学習機能に関する研究を完成させて,上記(1)における全体のシステムへ取り込んだ。
発見的探索アルゴリズムの理論と実働化

篠原歩

1996年～ 1996年

詳細を見る詳細を閉じる

人工知能の問題解決において,探索は常に鍵となる役割を果たしている.実際のアプリケーションにおいては,問題固有の知識を利用しながら探索を制御し,探索経路の組み合わせ的爆発に対する工夫を行うことが必要である.このような経験的な知識を利用した探索は,発見的探索アルゴリズムと呼ばれているが,そのパフォーマンスは個々の問題固有の性質に強く依存し,効率の良い探索技法の統一的な開発,解析が極めて困難である.この発見的アルゴリズムを計算論的学習理論の枠組みでとらえ,さらに具体的な問題を用いてその有用性を実証することを目標として研究を展開した. まず,複数の有力なアルゴリズムを統合して,よりパフォーマンスの高いシステムを構築するための手法として,重みつき投票アルゴリズム(WM)の拡張(WM^*)を行った.WMは,各アルゴリズムに予測を投票させ,その投票結果によって全体的な判断を下すものである.我々の拡張によるWM^*は,おのおののアルゴリズムが投票を棄権することを認めるものであり,直観的には,各アルゴリズムは自信のない予測については棄権によって発言権の低下を防ぐことができると期待される.実際に我々は,WM^*による予測の方がWMによる予測よりも原理的に優れていることを理論的に証明した.さらに,このWM*を組み込んだ領域予測システムHAKKEのプロトタイプを作成し,アミノ酸配列データからのαヘリックス部位と膜貫通部位の同定問題に対する計算機実験によって,この優位性を検証した. また,パターン言語の学習可能性を探究し,次のような知見を得た.(1)部分列言語の和集合のクラスは,非常に少ない所属性質問と等価性質問を用いて学習可能である.(2)部分列言語のクラスは,所属性質問のみで学習可能である.(3)パターン言語のある部分クラスは,1つの正例と非常に少ない所属性質問を用いて学習可能である.
機械学習と機械発見による生物情報の概念形成

篠原歩, 正代隆義

1996年～ 1996年

詳細を見る詳細を閉じる

本研究は,塩基配列やアミノ酸配列等の配列データに対して,その中の機能部位や機能領域を予測できるシステムを構築するための体系的な方式を研究し,実用的な領域予測システムを実働化することを目的とする.この目的を達成するために,我々は以下の項目に力点をおいて研究を展開した. (1)領域予測問題の抽象化と定式化.(2)領域予測アルゴリズムの開発.(3)上記アルゴリズムの理論的基礎.(4)計算機実験による上記アルゴリズムの評価. まず,文字列情報の中の特定の機能部位を同定する問題を,文字列の長さを保存する関数のクラスの学習問題として定式化した.そして,その関数の学習アルゴリズムとして,重み付き投票アルゴリズム(WM)を拡張したアルゴリズム(WM^*)を開発した.WMは,複数の予測アルゴリズムを統合して,よりよい精度で予測が行えることを指向するものであり,プールの中の各予測アルゴリズムに予測を投票させ,その投票結果によって全体的な判断を下すものである.我々の拡張によるWM^*は,おのおのの予測アルゴリズムが投票を棄権することを認めるものである.このことにより,直観的には,各予測アルゴリズムは自信のない予測については棄権によって発言権の低下を防ぐことができると期待される.実際に我々は,WM^*による予測の方がWMによる予測よりも原理的に優れていることを理論的に証明した.さらに,このWM^*を組み込んだ領域予測システムHAKKEのプロトタイプを作成し,アミノ酸配列データからのαヘリックス部位の同定問題と,膜貫通部位の同定問題に対する計算機実験によって,この優位性を検証することに成功した.この理論的解析および計算機実験の結果から,我々の提案するWM^*アルゴリズムは複数の戦略を統合する予測アルゴリズムとして従来のWMよりも優れていることが確認できた.
実効的な学習理論の構築

十益ツオイクマン, 篠原歩

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (C)

研究機関：Kyushu University

1995年～ 1996年

詳細を見る詳細を閉じる

研究期間の最初の年度では,LangeとWiehagenのパターン言語の学習アルゴリズムにおける,計算時間の平均的解析を行なった.このアルゴリズムは,すべてのパターン言語のクラスを,正例から極限において同定する.ここでは,学習が終了するまでの平均の時間を,適切なモデルを構築して解析する. LangeとWiehagenのパターン言語の学習アルゴリズムに関連して,次のような結果が得られた.Α={0,1,...,}を任意の有限なアルファベットとするとき,κ個の異なる変数を含むパターンπを学習するためにかかる時間は,最善の場合で,Ο(log_<|A|>(|A|+κ)|π|^2),最悪の場合は,制限なしであることを示した.さらに,正規分布の基で,この計算時間は,平均の場合,Ο(2^κκ^2|A||π|^2log_<|A|>(κ|A|))であり,ほとんどすべての確立分布の基で,この計算時間は,O(2^κκ^2|π|^2log_<|A|>(κ|A|))に節約できることを示した. これらの結果は,その他のパターン言語の学習アルゴリズムに応用可能である.その例として,質問に基づく学習や,良い例からの学習がある. 次の年度では,一変数パターン言語の正例からの学習について研究し,三つの新しいアルゴリズムを得た.はじめのアルゴリズムは,Angluinのアルゴリズムのアップデ-トタイムをO(n^4 log n)からO(n^2 log n)に節約したという点で,画期的である.次に,このアルゴリズムを改良して,効率的な並列アルゴリズムを構築した.さらに,Angluinの包含性質問のみを用いた学習モデルをすべての1変数パターン言語に応用し,有効なアルゴリズムを構築した. 続いて,現在までで,もっとも効率的な1変数パターン言語学習アルゴリズムを構築した.このアルゴリズムは,正例が,その例の長さに依存した確立分布にしたがって選ばれるとき,O(l^2 log l)時間でパターンを学習する.このアルゴリズムの計算時間全体は,最悪の場合は,やはり制限不可能であるが,その平均計算時間は,最善の場合の時間に関係したある定数のみによって制限される.
並列知識獲得システムの開発

宮野悟, 下薗真一, 篠原歩, 正代隆義, 篠原武, 有川節夫, 内田智之, 山本章博

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (A)

1994年～ 1996年

詳細を見る詳細を閉じる

人間が社会活動の中で行っている知識獲得は,獲得された知識の質とその効率により,科学や産業の発展を大きく左右している.情報処理活動の中で,質の良い知識を効率よく獲得できる能力を備えた組織は,分野を問わず,それにより大きな発展を約束されているといっても過言ではない. これまで人間の知的活動として位置づけられてきた知識獲得は,人工知能や知識情報処理技術の発達の中で,学習や類推といった方式により,人間に代わって計算機上のシステムがそれを行うことが研究され,様々の可能性が提示されるようになった. 本研究では,これまでの学習についての基礎的研究の成果とシステム化およびゲノムデータからの知識獲得の研究を基礎にして,次の二つを達成することに成功した. 1.並列知識処理の観点からの知識獲得方式の構築. 2.申請者らが開発した知識獲得システムBONSAIを基本プロセスとした一般性のある並列知識獲得システムの開発. これにより,ネットワーク上で稼働するようなエキスパートシステム等における知識獲得エンジンとしての機能を果たすことが可能となった.また,自然言語及び遺伝子データ等を扱う基礎科学において知識獲得の支援ための基本ツールとして応用することも本研究の応用としてとらえることができる. 現在の社会では,極めて大量のデータが発生しそのデータから有用な知識を獲得することが極めて重要な問題となっている.産業革命により家内製手工業から工場的な生産方式に転換したように,データからの知識獲得も,人間による発見的な方式から,広い範囲に網を打つような自動的な知識獲得方式の構築が急務である.情報検索システムは,最も基本的な形でこうした問題に貢献したものである.本研究は,より高度な知識獲得が並列知識処理の方式により可能となることを実証し,このような情勢に正面から取り組んだ.また本研究で開発したシステムは,ワークステーションシステムの現実的な使用形態を積極的に活用していることから,その実用化は応用の柔軟さ相まって,十分な社会的貢献をなすものといえる.近いうちにこのシステムは東京大学医科学研究所ヒトゲノム解析センターで公開することになっている.こうした,知識獲得システムの情報化社会への自然な浸透により,計算機が行うべき仕事と人間が本来能力を発揮すべき創造といった仕事が分業化され,社会の知的活力は一層増す方向に向かうことになることが期待される.
学習アルゴリズムによる機械発見

有川節夫, 宮野悟, 廣渡栄寿, 篠原歩, THOMAS Zeugm, 新島耕一, 山本章博

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for Scientific Research (B)

研究機関：KYUSHU UNIVERSITY

1994年～ 1996年

詳細を見る詳細を閉じる

本研究は、学習リルゴリズムと機械発見について、論理と方式から、手間と効率化、作業環境に至るまでを体系的に追求し、科学発見の機械化のための基礎を確立することを目的として、以下の各項目について研究を展開してきた。 (1)機械発見の計算可能論理。まず、帰納推論の枠組みで機械発見の論理を展開し、K.Popperの科学者による科学的発見の論理と対照的に、計算機による機械発見においては、仮説空間自体の論駁可能性が、すなわち仮説空間の観測データによる棄却可能性が、本質的であることを明らかにし、そのような仮説空間で十分広いものが存在することを基本形式体系を用いて証明した。 (2)機械発見のための知識表現。科学技術における実験観測データのほとんどが数値データであるにも拘わらず、数値を直接扱う機械学習・機械発見については、体系的な研究がこれまでなされていなかった。本研究では、まず、実数の表現に至るまでの正確な基礎付けを行い、閉区間という表現系を用いて与えられた数値データから微分方程式を学習・発見する方式を研究開発し、有効性を確認した。これは、係数が閉区間で表されるため、一種の精度保証付きの仮説(この場合は、微分方程式)を発見するという、全く新しい方式を提案したことにもなる。 (3)PAC学習による機械発見。帰納推論に基づく機械発見の論理をPAC学習に基づく論理に一般化した。また、PAC学習可能性を示すVC次元に関して計算量理論の観点から詳細な理論を展開した。 (4)大規模データベースからの機械発見。アミノ酸配列等の遺伝子データを対象にした機械発見システムBONSAIを開発し、その並列化版BONSAI Gardenを開発し、実際の多くの領域で分子生物学上の知識の機械発見に成功した。また、これを領域予測のシステムとして発展させ、HAKKEというシステムを開発した。
確率論的近似学習と計算論的教示の理論

篠原歩

1995年～ 1995年

詳細を見る詳細を閉じる

PAC学習可能性に関しては,仮説空間全体の反駁可能性を含めた「反駁PAC学習可能性」を提案し,学習に必要なデータの個数と計算時間についての解析を行った結果,次のような知見が得られた. 1.反駁学習に必要なデータの個数の解明.この結果により,従来のPAC学習モデルにおいて必要とされるデータの個数と,反駁学習モデルにおいて必要とされるデータの個数は,入力されるパラメーターの多項式サイズという点では,同じであることを示した. 2.概念クラスが多項式時間で反駁学習可能となるための必要十分条件となるアルゴリズムの構築.この結果は,多項式時間反駁学習可能性の特徴付けに役立ち,さらには,多項式時間で反駁学習可能となる概念クラスを見つけ出す手がかりとなる. また,実用的に広く用いられている,順序付き二分決定グラフ(OBDD)の学習可能性についても,そのPAC学習可能性を解明した. これらの結果をふまえて,ゲノム情報データからの知識獲得システムBONSAIを並列に走らせて知識獲得を行うBONSAI Gardenシステムを実働化し,計算機実験を行った. 一方,これらの情報処理技術の根幹をなす,文字列照合問題について,パタンもテキストも両方とも圧縮されたデータについて,それらを陽に展開することなく,そのまま文字列の照合を行う多項式時間アルゴリズムの開発にも成功した.これは,今後,さらにさまざまな方向へ拡張が期待される成果である.
探索アルゴリズムの効率化

宮野悟, 下薗真一, 篠原歩, 正代隆義

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for General Scientific Research (C)

研究機関：KYUSHU UNIVERSITY

1994年～ 1995年

詳細を見る詳細を閉じる

本研究課題では,これまで開発されてきた探索技法の有効性と限界を確認し,新たな探索方式の確立と探索アルゴリズムの効率化を計算量理論と実際の両面から行なうことが主な目的であった.この目的に沿って,探索問題を定式化し,探索アルゴリズムの設計とその並列化を行ない,さらに探索方式の現実的検討を行なった.得られた成果は次のようなものである. タンパク質の構造を数学的なグラフとして抽象化し,効率のよい構造探索を行なうための基礎となすために,グラフを項とする論理プログラミングであるFGS (Formal Graph System)の理論を展開した.グラフの認識問題のいくつかは,このFGSの反駁木問題を解くことによって,効率のよい並列アルゴリズムを持つことを証明した。ある文字列から,それを表現する最も小さいグラフを求める問題は,Walk情報からのグラフ再構成問題として知られている.この問題は,キャタピラグラフを入力としたとき,多項式時間近似アルゴリズムさえ持ちそうにないことを証明した.このことから,タンパク質のような有限長の文字列から,効率のよいグラフ表現を導き出すためには,新しい視点からの近似アルゴリズムの研究が不可欠であることがわかり,現在その研究に着手している. タンパク質の探索の中で最も重要なものはモチーフの探索である.このモチーフを表現するために,従来,知識獲得システムBONSAIで用いていた正規パターンを元にして,正規パターンの曖昧さを表すモチーフ表現を構築した.この表現を用いて,正の例と負の例からの知識獲得実験を行ない,成果を得ている. 本研究の成果は,並列知識獲得システムBONSAI Gardenとしてまとめられ,主にゲノムデータからの知識獲得システムとして多くの研究者に利用されている.
計算論的教示の理論

篠原歩

1994年～ 1994年

詳細を見る詳細を閉じる

本研究は,教示と学習のメカニズムを計算量理論の観点からとらえる枠組みを構築し,それらの関係,違いを情報科学的に解明することを目的とするものである.本年度は,まず,PAC学習可能性を完全に特徴づける尺度として知られている,Vapnik-Chervonenkis次元(VC次元)について,その計算量に関する諸問題を解決した.具体的には,VC次元を求める問題と,O(log^n)変数の論理式の充足可能性問題との間の相互の多項式時間還元を与えることによって,この問題がNP完全でもなく,かつ多項式時間では解けないという強い状況証拠を与えることに成功した.こここまた,VC次元の様々な拡張に対しても同様な結果を得ている. 次に,「反駁学習可能性」を,PAC学習の枠組みにおいて定式化し,その特徴付けを行った.反駁可能性とは,想定している仮説空間の中に目標概念をうまく説明するものが存在しない場合に,その仮説空間全体を反駁できることをいい,原理的には,仮説空間そのものの善し悪しを判断する基準となる.ここで定義された反駁PAC学習可能性は,多項式サンプルという観点からは,通常のPAC学習可能性と同値であることを証明した. さらに,コンパクトに表現された文字列に対する多項式時間の文字列検索アルゴリズムを与えた.これは,テキストそのものは長大だが,そのテキストがある規則を用いてコンパクトに表現されているとき,一旦テキストを展開せずに,そのままの形で別の文字列を検索するという新しい手法である.今後は,複数の文字列への対応,近似を許した検索などへの様々な拡張が考えられる.
類推と最小記述長原理によるゲノムデータの知識処理

有川節夫, 篠原歩, 正代隆義

1994年～ 1994年

詳細を見る詳細を閉じる

本研究は,類推についての理論的研究の成果とシステム化の経験を基礎にして,類推という極めて自然で,問題解決の初期の段階で活用される推論方式とMDL原理という強力な知識獲得方式に基づく,ゲノムデータ処理に適した一般性のある知識処理の方式を確立することを目的としている.本年度は,以下の成果を得た. (1)ゲノムデータのための類比の研究配列間のホモロジーに対応するものが「類比」であるが,構造等を考慮したさらに高次の類比の定式化を行った.それと同時に高次パターンマッチングアルゴリズムを研究開発した. (2)MDL原理の研究アミノ酸のインデックス化は,KyteとDoolittleの研究に見られるように,タンパク質の機能・構造予測に極めて有用な概念である.このインデックス化と正則パターン上の決定木を組み合わせた概念は,これまでの研究でその有効性が実証されている.そこで,MDL原理を用いて,アミノ酸配列等のデータからそのインデックス化と決定木を作り出す方式を開発した. (3)類推の効率化およびMDL原理の効率的実現方式の研究これまで開発してきた類推方式で実現されている類推エンジンの高速・効率化を行った.また,(1)の成果に対応した効率の良い新たな類推方式を開発した.さらに,MDL原理を計算機上で実現し,そののアルゴリズムの効率化の理論的限界について研究した. (4)計算機実験高次パターンマッチングアルゴリズム,類推の効率化,およびMDL原理に基づく決定木構成のアルゴリズムを本研究費で購入したワークステーション等を用いて実現し,アミノ酸列からの知識獲得問題に適用し,有用な成果を得た.
確率的近似学習のパラダイムによる遺伝的アルゴリズムの効率の解析および実働化

篠原歩

1993年～ 1993年

詳細を見る詳細を閉じる

本研究の目的は、理論的な研究はすすんでいるが実用的な応用例に乏しいPAC学習のパラダイムと、理論的解析法の整備されないままにも実用的なアプリケーションが開発されつつある遺伝的アルゴリズムを融合し、理論と応用の両面から、生物学的データからの知識獲得を行なうシステムを開発することである。今年度は、以下の知見が得られた。 1.PAC学習可能性を確かめた上でワークステーション上に実働化した知識獲得システム「BONSAI」を、並列化可能性の観点から見直し、そのプロトタイプを作成した。その中で、特に計算量を要する、パターンの検索部分に対し、遺伝的アルゴリズムを適用して、その効果を確かめた。これらの理論的な解析については、今後ともに引き続き重要な研究の課題となると思われる。また、ここで構築したシステムは、実際の遺伝子データのように、もともとの分類のはっきりしない問題に対しても有効であると期待される。 2.PAC学習可能性を特徴づける組み合せ量として重要な、VC次元を求めるための計算量の評価を行った。さらに、これを一般の関数に関して拡張した次元についても同様な解析を行った。その結果、この計算量は、変数の個数を限定した論理式の充足可能性問題との還元可能性で特徴づけられ、NP完全にもなりそうにはないがPで解けそうもない、という、計算量理論の観点からも興味ある知見を得た。この結果は、学習アルゴリズムの計算量の評価とは独立した問題ではあるが、今までと異なる観点から学習モデルを評価する際に有用になると思われる。
確率的近似学習のパラダイムによる遺伝的アルゴリズムの効率の解析および実働化

篠原歩

1992年～ 1992年
並列学習アルゴリズムによる大量ゲノムデータからの知識獲得の研究

宮野悟, 篠原歩, 有川節夫

1992年～ 1992年

詳細を見る詳細を閉じる

1.決定木とインデックス化の機械学習による知識獲得機械学習によって,構造のわからない1次元の文次列データから知識を獲得する手法として,本年度は,初年度に着手した正規パターン上の決定木の学習についての理論的結果に基づき,機械学習システムの基本設計とその中核部分の実働化を行った。そして高度の学習を狙い,その学習可能性,探索に要する計算量などを解析した。そして,これらの理論的研究に基づき,その学習可能性,探索に要する計算量などを解析した。そして,これらの理論的研究に基づき,文字列データからの知識獲得システムBONSAIの開発を行い,ワークステーション上に実働化することに成功した。BONSA夫は,文字列データからの知識獲得システムである。このシステムは正の例と負の例の集合が与えられると,それらを分類する仮説として,アルファベットのインデックス化と正規パターン上の決定木を発見する。アルファベットのインデックス化とは,入力データに使われている文字を,あらかじめ設定された,より少ない個数の文字へ変換する対応づけである。例えば,アミノ酸配列のデータを入力とした場合,20種類のアミノ酸の記号を数種類に分類することに相当し,このようなアミノ酸の分類は分子生物学の世界で普通に行われていることである。正当パターン上の決定木とは,各ノードに正規パターンと呼ばれる判定規則を用いた決定木である。正規パターンとは,「モチーフ」を一般化した概念である。BONSAIから出力された決定木のノードに現れる正規パターンから,重要なモチーフが抽出されることになる。また同時に,タンパク質の分類にBONSAIを利用した場合,BONSAIが発見してくるインデックス化から,アミノ酸のどのような分類が有効であるのかを知ることができる。 2.実験結果BONSAIは膜貫通領域予測問題に対して極めて精度の良い仮説を発見した。それとともに,インデックス化の探索の方法として用いた局所探索法によって,親水度にほとんど対応したインデックス化をBONSAIが発見したことは,この方式の有効性を十分に証明している。またシグナル配列の問題に対しても極めて良いインデックス化と決定木を発見している。
学習と教示のアルゴリズム論的研究

宮野悟, 宮原哲浩, 篠原歩, 有川節夫

提供機関：Japan Society for the Promotion of Science

制度名：Grants-in-Aid for Scientific Research

研究種目：Grant-in-Aid for General Scientific Research (C)

研究機関：Kyushu University

1990年～ 1991年

詳細を見る詳細を閉じる

本研究では,まず「教示可能性」という概念の定式化に成功し,従来のPAC学習可能性(確率的心似学習)との関係を明らかにした.そして,この枠組みの中で,教示し易いが学習しにくい概念クラスなどを具体的に示した.また,学習のための小さな教材を作成することの困難さについても言及することができた.また類推による教示と学習の研究では,計算量を考えた研究がほとんどなされていない状況であったが,有川・原口の類推機構の中にNP困難な状況が現れることを明らにした.こうして,この類推機構では最も基本的な部分の計算量が大きくなる可能性が強く,この部分を合理的に解決することが新たな課題として生まれた. 教示と学習の研究の中で概念クラスの小さな集合被覆を求める問題が教示可能性と深く関係していることを示したが,そのための並列アルゴリズムの研究を行い極大独立点集合を用いるという着想で極小な集合被覆を求める並列アルゴリズムを得ることができた. 学習の理論を発展させる過程で教示のためのkeyと呼ばれる概念に到達したが,このKeyを発見するための方式を開発することがこの研究を進めるうえで不可欠であることが判明した.そこで研究をこのkey発見のための方式の追求に集中した.その結果,正則パタ-ン上の決定木という概念に到達し,与えられたサンプルからそれを合理的に説明する正則パタ-ン上の決定木を学習するアルゴリズムを開発した.そしてサンプルから正則パタ-ン上の決定木を学習するシステムを試作した.この学習システム上での様々な実験を通して,この方式が他の分野においても極めて有効であることを確認した.また極小な集合被覆を求める近似アルゴリズムを核にして,与えられたサンプルをEFSとして合理的に説明する仮説を作り出す方式をつくり,それに基づいたシステムを試作した.そして,上述の正則パタ-ン上の決定木を学習する方式との比較を行った.その結果,上述の学習システムのほうがより効率的であることが判明した.しかし,EFSに基づく方法はより大きな多様性をもっていることも明らかになった.今回試作した学習システムとこの研究を通して得られた知見はこの様なシステムを構築するための基礎理論と技術を与えるものと確信する.
ソフトウェア構成法における類推と帰納推論

有川節夫, 篠原歩, 篠原武, 宮野悟

1990年～ 1990年

詳細を見る詳細を閉じる

高機能高品質ソフトウェアの構成法を類推と帰納推論の観点からモデル化して,その本質に迫ることが本研究の目標である.この目標に沿って本年度は,論理型言語PrologとEFSを対象にして以下の要領で研究を行い多くの基礎的な成果を得た.ソフトウェア開発者は,問題が与えられたとき通常次の3つの手順で考える.(1)過去に同じ問題を扱ったことはないか.(2)過去に類似した問題を扱ったことはないか.(3)全く新しい問題であるか.本研究で対象にするのは(2)と(3)の場合である. (2)の場合には類推が使われることになる.具体的には,以下のようなプロセスが使われる.すなわち,開発しようとしているプログラム“A"に類似したプログラムBを選び出し,Bとゴ-ルの例glとを対象にして類推を行い,そこで使われたプログラム節C1を取り込む.こうしたプロセスを何回か繰り返して,ゴ-ルの例gl,…,gnに対して節Cl,…,Cnを取り込んで,“A"の骨格を形成する.この方式の理論を構築した.具体的には,まず類推のための抽象化の研究を行い,類推のソ-スを検索するために,プログラムを抽象化によって索引付け,それを用いて可能性のない対象を捨てる方式を開発した.また,学習の主要なパラダイムとして注目を集めているEBL(説明に基づく学習)の類推による拡張を行った. (3)の場合には,帰納推論が活用され得る.本年度は,EFS(Elementary Formal System)という文字列を直接扱える一種の論理型言語を用いて,帰納推論の統一的枠組みを与え,このEFSの有効性を明らかにした.また,正デ-タからの帰納推論の能力が実は相当に大きいことやPAC学習可能な言語族等をEFSの枠組みで明確にした.さらに,Muggletonによる逆導出法についても基礎研究を行い,初年度の研究は,ほぼ計画通りの成果が得られた.

︎全件表示 ︎最初の5件までを表示

担当経験のある科目(授業) 2

知能システム科学　東北大学大学院情報科学研究科
オートマトン・言語理論　東北大学工学部

社会貢献活動 2

東北大学サイエンスカフェ

2007年8月31日～

詳細を見る詳細を閉じる

第２５回「ロボカップサッカーと人工知能～考えるロボットは実現できるのか？」
ときめき☆ひらめきサイエンスようこそ大学の研究室へ日本学術振興会

2007年8月9日～

詳細を見る詳細を閉じる

科研費による研究成果の一端を高校生が見る，聞く，触れることで，学術と日常生活との関わりや，科学がもつ意味を理解してもらうプログラム．「アルゴリズムを体感しよう ---ロボットプログラミングを通じて---」と題して，講演とロボットプログラミングの実習を行った．