En passant par une page de documentation, je me suis attardé sur std::next_permutation. Ça m’a tout de suite donné des idées d’anagrammes. En effet, de pouvoir aussi facilement boucler irréfragablement sur toutes les permutations des lettres d’un mot m’a suscité l’irrépressible envie de créer un petit détecteur d’anagrammes.
Évidemment, pour détecter un anagramme, il faut d’abord et avant tout avoir une base de données de mots valides pour une langue donnée. Il se trouve que j’ai une telle base de données. En effet, il y a déjà une vingtaine d’années, j’avais réalisé une petite page web d’aide aux mots-croisés. Pour ce faire j’avais contacté, via un forum, un cruciverbiste-internaute qui avait eu la grande gentillesse de me faire parvenir ce fichier par courriel. C’était un gros fichier à l’époque: presque 3 Mo. En fait, à l’origine c’était même 26 fichiers allant de A.txt à Z.txt. Cruciverbiste-internaute des années ’90 qui se reconnait dans cette histoire, je te remercie encore une fois!
Le corpus en tant que tel date un peu: le mot courriel, par exemple, n’y apparaît même pas. Quoi qu’il en soit, avec ses 280000 entrées composées de noms propres, de substantifs et d’adjectif au singulier comme au pluriel, de verbes conjugués à toutes les formes, c’est suffisant pour tenter quelques expériences significatives.
En tout cas, c’est amplement suffisant pour tester une première version d’un détecteur d’anagramme. Une version pas très robuste mais qui a le mérite de tester l’utilisation de std::next_permutation.
La première version lit la base de données en insérant dans un std::vector> tous les mots rencontrées. Le vecteur est triée pour permettre une recherche rapide avec std::binary_search
Une fonction ressemblant à ça pourrait par exemple faire l’affaire (j’assume un compilateur C++11 ou plus qui garantit que les objets comme la base de données ne sont pas retournés par copie sur la pile mais bien en utilisant le mécanisme de Copy Elision).
Lecture de la base de données et insertion dans un vecteur trié
Avec un vecteur ainsi trié, on peut rechercher un mot avec grosso-modo la même efficacité que dans un arbre binaire. En imaginant qu’on boucle sur les différentes permutations des lettres d’un mot, on voudra tester pour chaque combinaison si le mot est présent ou pas dans la base de données. Quelque chose comme ça.
Utilisation de binary_search pour trouver un mot dans une liste triée
Une fois qu’on a une base de données chargée et un mécanisme pour tester si un mot (une combinaison de lettres) est valide (donc présent dans le base de données), il ne reste plus qu’à obtenir un mot à tester, boucler sur toutes ses permutations et vérifier pour chaque anagramme si il correspond à un mot valide dans la langue française (ici représentée par notre fichier de base de données).
On pourrait par exemple lire en boucle sur stdin pour obtenir des mots, qu’on testerait un à la fois. Pour chacun des mots, la liste des anagrammes valides serait envoyée sur stdout, et ainsi de suite. On remarque que pour initier les permutations, le mot est tout d’abord trié en ordre lexicographique, de manière à commencer par le « premier » anagramme.
Ça ressemblerait donc à ça.
int main(int argc, char** argv)
{
if(argc<=1)
return 0;
std::string str = argv[1];
auto db = GetAnagramDB(str);
std::cout << "Word to look for: ";
while(std::cin >> str )
{
std::sort(str.begin(), str.end());
int num = 0;
while(std::next_permutation(str.begin(), str.end()) )
{
if( isInDatabase(str) )
{
std::cout << str << std::endl;;
num++;
}
}
std::cout << "Found : " << num << std::endl;
std::cout << "Word to look for: ";
}
return 0;
}
Boucle naïve pour la recherche d'anagrammes valides basé sur std::next_permutation
Cette boucle et ce programme fonctionne parfaitement comme il se doit. Par contre il souffre de quelques faiblesses:
Le nombre de permutations est N! ; pour un mot de 10 lettres, on a déjà plus de 3,5 millions de combinaisons à tester (3628800)
Les casses minuscule et majuscules sont considérées comme étant des lettres différentes
Les accents et autres diacritiques génèrent des lettres différentes
Dans le prochain épisode sur les anagrammes, on améliorera tout ça en repensant la base de données et en évitant les multiples permutations. On s’affranchira aussi des problèmes de casse et de diacritiques.
Souvent lorsqu’on manipule du texte, on cherche à retrouver la forme de base des caractères, c’est-à-dire sans les signes diacritiques. Ce peut être utile pour générer une liste en ordre alphabétique de mots par exemple (on notera que dans l’ordre lexicographique des dictionnaires français, le E, et le É ont la même valeur).
Cet exercice peut être assez complexe car fortement dépendant de l’encodage des caractères (UTF-8, ASCII étendu, etc.) et de la définition donnée à « forme de base« . En effet, d’une langue à l’autre, cette notion peut varier et les diacritiques dans certaines langues donne une lettre à part entière. Par exemple en espagnol, la lettre ñ est une lettre à part qui est classée après le n.
Le remplacement des accents dans une application multi-langues est une tâche complexe et pour se faire, le mieux est d’être aidé par des bibliothèques comme ICU.
En revanche, pour tous les cas relativement fréquents où les caractères sont simplement codés sur un octet en utilisant l’ASCII étendu avec l’encodage ISO-Latin-1, on pourrait utiliser le petit bout de code suivant (inspiré d’une réponse sur Stack Overflow).
Il fut un temps où l’étude de l’apprentissage automatique ou apprentissage statistique était mon quotidien. Depuis on est passé du machine learning au Deep Learning sous fond de cloud computing. Beaucoup de mots nouveaux pour des concepts pas si neufs en fait. En revanche, je dois avouer que le syntagme « Deep Learning » est un tantinet de rien du tout plus bankable et sexy que le titre d’un mémoire tel que: « Optimisation d’ensembles de classifieurs non paramétriques avec apprentissage par représentation partielle de l’information« . Et pour être tout à fait honnête il ne s’agit pas non plus exactement de la même chose.
Il fut donc un temps pas si lointain où je m’intéressais de près aux problématiques d’apprentissage. Depuis, pour toutes sortes de raison dont celle-ci, j’ai commencé à m’intéresser aussi aux services de cloud computing (doit-on vraiment dire infonuagique ?), notamment ceux offerts par Amazon (un célèbre vendeur de chaussettes et autres bidules essentiels).
Récemment, au gré de mes pérégrinations autour dece service, je rencontre cette promesse: Amazon Machine Learning. Forcément, cela m’interpelle aussi tins-je mordicus à tenter l’expérience.
La promesse est donc la suivante: on fournit des données en entrée, Amazon fournit la capacité de calcul et le savoir faire pour créer un modèle de prédiction, ou de classification sans trop avoir besoin de s’encombrer des détails d’implémentation.
Je veux tester. Alors comment faire ?
Le plus évident me semble alors de ressortir de fond des boules à mites des données sur lesquelles j’ai déjà pu travailler. En l’occurrence une célèbre base de données étiquetées de chiffres manuscrits (MNIST) dont voici quelques exemples ci-dessous.
Exemples de chiffres issus de la base de données MNIST
Je me propose donc ici de relater cette expérience. Cette base de données a été exploitée par de nombreux chercheurs, et notamment Luis Oliviera qui vers 2003 obtenait un taux de reconnaissance de plus de 99%. Moi-même, dans un contexte légèrement différent mais sur les mêmes données, j’arrivais autour de 97%. La question est donc la suivante: comment, hors des laboratoires de recherche et 10 à 15 ans plus tard, les services grand public performent-ils?
Il s’agit globalement d’histogrammes sur les concavités (6 vecteurs de 13 dimensions = 78 caractéristiques).
Histogramme des concavités
Concaténés avec 6 autres vecteurs d’histogramme des contours (6 vecteurs de 8 dimensions = 48 caractéristiques).
Histogramme des contours
Finalement, l’aire (nombre de pixels noirs) de chacune des 6 régions est ajoutée pour donner créer un point dans un espace de 78 + 48 + 6 = 132 dimensions. Les différents histogrammes sont normalisés mais je laisse le lecteur curieux le soin de se référer à l’article original pour en connaitre tous les détails.
Chacune des observations, ici des chiffres manuscrits, est donc réduite à n’être plus qu’un point dans cet espace de 132 dimensions.
J’ai retrouvé quelques unes des ces bases de données avec les caractéristiques extraites. Il ne reste plus qu’à les restructurer légèrement afin que Amazon ML puisse les lire. Il me faut donc les transformer au format CSV. Puisque dans mes fichiers les champs sont séparés par uneespace (j’insiste sur le caractère féminin de ce mot dans le contexte typographique) et non pas par une virgule, un petit coup de
sed 's/ /,/g' TRAIN1k > TRAIN1k.csv
Remplacer les espaces par des virgules dans un fichier
fera l’affaire pour remplacer toutes les espaces par de virgules.
Il est aussi dit que chacune des colonnes doit être identifiée par un nom. Pour ce faire, il existe deux méthodes. La première consiste à mettre le nom de chacune des caractéristiques au format CSV sur la première ligne du fichier. La seconde est des mettre ces informations dans un second fichier au même format. J’opte pour la seconde méthode puisque qu’elle me permettra de réutiliser le même fichier pour différentes base de données (en faisant varier la taille des données d’apprentissage par exemple). L’alternative étant de coller cette en-tête au début de chaque nouveau fichier. Au final, je me suis aperçu que nommer les colonnes était tout à fait optionnel.
Nommer nos caractéristiques ne ressemble évidemment à rien dans notre cas quand on comprend comment elles ont été extraites. Je choisis donc de les nommer Feature_1, Feature_2, etc. La dernière colonne se nommera Target puisque c’est la cible (la bonne réponse, la classe recherchée). Le petit one liner (oserais-je un uniligne?) qui va bien est le suivant:
for I in `seq 132`; do echo -ne "Feature_$I,"; done > header.csv; echo Target >> header.csv
Générations des noms de colonnes dans un fichier CSV
J’ai donc 133 valeurs séparées par des virgules, les 132 premières étant Feature_1, Feature_2, et la dernière Target. Ce qui correspond à mon fichier d’entrée.
Upload du fichier
Il faut le mettre dans S3 (ou Redshift). Par exemple j’en ai mis un ici. Le fichier d’en-tête est quant à lui ici.
Il faut bien s’assurer que Amazon ML a les permissions pour accéder aux fichiers déposés sur S3. Bizarrement, cela s’avère ne pas être trivial et je suis resté longtemps avec le message ci-dessous.
Message d’erreur Amazon ML
Une fois que le système est bien configuré, on arrive à ceci:
Capture d’écran d’Amazon ML qui est content d’avoir validé notre fichier d’entrée.
Attention à bien choisir le type de donnée pour la cible. Le système supporte comme entrées et sorties des valeurs binaires, des valeurs numériques, des classes et du texte.
En laissant par défaut une valeur numérique comme sortie attendue, on crée un système qui fait de la prédiction et non pas un classificateur (ou classifieur). Et on se retrouve avec des résultats farfelus comme le montre la figure plus basse (farfelu pour notre problème spécifique, la prédiction de valeur étant dans d’autres cas un excellent cas d’application de l’apprentissage supervisé).
Ce graphique nous dit que si on confond 1 avec 2, c’est moins grave que si on confond 1 avec 9 (car 1 est plus proche de 2). En prédiction (par exemple si on cherche à prédire une grandeur physique comme une vitesse) ça peut avoir un certain sens. Par contre, en classification il n’y a pas ce genre de proximité. On a trouvé la bonne réponse ou pas. Soit c’est un 1, soit c’est un 2, mais ce n’est pas entre les deux.
Donc on reprend. On choisi bien une target qui sera une Category.
Une fois l’apprentissage terminé, on a intérêt tester avec une nouvelle base de données, appelée base de test (ou de validation mais n’entrons pas dans ces détails). J’ai créé un premier modèle à partir de 5000 observations (uniformément distribuées). Et un base de test de 25000.
Le processus est vraiment simple. Une fois la base de données accessible, on appuie sur bouton et l’apprentissage commence. Cela n’a pris que quelques minutes pour créer un modèle à partir de 5000 observations.
On ne sait rien du modèle généré mais on peut en récupérer le taux de reconnaissance. Dans ce cas, un peu moins de 95% sur la base d’apprentissage. Si on ne peut récupérer le modèle, on peut cependant l’utiliser pour faire 3 choses:
mesure sa performance en généralisation en lui passant une nouvelle base de données étiquetées
classifier des bases de données non-étiquetées
classifier en temps réel des observations (par exemple venant d’une application smartphone)
Je me suis arrêté à la mesure de performance en généralisation en faisant varier la taille de l’ensemble d’apprentissage. La figure plus bas montre les taux de reconnaissance obtenus sur les bases d’apprentissage et de test. On semble arriver à une asymptote autour des 98% de reconnaissance, ce qui est un score tout à fait honorable pour un classificateur complètement généraliste.
Outre un taux de reconnaissance, Amazon ML permet de visualiser une matrice de confusion (voir ci-dessous) et même de télécharger l’ensemble des prédictions faites par le classificateur.
Conclusion
Amazon offre la possibilité d’utiliser son infrastructure pour faire de l’apprentissage supervisé. Il n’est pas nécessaire de comprendre comment l’apprentissage se fait, il suffit d’avoir des données étiquetées, de les mettre au bon format et de les envoyer. Les résultats, du moins sur des bases issue de MNIST sont tout à fait respectables. Bien qu’on ne puisse pas récupérer les modèles, on peut les utiliser couplés avec les autres services AWS. En d’autre termes, tout un chacun peut maintenant avoir un service web basé sur de l’apprentissage supervisé sans avoir de compétences particulières dans le domaine. Il faut bien sûr des données étiquetés et surtout, de bonnes features bien extraites. Sur ce dernier point, la prochaine étape sera peut-être un Amazon Deep Learning ou quelque service du genre, permettant de laisser au système le soin de déterminer la meilleure représentation des données.
Je redonne un coup de jeune à ma salle de bain et je dois tailler un plan de travail pour y poser un lavabo. Comment donc reporter le profil du mur sur une planche à couper ?
Côté bricolage classique, pas de soucis. Je remplace la toilette suspendue par une autre et je la déplace. Un peu de plomberie, un peu de Gyproc (BA-13) et de carrelage, tout va bien. Mais, vient le moment de poser le lavabo sur un réceptacle idoine. Selon les plans initiaux, tout est très simple. Il suffit de poser un plan de travail judicieusement coupé à l’endroit prévu à cet effet par des montants vissés dans les murs.
Or, il s’avère que ledit endroit en composé de plusieurs murs se jouxtant à angles tout sauf droits et que l’arête principale du plan de travail ne peut pas être matérialisée facilement : c’est une arête imaginaire entre le bord d’un mur et le bord de la toilette. D’où la difficulté à prendre des cotes fiables.
Les lieux
On peut voir le contexte du projet sur les photos ci-dessous. Un bâti en bois recouvert de BA13 et de carrelage. Et surtout, des murs (à droite sur les images) devant accueillir un plateau judicieusement coupé.
Bâti en tasseau de sapin
Bâti recouvert de BA13
Carrelage de l’espace WC
WC installé
La solution
En bon bricoleur du dimanche, j’ai choisi d’utiliser un scanner 3D pour résoudre mon problème de report du profil de murs sur la planche à découper. J’ai jeté mon dévolu sur un TX8 de chez Trimble. En toute transparence, je dois mentionner le fait que ce soit mon employeur et que l’accès à la fois au matériel et aux logiciels (Trimble RealWorks et Trimble SketchUp) nécessaires à l’opération ont complètement motivé ce choix. Néanmoins, dans le principe, tout un chacun devrait sans doute pouvoir réaliser une opération similaire avec une Kinect et un logiciel libre comme CloudCompare (ou pas, je serais curieux de savoir).
La technologie
Le scanner 3D va permettre de mesurer précisément l’espace dans ma salle de bain. Le principe est de lancer des impulsions laser et de mesurer le temps qu’elles mettent à revenir jusqu’au télémètre embarqué dans le scanner. La vitesse de la lumière étant connue, il est ainsi possible de mesurer la distance parcourue. On convertit ainsi des secondes en mètres (ou en l’occurrence ici, des nanosecondes en millimètres).
Comme le scanner scanne (c’est à dire qu’il effectue un balayage), les impulsions vont ainsi échantillonner des points tout autour de l’instrument, permettant d’obtenir un nuage de points. À tire indicatif, le scanner Trimble TX8 échantillonne ainsi un million de points par seconde.
Les captures d’écran ci-dessous montrent le nuage de points obtenu après la numérisation de ma salle de bain. On est sur un petit nuage de points de quelques dizaines de millions de points.
Nuage de points. Salle de bais vue de l’extérieur.
Nuage de points. Salle de bais vue de l’intérieur.
Nuage de points. Salle de bais vue de dessus.
Le logiciel Trimble RealWorks permet d’effectuer des segmentations et donc de ne retenir que les points utiles à notre sujet, soit les murs et les montants en bois sur lesquels le plan de travail doit s’appuyer.
Les images suivantes en montre l’exemple : seuls ne sont visibles que quelques bouts de murs avec les montants de support.
Nuage de points: Murs et montants
Nuage de points: Murs et montants
Nuage de points: Murs et montants
La modélisation
Une fois la zone d’intérêt isolée, d’autres outils permettent de tracer un plan 3D tangent à 3 points répartis sur les montants en bois.
Plan 3D définit par trois points répartis sur les montants de support
Et une fois ce plan défini, on peut l’utiliser pour dessiner le contour des murs en s’aidant du nuage de points.
Contours du plateau dessinés à l’aide du nuage de points
Le polygone en vert représente maintenant la forme exacte souhaitée pour mon plateau à lavabo. Les images suivantes le montre dans l’espace en 3D. D’abord sous forme de contours sur le plan puis de polygone plein.
Countour du plan de travail dans la 3D
Vue 3D du dessus du plan de travail
Vue 3D du dessus du plan de travail
Les cotes et les coupes
Une fois cette géométrie obtenue, c’est un jeu d’enfant de l’exporter vers SketchUp et d’en sortir toutes les cotes et mesures qui peuvent être utiles.
Cotes vues du laptop
Cotes vue de SketchUp
Puis de reporter ces mesures sur la planche à débiter.
La planche à découper
Le reports des cotes sur la planche
Vue de dessus du plateau une fois coupé
Au final, il ne reste plus qu’à couper et à poser.
Plan de travail taillé et déposé sur les supports
La suite est aussi passionnante mais c’est du bricolage classique comme on en trouvera sur tout bon blog de rénovation de salle de bain. Je laisse donc aux experts carreleurs-blogueurs le soin de détailler le sujet.
Résultat
Plan percé pour le lavabo
Plateau percé en attente du lavabo
Lavabo et plan de travail en vue de dessus
Installation finale
En conclusion
Pour reporter un profil mural sur une planche à couper, on peut soit écumer les solutions telle celle du carton et de l’X-ACTO, soit s’aider d’un scanner 3D et de la suite logicielle appropriée.
Note:
Bien sûr, le prix du scanner + suite logicielle dépasse largement l’investissement fait dans ma salle de bain (au moins par un facteur 50). Aussi, je ne conseille à personne d’acheter ce type de matériel uniquement dans le but de couper un bout de bois. Néanmoins, la capture de données 3D peut se faire par des moyens moins onéreux. En fouillant un peu et en bricolant, les principes énoncés doivent sans doute pouvoir être mis en œuvre avec du matériel un peu plus DIY.
Rencontrés aujourd’hui, au Maker Faire de Paris: des bloggueurs inspirés par la domotique qui ont développé le « Smart Board Sensors » : une interface à base de Arduino permettant d’interfacer facilement une foultitude de capteurs et d’y accéder via HTTP et JSON.
Sur le stand, il y avait notamment une démo avec des électrovannes et des hygromètres. ça m’a rappelé quelque chose… http://www.domotique-info.fr/
Suites aux événement du vendredi 13 novembre 2015 à Paris (où j’habite), j’ai envie de partager cette petite ligne de code à lancer dans un shell (en tout cas ça fonctionne en bash).
t=$(($(tput cols)/3));for FR in $(seq $(tput lines));do printf "e[44m%${t}se[47m%${t}se[41m%${t}se[0mn";done # French Flag
Le résultat devrait être quelque chose qui ressemble à l’image suivante:
Lors des derniers posts, on s’est quitté sur des considérations d’encodage de caractère, de détection de langue et d’API REST. Comme on dit en Papouasie-Nouvelle-Guinée: « Time flies » !
Pendant cet épisode silencieux, une événement s’est produit: j’ai découvert la guitare (un instrument de musique généralement à six cordes). Le silence était donc tout à fait relatif, le reste de la maison peut en témoigner… Bon, bref, l’objectif ici n’est pas de m’épancher sur ma nouvelle vie de rock star (auprès des mes chats, ça fonctionne bien) mais de partager ce que j’ai découvert en essayant de comprendre tout ce qui m’apparaissait arbitraire derrière les concepts de gamme, de ton, de demi-ton. Et pourquoi 12 demis tons (pourquoi pas 10 ou 16). Et puis, entre mi et fa, pourquoi ce hiatus impromptu? Comme on dit aux Malouines: « First things first« , alors commençons par le commencement.
Pour tout individu ayant été un tant soit peu en contact avec la musique occidentale, il y a 7 notes, soit Do, Ré, Mi, Fa, Sol, Laet Sien suivant la nomination de Guido , ou C, D, E, F, G, Aet Bselon la notation anglo-saxonne. Après on recommence. Mais en plus aiguë. On repart de Domais une octave au-dessus. D’autres systèmes existent mais ce n’est pas l’objet de cet article.
Tout de suite, on se dit hé, ben ouais, 7 notes, comme les 7 jours de la semaine, les 7 péchés capitaux, les 7 plaies d’Égypte, les 7 nains de Blanche-Neige, les 7 doigts de la mains, les 7 commandements, les 77 dalmatiens, etc. Je m’emporte. C’est un peu vrai. N’empêche que les trucs un peu cool et mystérieux viennent souvent en bande de 7 (comme les Tortues Ninja, les mousquetaires, les saisons, les 7 tomes d’Harry Potter, le 7e ciel, les atomes de carbone dans l’heptane et le Supplique pour être enterré à la plage de Sète).
Donc, on se dit « héhé, 7 c’est cool, c’est un nombre premier sûr, c’est un peu mystiquifianisant, etc. c’est pour ça qu’il y a sept notes dans notre gamme ». Comme aurait dit Ovide: « Que nenni! » En fait l’explication est ailleurs.
Bien qu’il y ait plusieurs sortes de gammes, il y a un principe généralement admis: quand on double la fréquence d’une note, on retombe sur la même note en plus aiguë (augmentée d’une octave). Corollaire: en divisant par deux la fréquence d’une note, on reste sur la même note mais une octave plus basse.
Par exemple, si on part du Laà 440 Hertz on trouve:
\(440 Hz \times 2 = 880 Hz\) fréquence du Lasuivant. Aussi \(\frac{440 Hz}{2} = 220 Hz\): fréquence du La plus grave.
Illustration de la plage de fréquence d’une octave
Donc, entre deux notes identiques séparées d’une octave on a un intervalle de fréquence. Intervalle à diviser (couper en rondelles) pour obtenir des notes intermédiaire. On pourrait tous diviser cet intervalle en \(2, 3, 7, 12, 17, 32\) ou n’importe quel nombre et inventer son système musical personnel. C’est un peu ce qu’a fait notre ami Pythagore.
Après avoir savamment observé son monocorde favori, il s’aperçut que les notes étaient rarement pures. Une note pure est produite par une onde sinusoïdale unique, qui oscille à une fréquence audible, ce qui pour l’humain correspond grosso modo à la plage \(20 Hz-20 kHz\). En fait, de façon naturelle, un corps vibrant génère des harmoniques, c’est à dire des notes secondaires particulières. Sans doute parce qu’elles sont naturelles et qu’on les retrouve un peu partout un peu tout le temps, l’oreille humaine y trouve un certain réconfort. Une certaine harmonie.
Harmoniques
Les harmoniques sont des multiples entier d’une fréquence de base. Si notre fréquence de base est <e\(f\), les harmoniques seront \(0 f, 1f, 2f, 3f, 4f, 5f\), etc. Chacun des harmoniques (si si, harmonique est masculin). Par exemple, un son à \(0 Hertz\) produira respectivement les harmoniques de fréquences suivantes: \(0 Hz, 0 Hz, 0 Hz, 0 Hz\), etc. En d’autre mots: s’il n’y a pas de source sonore ,il n’y a pas d’harmoniques. C’est plutôt rassurant et corrobore plusieurs lois physiques, notamment en rapport avec la conservation de l’énergie.
Comme les premiers harmoniques ont tendances à être de plus forte amplitude que ceux plus loin dans le spectre, on se concentre généralement sur ces derniers.
Si on se concentre sur les premiers entiers naturels, on a 0, 1, 2, 3, 4, 5.
\(0 f\), c’est un peu intérêt et on ne peut pas en faire grand chose.
\(1 f\) s’appelle fondamentale puisque c’est la fréquence de base. Le fondement. On se rappelle que 1 est l’élément neutre de la multiplication, ce qui veut dire que \(1 \times f = f\). C’est d’ailleurs aussi vrai pour quelques autres valeurs tel que le rappelle le tableau ci-dessous.
Tableau de la multiplication par 1 de nombres célèbres
\(2 f\), on l’a déjà rencontré, c’est la même note mais à l’octave. Comme c’est la même note, ce n’est d’aucune utilité pour construire une gamme.
\(3 f\) est le premier harmonique intéressant. Comme c’est le 3e, on l’appelle quinte. (En fait, il y a une autre raison qu’on verra plus loin). C’est le premier et le plus simple. C’est avec lui qu’on va construire notre gamme.
\(4 f\) est le double de 2f, donc l’octave de l’octave. Si on était parti du La à \(440 Hz\), on serait maintenant sur le La \( \left(2 \times 440 Hz \right) \times 2\), soit un La de \(1760 Hz\). Comme on reste encore sur la même note, ce n’est toujours pas utile pour notre gamme.
\(5 f\) est le second harmonique à produire une nouvelle note. Comme c’est le 5e harmonique, on l’a naturellement nommé tierce. D’ailleurs, en plus de faire des gammes, Pythagore faisait des accords (avec des orchestres de monocordes?) et ce qu’on appelle accord parfait est justement composé de la fondamentale, de la tierce et de la quinte.
Nomenclature des premiers harmoniques
0f
1f
2f
3f
4f
5f
rien
la fondamentale
l’octave
la quinte
l’octave de l’octave (2X2f)
la tierce
Une fois tout ça en place, on va se concentrer sur la quinte: le troisième harmonique, soit le premier harmonique à produire une nouvelle note.
Cette note de fréquence \(3 f\) est supérieure à \(2 f\). (on se souviendra que \(3 \gt 2\) et que \( f\) est strictement positif). Elle est donc en dehors de l’intervalle \(\left[f, 2f \right]\) sur lequel on veut construire une gamme. Heureusement, grâce à une propriété énoncée plus haut, on sait que cette note existe aussi sur une octave plus basse (plus grave). Pour descendre d’une octave on divise par 2 la fréquence, par conséquent \(3 f\) et \(\frac{3}{2}f\) sont une seule et même note (à l’octave près). Bien sûr, \(\frac{3}{2}f\) = \(1.5 f\); ce qui tombe bien sur une fréquence comprise entre \(f\)et \(2 f\). On a enfin généré une première nouvelle note pour notre gamme. Si la note de départ était un Do, 3/2f tombera sur le Sol. Do, Ré, Mi, Fa, Sol: Il y a 5 notes entre Do et Sol, on appelle donc ça une pintequinte. En fait, il n’y a que trois notes entre Do et Sol. Mais bon, pour aller de Do à Sol, il faut bien dire Do, Ré, Mi, Fa, Sol, ce qui nécessite 5 notes. C’est comme ça qu’on en arrive à nommer le produit du 3e harmonique «quinte».
Grayé de cet algorithme, on peut réitérer de façon récursive le processus. On prend la quinte de notre quinte. Partant de Sol = \( \frac{3}{2}f \), on trouve \( 3\times \left( \frac32 \right) f = \frac92 f \). Pour revenir dans l’intervalle \(\left[f, 2f \right]\) on peut diviser par deux autant de fois que l’on veut, en l’occurrence ici on le fera deux fois pour s’arrêter à \(\frac98f = 1,125f\). On a donc une série de multiplications par 3 des fréquences et de divisions par 2 pour ramener la note dans l’intervalle de l’octave. Dit autrement, la fréquence de chaque note dans notre gamme basées sur les quintes successives a la forme
$$\left(\frac{3^n}{2^m}\right)f$$
Répartition des notes sur une octave
p.s.: cet article est resté à l’état de brouillon depuis longtemps, trop longtemps. Le choix éditorial du jour est donc de le publier en l’état. Sans toutes le conclusions sur les gammes tempérées ou non, sur la quinte du loup et sans les tables où l’on peut voir la correspondance entre Hertz et note. Ces dernières tergiversations pourront toujours venir en complément.
On se souviendra que dans les articles précédent, j’ai présenté le dongle Wi-Fi Edimax EW-7811Un. Il est tout beau. Il est tout petit. Il est reconnu par la Raspbian et sur Lego Mindstorm. En plus il coûte moins de 10€. Bref, il a tout ce qu’il faut.
Enfin presque. Dès qu’il a chaud il boude. Le dongle est donc très bien pour une utilisation occasionnelle dans une maison par exemple. Dans mon cas, il doit assurer la liaison 24/24 depuis le cabanon du jardin (là où il y la le contrôle des électrovannes et tout et tout). Ledit cabanon étant ce qu’il est, c’est à dire ni plus ni mois que bonne vieille shed des familles, sans isolation aucune, la température monte l’été largement au-dessus des specs présumées. Enfin, c’est la conclusion à laquelle je suis parvenu. Ayant passé une gros câble RJ-45 de la maison au jardin pour fin d’investigation, j’ai pu m’assurer que le Raspberry Pi était toujours alerte même lorsque le dongle tait mort. En ces occasions, seul un reboot physique permettant de récupérer le dongle. Il faut couper l’alimentation du système. Un soft reboot n’arrive pas à relancer le Edimax EW-7811Un.
J’avais commandé deux dongle identiques et j’ai eu le même comportement avec les deux dongles. Ma conclusion est non scientifique mais relativement étayée par les faits sur un échantillon de 2 observations. J’ai d’autres aspirations que de valider ma théorie par des tests de Student ce qui me demanderaient d’agrandir mon échantillon au-delà de ce que je suis prêt à pourvoir en ressources pour ce problème. D’un point vue plus pratique, j’ai acheté deux autres dongles Ouiphi. Je les ai testés. J’en ai gardé un pour sa facilité de configuration. Le premier (j’ai perdu la référence mais je pourrais la retrouver en fouillant dans mon historique de commandes auprès d’un plus grand fournisseur de tout et n’importe quoi en-ligne) ne voulait pas se configurer facilement sur ma Raspbian. Le second, dont la référence m’échappe au moment d’écrire ces lignes (mais qui pourrait être retrouvée si telle était ma volonté) s’est installé comme un charme, et n’a plus jamais décroché.
Conclusion:
Le dongle WI-FI Edimax EW-7811Un est mignon, il est tout petit, mais il craint la chaleur. Ou du moins, il craint d’être online trop longtemps (la chaleur comme source du problème étant une hypothèse probable mais pas entièrement démontrée). Je le conseille donc plutôt pour une utilisation occasionnelle. Si l’objectif est d’avoir du 24/7 (ce qui approche la valeur de 3,428571428571429 mais vous aviez compris que je ne parlais pas de ça), alors mieux vaut chercher un dongle un peu plus gros, mais un peu plus robuste.
Comme mentionné précédemment, manipuler du texte en différentes langues nécessite de s’intéresser au codage des caractères. Il y a beaucoup de choses à dire sur l’ASCII (version originale à 7 bits, puis étendue à 8 bits), sur l’Unicode et les différentes façon de représenter les caractères. Mais Internet est là pour ça et beaucoup l’ont expliqué mieux que je ne saurais le faire.
Concentrons nous donc sur le problème concret de la création d’histogramme de n-gram à partir de caractères UTF-8. Selon votre langage de programmation favori, un caractère peut avoir différentes significations. En C et comme dans beaucoup de ses dérivés, un « char » est une suite de 8 bits. C’est donc simplement un nombre entier compris entre [-127, 128] ou [0, 255] selon qu’on le considère signé ou non-signé. C’est tout. Fin de l’histoire. Il n’y a aucune notion de représentation derrière, un caractère est un entier défini sur un domaine restreint de 256 valeurs. Ça tombait plutôt pas mal, le standard ASCII, après une mise à jour, associait une lettre, un élément de ponctuation, un chiffre, un caractère à chacune de ces 256 valeurs possibles. La plupart des langues basées sur l’alphabet latin peuvent être couvertes avec 256 symboles (sachant qu’il faut aussi garder de la place pour le chiffres, la ponctuation, des signes essentiels comme $, £, &, @, % et autres #. En y ajoutant quelques symboles qu’on ne voit pas mais qui sont nécessaires (comme le changement de ligne (0x0D), le son de cloche (0x07) ou le 0x15 NAK « negative acknowledge », on remplit rapidement l’espace disponible. Notons que l’euro (€) n’existait pas à l’époque, donc le symbole n’est pas inclut dans l’ASCII. On le retrouve grâce à l’Unicode.
256, c’est joli mais c’est petit
En fait, toutes les langues utilisant un alphabet latin ne peuvent pas s’écrire avec 256 symboles (moins les trucs bizarres comme le NAK). Si on met les ğ et Ş turcs, il n’y a plus de place pour les Ð, Þ ou æ islandais par exemple. Et puis vous savez quoi ? Il y a une multitude de langues qui n’utilisent pas l’alphabet latin ! Déjà que l’ascii ne couvrait pas toutes les déclinaisons de cet alphabet, on peut imaginer le problème des alphabets inuit, cyrillyque, hindî, grec, arabe ou hébreux et plus encore des idéogrammes asiatiques tels les sinogrammes ou les hiraganas.
On veut des bits
Naturellement on se dit qu’il n’y a qu’à rajouter des bits. En effet, en passant à seize (16) bits par caractères, on atteint un potentiel de 65536 symboles différents. En passant à 32 bits, on ouvre les mode des possibles à plus de 4 milliards de lettres/symboles/idéogrammes/smileys.
Bref, tout ça pour dire que l’UTF-8 peut représenter l’ensemble des caractères des langues naturelles en utilisant un nombre variable d’octets. Pour les 128 symboles de l’ASCII de base (2 7 bits = 128 possibilités) tout se passe comme il faut, un seul octet est nécessaire. Ça couvre l’anglais, la ponctuation et quelques autres caractères fondamentaux comme l’inénarrable barre verticale « | » (0x7C).
Mais me direz-vous, octet, octant, octogone, octopode ça me rappelle vaguement le nombre huit. Et bien oui, le huitième bit de l’octet UTF-8 sert à signaler qu’on est dans un cas spécial et qu’il faut combiner les bits déjà lus avec ceux de l’octet suivant pour retrouver notre caractère qui est donc en dehors du domaine des 128 codes de base. Le second octet ayant évidemment lui-même un bit signalant la possibilité d’aller voir chez l’octet suivant et ainsi de suite jusqu’à… 4. Donc un caractère codé en UTF-8 est une suite de 1, 2, 3 ou 4 octets.
L’UTF-8 a beaucoup d’avantages et est largement répandu sur Internet. Je fais donc le Postulat numéro 1 (ou serait-ce un axiome?) que les données d’entrées seront codées de cette façon. Si ce n’est pas le cas, la pléthore d’outils permettant la conversion d’autres systèmes vers UTF-8 permettra, via un pré-traitement des données, de s’assurer de la validité dudit postulat.
Mais alors, c’est quoi un caractère ?
Ça peut être beaucoup de chose. Twitter s’est d’ailleurs posé la question puisque leur mission est de les compter jusqu’à hauteur de 140 (un nombre abondant). Leur définition semble satisfaisante pour les besoins de création de n-gram. Grosso-modo, un unigramme est un « code point« , c’est à dire un ensemble de 1, 2, 3 ou 4 octets représentant une lettre, un idéogramme, un symbole.
Ce n’est pas parfait parce que l’Unicode permet la composition. Par exemple, pour faire ê, il y a plusieurs chemins. La lettre e peut être accentuée, c’est dire qu’une séquence comprenant 2 code points peut être utilisée (un « e » suivi d’un « ^ » ou vice versa, j’en sais trop rien) ou bien on peut aussi coder directement le symbole ê. C’est un exemple de non-orthogonalité flagrante selon une de ses définitions en informatique (2 façons d’arriver au même résultat). L’autre définition portant sur les effets collatéraux d’un appel de fonction sur un appel précédent. C’est dans le même esprit mais je m’égare…
Idéalement, tous les diacritiques devraient être normalisés pour être codés sous la même forme. Mais le postulat numéro 2 dit que ce n’est pas nécessaire. D’ailleurs, l’intérêt est de voir si ça marche avec n’importe qu’elle entrée ayant été le moins pré-traitée possible. Si ça ne fonctionne pas, on remettra en cause le Postulat numéro 2. Pour l’instant, on considère que le système sera assez robuste pour être efficace malgré le biais induit par les différents codages d’un même glyphe. Si ça se passe mal, on rétrogradera le postulat en hypothèse qu’on infirmera. Pour l’instant allons de l’avant.
La ponctuation ?
Les points, point d’interrogation, virgules sont de bons indicateurs de fin ou de début de mot. Ils sont donc utiles puisque selon les différentes langues, les lettres n’ont pas la même fréquence en début ou en fin de mot. L’espace (un nom féminin dans ce contexte !) joue donc aussi un rôle important et doit être considéré comme un caractère à part entière. Cependant, selon l’origine du texte, on peut se retrouver avec des suites de 2, 3 voire 10 espaces consécutives. Le trigramme » » (3 espaces à la queue-leu-leu) est même le plus fréquent avec les données Wikipedia pour le français et l’anglais sur mes premiers tests. C’est un facteur qu’il faudra prendre en compte.
Et concrètement ?
Tout ça pour dire que j’ai trouvé une façon simple de regrouper des unigrammes, des bigrammes et des trigrammes malgré le fait que chacun des code point soit en fait une une chaîne de caractères. Merci à cette librairie qui permet d’itérer sur les code points tout en gardant l’accès aux positions des octets sous-jacents. De cette façon, on peut avancer de un, deux ou trois caractères pour former les n-grammes et construire une std::string à partir des positions des octets. L’histogramme se bâtit en incrémentant les valeurs d’une std::map où la clef est une std::string et la valeur un compteur (int, long long, etc.)
Ce code compile avec une version récente de gcc (il y a quelques éléments de syntaxe du c++0x11). C’est une preuve de concept, pas du code de production, mais si vous voulez expérimenter la génération de n-grammes, c’est un bon point de départ.
Pour ma part j’ai testé quelques 100 000 lignes en français et en anglais venant de Wikipedia (avec et sans les tags XML) et malgré les biais induits par les nombreuses suites d’espaces et les séquences spéciales pour mettre en forme le texte sur Wikipedia (les [[[, »’, et autre), on voit déjà poindre les « de » et « ng » en pôle position pour respectivement les trigrammes français et anglais.
Le choix et le pré-traitement des corpus d’apprentissage sera un dossier en soi, mais d’ici là, je compte travailler sur le stockage des résultats (peut-être avec SQLite) et leur mise à jour (peut-être via une API REST.
Récemment, un article m’a rappelé qu’il était serait amusant de faire un système pour détecter de manière automatique la langue dans laquelle un texte est écrit. L’article en question parlait de complètement autre chose et ne faisait que reprendre les résultats d’un blog anglophone. Cependant, en présentant d’une certaine façon les distributions d’occurrence des lettres au sein de quelques langues européennes, je me suis souvenu que ces distributions donnaient une signature qu’on pouvait utiliser pour reconnaitre la langue d’un texte. Ce peut aussi d’ailleurs être utilisé pour briser les codes simples comme le chiffre de César tel que Simon Singh nous l’expliquait dans son excellent livre sur l’histoire des codes secrets.
Pour créer les signatures, on peut analyser la fréquence d’occurrence des lettres individuelles, mais aussi des séquences de deux lettres consécutives. Par exemple en français, la séquence « ch » est plus fréquente que « sh » ou « cz ». D’autres langues présenteront d’autres proportions pour ces même suites. Et pourquoi s’arrêter à deux ? On peut aussi répertorier les séquences de trois, quatre ou N lettres consécutives. C’est ce qui s’appelle des n-grams. Ça ne se résume pas qu’aux lettres et ça ne sert pas qu’à détecter une langue, mais c’est le contexte dans lequel le présent projet va les utiliser.
Sommairement, il s’agit donc de :
Créer des signatures basées sur les n-grams pour différentes langues
Extraire la signature d’un texte inconnu dont on veut identifier la langue
Comparer sa signature avec celles des langues « apprises »
En déduire l’idiome du texte
La signature n’étant que l’histogramme des fréquences d’occurrence des différents n-grams.
Heu… mais pour quoi faire ?
Clarifions tout de suite un point : je n’en ai personnellement aucune utilité. Ce n’est ni lié à des sujets professionnels, ni à un quelconque outil qui pourrait me servir. La recherche sur le sujet est bien avancée et je ne cherche pas à l’approfondir. Tous les jours on peut d’ailleurs voir à l’œuvre des sites qui ont de très bons résultats dans le domaine. Cependant, la (relative) simplicité de mise en œuvre d’une solution à un problème qui peut sembler aussi complexe est fascinante. C’est donc en pur dilettante que j’ai envie de jouer un peu avec ce problème.
D’un autre côté, bien que la solution soit conceptuellement simple, quelques détails pratiques font qu’il y a tout de même quelques petits défis à relever et questions à répondre. Comment trouver des données d’apprentissage ? Comment gérer les caractères internationaux, l’Unicode et les codages à nombre variable d’octets (par exemple l’UTF-8) ? Que faire de la ponctuation, des espaces, ou même des tags HTML dans le cas où les données viendraient de source web ? Quelle technique choisir pour mesurer la similarité des signatures (vecteurs de cardinalité et de dimensions différentes) ? Comment présenter les résultats ? Bref, suffisamment d’interrogations pour rendre le projet intéressant.
Étapes du projet
Avant de me lancer, j’ai détaillé sommairement les grands blocs ou thèmes sur lesquels il faut travailler. Je les présente ci-dessous, sachant que cela n’a rien de formel. Ce découpage est relativement orthogonal, ce qui permet de travailler indépendamment sur un sujet ou un autre.
Création des bases de données
Obtenir des sources de texte
Analyse des langues
Stockage des résultats
Reconnaissance de la langue
Analyse et création des signatures
Comparaison avec les signatures en base de données
Calcul des estimations de probabilité pour chaque langue
Interface et interaction
Soumission des données à analyser
Mise à jour de la base de données
Affichage des résultats
État des lieux
Corpus d’apprentissage
J’ai quelques pistes pour les corpus d’apprentissage. J’ai expérimenté un peu avec Wikipedia qui permet de télécharger l’intégralité de son contenu à un instant t. C’est trié par langue et de nombreuses langues sont disponibles. Pour récupérer le contenu de Wikipedia, c’est mieux que :
quirysse@beluga:~$ wget --random-wait -r -p -e robots=off -U mozilla http://en.wikipedia.org/wiki/Main_Page
De plus, les fichiers sont codés en XML dans le langage de Wikipedia, ce qui après quelques tests, même après avoir enlevé les tags XML, on trouve beaucoup d’occurrences de » [[ » et autres balises du genre. Ça reste quand même une option mais un peu de préparation de la base de données s’avèrera nécessaire. Il y a une piste avec European Parliament Proceedings Parallel Corpus 1996-2011. C’est d’ailleurs ce qui a été utilisé dans l’article cité plus haut.
Analyse
La génération d’histogrammes d’unigrammes, de bigrammes et de trigrammes n’est pas un souci en soi. Cependant, il faut penser au codage Unicode et comme l’UTF-8 semble tout indiqué, il faut gérer le fait qu’un caractère puisse être composé d’un nombre variable d’octets. Un article complet sur le sujet est en préparation, puisque grâce à cette bibliothèque on peut arriver rapidement à une solution.
Stockage
Les histogrammes, on en fait quoi ? Ils peuvent être longs à générer. On peut vouloir les mettre à jour en utilisant de nouveaux corpus et de nouvelles langues. Alors SQL, fichier maison ? A voir.
Détection de la langue
De façon naturelle on pense au cosinus, mais ça cause certaines difficultés. Je pense plutôt à une erreur RMS ou une distance euclidienne sur les dimensions présentes dans le vecteur d’entrée. Et puis qu’est-ce qu’on fait des hapax et des n-grams très rares. On les garde ou on nettoie le vecteur d’entrée ? Rien n’est fixé mais on en reparlera.
Interface
Évidemment, tout commence toujours pas une série de petits scripts bash et 2 ou 3 mini programmes en C++. Mais au final, une API REST pour obtenir les probabilités des différentes langues sachant une signature pour un texte en entrée, ça serait sympa, non ? Et une page web où l’on verrait les probabilité évoluer en même temps qu’on entre du texte dans un champ, ça serait encore mieux ! C’est un dossier qui est encore un peu loin, mais il y a du potentiel pour faire un système agréable. Pour l’instant, on va en rester au bash…
Conclusion
Donc, voilà où on en est. L’UTF-8 est à peu près réglé (article à suivre). Reste à faire le reste. C’est à dire, à peu près tout…
Site sur le bricolage, la bidouille et l'informatique
