« v2:Idées » : différence entre les versions

De Disposition de clavier bépo
Aucun résumé des modifications
Ligne 122 : Ligne 122 :
* une puissance de calcul suffisante pour explorer plus largement l'espace des dispositions possibles, ce qui signifie potentiellement de meilleurs résultats ;
* une puissance de calcul suffisante pour explorer plus largement l'espace des dispositions possibles, ce qui signifie potentiellement de meilleurs résultats ;
* possibilité de rajouter des contraintes / changer les calculs à effectuer de façon transparente pour l'utilisateur (sans qu'il n'ait rien à faire) et de façon sécurisée via le mécanisme prévu à cet effet du moteur BOINC ;
* possibilité de rajouter des contraintes / changer les calculs à effectuer de façon transparente pour l'utilisateur (sans qu'il n'ait rien à faire) et de façon sécurisée via le mécanisme prévu à cet effet du moteur BOINC ;
* possibilité de « voire où ça en est rendu » de façon interactive via interface Web. On pourrait en dériver, par exemple, une page mise à jour en temps réel avec la liste des 5 meilleures dispositions actuellement trouvées candidates pour une v2.
* ce qui donne la possibilité d’explorer séparément différentes voies en diffusant sur bépo@home les paramètres/binaires correspondants. Par exemple, on peut envisager les positions pour la [[place des chiffres]] et recenser les meilleures solutions trouvées dans chaque cas ;
* possibilité de « voire où ça en est rendu » de façon interactive via interface Web. On pourrait en dériver, par exemple, une page mise à jour en temps réel avec la liste des 5 meilleures dispositions actuellement trouvées candidates pour une v2 ;
* possibilité de garder différentes solutions optimales en parallèle sur le front de Pareto. On peut en déduire sur une page web les points forts et faibles (contraintes les mieux et moins bien respectées) pour chacune des solutions candidates trouvées.


Inconvénients :
Inconvénients :
* Mise en place assez lourde.
* Mise en place assez lourde.

Version du 23 mai 2008 à 14:14

Attention

Page en cours de construction

Corpus

Placement des mains et utilisation du clavier

C'est une question primordiale, mais qui n'a pas été totalement tranchée dans la version 1.

Rangée de garde

  • QSDF et JKLM
  • QZEF et JIOM
  • QSDF et KLMÙ

Méthode de saisie

Accessibilité des touches du point de vue dactylographique

Accessibilité des touches

Carte d'accessibilité des touches


Accessibilité des digrammes

Carte d'accessibilité des digrammes

Contraintes

Il s'agit de répertorier toutes les contraintes, y compris incompatibles, qu'il faut tenter de satisfaire au mieux. Ces contraintes devront être intégrées à un algorithme afin de les combiner de façon optimale en testant les différentes possibilités. La liste est également utile pour expérimenter « à la main » et ne rien oublier.

Force des contraintes

Contraintes « dures » : Intégrées à l'algorithme dans les prérequis, vérifiées quoi qu'il arrive par construction. Exemple : contraintes liées aux positions des touches sur les types de clavier existants.

Contraintes « douces » : Caractérisées par une fonction de coût quantifiant l'importance de la contrainte. Exemple : contraintes liées aux fréquences des caractères et aux accessibilité des touches.

Types de contraintes

Contraintes liées aux enchaînements de caractères :

  • Enchaînements typographiques, par exemple placer la ponctuation haute et les guillemets en shift pour l'enchaînement avec l'espace insécable ;
  • Enchaînements de caractères allant ensemble à l'usage.

Contraintes dues à l'appariement logique des caractères.

  • Par exemple mettre « ( » et « ) » côte à côte et dans cet ordre. À déterminer : comment les intégrer au mieux. On peut par exemple considérer ces deux caractères en bloc, inséparables, et cumuler accessibilité et fréquences sur les deux touches.
  • Autre appariements logiques : « . » et « : », « , » et « ; » que l'on peut placer l'un au dessus de l'autre.

Liste des contraintes

