Structural and Computational Existence Results for Multidimensional Subshifts

Symbolic dynamics is a branch of mathematics that studies the structure of infinite sequences of symbols, or in the multidimensional case, infinite grids of symbols. Classes of such sequences and grids defined by collections of forbidden patterns are called subshifts, and subshifts of finite type are defined by finitely many forbidden patterns. The simplest examples of multidimensional subshifts are sets of Wang tilings, infinite arrangements of square tiles with colored edges, where adjacent edges must have the same color. Multidimensional symbolic dynamics has strong connections to computability theory, since most of the basic properties of subshifts cannot be recognized by computer programs, but are instead characterized by some higher-level notion of computability. This dissertation focuses on the structure of multidimensional subshifts, and the ways in which it relates to their computational properties. In the first part, we study the subpattern posets and Cantor-Bendixson ranks of countable subshifts of finite type, which can be seen as measures of their structural complexity. We show, by explicitly constructing subshifts with the desired properties, that both notions are essentially restricted only by computability conditions. In the second part of the dissertation, we study different methods of defining (classes of ) multidimensional subshifts, and how they relate to each other and existing methods. We present definitions that use monadic second-order logic, a more restricted kind of logical quantification called quantifier extension, and multi-headed finite state machines. Two of the definitions give rise to hierarchies of subshift classes, which are a priori infinite, but which we show to collapse into finitely many levels. The quantifier extension provides insight to the somewhat mysterious class of multidimensional sofic subshifts, since we prove a characterization for the class of subshifts that can extend a sofic subshift into a nonsofic one.

Les cadres intermédiaires et l’information : modélisation des comportements informationnels de cadres intermédiaires d’une municipalité en transformation

Un atout majeur des organisations consiste en leur capacité à créer et exploiter l’information et les connaissances, capacité déterminée entre autres par les comportements informationnels. Chargés de décisions stratégiques, tactiques et opérationnelles, les cadres intermédiaires sont au cœur du processus de création des connaissances, et leurs comportements informationnels doivent être soutenus par des systèmes d’information. Toutefois, leurs comportements informationnels sont peu documentés. La présente recherche porte sur la modélisation des comportements informationnels de cadres intermédiaires d’une organisation municipale. Plus spécifiquement, elle examine comment ces cadres répondent à leurs besoins d’information courante dans le contexte de leurs activités de gestion, c’est-à-dire dans leur environnement d’utilisation d’information. L’étude répond aux questions de recherche suivantes : (1) Quelles sont les situations problématiques auxquelles font face les cadres intermédiaires municipaux ? (2) Quels sont les besoins informationnels exprimés par les cadres intermédiaires municipaux lors de situations problématiques ? (3) Quelles sont les sources d’information qui soutiennent les comportements informationnels des cadres intermédiaires municipaux ? Cette recherche descriptive s’inscrit dans une approche qualitative. Les 21 cadres intermédiaires ayant participé à l’étude proviennent de deux arrondissements d’une municipalité québécoise fusionnée en 2002. Les modes de collecte de données sont l’entrevue en profondeur en personne et l’observation directe auprès de ces cadres, et la collecte de documentation pertinente. L’incident critique est utilisé comme technique de collecte de données et comme unité d’analyse. Les données recueillies font l’objet d’une analyse de contenu qualitative basée sur la théorisation ancrée. Les résultats indiquent que les rôles de gestion proposés dans les écrits pour les cadres supérieurs s’appliquent aussi aux cadres intermédiaires, bien que le rôle conseil ressorte comme étant particulier à ces derniers. Ceux-ci ont des responsabilités de gestion aux trois niveaux d’intervention opérationnel, tactique et stratégique, bien qu’ils œuvrent davantage au plan tactique. Les situations problématiques dont ils sont chargés s’inscrivent dans l’environnement d’utilisation d’information constitué des composantes suivantes : leurs rôles et responsabilités de gestion et le contexte organisationnel propre à une municipalité en transformation. Les cadres intermédiaires ont eu à traiter davantage de situations nouvelles que récurrentes, caractérisées par des sujets portant principalement sur les ressources matérielles et immobilières ou sur des aspects d’intérêt juridique, réglementaire et normatif. Ils ont surtout manifesté des besoins pour de l’information de nature processuelle et contextuelle. Pour y répondre, ils ont consulté davantage de sources verbales que documentaires, même si le nombre de ces dernières reste élevé, et ont préféré utiliser des sources d’information internes. Au plan théorique, le modèle de comportement informationnel proposé pour les cadres intermédiaires municipaux enrichit les principales composantes du modèle général d’utilisation de l’information (Choo, 1998) et du modèle d’environnement d’utilisation d’information (Taylor, 1986, 1991). L’étude permet aussi de préciser les concepts d’« utilisateur » et d’« utilisation de l’information ». Au plan pratique, la recherche permet d’aider à la conception de systèmes de repérage d’information adaptés aux besoins des cadres intermédiaires municipaux, et aide à évaluer l’apport des systèmes d’information archivistiques à la gestion de la mémoire organisationnelle.

