Study of index construction and compression algorithms in fully-online setting

全在线环境下索引构建和压缩算法研究

• 批准号: 21K17817
• 负责人: 高木 拓也
• 金额: $ 2.58万
• 依托单位: Fujitsu Limited (Fujitsu Research)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21K17817/
• 关键词: 文字列情報学; 全文索引; オンライン索引; 圧縮索引; 接尾辞木; 羅生門集合; 説明可能性; 圧縮アルゴリズム; 完全オンライン索引

本研究は，様々な文字列情報学における問題に対し「どのようにすれば完全オンラインへの拡張が可能か？」を明らかにすることを目標としている．特に，(i)文脈性 (ii)完全オンライン性 (iii) 低メモリ性をもつ索引，すなわち「完全オンライン圧縮文字列索引」の構築を目指している．これを実現するためには，圧縮索引の通常オンライン構築アルゴリズムの開発と，その完全オンライン化の二つのステップが必要である．2022年度は機械学習分野において決定木モデルの列挙構造が動的計画法と同様の構造を持つことを見出し，『羅生門集合』と呼ばれる最適決定木とほとんど同じ精度を持つ決定木の集合を構築するアルゴリズムを初めて与えることに成功した．列挙した決定木は特徴量数の指数個存在する可能性があるため，これを保持するためにはよりコンパクトな索引が必要となる．この課題に対して本研究の圧縮索引構造のアイデアを用いることにより解決することに成功した．羅生門集合は機械学習モデルの説明可能性から近年注目されている概念であり，今後決定木以外のモデルへの拡張が考えられる．また昨年度に引き続き，東北大学のDiptarama Hendrian助教授・九州大学の稲永俊介教授らの協力のもと，昨年度おおむね完成していた最近印付き祖先（Nearest Marked Ancestor）クエリ構造を利用する線形サイズ接尾辞木（Linear-size Suffix Tree）の構築アルゴリズムを精査し具体的な手法を与えることに成功した．

This study is aimed at solving the problem of character string informatics: "How can we solve the problem of complete character string informatics?" The first time I saw him, I saw him. In particular,(i) contextual (ii) completely independent (iii) low-independent index construction refers to the construction of a "completely independent compressed text string index." In 2022, it was necessary to reduce the development of index structure and complete index structure. In 2022, it was necessary to reduce the development of index structure and complete index structure."Rashomon Collection" is the most suitable decision tree. It is the same precision. It is the first decision tree to construct the collection. The index of the characteristic quantity of the column is necessary. This paper presents a method for solving the problem of compression index structure. Rashomon set is a mechanical learning model. It is possible to explain the concept of Rashomon set in recent years. Last year, Diptarama Hendrian Assistant Professor of Tohoku University and Professor Toshisuke Inaga of Kyushu University cooperated with each other. Last year, the Nearest Marked Ancestor was completed. The structure of the tree was used to construct the Linear-size Suffix Tree.

项目成果

Counterfactual Explanation Trees: Transparent and Consistent Actionable Recourse with Decision Trees

• 发表时间: 2022
• 作者: Kentaro Kanamori;Takuya Takagi;Ken Kobayashi;Yuichi Ike

Distribution-Aware Counterfactual Explanation by Mixed-Integer Linear Optimization

通过混合整数线性优化进行分布感知反事实解释

• DOI: 10.1527/tjsai.36-6_c-l44
• 发表时间: 2021
• 期刊: Transactions of the Japanese Society for Artificial Intelligence
• 作者: Kanamori Kentaro;Takagi Takuya;Kobayashi Ken;Arimura Hiroki
• 通讯作者: Arimura Hiroki

Ordered Counterfactual Explanation by Mixed-Integer Linear Optimization

通过混合整数线性优化进行有序反事实解释

• 发表时间: 2020
• 期刊: 35th Conference on Aritificial Intelligence (AAAI 2021)
• 作者: Kentaro Kanamori;Takuya Takagi;Ken Kobayashi;Yuichi Ike;Kento Uemura;Hiroki Arimura
• 通讯作者: Hiroki Arimura

Explainable and Local Correction of Classification Models Using Decision Trees

• DOI: 10.1609/aaai.v36i8.20816
• 发表时间: 2022-06
• 作者: Hirofumi Suzuki;Hiroaki Iwashita;Takuya Takagi;Keisuke Goto;Yuta Fujishige;Satoshi Hara

Exploring the Whole Rashomon Set of Sparse Decision Trees

探索整个罗生门稀疏决策树集

• 发表时间: 2022
• 作者: Rui Xin;Chudi Zhong;Zhi Chen;Takuya Takagi;Margo Seltzer;Cynthia Rudin
• 通讯作者: Cynthia Rudin