Problème d’optimisation¶

Enoncé 1¶

Problème P1 : Optimiser un système de complétion

On suppose que l’ensemble des complétions $C=\acc{c_j}$ est connu. On souhaite ordonner cet ensemble pour obtenir l’ensemble ordonné des complétions $S=(s_i)$ qu’on considère comme une permutation $\sigma$ de l’ensemble de départ : $S(\sigma) = (s_i) = (c_{\sigma(j)})$ . Ce système de complétion est destiné à un des utilisateurs qui forment des recherches ou requêtes $Q=(q_i, w_i)_{1 \leqslant i \leqslant N_Q}$ . $q_i$ est la requête, $w_i$ est la fréquence associée à cette requête. On définit l’effort demandé aux utilisateurs par ce système de complétion :

$E(C, Q, \sigma) = \sum_{i=1}^{N_Q} w_i M'(q_i, S(\sigma))$

Déterminer le meilleur système de complétion revient à trouver la permutation $\sigma$ qui minimise $E(C, Q, \sigma)$ .

La métrique $M'$ peut être remplacée par $M"$ . La différence peut paraître insignifiante mais elle ne l’est pas tant que ça. Le système de complétion peut se concevoir comme une compression : le système de complétion permet de coder l’ensemble des recherches d’un utilisateur $Q$ avec moins de caractères que celui-ci en a besoin pour les taper. On ajoute les caractères $rightarrow$ et $\downarrow$ aux lettres de l’alphabet et cela permet de coder plus rapidement une requêtes. La quantité suivante peut être considérée comme le taux de compression :

$t(C, Q, \sigma) = \frac{ E(C, Q, \sigma) } { \sum_{i=1}^{N_Q} w_i l(q_i) }$

L’idée derrière cette métaphore est le fait d’avoir une idée de la borne inférieure pour ce taux de compression. On s’inspirer de la complexité de Lempel-Ziv (calculating Lempel-Ziv (LZ) complexity (aka sequence complexity) of a binary string) ou du codage de Huffman. $M'$ permet une compression avec perte et $M"$ sans perte. Le calcul de $M'$ autorise deux jumps de suite :

$abb (\downarrow \downarrow \downarrow \downarrow \downarrow)$

Mais les deux dernières touches $\downarrow$ peuvent s’appliquer au premier préfixe ou aux suggestions montrées par la complétion obtenue après trois $\downarrow$ .

$abb (\downarrow \downarrow \downarrow) (\downarrow \downarrow)$

La métrique $M"$ interdit ce cas.

Enoncé 2¶

Problème P2 : Optimiser un système de complétion filtré

On suppose que l’ensemble des complétions $C=\acc{c_j}$ est connu. On souhaite ordonner cet ensemble pour obtenir l’ensemble ordonné des complétions $S=(s_i)$ qu’on considère comme une permutation $\sigma$ de l’ensemble de départ : $S(\sigma) = (s_i) = (c_{\sigma(j)})$ . On utilise aussi une fonction $f$ qui filtre les suggestions montrées à l’utilisateur, elle ne change pas l’ordre mais peut cacher certaines suggestions si elles ne sont pas pertinentes. Ce système de complétion est destiné à un des utilisateurs qui forment des recherches ou requêtes $Q=(q_i, w_i)_{1 \leqslant i \leqslant N_Q}$ . $q_i$ est la requête, $w_i$ est la fréquence associée à cette requête. On définit l’effort demandé aux utilisateurs par ce système de complétion :

$E(C, Q, \sigma, f) = \sum_{i=1}^{N_Q} w_i M'(q_i, S(\sigma), f)$

Déterminer le meilleur système de complétion revient à trouver la permutation $\sigma$ qui minimise $E(C, Q, \sigma, f)$ .

Comme suggéré au paragraphe Il faut montrer toutes les complétions, le filtre $f$ peut rejetter une suggestion si elle est montrée à une position qui ne permet aucun gain à l’utilisateur, c’est-à-dire que la différence des longueurs complétion - préfixe est plus petite que la position où elle est montrée.

Une idée¶

On aimerait bien pouvoir trouver l’ordre optimal par morceau, supposer que l’ordre optimal pour l’ensemble des complétions correspond à l’ordre des complétions sur un sous-ensemble partageant le même préfixe.

Lemme L1 : M” et sous-ensemble

On suppose que la complétion $q$ est préfixe pour la requête $q'$ et $\sigma(q) < \sigma(q')$ ce qui signifie que la complétion $q$ est toujours affichée avant la complétion $q'$ si elles apparaissent ensemble. Alors $M'(q, S) < M'(q', S)$ . Plus spécifiquement, si on considère l’ensemble $S'(q) = \acc{ s-q \in S | q \prec s }$ ( $s-q$ est la complétion $s$ sans son préfixe $q$ ).

$M'(q', S) = M'(q'-q, S') + M'(q, S)$

On sait déjà, par construction que $M'(q', S) \leqslant M'(q'-q, S') + M'(q, S)$ . Par l’absurde, on suppose que $M'(q', S) < M'(q'-q, S') + M'(q, S)$ , comme la requête $q-q'$ est toujours affichée avant la requête $q'$ , cela voudrait dire qu’on aurait trouvé une façon plus optimale d’écrire la requête $q-q'$ avec le système $S$ ce qui impossible d’après la définition de la métrique $M'$ . Cette propriété n’aide pas forcmément à trouver un algorithme pour optimiser l’ordre des complétions dans la mesure où la propriété suppose qu’une complétion soit affiché avant toutes celles dont elle est le préfixe. La propriété suivante est évidemment vraie pour le cas particulier qu’on vient de mentionner. Si elle est vraie, cela devrait permettre de procéder par sous-ensemble pour trouver l’ordre optimal.

Théorème T1 : M”, ordre et sous-ensemble

Soit $q$ une requête de l’ensemble de complétion $S$ ordonnées selon $sigma$ . Si cet ordre vérifie :

(1)¶ $\forall k, \; \sigma(q[1..k]) \leqslant \sigma(q[1..k+1])$

On note l’ensemble $S'(q[1..k]) = \acc{ q[k+1..len(q)] \in S }$ :

alors :

$\forall k, \; M'(q[1..k], S) = M'(q[k+1..l(q)], S'(q[1..k]) + M'(q[1..k], S)$

Ceci découle de l’application du lemme précédent. Ce théorème permet presque de déterminer le meilleur ordre sigma parmi ceux qui vérifie la contrainte (1), à savoir une requête courte est toujours affichée avant celles qui la complètent. On procède par récurrence, on suppose connu les ordres $\sigma(q)$ pour l’ensemble des complétions qui commencent par le préfixe $p = q[1..k]$ , $S'(q[1..k]) = \acc{ q | q[1..k] = p, q \in S }$ . Pour $i =k-1$ , le meilleur ordre : $\sigma$ revient à fusionner les listes ordonnées obtenues pour chaque préfixe de longueur $k$ . Il faut démontrer la possibilité de traiter les complétions par ordre croissant.