Formalisation#
Problème d’optimisation#
Je me réfère pour cela à l’article [Sevenster2013] (voir aussi [Bampoulidis2017]) qui introduit différentes façons de construire un système d’autocompétion et qui les compare à l’usage. Et s’il existe plusieurs façons de faire, il faut d’abord mettre au point une façon de les comparer. Je me place dans le cadre d’un moteur de recherche car c’est l’usage principal, que celui-ci soit un moteur de recherche ou une recherche incluse sur un site de vente. A la fin de la journée, on sait quelles sont les requêtes saisies par les utilisateurs et le nombre de fois qu’elles ont été saisies : \((q_i, w_i)\) pour \(i \in [[1, N]]\).
Sans système de complétion, les utilisateurs saisissent donc \(K=\sum_{i=1}^N l(q_i) w_i\) où \(l(q_i)\) est la longueur de la complétion \(q_i\). Avec le système de complétion, les utilisateurs saisissent moins de caractères, c’est ce chiffre là qu’on cherche à minimiser. L’unité est le charactère saisi ou keystroke en anglais.
Même avec le même système de complétion, il n’est pas dit que tous les utilisateurs saisissent la même requête de la même façon. Pour simplifier, on va supposer que si malgré tout et ne considérer que la façon minimale de saisir une requête.
L’exemple précédent illustrent deux façons de saisir le terme autocomplétion (sur Wikipédia), autocom + 4 touches vers le bas ou autocomp + 1 touche vers le bas, soit 7+4=11 touches dans le premier cas ou 8+1=9 touches dans le second cas.
Définition D1 : Minimum Keystroke
On définit la façon optimale de saisir une requête sachant un système de complétion \(S\) comme étant le minimum obtenu :
La quantité \(K(q, k, S)\) représente le nombre de touche vers le bas qu’il faut taper pour obtenir la chaîne \(q\) avec le système de complétion \(S\) et les \(k\) premières lettres de \(q\).
De façon évidente, \(K(q, l(q), S)=0\) et \(M(q,S) \infegal l(q)\) et \(K(q, k, S) > 0\) si \(k < l(q)\). On prend également comme convention \(\forall q \notin S, \; K(q, k, S) = \infty\) et \(\forall q \notin S, \; M(q, S) = l(q)\). Certains systèmes proposent des requêtes avant de saisir quoique ce soit, c’est pourquoi on inclut la valeur \(M(q, 0)\) qui représente ce cas. Construire un système de complétion revient à minimiser la quantité :
Ensemble des complétions#
Il n’y a pas de restriction sur la fonction \(K(q, k, S)\) mais on se limitera dans un premier temps à une fonction simple. On suppose que le système d’autocomplétion dispose d’un ensemble de requêtes ordonnées \(S = (s_i)\) et la fonction :
Où \(S(q[1..k])\) est le sous-ensemble ordonné de \(S\) des complétions qui commencent par les \(k\) premières lettres de \(q\) et de longueur supérieure strictement à \(k\). \(position(q, S(q[1..k]))\) est la position de \(q\) dans cet ensemble ordonné ou \(\infty\) si elle n’y est pas. Cette position est strictement positive \(K(q, k, S) \supegal 1\) sauf si \(k=l(q)\) auquel cas, elle est nulle. Cela signifie que l’utilisateur doit descendre d’au moins un cran pour sélectionner une complétion. On note \(\sigma(q)\) la position de la complétion \(q\) dans l’ensemble \(S\). Par construction, \(s_ \neq s_2 \Longrightarrow \sigma(s_1) \neq \sigma(s_2)\).
\(\#\) désigne le cardinal de l’ensemble. Trouver le meilleur système de complétion \(S\) revient à trouver la meilleure fonction \(K(q, k, S)\) et dans le cas restreint l’ordre sur \(S\) qui minimise cette fonction. Le plus souvent, on se contente de trier les complétions par ordre décroissant de popularité. On considérera par la suite qu’on est dans ce cas.
Gain#
On définit le gain en keystroke comme étant le nombre de caractères saisis en moins :
Minimier \(M(S)\) ou maximiser \(G(S) = \sum_{i=1}^N G(q_i, S) w_i\) revient au même.
Où \(K=\sum_{i=1}^N l(q_i) w_i\) l’ensemble des caractères tapés par les utilisateurs. \(\frac{G(S)}{K}\) est en quelque sorte le ratio de caractères économisés par le système de complétion.
Does Online Evaluation Correspond to Offline Evaluation in Query Auto Completion? (2017) Alexandros Bampoulidis, João PalottiMihai LupuJon BrasseyAllan Hanbury ECIR 2017: Advances in Information Retrieval
Algorithmic and user study of an autocompletion algorithm on a large medical vocabulary (2013), Merlijn Sevenster, Rob van Ommering, Yuechen Qian Journal of Biomedical Informatics 45, pages 107-119