Étude sur l’influence du vocabulaire utilisé pour l’indexation des images en contexte de repérage multilingue

Depuis quelques années, Internet est devenu un média incontournable pour la diffusion de ressources multilingues. Cependant, les différences linguistiques constituent souvent un obstacle majeur aux échanges de documents scientifiques, culturels, pédagogiques et commerciaux. En plus de cette diversité linguistique, on constate le développement croissant de bases de données et de collections composées de différents types de documents textuels ou multimédias, ce qui complexifie également le processus de repérage documentaire. En général, on considère l’image comme « libre » au point de vue linguistique. Toutefois, l’indexation en vocabulaire contrôlé ou libre (non contrôlé) confère à l’image un statut linguistique au même titre que tout document textuel, ce qui peut avoir une incidence sur le repérage. Le but de notre recherche est de vérifier l’existence de différences entre les caractéristiques de deux approches d’indexation pour les images ordinaires représentant des objets de la vie quotidienne, en vocabulaire contrôlé et en vocabulaire libre, et entre les résultats obtenus au moment de leur repérage. Cette étude suppose que les deux approches d’indexation présentent des caractéristiques communes, mais également des différences pouvant influencer le repérage de l’image. Cette recherche permet de vérifier si l’une ou l’autre de ces approches d’indexation surclasse l’autre, en termes d’efficacité, d’efficience et de satisfaction du chercheur d’images, en contexte de repérage multilingue. Afin d’atteindre le but fixé par cette recherche, deux objectifs spécifiques sont définis : identifier les caractéristiques de chacune des deux approches d’indexation de l’image ordinaire représentant des objets de la vie quotidienne pouvant influencer le repérage, en contexte multilingue et exposer les différences sur le plan de l’efficacité, de l’efficience et de la satisfaction du chercheur d’images à repérer des images ordinaires représentant des objets de la vie quotidienne indexées à l’aide d’approches offrant des caractéristiques variées, en contexte multilingue. Trois modes de collecte des données sont employés : l’analyse des termes utilisés pour l’indexation des images, la simulation du repérage d’un ensemble d’images indexées selon chacune des formes d’indexation à l’étude réalisée auprès de soixante répondants, et le questionnaire administré aux participants pendant et après la simulation du repérage. Quatre mesures sont définies pour cette recherche : l’efficacité du repérage d’images, mesurée par le taux de succès du repérage calculé à l’aide du nombre d’images repérées; l’efficience temporelle, mesurée par le temps, en secondes, utilisé par image repérée; l’efficience humaine, mesurée par l’effort humain, en nombre de requêtes formulées par image repérée et la satisfaction du chercheur d’images, mesurée par son autoévaluation suite à chaque tâche de repérage effectuée. Cette recherche montre que sur le plan de l’indexation de l’image ordinaire représentant des objets de la vie quotidienne, les approches d’indexation étudiées diffèrent fondamentalement l’une de l’autre, sur le plan terminologique, perceptuel et structurel. En outre, l’analyse des caractéristiques des deux approches d’indexation révèle que si la langue d’indexation est modifiée, les caractéristiques varient peu au sein d’une même approche d’indexation. Finalement, cette recherche souligne que les deux approches d’indexation à l’étude offrent une performance de repérage des images ordinaires représentant des objets de la vie quotidienne différente sur le plan de l’efficacité, de l’efficience et de la satisfaction du chercheur d’images, selon l’approche et la langue utilisées pour l’indexation.

Le comportement informationnel des jeunes adultes québécois en matière de santé sexuelle

