Entendendo como IME (Shapley Values) explica previsões

Pol Ferrando Blocked Desbloquear Seguir Seguindo 2 de janeiro

Em um post recente , apresentei três abordagens existentes para explicar previsões individuais de qualquer modelo de aprendizado de máquina. Após o post focado em LIME , agora é a vez do IME (Método baseado em Interações para a Explicação) , um método apresentado por Erik Strumbelj e Igor Kononenko em 2010. Recentemente, este método também foi chamado de Shapley Values .

Intuição por trás do IME

Quando um modelo fornece uma previsão para uma observação, todas as características não desempenham o mesmo papel: algumas delas podem ter muita influência na previsão do modelo, enquanto outras podem ser irrelevantes. Consequentemente, pode-se pensar que o efeito de cada característica pode ser medido verificando qual seria a previsão se essa característica estivesse ausente; quanto maior a mudança na saída do modelo, mais importante deve ser o recurso.

No entanto, observar apenas um único recurso por vez implica que as dependências entre os recursos não são levadas em consideração, o que poderia produzir explicações incorretas e enganosas sobre o processo de tomada de decisão do modelo. Portanto, para evitar perder qualquer interação entre os recursos, devemos observar como a previsão muda para cada possível subconjunto de recursos e, em seguida, combinar essas alterações para formar uma contribuição exclusiva para cada valor de recurso.

Fonte: https://www.ingenioustechnologies.com/blog/are-you-using-the-right-attribution-model-for-your-business/

Precisamente, o IME baseia-se na ideia de que os valores de recurso de uma instância trabalham juntos para causar uma alteração na previsão do modelo com relação à saída esperada do modelo e divide essa alteração total na previsão entre os recursos de uma maneira que é “ justo ”às suas contribuições em todos os possíveis subconjuntos de recursos.

Noções básicas de teoria dos jogos cooperativos

Um jogo cooperativo (ou coalizão) é uma tupla ({1, …, p}, v), onde {1, …, p} é um conjunto finito de jogadores p e v: 2? ? ? é uma função característica de tal forma que v (?) = 0.

Subconjuntos de jogadores S? {1,…, p} são coalizões e o conjunto de todos os jogadores {1,…, p} é chamado de grande coalizão . A função característica v descreve o valor de cada coalizão. Costumamos supor que a grande coalizão se forma e o objetivo é dividir seu valor (definido pela função característica) entre os jogadores de uma maneira “justa”. Portanto, a solução é um operador ? que atribui ao jogo ({1,…, p}, v ) um vetor de payoffs ? = (??, ??,…, ??).

Para cada jogo com pelo menos um jogador existem soluções infinitas, algumas das quais são mais “justas” do que outras. As quatro propriedades a seguir são tentativas de axiomatizar a noção de “justiça” de uma solução:

  • Axiom 1: Eficiência

?? ( v ) + ?? ( v ) +… + ?? ( v ) = v ({1,…, p})

  • Axiom 2: Simetria

Se para dois jogadores i e j , v (S? {i}) = v (S? {j}) é válido para todo S , onde S? {1,…, p} e i, j? S, então ?? ( v ) = ?? ( v ).

  • Axioma 3: manequim

Se v (S? {i}) = v (S) é válido para todo S , onde S? {1,…, p} e i? S, então ?? (v) = 0.

  • Axiom 4: Additivity

Para qualquer par de jogos v , w : ( v + w ) = ? ( v ) + ? ( w ), onde ( v + w ) ( S ) = v ( S ) + w ( S ) para todos os S.

O valor de Shapley é uma maneira “justa” de distribuir os ganhos totais v ({1,…, p}) para os jogadores p no sentido de que é a única distribuição com as quatro propriedades desejáveis anteriores.

Além disso, existe uma fórmula equivalente para o valor de Shapley:

