LIME (Local Interpretable Model-agnostic Explanations)

본 내용은 "Why should i trust you?: Explaining the predictions of any classifier." 논문의 내용을 참조하여 작성되었습니다.

Introduction

의사결정을 위해 다양한 분야에서 머신러닝 기법이 활용되기 시작했습니다. 하지만 머신러닝 모형 대부분은 블랙박스(black box)모형이기에 해석이 어렵다는 단점이 있습니다. 최근 이를 해석하기 위한 연구가 활발히 진행되고 있습니다.

논문에서는 결과를 신뢰하는 것을 예측결과 신뢰도와 모형 신뢰도로 정의합니다.

예측결과를 신뢰(Trusting a prediction) 하는 것은 개별 예측결과를 믿고, 의사결정을 할 수 있는가에 대한 문제입니다. 예를 들어, 감기를 예측 하는 모형을 가정해보겠습니다. 어떤 사람의 진료결과를 모형에 넣었을 때, "감기 입니다." 라고 말해주는 것 보다는, 두통의 정도가 90이고 증상에 대한 점수가 -50일 때, 합이 40이니 "감기 입니다."라고 결론을 주는 것이 의사 결정에 큰 도움이 될 것입니다.

모형을 신뢰(Trusting a model)하는 것은 모형 자체를 믿을 수 있는가에 대한 문제입니다. 검증 데이터(validation data) 기반으로 모형을 평가하고, 주로 정확도(accuracy)를 이용하여 모형의 성능을 평가합니다. 하지만, 학습 모형을 실 데이터에 적용해보면 정확도를 과대측정하는 경우가 많습니다.

논문에서는 두 가지 신뢰도 문제를 해결하기 위하여 두 방법을 제안합니다.

LIME: 예측결과를 설명해주는 알고리즘으로 국소적으로 해석가능한 모형으로 근사시켜줍니다.
SP-LIME: 모형 전체의 신뢰도를 확인하기 위해, 결과를 대표할 수 있는 데이터 몇 가지를 선택해주는 알고리즘입니다.

Local Interpretable Model-agnostic Explanations (LIME)

Interpretable Data Representations

LIME을 설명하기 앞서 feature와 Interpretable data representations으로 구분짓겠습니다. Blackbox 모형을 해석하기 위해서는 사람이 해석할 수 있는 데이터 형태로 표현되어야 될 것 입니다. 즉 실제로 모형에 투입되는 feature와 별개로 인간이 해석할 수 있는 데이터 형태로 나타내는 것을 Interpretable Data Representations이라고 부릅니다.

Interpretable Data Representations의 예시

텍스트 데이터: 단어의 유무를 나타내는 binary vector. (모형에는 word embedding 결과 등이 feature로 이용될 수 있다.)
이미지 데이터: 이미지상 비슷한 부분(super-pixel, segmentation)의 유무를 나타내는 binary vector.
테이블 데이터: 연속형의 경우 feature와 동일하며, 범주형의 경우 각 변수의 수준별 유무를 나타내는 binary vector.

앞으로 $d$차원 데이터의 원데이터를 $x\in\mathbb{R}^{d}$로 나타내고, $x$에 대한 interpretable representation을 $x'\in\{0, 1\}^{d'}$로 나타내겠습니다.

Fidelity-interpretability trade-off

먼저 fidelity와 interpretability에 대해서 살펴보겠습니다.

(Local) Fidelity

논문의 핵심 전제로, 데이터 공간의 전체에서 모형을 설명하는 것은 어려울지라도, 국소적인 데이터 공간(설명하고자 하는 데이터와 가까운 거리에 있는 공간)에서는 의미 있는 모형으로 설명해낼 수 있다는 것입니다.

위 예제를 살펴 보겠습니다. 굵은 빨간 십자가가 설명하고자 하는 데이터 이고, 검은 점선은 explanation입니다. 검은 점선을 전체 모형의 관점으로 살펴보면 우측의 빨간 점 3개와 좌측의 파란 점 2개를 설명할 수 없습니다. 하지만 국소적인 공간에서 검은 점선을 살펴보면 완벽하게 빨간 십자가와 파란 점을 구분해 낼 수 있습니다.

Interpretability