Depuis quelques années, les statistiques indiquent une croissance exponentielle de l’incidence de certaines infections transmissibles sexuellement chez les jeunes adultes. Certaines enquêtes témoignent en outre des comportements peu responsables en matière de santé sexuelle chez cette population, bien que l’offre d’information sur les conséquences de tels comportements soit importante et diversifiée. Par ailleurs, le comportement informationnel de cette population en matière de santé sexuelle demeure peu documenté. La présente étude porte sur le comportement informationnel de jeunes adultes québécois en matière de santé sexuelle. Plus spécifiquement, elle répond aux quatre questions de recherche suivantes : (1) Quelles sont les situations problématiques auxquelles les jeunes adultes sont confrontés en santé sexuelle?, (2) Quels sont les besoins informationnels exprimés par les jeunes adultes lors de ces situations problématiques?, (3) Quels sont les processus et les sources d’information qui soutiennent la résolution de ces besoins informationnels? et (4) Quelle est l’utilisation de l’information trouvée? Cette recherche descriptive a utilisé une approche qualitative. Le milieu retenu est l’Université de Montréal pour deux raisons : il s’agit d’un milieu cognitivement riche qui fournit un accès sur place à des ressources en santé sexuelle. Les huit jeunes adultes âgés de 18 à 25 ans qui ont pris part à cette étude ont participé à une entrevue en profondeur utilisant la technique de l’incident critique. Chacun d’entre eux a décrit une situation problématique par rapport à sa santé sexuelle et les données recueillies ont été l’objet d’une analyse de contenu basée sur la théorisation ancrée. Les résultats indiquent que les jeunes adultes québécois vivent des situations problématiques relatives à l’aspect physique de leur santé sexuelle qui peuvent être déclenchées par trois types d’éléments : un événement à risques, un symptôme physique subjectif et de l’information acquise passivement. Ces situations problématiques génèrent trois catégories de besoins informationnels : l’état de santé actuel, les conséquences possibles et les remèdes. Pour répondre à ces besoins, les participants se sont tournés en majorité vers des sources professionnelles, personnelles et verbales. La présence de facteurs contextuels, cognitifs et affectifs a particularisé leur processus de recherche d’information en modifiant les combinaisons des quatre activités effectuées, soit débuter, enchaîner, butiner et différencier. L’automotivation et la compréhension du problème représentent les deux principales utilisations de l’information. D’un point de vue théorique, les résultats indiquent que le modèle général de comportement informationnel de Choo (2006), le modèle d’environnement d’utilisation de l’information de Taylor (1986, 1991) et le modèle d’activités de recherche d’information d’Ellis (1989a, 1989b, 2005) peuvent être utilisés dans le contexte personnel de la santé sexuelle. D’un point de vue pratique, cette étude ajoute aux connaissances sur les critères de sélection des sources d’information en matière de santé sexuelle.

Non-negative matrix decomposition approaches to frequency domain analysis of music audio signals

On étudie l’application des algorithmes de décomposition matricielles tel que la Factorisation Matricielle Non-négative (FMN), aux représentations fréquentielles de signaux audio musicaux. Ces algorithmes, dirigés par une fonction d’erreur de reconstruction, apprennent un ensemble de fonctions de base et un ensemble de coef- ficients correspondants qui approximent le signal d’entrée. On compare l’utilisation de trois fonctions d’erreur de reconstruction quand la FMN est appliquée à des gammes monophoniques et harmonisées: moindre carré, divergence Kullback-Leibler, et une mesure de divergence dépendente de la phase, introduite récemment. Des nouvelles méthodes pour interpréter les décompositions résultantes sont présentées et sont comparées aux méthodes utilisées précédemment qui nécessitent des connaissances du domaine acoustique. Finalement, on analyse la capacité de généralisation des fonctions de bases apprises par rapport à trois paramètres musicaux: l’amplitude, la durée et le type d’instrument. Pour ce faire, on introduit deux algorithmes d’étiquetage des fonctions de bases qui performent mieux que l’approche précédente dans la majorité de nos tests, la tâche d’instrument avec audio monophonique étant la seule exception importante.

Algorithmes de recommandation musicale

Ce mémoire est composé de trois articles qui s’unissent sous le thème de la recommandation musicale à grande échelle. Nous présentons d’abord une méthode pour effectuer des recommandations musicales en récoltant des étiquettes (tags) décrivant les items et en utilisant cette aura textuelle pour déterminer leur similarité. En plus d’effectuer des recommandations qui sont transparentes et personnalisables, notre méthode, basée sur le contenu, n’est pas victime des problèmes dont souffrent les systèmes de filtrage collaboratif, comme le problème du démarrage à froid (cold start problem). Nous présentons ensuite un algorithme d’apprentissage automatique qui applique des étiquettes à des chansons à partir d’attributs extraits de leur fichier audio. L’ensemble de données que nous utilisons est construit à partir d’une très grande quantité de données sociales provenant du site Last.fm. Nous présentons finalement un algorithme de génération automatique de liste d’écoute personnalisable qui apprend un espace de similarité musical à partir d’attributs audio extraits de chansons jouées dans des listes d’écoute de stations de radio commerciale. En plus d’utiliser cet espace de similarité, notre système prend aussi en compte un nuage d’étiquettes que l’utilisateur est en mesure de manipuler, ce qui lui permet de décrire de manière abstraite la sorte de musique qu’il désire écouter.