onde S? é o grupo simétrico do conjunto finito {1,…, p} (isto é, o conjunto de todas as permutações do conjunto de jogadores {1,…, p}) e Pre ^ i (O) é o conjunto de jogadores que são predecessores do jogador i na permutação O? S? (isto é, os números que aparecem antes do número i na permutação O? S?).

Método

Seja X = X × X × × × X × o espaço de características das características p , representado pelo conjunto {1,…, p}.

Seja f o modelo sendo explicado. Na classificação, f (x) é a probabilidade (ou um indicador binário) de que x pertence a uma determinada classe. Para várias classes, o IME explica cada classe separadamente, assim, f (x) é a previsão da classe relevante. Na regressão, f (x) é a função de regressão.

Finalmente, vamos y = (y?,…, y?) ?X a instância do espaço de feição cuja predição queremos explicar.

Strumbelj e Kononenko definem a diferença de previsão de um subconjunto de valores de recurso em uma instância específica como a alteração na expectativa causada pela observação desses valores de recurso. Formalmente:

Seja f um modelo. Seja S = {i?, i?,…, i?} ? {1,…, p} seja um subconjunto de recursos. A diferença de previsão ?? (S) do subconjunto de características S? {1,…, p} na instância y = (y?,…, y?) ?X é:

Note que ? define uma função ??: 2? ? ? do conjunto de todos os subconjuntos possíveis de características para ? que satisfaz ?? (?) = E [f (X?,…, X?)] – E [f (X?,…, X? )] = 0. Portanto, ? é uma função característica válida para o jogo cooperativo com as características p como jogadores. Portanto, ({1,…, p}, ??) forma um jogo cooperativo como definido anteriormente. Em outras palavras, o IME considera os recursos como jogadores de um jogo em que o valor das coalizões é a mudança na previsão do modelo definida por ??, portanto o objetivo do IME é dividir a diferença total na previsão ?? ({1,…, p}) entre os recursos de maneira “justa”.

A contribuição sugerida da i -ésima característica para a explicação da predição de y é o valor de Shapley do jogo cooperativo ({1,…, p}, ??):

Seja {1,…, p} o conjunto de feições e seja ?? a diferença de predição definida acima. A contribuição da i -ésima característica para a explicação da predição de y é:

Ou, de forma equivalente, usando a fórmula alternativa para o valor de Shapley:

onde S? é o conjunto de todas as permutações do conjunto de características {1,…, p} e Pre ^ i (O) é o conjunto de características que são predecessoras do recurso i em permutação O? S?.

Note que esta definição de contribuições não é casual: o valor Shapley $ ? $ de um jogo de coalizão ({1,…, p}, v ) é uma maneira “justa” de distribuir os ganhos totais para os p jogadores. No nosso caso, os axiomas 1 a 3 tornam-se três propriedades desejáveis do IME como um método de explicação:

1. Eficiência axiomática: ?? (??) + ?? (??) +… + ?? (??) = ?? ({1,…, p}) = E [f | y] -E [f] = f (y) – E [f]

Ou seja, a soma de todas as contribuições p na explicação de uma observação é igual à diferença entre a previsão do modelo para a instância e a saída esperada do modelo, sem fornecer informações sobre os valores do recurso da instância. Essa propriedade torna as contribuições mais fáceis de comparar entre observações diferentes e modelos diferentes.

2. axioma de simetria:

Se para dois jogadores i e j , ?? (S? {i}) = ?? (S? {j}) é válido para todo S , onde S? {1,…, p} e i, j? S, ?? ( ??) = ?? (??).

Em outras palavras, se duas características têm uma influência idêntica na previsão, elas recebem contribuições idênticas.

3. axioma dummy:

Se ?? (S? {i}) = ?? (S) é válido para todo S , onde S? {1,…, p} e i? S, então ?? (??) = 0.

Isto é, uma característica é atribuída uma contribuição de 0 se não tem influência na previsão.