국소 공간의 explanation이 전체 공간을 설명할 수는 없습니다. 왜냐하면 국소적으로 중요한 feature가 전체 공간에서는 중요하지 않을 수 있고, 반대의 상황도 발생할 수 있기 때문입니다. 반면에 전체 공간의 explanation은 국소 공간을 설명할 수 있지만, 이는 모형의 복잡성 때문에 해석(interpretability)하기 어렵습니다.

따라서 local fidelity를 너무 신경쓰면 interpretability은 좋아지지만, global fidelity를 확신할 수 없고, global fidelity에 중점을 두면, local fidelity와 iterpretability이 떨어지게됩니다. 논문에서는 이를 Fidelity-Interpretability Trade-off라고 표현했습니다. (trade-off라는 표현이 잘 와닿지는 않지만.. 아마 곧 이어질 최적화 문제에서 interpretability를 complexity로 대신 반영시키기 때문에 이렇게 표현한듯 합니다..)

Interpretability와 Local fidelity 모두를 반영할 수 있는 explanation을 찾는 과정은 다음과 같이 요약할 수 있습니다.

$f: \mathbb{R}^{d}\rightarrow\mathbb{R}$, $f$는 학습한 모형 (즉 blackbox model).
$g:X'\rightarrow \mathbb{R}, g\in G$, Prediction에 대한 Explanation을 모형 $g$로 정의합니다. 여기에서 $G$는 잠재적으로 해석이 가능한 모형의 집합(예를 들어, linear models, decision trees)으로, 분석결과를 쉽게 설명할 수 있는 모든 모형을 말합니다.
$\Omega(g)$ 모형의 복잡도를 정의합니다. 이는 interpretability와 대조됩니다. 예를 들어, $\Omega(g)$는 Decision Tree, Linear model에서 각각 나무의 깊이, non-zero 계수의 개수를 의미합니다.
$\pi_x(z)$ 유사도 측도 (proximity measure)를 정의합니다. 이는 설명하고자하는 데이터 $x$와 다른 데이터 $z$간의 유사도 측도입니다.

Interpretability와 Local fidelity를 모두 충족시키는 Explanation $g$를 찾기 위한 최적화 문제는 $$\xi(x)=\underset{g\in G}{\operatorname{argmin}}\mathcal{L}(f,g,\pi_{x})+\Omega(g)$$ 로 정의됩니다. 여기에서 $G$는 explanation families, $\mathcal{L}$은 fidelity functions(locality-aware loss), $\Omega$는 complexity measures이다. 이어서 $\mathcal{L}$을 자세히 살펴 보겠습니다.

Sampling for Local Exploration

Local explanation을 생성하기 위해선 데이터가 필요할 것입니다. 텍스트 데이터, 이미지 데이터, tabular 데이터에 따라서 약간의 차이는 있지만, 기본은 설명하고자하는 데이터에서 약간의 변화를 주고 어떤 feature가 변했을 때 결과가 크게 변하면, 모형에 영향을 많이 준다는 것 입니다. 여기에서는 설명하고자하는 데이터 주변을 탐색하기 위해서 어떻게 sampling을 하는지 살펴보고, 앞서 다룬 최적화 문제에서 locality-aware loss를 어떻게 계산하는지 살펴보겠습니다.

LIME의 M은 Model-agnostic을 의미합니다. 즉 모형에 상관없이 local explanation을 생성하는 것이 목적입니다. 따라서 $f$에 대한 특정모형을 가정하지 않고, 하기 내용을 진행하겠습니다. $f$를 국소적으로 설명하기 위하여 다음의 과정을 거칩니다.