Génération et reconnaissance de rythmes au moyen de réseaux de neurones à réservoir

Les fichiers sons qui accompagne mon document sont au format midi. Le programme que nous avons développés pour ce travail est en language Python.

Élaboration d'un corpus étalon pour l'évaluation d'extracteurs de termes

Ce travail porte sur la construction d’un corpus étalon pour l’évaluation automatisée des extracteurs de termes. Ces programmes informatiques, conçus pour extraire automatiquement les termes contenus dans un corpus, sont utilisés dans différentes applications, telles que la terminographie, la traduction, la recherche d’information, l’indexation, etc. Ainsi, leur évaluation doit être faite en fonction d’une application précise. Une façon d’évaluer les extracteurs consiste à annoter toutes les occurrences des termes dans un corpus, ce qui nécessite un protocole de repérage et de découpage des unités terminologiques. À notre connaissance, il n’existe pas de corpus annoté bien documenté pour l’évaluation des extracteurs. Ce travail vise à construire un tel corpus et à décrire les problèmes qui doivent être abordés pour y parvenir. Le corpus étalon que nous proposons est un corpus entièrement annoté, construit en fonction d’une application précise, à savoir la compilation d’un dictionnaire spécialisé de la mécanique automobile. Ce corpus rend compte de la variété des réalisations des termes en contexte. Les termes sont sélectionnés en fonction de critères précis liés à l’application, ainsi qu’à certaines propriétés formelles, linguistiques et conceptuelles des termes et des variantes terminologiques. Pour évaluer un extracteur au moyen de ce corpus, il suffit d’extraire toutes les unités terminologiques du corpus et de comparer, au moyen de métriques, cette liste à la sortie de l’extracteur. On peut aussi créer une liste de référence sur mesure en extrayant des sous-ensembles de termes en fonction de différents critères. Ce travail permet une évaluation automatique des extracteurs qui tient compte du rôle de l’application. Cette évaluation étant reproductible, elle peut servir non seulement à mesurer la qualité d’un extracteur, mais à comparer différents extracteurs et à améliorer les techniques d’extraction.

Who influence the music tastes of adolescents? A study on interpersonal influence in social networks

Research on music information behavior demonstrates that people rely primarily on others to discover new music. This paper reports on a qualitative study aiming at exploring more in-depth how music information circulates within the social networks of late adolescents and the role the different people involved in the process play. In-depth interviews were conducted with 19 adolescents (15-17 years old). The analysis revealed that music opinion leaders showed eagerness to share music information, tended to seek music information on an ongoing basis, and were perceived as being more knowledgeable than others in music. It was found that the ties that connected participants to opinion leaders were predominantly strong ties, which suggests that trustworthiness is an important component of credibility. These findings could potentially help identify new avenues for the improvement of music recommender systems.

Construction et validation de filtres de recherche bibliographique pour soutenir la prise de décisions basée sur les évidences : le cas de la sécurité des patients.

Les filtres de recherche bibliographique optimisés visent à faciliter le repérage de l’information dans les bases de données bibliographiques qui sont presque toujours la source la plus abondante d’évidences scientifiques. Ils contribuent à soutenir la prise de décisions basée sur les évidences. La majorité des filtres disponibles dans la littérature sont des filtres méthodologiques. Mais pour donner tout leur potentiel, ils doivent être combinés à des filtres permettant de repérer les études couvrant un sujet particulier. Dans le champ de la sécurité des patients, il a été démontré qu’un repérage déficient de l’information peut avoir des conséquences tragiques. Des filtres de recherche optimisés couvrant le champ pourraient s’avérer très utiles. La présente étude a pour but de proposer des filtres de recherche bibliographique optimisés pour le champ de la sécurité des patients, d’évaluer leur validité, et de proposer un guide pour l’élaboration de filtres de recherche. Nous proposons des filtres optimisés permettant de repérer des articles portant sur la sécurité des patients dans les organisations de santé dans les bases de données Medline, Embase et CINAHL. Ces filtres réalisent de très bonnes performances et sont spécialement construits pour les articles dont le contenu est lié de façon explicite au champ de la sécurité des patients par leurs auteurs. La mesure dans laquelle on peut généraliser leur utilisation à d’autres contextes est liée à la définition des frontières du champ de la sécurité des patients.