Tanto a magnitude quanto o sinal das contribuições são importantes. Primeiro, se uma característica tem uma contribuição maior do que outra, ela tem uma influência maior na previsão do modelo para a observação de interesse. Segundo, o sinal da contribuição indica se o recurso contribui para aumentar (se positivo) ou diminuir (se negativo) a saída do modelo. Por fim, as contribuições geradas somam a diferença entre a previsão de saída do modelo e a saída esperada do modelo, sem fornecer informações sobre os valores dos recursos. Em resumo, podemos discernir o quanto a saída do modelo muda devido aos valores de recurso específicos para a observação, quais recursos são responsáveis por essa alteração e a magnitude da influência de cada recurso.

Na prática, o principal desafio desse método é a complexidade do tempo exponencial, porque o cálculo das contribuições requer o uso de todos os subconjuntos possíveis de recursos. Para evitar esse problema, Strumbelj e Kononenko desenvolveram um procedimento de amostragem eficiente para aproximar contribuições de recursos, perturbando os recursos de entrada da instância:

Note que f (x ') e f (x' ') são as predições do classificador para duas observações, que diferem apenas no valor do i -ésimo recurso. Eles são construídos tomando a ocorrência z e então mudando o valor de cada característica que aparece antes da i -ésima característica na ordem O (para x ', a i-ésima característica também é alterada) para o valor dessa característica na observação que queremos explique y .

Exemplo

Sejam X?, X? duas características binárias, C = {0,1} uma classe binária e X = {0,1} × {0,1} nosso espaço de recurso. Assumimos que todas as combinações de valores de recursos são equiprováveis, conforme mostrado na tabela abaixo.

Suponha que a classe seja definida pela disjunção C = X?? X?, ou seja, C = 1 se X? = 1 ou X? = 1 e 0 caso contrário. Seja f: X ? [0,1] um classificador (ideal).

Um conjunto de dados simples usado para fins ilustrativos. Todas as combinações de recursos são igualmente prováveis.

Vamos calcular a explicação produzida pelo IME para explicar a previsão para a observação y = (1,0) a partir da perspectiva do valor de classe 1. Neste caso, podemos calcular analiticamente a contribuição de cada característica. Especificamente, usaremos a fórmula alternativa para o valor de Shapley.

Primeiro, precisamos calcular o grupo simétrico S? do conjunto finito {1,2}, que tem 2! = 2 elementos: S? = {{1,2}, {2,1}}

Em segundo lugar, temos que calcular as diferenças de previsão para todos os subconjuntos de recursos, então calculamos primeiro a previsão esperada se nenhum valor de recurso for conhecido:

Agora podemos calcular as diferenças de previsão:

Finalmente, podemos calcular as contribuições dos recursos:

A contribuição da primeira característica é positiva, enquanto a contribuição da segunda característica é negativa, o que é razoável. Como a classe é 1 quando pelo menos uma das características é 1, a primeira característica da nossa instância fez o modelo predizer 1, então esse valor contribuiu para a decisão do modelo de prever 1. Pelo contrário, a segunda característica tornou menos provável que 1 era a classe prevista, por isso teve uma influência negativa na decisão do modelo. Além disso, o valor absoluto da primeira contribuição é maior que o segundo, o que significa que a primeira característica foi decisiva para a previsão. Por fim, observe que as duas contribuições somam a diferença inicial entre a previsão para essa instância e a previsão esperada quando os valores de recurso são desconhecidos: ?? + ?? = 3 / 8–1 / 8 = 1/4 = 1–3 / 4 = f (1,0) -E [f (X?, X?)], que foi assegurado pelo axioma 1.

Em resumo, a explicação produzida pelo IME para a previsão da instância (1,0) é que a decisão do modelo é influenciada por ambas as características, sendo a primeira característica mais decisiva em favor da predição (correta) da classe 1 do que da segunda característica, cujo valor foi contra esta decisão.

Este foi um exemplo muito simples que conseguimos calcular analiticamente, mas isso não será possível em aplicações reais, nas quais precisaremos da solução aproximada pelo algoritmo. Em posts futuros, explicarei como explicar previsões com Shapley Values usando R e Python.