$x'\in\{0,1\}^{d}$, $x$의 interpretable representation가 0이 아닌 representation을 랜덤하게 뽑습니다. 샘플링시 두 가지가 고려되는데, '선택되는 representation'+'representation의 수' 모두 uniformly random sampling 합니다. 여기서 얻어진 샘플을 perturbed sample, $z'\in\{0,1\}^{d'}$, 이라고 부릅니다.
$z'$를 feature 형태, 즉 모형의 input 형태 $z$로 바꾸어 준다.
모형 $f$에 $z$를 input으로 넣어, $f(z)$를 얻는다.
Local-aware loss를 다음과 같이 계산한다. (상황에 따라서 다른 loss로 적용가능합니다.) $$\mathcal{L}(f,g,\pi_{x})=\sum_{z,z'\in\mathcal{Z}}\pi_{x}(z)\left(f(z)-g(z')\right)^{2}$$ 즉 interpretable space에서 모형을 적합 시키되, $Y$는 설명하고자하는 모형 $f$의 결과를 이용하고, $x'$의 perturbed sample $z'$를 이용하고, $f(z)-g(z')$ 오차의 정도 $x$와 유사할 수록 더 크게 반영시키는 형태입니다.
위 오차를 이용해서 앞서 제시된 최적화 문제를 풀어 explanation $g$를 얻습니다.

데이터 형태(텍스트, 이미지, tabular)별로 perturbed sample 을 구체적으로 살펴보겠습니다.

텍스트 데이터의 interpretable space는 어떤 단어의 유무를 나타내는 binary vector입니다. 예를 들어 "I hate the dog."라는 문장이 있으면 perturbed sample은 "I hate", "I the dog", "I hate dog", "I dog" 등이 됩니다.
이미지 데이터의 interpretable space는 super-pixel의 유무를 나타내는 binary vector로 나타낼 수 있습니다. 슈퍼 픽셀 중 몇개를 랜덤하게 뽑고, 뽑히지 않은 부분은 회색으로 가린 것이 perturbed sample이 됩니다. 이를 input으로 $f$에 넣으면 활성화된 부분 중 어떤 부분이 결과에 큰 영향을 주었는지 알 수 있습니다.
Tabular 데이터는 categorical feature와 numerical feature에 따라 interpretable space의 차이가 있습니다. Numerical feature는 interpretable space와 feature space가 상동합니다. Categorical feature는 값의 수준(level)에 따른 binary vector가 intepretable space가 됩니다. 예를 들어 A, B, C 3개의 범주가 있으면 one-hot encoding의 형태처럼 A, B, C 각각에 대한 binary vector로 생각할 수 있습니다. Numerical interpretable space의 perturbed sample은 $x$의 값에 $N(0,1)$을 training data의 numerical feature의 평균과 표준편차로 역변환 하여 더해줍니다. Categorical의 경우 $x$에 해당 하는 값만 1로 생각하고 나머지 수준(level)을 모두 0로 생각하여, 1이 뽑히면 그대로 이용하고 아닌 경우 나머지 중 아무 값을 sampling합니다. (Numerical feature의 경우 값을 binning하여 Categorical feature와 동일한 방법으로 perturbed sample을 만들 수 있습니다.)

Sparse Linear Explanations

Local explanation이 모든 $x'$ interpretable representation으로 구성되어 있다면 데이터가 복잡한 경우 큰 도움이 되지 않을 것입니다. 따라서 실무자가 감당할 수 있을 representation의 수(Sparse)만큼 representation을 선택하고, 선택된 representation을 이용해서 linear model (Linear Explanations)에 적합합니다.

$G$를 linear model family로 고려하면, $g(z')=w_{g}z'$ 형태의 모든 선형 모형을 대변할 수 있습니다. 논문에서는 유사도 척도를 exponential kernel로 정의했습니다. $$\pi_{x}(z)=e^{-\frac{D(x,z)^{2}}{\sigma^{2}}},$$ 여기에서 $D$는 $x$, $z$의 거리를 나타내는 임의의 함수 입니다. 이어서 앞서 정의한 Locality-aware loss를 $$\mathcal{L}(f,g,\pi_{x})=\sum_{z,z'\in\mathcal{Z}}e^{-\frac{D(x,z)^{2}}{\sigma^{2}}}\left(f(z)-g(z')\right)^{2}$$ 로 나타낼 수 있습니다.

다음으로 최적화 문제의 모형 복잡도 $\Omega(g)$를 논문에서는 다음과 같이 정의했습니다. $$\Omega(g)=\infty\unicode{x1D7D9}_{\|\beta\|_{0}>k}=\infty I(\|\beta\|_{0}>K)+0 I(\|\beta\|_{0}\leq K),$$ 여기에서 $\|\beta\|_{0}=\sum_{j}|\beta_{j}|^{0}$으로 0이 아닌 $\beta$에 대해서 1의 값을 갖습니다. 즉, 0이 아닌 회귀 계수가 K보다 커지면 손실 함수가 $\infty$가 되고 아닌 경우는 Locality-aware loss의 값이 됩니다.

정리하면 최적화 문제는 $$\xi(g)=\underset{\beta}{\operatorname{argmin}}\left[\sum_{i=1}^{N}e^{-\frac{D(x,z_{i})^{2}}{\sigma^{2}}}\left(f(z_{i})-g(z_{i}')\right)^{2}+\infty\unicode{x1D7D9}_{\|\beta\|_{0}>K}\right]$$가 됩니다. 논문에서는 interpretable representation $K$개를 선택하는 것을 constant, 즉 사용자가 정하도록 했으며, 최적의 $K$개를 찾는 것은 future work으로 남겨 두었습니다. 이어 논문에서는 interpretable representation $K$개를 고르는 방법으로 LASSO를 이용했으며 이렇게 interpretable representation을 고르는 방법을 K-LASSO 알고리즘이라고 부릅니다.

LIME 알고리즘은 위와 같습니다. 논문에서는 LASSO로 interpretable representation을 선택했지만 다른 변수 선택 알고리즘을 적용하더라도 같은 방식으로 local explanation $g$를 얻을 수 있습니다.

SP-LIME (Submodular Pick for Explaining Models)

SP-LIME은 앞서 다룬 Accuracy이 문제점을 해결하기 위함으로, 특징이 다른 데이터 몇 가지를 뽑고, 각 데이터의 local explanation을 살펴 봄으로써 모형 전체의 신뢰성을 확인하기 위한 방법입니다.

지금부터 데이터 $X\in\mathbb{R}^{n\times d}$를 고려하겠습니다. SP-LIME에서 데이터를 몇가지만 살펴보는 이유는 너무 당연하게도 모든 데이터를 살펴보기 어렵기 때문입니다. 그래서 최대한 특징이 다른 데이터를 선택해주는 것 입니다. 먼저 살펴볼 데이터 budget $B$를 정합니다. Original representation으로 부터 $X'\in\mathbb{R}^{n\times d'}$을 구축할 수 있고, 데이터의 row와 column을 표현할 수 있는 $n\times d'$ explanation matrix $\mathcal{W}$를 정의합니다. Linear model을 explanations으로 사용했다면, 데이터 $x_{i}$에 대하여, explanation $g_{i}=\xi(x_{i})$를 얻을 수 있고, $\mathcal{W}_{ij}=|w_{g_{ij}}|$로 나타낼 수 있습니다. 추가적으로 $I_{j}$를 정의하고, 이는 $j$ column의 global importance를 나타냅니다. 여기에서 $I_{j}$는 단순히 binary로 표현할 수도 있고, $I_{j}=\sqrt{\sum_{i=1}^{n}\mathcal{W}_{ij}}$로 나타 낼 수도 있습니다. 최대한 특징이 다르면서, 많은 정보를 포함하고 있는 데이터를 추출하기 위해 coverage function을 $$c(\mathcal{V},\mathcal{W},I)=\sum_{j=1}^{d'}\unicode{x1D7D9}_{\exists i\in\mathcal{V}:\mathcal{W_{ij}}>0}I_{j}$$로 정의합니다. 여기에서 $\mathcal{V}$는 선택된 데이터들의 집합입니다. 논문의 예제를 약간 변형해서 살펴보겠습니다.

만약 $\mathcal{V}=\{1,3\}$이라고 하면, $c(\mathcal{V},\mathcal{W},I)=(1+4)+(4+2)$가 될 것입니다. 추가 설명을 붙이면, $x1$의 경우 $f1$, $f2$에 대해서 설명이 되고 각 global importance는 1, 4이기 때문이며, $x3$의 경우도 같습니다. 이렇게 데이터를 선택하는 문제를 논문에서 Pick problem으로 정의했습니다. Pick Problem은 Coverage function을 최대화하는 집합 $\mathcal{V}$를 찾으면 중요한 데이터를 추출할 수 있을 것 입니다. 이를 수식으로 나타내면, $$Pick(\mathcal{W},I)=\underset{\mathcal{V},|\mathcal{V}|\leq B}{\operatorname{argmax}}c(\mathcal{V},\mathcal{W},I)$$가 됩니다. 하지만 굉장히 많은 경우의 수를 고려해야 되기에 한 번에 문제를 해결하는 것은 어려움이 있습니다. 이를 greedy하게 풀어내는 방법이 SP-LIME입니다.

References

https://towardsdatascience.com/understanding-how-lime-explains-predictions-d404e5d1829c
Ribeiro, Marco Tulio, Sameer Singh, and Carlos Guestrin. "Why should i trust you?: Explaining the predictions of any classifier." Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. ACM, 2016.

YJJo