A Document Browsing Tool Based on Book Indexes

This research project is a contribution to the global field of information retrieval, specifically, to develop tools to enable information access in digital documents. We recognize the need to provide the user with flexible access to the contents of large, potentially complex digital documents, with means other than a search function or a handful of metadata elements. The goal is to produce a text browsing tool offering a maximum of information based on a fairly superficial linguistic analysis. We are concerned with a type of extensive single-document indexing, and not indexing by a set of keywords (see Klement, 2002, for a clear distinction between the two). The desired browsing tool would not only give at a glance the main topics discussed in the document, but would also present relationships between these topics. It would also give direct access to the text (via hypertext links to specific passages). The present paper, after reviewing previous research on this and similar topics, discusses the methodology and the main characteristics of a prototype we have devised. Experimental results are presented, as well as an analysis of remaining hurdles and potential applications.

Design and Development of an Adaptable Frame -Based System for Dravidian Language Processing

This work is aimed at building an adaptable frame-based system for processing Dravidian languages. There are about 17 languages in this family and they are spoken by the people of South India.Karaka relations are one of the most important features of Indian languages. They are the semabtuco-syntactic relations between verbs and other related constituents in a sentence. The karaka relations and surface case endings are analyzed for meaning extraction. This approach is comparable with the borad class of case based grammars.The efficiency of this approach is put into test in two applications. One is machine translation and the other is a natural language interface (NLI) for information retrieval from databases. The system mainly consists of a morphological analyzer, local word grouper, a parser for the source language and a sentence generator for the target language. This work make contributios like, it gives an elegant account of the relation between vibhakthi and karaka roles in Dravidian languages. This mapping is elegant and compact. The same basic thing also explains simple and complex sentence in these languages. This suggests that the solution is not just ad hoc but has a deeper underlying unity. This methodology could be extended to other free word order languages. Since the frame designed for meaning representation is general, they are adaptable to other languages coming in this group and to other applications.

Analytical Study of Typographical Errors in OPACS and Corrective Measures

The present study is an attempt to highlight the problem of typographical errors in OPACS. The errors made while typing catalogue entries as well as importing bibliographical records from other libraries exist unnoticed by librarians resulting the non-retrieval of available records and affecting the quality of OPACs. This paper follows previous research on the topic mainly by Jeffrey Beall and Terry Ballard. The word “management” was chosen from the list of likely to be misspelled words identified by previous research. It was found that the word is wrongly entered in several forms in local, national and international OPACs justifying the observations of Ballard that typos occur in almost everywhere. Though there are lots of corrective measures proposed and are in use, the study asserts the fact that human effort is needed to get rid of the problem. The paper is also an invitation to the library professionals and system designers to construct a strategy to solve the issue

Analytical Study of Typographical Errors in OPACS and Corrective Measures

The present study is an attempt to highlight the problem of typographical errors in OPACS. The errors made while typing catalogue entries as well as importing bibliographical records from other libraries exist unnoticed by librarians resulting the non-retrieval of available records and affecting the quality of OPACs. This paper follows previous research on the topic mainly by Jeffrey Beall and Terry Ballard. The word “management” was chosen from the list of likely to be misspelled words identified by previous research. It was found that the word is wrongly entered in several forms in local, national and international OPACs justifying the observations of Ballard that typos occur in almost everywhere. Though there are lots of corrective measures proposed and are in use, the study asserts the fact that human effort is needed to get rid of the problem. The paper is also an invitation to the library professionals and system designers to construct a strategy to solve the issue

Hierarchies of conceptual scales

Formal Concept Analysis allows to derive conceptual hierarchies from data tables. Formal Concept Analysis is applied in various domains, e.g., data analysis, information retrieval, and knowledge discovery in databases. In order to deal with increasing sizes of the data tables (and to allow more complex data structures than just binary attributes), conceputal scales habe been developed. They are considered as metadata which structure the data conceptually. But in large applications, the number of conceptual scales increases as well. Techniques are needed which support the navigation of the user also on this meta-level of conceptual scales. In this paper, we attack this problem by extending the set of scales by hierarchically ordered higher level scales and by introducing a visualization technique called nested scaling. We extend the two-level architecture of Formal Concept Analysis (the data table plus one level of conceptual scales) to many-level architecture with a cascading system of conceptual scales. The approach also allows to use representation techniques of Formal Concept Analysis for the visualization of thesauri and ontologies.