Reducing counterfactual sequences generation in recommender systems to the trace alignment problem

In the paper by [@degiacomoDisruptiveEffectivenessAutomated2017], a solution of the Trace Alignment problem is proposed, with the use of automatas.

In the context of the paper, the trace alignment problem is described as follows: given a trace $t$ of events and an $LT{L}_f$ formula $\varphi$ that describes an automata, s.t. $t⊭\varphi$, find a trace $t^{\prime }s.t.ˆt\models \varphi$ and $\text{cost}(t,t^{\prime })$ is minimal.

Where $\text{cost}(a,b)$ is the cost of transforming the sequence $a$ to the sequence $b$ with a series of edits.

Finding a counterfactual example for a sequence $x$ of items in the context of recommender system is a very similar task, where a new sequence $x^{\prime }$ has to be found which is the most similar possible to the original sequence $x$, and such that the recommender model $\mathcal{F}$‘s output is different, i.e $\mathcal{F}(x)\ne \mathcal{F}(x^{\prime })$.

The problem is the fact that in [@degiacomoDisruptiveEffectivenessAutomated2017], the function $F$ that the automaton represents is known, while for the recommender system, the method should be model agnostic, meaning the $F$ is a black-box.

To solve this problem, Automata Learning can be used, where a dataset of good and bad examples is constructed using the black box model $F$, and then used to learn an automata that accepts the good examples, and rejects the bad examples. This automata can then be used in the trace alignment algorithm as the function $F$ in order to find a counterfactual sequence.

One of the problem with this approach is that since the good examples are the one that recommend the next item $I$ for the sequence $x$, and the bad examples are the one that recommend a different item, we would need to train a new automata for each sequence that outputs a different item.

Another idea would be to approximate the whole neural network with an automata

---

tags: automata sequential related: Trace Alignment