# 修論　メモ

## イントロ

### 研究背景
司法判断やローン承認などの重要な意思決定タスクへの機械学習モデルの適用において，モデルの解釈可能性に関する懸念が高まっている[Guidotti:CSUR,Rudin:NMI2019]．
モデルの予測に基づく意思決定が個人に大きな影響を与える可能性がある場合，意思決定者は意思決定の理由を提供し，ユーザーにその正しさを保証しなければならない[Rudin:NMI2019]。
そのため、決定木やルールセット、ルールリストなどの解釈可能なモデルの学習が近年注目されている[hastie2001eslbook,Guidotti:CSUR,angelino:rudin:kdd2017corels,hara:ishihata:aaai2018rulemodels].
これらのモデルは解釈可能な形（シンプルな"if-then"ルールの組み合わせ）で表現されているため、モデルがどのように予測を行うのかを、人が容易に理解し、検証することができます。

最近では、解釈可能なモデルについて、異なる特徴を用いることで、ほぼ同等の精度を持つ複数のモデルが存在するという状況についても懸念されている。[semenova:rudin:parr:arxiv2019rashomon,Marx:ICML2020,Hancox-Li:FAT2020]
Breiman[breiman:statsci2001twocultures]は、このような現象を「羅生門効果」と名付け、モデルに対する解釈の多重性の問題を指摘している。
Fisher, Rudin, and Dominica[Fisher:JMLR2019]は，これらの観察結果に触発されて，最適に近い精度を達成するモデルの集合を特徴づける研究を開始しました（これを彼らは「羅生門セット」と呼びました）．
大雑把に言うと、ある誤差許容度$\varepsilon \geq 0$を持つモデルクラスのRashomon setは以下のように定義されます。
$$ \mathcal{R}_{\varepsilon} := \{h \in \mathcal{H} | L(h) \leq L(h^*) + \varepsilon \} $$
ここで、$L$は経験的リスクであり、$h^* \in \mathcal{H}$は経験的リスクを最小化する最適モデルである。

このように$\mathcal{R}_\varepsilon$に含まれるモデルは、同じような精度を達成するものの、個々の入力に対する予測が著しく異なることが多く、異なる性質を持つ可能性がある[Rudin:NMI2019,Marx:ICML2020,Hancox-Li:FAT2020]。
このように、羅生門セット$\mathcal{R}_\varepsilon$を特徴づけることは、特定の予測問題に対するあるモデルクラス$\mathcal{H}$の信頼性を検証する上で重要な役割を果たします。
[Marx:ICML2020].

羅生門セットには、多様な振る舞いを持つ、ほぼ同じ精度のモデルが含まれる可能性があるため、羅生門セットの特徴付けは、特定の予測問題に対するあるモデルクラス$\mathcal{H}$の信頼性を検証する上で重要な役割を果たします[Rudin:NMI2019,Rudin:arXiv2021]。
羅生門セットを特徴づける基準は、様々な観点からいくつか提案されています。
例えば，羅生門集合の特徴としては，解釈可能性[Fisher:JMLR2019]だけではなく，モデル空間に対する体積の比率[Semenova:rudin:parr:arxiv2019rashomon],
だけでなく、予測多重性(Predictive multiplicity)[Marx:ICML2020]やFairness~Coston:ICML2021,Aivodji:NIPS2021}もあります。

羅生門集合$\mathcal{R}_\varepsilon$を既存の基準で特徴づけるためには、与えられたデータセット上で、あるモデルクラス$\mathcal{H}$に対する$\mathcal{R}_\varepsilon$を計算する必要がある場合が多い。

しかし，羅生門集合を計算するアルゴリズムは近似的なものを除いてほとんどなく，正確に計算することは困難である。
Semenovaは決定木の羅生門集合を近似的に計算するためのサンプリングベースのランダム生成法を発表しました。

一方でRuggieri[Ruggieri:ICML2017]は異なる決定木を体系的に列挙するアルゴリズムを提案していますが、原・石畠[hara and Ishihata~hara:ishihata:aaai2018rulemodels]はLawler法 framework~Lawler:MS1972}を用いてtop-$K$個の異なるルールリストとルールセットを列挙する効率的なアルゴリズムを提案しています。

既存の手法[semenova:rudin:parr:arxiv2019rashomon, hara:ishihata:aaai2018rulemodels]は、複数の異なるモデルの集合を提供することができますが、それらは対象となる羅生門集合$\mathcal{R}_\varepsilon$の中で最適に近いモデルのサブセットを生成することができるランダム化または近似的なアルゴリズムです。

したがって、現実のデータセット上で解釈可能なモデルのクラスのための羅生門セットを正確に計算し、羅生門セットを特徴づける既存の基準を測定した人はいません[Rudin:NMI2019]。

私たちの貢献は以下のようにまとめられます。

ルールリストクラスの羅生門集合を計算するための厳密なアルゴリズム**CorelsRS**を提案します。
本アルゴリズムは、単一の最適なルールリストを学習するための洗練された分岐結合アルゴリズムであるCORELSに基づき、ルールの長さなどの特定の制約の下で、与えられたデータセット上の羅生門セットのすべてのルールリストを効率的に列挙することができます。