Il s'agit dans cette section de lister les contraintes dans un formalisme d'expression commun, nécessaire si on veut pouvoir les combiner. Les contraintes « dures » sont simplement listées afin de pouvoir être prises en compte dans l'algorithme. Les contraintes « douces » sont exprimées comme suit :

  • Poids : Un nombre exprimé sur une échelle arbitraire, indiquant l'importance relative de cette contrainte par rapport aux autres. Peut être converti en % en divisant par la somme de tous les poids.
  • Fonction de coût : Permet de quantifier la contrainte en lui donnant une valeur, ici entre 0 et 1. Ce faisant, permet aux différentes contraintes d'êtres combinées. La somme de ces valeurs pour toutes les contraintes pondérées par leur poids respectif est appelée fonction objective. C'est cette dernière que l'on souhaite optimiser.
  • Paramètres : Ce dont la fonction de coût à besoin pour être exprimée. Par exemple, une accessibilité de touches, ou une fréquence. Les paramètres peuvent avoir dans certains cas une influence importante sur la fonction de coût et par conséquent sur le résultat final.

Contraintes « dures »

  • Tenir compte des différents types de clavier ;
  • Tenir compte des différents placements des mains ;
  • À compléter.


Contraintes « douces »

Alternance

  • Poids : 1
  • Paramètres :
  • A : ensemble des digrammes sur 2 mains
  • D : ensemble de tous les digrammes
  • f(d) : fréquence du digramme d
  • Fonction de coût : C = ( ∑d∊Af(d) ) / ( ∑d∊Df(d) )


Charge des doigts

Accessibilité / fréquence


Multi-critères

Cette section se veut introductive de la notion, compréhensible par un lecteur non-initié aux techniques d'optimisation multi-critères, et lisible en bon Français. Si ce n'est pas le cas merci de le signaler sur le canal IRC ou la liste de discussion.


L'idée de l'optimisation multi-critères est de répondre au mieux à différents critères parfois contradictoires. Dans un tel problème, il n'y a souvent pas de solution unique qui serait « la meilleure ». Il y a au contraire de nombreuses solutions correspondant chacune a un compromis particulier sur les contraintes.

Ce genre de configuration est ce que l'on trouve en fait le plus souvent dans la vie réelle, à savoir qu'il n'existe pas de solution parfaite mais plutôt un ensemble de compromis. Exemple :

Chaque carré est une disposition clavier possible. Voir l'explication dans le texte principal.

Commentaire de l'image : Selon que l'on accorde plus d'importance au critère 1 ou au critère 2 on peut choisir l'une des dispositions A ou B. Ici les deux dispositions A et B sont « optimales » : d'autres solutions comme C peuvent être améliorées dans un des deux critères, mais pour A et B on ne peut pas améliorer un critère sans perdre sur un autre. L'ensemble de toutes les solutions « optimales » forme ce qu'on appelle le front de Pareto. On y retrouve tous les meilleurs compromis possibles.

L'optimisation multi-critères est un champs de recherche qui vise a établir le même genre de dessin que ci-dessus, avec potentiellement bien plus de deux critères à optimiser. Il existe différente techniques pour y arriver. Un des buts est alors « d'explorer » le front de Pareto. C'est à dire demander à l'ordinateur de trouver des solutions « optimales » comme ci-dessus. Une technique simple mais qui ne permet d'explorer qu'une partie limitée du front est tout simplement de recommencer plusieurs fois les calculs avec différents poids pour les contraintes. Des techniques plus avancées d'échantillonage statistique (dont les algorithmes génétiques) permettent de répartir plus équitablement les solutions obtenues sur l'ensemble du front.

Pour comprendre ce que cela signifie ici, imaginez que l'algorithme vous donne 5 dispositions candidates, réalisant chacune un compromis entre les différents critères. L'expérimentateur humain (ou de façon collective via IRC, etc) reste au centre de la boucle et peut choisir le solution qui lui plait. Mieux, on peut aussi voir l'influence d'un paramètre ou d'un autre. Si on a fait une erreur dans les paramètres des différentes contraintes on la retrouve parfois de façon évidente ici. On peut alors règler ces paramètres pour qu'ils correspondent aux mieux à ce que l'on attends.

