人工知能・機械学習・自然言語処理周辺の技術情報

2018-10-02

【論文解説】Learning Certifiably Optimal Rule Lists

文責:菊地真人

著者:Elaine Angelino, Nicholas Larus-Stone, Daniel Alabi, Margo Seltzer, Cynthia Rudin
会議名:SIGKDD 2017
開催年:2017

目次

どんなもの?
先行研究と比較して
技術や手法の要点
有効性の検証
議論の余地はあるか

どんなもの?

相関ルールリストの作成を目的として,離散最適化の枠組みを提案した.提案手法は証明付きの最適解を提供し,様々な境界(bounds),効率的なデータ構造,計算上の再利用を駆使することで高速化と消費メモリ量の削減を実現した.

先行研究と比較して

相関ルールの予測問題において最適化の枠組みを取り入れ,透明性のあるモデルを提案した.

技術や手法の要点

正則化付きの経験的リスク関数を最小化する枠組みで以下を提供する.
A) 最適解
B) 最適性の証明
C) 近似的な(複数の)最適解,およびそれらと真の最適解との距離

有効性の検証

二つのタスクを用い,8つの既存アルゴリズムとの性能比較を行った.
タスク1:過去二年間の再犯率予測(ProPublica COMPASデータセットを使用)
タスク2:職務質問による武器の発見予測(NYCLU 2014 stop-and-friskデータセットを使用)
提案手法は,精度を犠牲にすることなく短いルールリストを学習し,他アルゴリズムと同精度の予測モデルを生成できる.そして最適解への収束も高速であった.アルゴリズム内で設定した境界を使用することで効率的かつ大幅にルールの探索空間を削減できることを示した(タスク1では数十秒以内,タスク2では一秒未満で目的関数が最適解となった).

議論の余地はあるか

社会的影響への重要性から,提案手法は解釈可能な予測モデルの生成に利用できる.加えて解釈可能性には様々な意味があるため,本稿のアイデアは解釈可能性の他の定義にも拡張できる.他には次の応用が考えられる.例えば,因果推論,ルールリスト空間を探すためのモンテカルロ探索など.