配列の対を生成する統計的言語モデルの開発と配列解析への適用

生成序列对的统计语言模型的开发及其在序列分析中的应用

• 批准号: 15700244
• 负责人: 上田 展久
• 金额: $ 1.73万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2003
• 资助国家: 日本
• 起止时间: 2003 至 2005
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-15700244/
• 关键词: 統計的言語モデル; 確率文脈自由文法; EMアルゴリズム; 確率モデル; 周辺化グラフカーネル; 化学構造; 分類; ラベルつき順序木; ラベル付き順序木; 動的計画法; 糖鎖

本研究の対象である,複雑な構造を持つ配列を解析するための統計的言語モデルとして,大域的な依存性を持つ配列(大域依存配列)の対を生成する効率的な言語モデルを開発した.ここでは大域的な依存性として,回文のような任意の距離で離れている文字間の依存性を考えた.このような大域依存配列の対を生成する既存の統計的言語モデルとして,対確率文脈自由文法が知られているが,この文法では,尤度の計算に文長の6乗に比例する時間が計算時間として必要になる.これに対して,開発したモデルでは文長の4乗に比例する時間で尤度の計算時間の上限が抑えられることを示し,開発したモデルにより時間効率が向上できることを明らかにした.このモデルは,大域依存配列を生成する効率的な言語モデルを開発し,対の配列に対する文法に拡張することにより実現された.大域依存配列に対する既存の言語モデルである確率文脈自由文法では,尤度の計算に文長の3乗に比例する時間が必要となる.一方,開発したモデルでは,大域依存配列を表せる表現力を持ちながら,尤度の計算時間は文長の2乗に比例する時間で抑えられることを示し,効率性を向上させた.合わせて,確率パラメータをデータから学習するEMアルゴリズムを導出し,尤度を増加させるパラメータ更新に掛かる時間も文長の2乗に比例する時間で抑えられることを示した.これらの結果をまとめた論文を現在投稿している.また,昨年まで行なった(a)順序付きラベル木に対する確率モデルと(b)確率モデルに基づくグラフ構造の解析方法について,(a)はバイオインフォマティクスの特集号,(b)は化学情報学の論文誌にそれぞれ論文が掲載された.

This study aims to analyze the structure of complex structure, maintain alignment, analyze statistical speech, and develop effective speech for large domain dependency, maintain alignment (large domain dependency alignment), and generate pairs. A study of the dependency between characters in a large domain, a palindrome and an arbitrary distance. The large domain dependent arrangement and the corresponding generation of existing statistical speech patterns, the accuracy of context-free grammar, the grammar, especially the calculation of text length and 6-point ratio, the calculation time and the necessary time. The time limit of the calculation time is higher than the time limit of the calculation time. This is the first time that a domain dependent arrangement has been created. Large domain dependent arrangement is necessary for the calculation of the length of text and the proportion of text in the context of free grammar. On the one hand, the development of a large domain depends on the allocation of the table, the performance of the table, especially the calculation time and the length of the text, the proportion of the time, the efficiency of the table. In addition, the accuracy of the rate of change in the learning process, especially the increase in the rate of change in the learning process, and the increase in the rate of change in the learning process. The results of this paper are now being submitted. In the past year, we have conducted research on (a) the accuracy of the sequence analysis,(b) the accuracy of the analysis method of the basic structure,(a) the special collection number of the chemical information,(b) the paper published in the Journal of Chemical Informatics.

项目成果

A probabilistic model for mining labeled ordered trees: capturing patterns in carbohydrate sugar chains

挖掘标记有序树的概率模型：捕获碳水化合物糖链中的模式

• DOI: 10.1109/tkde.2005.117
• 发表时间: 2005
• 期刊: IEEE Transactions on Knowledge and Data Engineering
• 影响因子: 8.9
• 作者: Nobuhisa Ueda;Kiyoko F. Aoki;Atsuko Yamaguchi;T. Akutsu;Hiroshi Mamitsuka
• 通讯作者: Hiroshi Mamitsuka