Au final bien sûr on doit obtenir une disposition unique. Cependant cette méthode permet non seulement de trouver des compromis auxquels on aurait pas forcément pensé, mais aussi de les trouver de façon systématique et bien plus efficace qu'une recherche « à la main ».

Enfin, un dernier point est également la qualité des solutions obtenues. Prenons l'exemple du Corpus de texte qui sert à établir des statistiques. Si on réalise un Corpus unique avec des proportions diverses prédéfinies (un peu de Français littéraire, des mails, du code, quelques langues étrangères…) on a de grandes chances d'obtenir une solution comme le point C ci-dessus. Alors que si on sépare les Corpus en différents usages et que l'on calcule les solutions compromis « optimales » pour ces usages, on obtient des solutions comme A et B. L'optimisation multi-critères permet dans ce cas de trouver de meilleures solutions.

Algorithme incrémental

Lorsqu'un changement apparaît, une nouvelle idée, une meilleure carte d'accessibilité des touches, de nouvelles contraintes auxquelles ont aurait pas pensé, l'idée est de les intégrer à l'algorithme et de recalculer une solution. Malheureusement cela peut potentiellement provoquer un layout complètement différent. Autant ce n'est pas un problème dans les phases initiales de développement d'une nouvelle version (mieux vaut alors une version optimale), autant cela peut être un point bloquant dans une branche destinée à être stabilisée (mais si on découvre un point critique, la contrainte peut être assouplie).

Pour ne pas avoir ce problème il faut trouver un algorithme qui préserve en partie le layout actuel lorsque de nouvelles contraintes sont ajoutées.

Une première idée est de se limiter à l'espace de toutes les inversions ou permutations de 3 touches maximum. Le problème est que cela ne tient pas compte de l'importance relative des touches en question.

Une idée plus avancée est :

  • Définir une métrique de « distance de disposition »
  • Les caractères principaux ont plus grand poids
  • Les caractères secondaires plus de latitude de mouvement
  • La métrique est sensée mesurer le degré de changement dans un critère correspondant à ce qui serait perçu de façon acceptable pour un degré de changement donné.
  • Ajouter une contrainte « douce » à la liste des contraintes en utilisant cette métrique


bépo@home

L'idée est d'utiliser le moteur de calculs distribués BOINC afin de réaliser l'optimisation pour les placements de touches.

Avantages :

  • Ça permettrait à chacun de contribuer utilement au projet en faisant tourner un « bépo@home » équivalent du « seti@home ». Non seulement les participants se sentent (et sont) utiles au projet, mais en plus cela permet à chacun de contribuer facilement ;
  • une puissance de calcul suffisante pour explorer plus largement l'espace des dispositions possibles, ce qui signifie potentiellement de meilleurs résultats ;
  • possibilité de rajouter des contraintes / changer les calculs à effectuer de façon transparente pour l'utilisateur (sans qu'il n'ait rien à faire) et de façon sécurisée via le mécanisme prévu à cet effet du moteur BOINC ;
  • ce qui donne la possibilité d’explorer séparément différentes voies en diffusant sur bépo@home les paramètres/binaires correspondants. Par exemple, on peut envisager les positions pour la place des chiffres et recenser les meilleures solutions trouvées dans chaque cas ;
  • possibilité de « voire où ça en est rendu » de façon interactive via interface Web. On pourrait en dériver, par exemple, une page mise à jour en temps réel avec la liste des 5 meilleures dispositions actuellement trouvées candidates pour une v2 ;
  • possibilité de garder différentes solutions optimales en parallèle sur le front de Pareto. On peut en déduire sur une page web les points forts et faibles (contraintes les mieux et moins bien respectées) pour chacune des solutions candidates trouvées.

Inconvénients :

  • Mise en place assez lourde.