COMPAS datasetを用いた実験により、我々の提案したアルゴリズムが羅生門集合の全てのルールリストを列挙することに成功したことを確認した。
さらに，本アルゴリズムで得られた羅生門集合を用いて，COMPASデータセット上のルールリストの特性を，predictive multiplicity[Marx:ICML2020]，unfairness range[Coston:ICML2021, Aivodji:NIPS2021]の観点から分析した．

### 研究目的

### 研究内容

### アブスト
司法判断のような重要な意思決定タスクへの機械学習モデルの適用においては、異なる特徴に依存して同様の精度を達成するモデルが複数存在することが多く、これを "羅生門効果 "と呼んでいます。
このようなモデルの集合は「羅生門集合」と呼ばれ、多様な振る舞いをするほぼ同等の精度のモデルが含まれている可能性があるため、羅生門集合を特徴づけることは、特定の予測問題に対する特定のモデルクラスの信頼性を、その解釈可能性、予測の多義性、公平性の観点から検証する上で重要な役割を果たします。
しかし、既存の手法では 羅生門集合を近似的に計算するもので、あるモデルクラスの羅生門集合を正確に計算するには 羅生門集合を正確に計算することはまだ困難である。
本論文では、解釈可能なモデルとしてよく知られているルールリストのクラスに注目し、ルールリストの羅生門集合の厳密な計算方法を研究します。
羅生門集合を正確に計算するために、最適なルールリストを学習する最新のアルゴリズムであるCORELSを拡張し、効率的なルールリストを提案します。羅生門集合のすべてのルールリストを列挙する効率的なアルゴリズムを提案する。羅生門集合のすべてのルールリストを列挙する効率的なアルゴリズムを提案する．
提案したアルゴリズムを用いて 提案したアルゴリズムを用いて，COMPASデータセットで学習したルールリストの羅生門セットを分析した．COMPASデータセットで学習されたルールリストの羅生門セットを、その予測の多さと公平性の観点から分析した。公平性の観点から分析した。

## 準備
### \subsection{Notation}
正の整数$n, m \in \mathbb{N}, n \leq m$とし、$[n]:=\{1, ..., n\}, [n, m] :=\{n, n+1, ..., m\}$とする。命題$\psi$に対して、$\mathbb{I}[\psi]$は指示関数である。もし$\psi$が真ならば、$\mathbb{I}[\psi]=1$であり、もし$\psi$が偽ならば、$\mathbb{I}[\psi]=0$である。

この論文では、予測問題として二値分類問題（binary classification problem）を考える。ここで、$\mathcal{J} \in \mathbb{
N}$は特徴量数である。入力と出力をそれぞれ$\mathcal{X} \subseteq \mathbb{R}^{\mathcal{J}}, \mathcal{Y}=\{0, 1\}$とする。他のほとんどのルールリストを学習する研究のように[citation]、全ての特徴量は二値特徴量であると仮定する。すなわち、$\mathcal{X}=\{0, 1\}^{\mathcal{J}}$である。例（example）は入力ベクトル$\bold{x}=(x_1, ..., x_{\mathcal{J}}) \in \mathcal{X}$と出力ラベル$y \in \mathcal{Y}$のタプル$(\bold{x}, y)$である。また、サンプル（sample）は$N$個の例の集合$S=\{(\bold{x}_n, y_n)^{N}_{n=1}\}$である。関数$h:\mathcal{X} \rightarrow \mathcal{Y}$を\itaric{分類機}（classifier）と呼ぶ。

分類機$h$とサンプル$S$が与えられたとき、$h$の経験的リスク（empirical risk）を以下のように定義する。
$$L(h|S):=\frac{1}{N}\sum^{N}_{n=1}{l(y_n, h(\bold{x}_n)} \in [0, 1]$$
ここで、$l: \mathcal{Y} \times \mathcal{Y} \rightarrow \mathbb{R}_{\geq 0}$は損失関数であり、予測$h(\bold{x})$と真のラベル$y$の違いを測る関数である。この論文では、0-1損失$l(y, \hat{y})=\mathbb{I}[y \neq \hat{y}]$を仮定する。$S$上の$h$の誤分類数（number of misclassifications）を$ \#Err(h|S)):= \sum^{N}_{n=1}{l(y, h(\bold{x}_n)) \in [0, ..., N]}。ここで、$L(h|S)= \frac{1}{N} \#Err(h|S)$である。

\subsection{Rule List}
この研究では、分類機のクラスとして、以下で定義する\bold{ルールリスト}（Rule List）と呼ばれる予測モデルに着目する。$J$個の特徴量の集合$[J]$を仮定すると、$\mathcal{X}=\{0, 1\}^{J}$上の連言（term）$t$はブーリアン特徴量の論理積$t=(x_{i_1} \wedge \cdots \wedge x_{i_l})$であり、これは$t$が真なら〜のような、Boolean assertion $t_1 : \mathcal{X} \rightarrow \{0, 1\}$を表している。
語彙（vocabulary）と呼ばれる、タームの有限集合$\mathcal{T}=\{t_i\}^{M}_{i=1} \subseteq 2^{[J]}$を仮定する。例えば、$"(age=18-20) \wedge (sex=Male)"$は実験で使用したタームである。既存研究通り、$\mathcal{T}$は頻出アイテムマイニングアルゴリズムを用いて、事前に列挙してあると仮定する。

$\mathcal{T}$上の長さ$K \geq 0$のルールリストは$K$個の異なるassociation rulesであり、$k=1, ..., K$に対して、$r_k = (t_k \rightarrow q_k) \in \mathcal{T} \times \mathcal{Y}$で構成されている$(K+1)$-タプル $d=(r_1, ..., r_K, r_{K+1})$である。（要確認）
##########
T上の長さK ≥ 0のルールリストは、k = 1, ... ... , Kについて、K個の明確な連想ルールrk = (tk → qk) ∈ T × Yからなる(K + 1)タプルd = (r1,...,rK,rK+1)である。, Kである。これは、条件文「if t, then q」に続くデフォルトルールrK+1 = (1 → q0) ∈ {1} × Yに対応する。× ここで，1は真を表す。
前置詞tk : X → {0, 1}は入力ベクトルxに対する前提条件であり、後置詞q∈Yは入力ベクトルxに対する条件を示す。
sequent q∈Yは予測値yを示す。図1はルールリストの一例である。
すべてのk ≤ Kに対して，π = (r1,...,rk)は，長さlen(π)=kのdの前置詞である．
また ◦でルールの連結を表す。
HとH⩽Kで表すと、すべてのルールリストとすべてのルールリストのクラスTT のクラスをHとH⩽Kとします．それぞれ，T上のすべてのルールリストと最大K≧0の長さのすべてのルールリストのクラスです．
###############

サンプル$S$、トレードオフパラメータ$\lambda \geq 0$、候補タームの集合$\mathcal{T}$が与えられたとき、ルールリストの学習問題は以下のように定式化される:
$$
h_{d^*} = \arg \min_{h_{d} \in \mathcal{H}_{\mathcal{T}}} R_{\lambda}(h_d | S) := L(h_d | S) + \lambda \cdot |d|．
$$
上の問題の最適解を見つけるのは困難な組合せ最適問題であるが、この問題はCORELSのような最近の分枝限定法による最適化アルゴリズムを用いることで、効率的に解くことができる。
ルールリストは"if then else"で表されるような予測モデルである。

\section{Problem Statement}
この章では、ルールリストに対する羅生門集合を厳密に計算する問題を正式に定義する。また、羅生門集合を解析する指標について紹介する。
\subsection{Computation of Rashomon Sets}
良いモデルを特徴づけるため、準最適な精度を達成するモデルの集合として、羅生門集合が紹介されている。予測問題$(\mathcal{X}, \mathcal{Y})$に対して、$\mathcal{H}$を分類機$h : \mathcal{X} \rightarrow \mathcal{Y}$の集合とする。$\mathcal{H}$を\iter{モデルクラス}と呼ぶ。既存研究に従って、羅生門集合をある損失関数$l$と与えられた誤差許容度$\varepsilon \geq 0$に関して、与えられた\iter{基準モデル}（reference classifier）$h_0 \in \mathcal{H}$に近い精度を達成する分類機の部分集合として定義する

\definition 1
モデルクラス$\mathcal{H}$、基準モデル$h_0 \in \mathcal{H}$、サンプル$S$と誤差許容度$\varepsilon \geq 0$が与えられたとき、羅生門集合$R_\varepsilon (h_0 | S)$は以下のように定義される：
$$
R_\varepsilon (h_0 | S) := \{ h \in \mathcal{H} | L(h | S) \leq L(h_0 | S) + \varepsilon \}．
$$
既存研究と同様に、基準モデル$h_0$を学習問題に対して、CORELSを用いることで得られる最適なルールリスト$h_{d^*}$と仮定する。注意点として、本研究の結果と基準モデル$h_0$の選び方は無関係である。

モデルクラス$\mathcal{H}_{\mathcal{T}}^{\leqslant K}$を解析する最初の問題を以下のように正式化する。
\Problem 1
与えられたサンプル$S$、タームの集合$\mathcal{T}$、基準モデル$h_0$、誤差許容度$\varepsilon \leq 0$とルールリストの長さ$K \leq 0$に対して、羅生門集合$R_{\varepsilon}(h_0 | S) \subseteq \mathcal{H}_{\mathcal{T}}^{\leqslant K}$を計算する。
問題１を解くことによって、ルールリストの羅生門集合$R_{\varepsilon}(h_0 | S)$を得ることができる。また、与えられた予測問題$S$上のモデルクラス$\mathcal{H}_{\mathcal{T}}^{\leqslant K}$の性質を次のsubsectionで説明する様々な視点から解析することができる。

\subsection{Evaluation Criteria for Characterizing Rashomon Set}
あるモデルクラスの性質を特徴づけるためのいくつかの有用な指標が提案されている。

\subsection{}

\subsubsection{Predictive Multiplicity}

\subsubsection{Unfairness Range}

\section{Algorithm}

\subsection{}

\subsection{}