Cette thèse présente des méthodes pour améliorer l'analyse syntaxique probabiliste en dépendances. Nous employons l'analyse à base de transitions avec une modélisation effectuée par des machines à vecteurs supports (Cortes and Vapnik, 1995), et nos expériences sont réalisées sur le français. L'analyse a base de transitions est rapide, de par la faible complexité des algorithmes sous-jacents, eux mêmes fondés sur une optimisation locale des décisions d'attachement. Ainsi notre premier fil directeur est d'élargir le contexte syntaxique utilisé. Partant du système de transitions arc-eager (Nivre, 2008), nous proposons une variante qui considère simultanément plusieurs gouverneurs candidats pour les attachements à droite. Nous testons aussi la correction des analyses, inspirée par Hall and Novák (2005), qui révise chaque attachement en choisissant parmi plusieurs gouverneurs alternatifs dans le voisinage syntaxique. Nos approches améliorent légèrement la précision globale ainsi que celles de l'attachement des groupes prépositionnels et de la coordination. Notre deuxième fil explore des approches semi-supervisées. Nous testons l'auto-entrainement avec un analyseur en deux étapes, basé sur McClosky et al. (2006), pour le domaine journalistique ainsi que pour l'adaptation au domaine médical. Nous passons ensuite à la modélisation lexicale à base de corpus, avec des classes lexicales généralisées pour réduire la dispersion des données, et des préférences lexicales de l'attachement des groupes prépositionnels pour aider à la désambiguïsation. Nos approches améliorent, dans certains cas, la précision et la couverture de l'analyseur, sans augmenter sa complexité théorique.

Existe um grande número de resenhas de usuário na internet contendo valiosas informações sobre serviços, produtos, política e tendências. A compreensão automática dessas opiniões é não somente cientificamente interessante, mas potencialmente lucrativa. A tarefa de classificação de sentimentos visa a extração automática das opiniões expressas em documentos de texto. Diferentemente da tarefa mais tradicional de categorização de textos, na qual documentos são classificados em assuntos como esportes, economia e turismo, a classificação de sentimentos consiste em anotar documentos com os sentimentos expressos no texto. Se comparados aos classificadores tradicionais, os classificadores de sentimentos possuem um desempenho insatisfatório. Uma das possíveis causas do baixo desempenho é a ausência de representações adequadas que permitam a discriminação das opiniões expressas de uma forma concisa e própria para o processamento de máquina. Modelos de tópicos são modelos estatísticos que buscam extrair informações semânticas ocultas na grande quantidade de dados presente em coleções de texto. Eles representam um documento como uma mistura de tópicos, onde cada tópico é uma distribuição de probabilidades sobre palavras. Cada distribuição representa um conceito semântico implícito nos dados. Modelos de tópicos, as palavras são substituídas por tópicos que representam seu significado de forma sucinta. De fato, os modelos de tópicos realizam uma redução de dimensionalidade nos dados que pode levar a um aumento do desempenho das técnicas de categorização de texto e recuperação de informação. Na classificação de sentimentos, eles podem fornecer a representação necessária através da extração de tópicos que representem os sentimentos expressos no texto. Este trabalho dedica-se ao estudo da aplicação de modelos de tópicos na representação e classificação de sentimentos de resenhas de usuário. Em particular, o modelo Latent Dirichlet Allocation (LDA) e quatro extensões (duas delas desenvolvidas pelo autor) são avaliados na tarefa de classificação de sentimentos baseada em múltiplos aspectos. As extensões ao modelo LDA permitem uma investigação dos efeitos da incorporação de informações adicionais como contexto, avaliações de aspecto e avaliações de múltiplos aspectos no modelo original. / There is a large number of user reviews on the internet with valuable information on services, products, politics and trends. There is both scientific and economic interest in the automatic understanding of such data. Sentiment classification is concerned with automatic extraction of opinions expressed in user reviews. Unlike standard text categorization tasks that deal with the classification of documents into subjects such as sports, economics and tourism, sentiment classification attempts to tag documents with respect to the feelings they express. Compared to the accuracy of standard methods, sentiment classifiers have shown poor performance. One possible cause of such a poor performance is the lack of adequate representations that lead to opinion discrimination in a concise and machine-readable form. Topic Models are statistical models concerned with the extraction of semantic information hidden in the large number of data available in text collections. They represent a document as a mixture of topics, probability distributions over words that represent a semantic concept. According to Topic Model representation, words can be substituted by topics able to represent concisely its meaning. Indeed, Topic Models perform a data dimensionality reduction that can improve the performance of text classification and information retrieval techniques. In sentiment classification, they can provide the necessary representation by extracting topics that represent the general feelings expressed in text. This work presents a study of the use of Topic Models for representing and classifying user reviews with respect to their feelings. In particular, the Latent Dirichlet Allocation (LDA) model and four extensions (two of them developed by the author) are evaluated on the task of aspect-based sentiment classification. The extensions to the LDA model enables us to investigate the effects of the incorporation of additional information such as context, aspect rating and multiple aspect rating into the original model.

Chan, Shing Kai. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 106-114). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgements --- p.v / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Problem Statement --- p.2 / Chapter 1.2 --- Motivation for Story Segmentation --- p.4 / Chapter 1.3 --- Terminologies --- p.5 / Chapter 1.4 --- Thesis Goals --- p.6 / Chapter 1.5 --- Thesis Organization --- p.8 / Chapter 2 --- Background Study --- p.9 / Chapter 2.1 --- Coherence-based Approaches --- p.10 / Chapter 2.1.1 --- Defining Coherence --- p.10 / Chapter 2.1.2 --- Lexical Chaining --- p.12 / Chapter 2.1.3 --- Cosine Similarity --- p.15 / Chapter 2.1.4 --- Language Modeling --- p.19 / Chapter 2.2 --- Feature-based Approaches --- p.21 / Chapter 2.2.1 --- Lexical Cues --- p.22 / Chapter 2.2.2 --- Audio Cues --- p.23 / Chapter 2.2.3 --- Video Cues --- p.24 / Chapter 2.3 --- Pros and Cons and Hybrid Approaches --- p.25 / Chapter 2.4 --- Chapter Summary --- p.27 / Chapter 3 --- Experimental Corpora --- p.29 / Chapter 3.1 --- The TDT2 and TDT3 Multi-language Text Corpus --- p.29 / Chapter 3.1.1 --- Introduction --- p.29 / Chapter 3.1.2 --- Program Particulars and Structures --- p.31 / Chapter 3.2 --- Data Preprocessing --- p.33 / Chapter 3.2.1 --- Challenges of Lexical Chain Formation on Chi- nese Text --- p.33 / Chapter 3.2.2 --- Word Segmentation for Word Units Extraction --- p.35 / Chapter 3.2.3 --- Part-of-speech Tagging for Candidate Words Ex- traction --- p.36 / Chapter 3.3 --- Chapter Summary --- p.37 / Chapter 4 --- Indication of Lexical Cohesiveness by Lexical Chains --- p.39 / Chapter 4.1 --- Lexical Chain as a Representation of Cohesiveness --- p.40 / Chapter 4.1.1 --- Choice of Word Relations for Lexical Chaining --- p.41 / Chapter 4.1.2 --- Lexical Chaining by Connecting Repeated Lexi- cal Elements --- p.43 / Chapter 4.2 --- Lexical Chain as an Indicator of Story Segments --- p.48 / Chapter 4.2.1 --- Indicators of Absence of Cohesiveness --- p.49 / Chapter 4.2.2 --- Indicator of Continuation of Cohesiveness --- p.58 / Chapter 4.3 --- Chapter Summary --- p.62 / Chapter 5 --- Indication of Story Boundaries by Lexical Chains --- p.63 / Chapter 5.1 --- Formal Definition of the Classification Procedures --- p.64 / Chapter 5.2 --- Theoretical Framework for Segmentation Based on Lex- ical Chaining --- p.65 / Chapter 5.2.1 --- Evaluation of Story Segmentation Accuracy --- p.65 / Chapter 5.2.2 --- Previous Approach of Story Segmentation Based on Lexical Chaining --- p.66 / Chapter 5.2.3 --- Statistical Framework for Story Segmentation based on Lexical Chaining --- p.69 / Chapter 5.2.4 --- Post Processing of Ratio for Boundary Identifi- cation --- p.73 / Chapter 5.3 --- Comparing Segmentation Models --- p.75 / Chapter 5.4 --- Chapter Summary --- p.79 / Chapter 6 --- Analysis of Lexical Chains Features as Boundary Indi- cators --- p.80 / Chapter 6.1 --- Error Analysis --- p.81 / Chapter 6.2 --- Window Length in the LRT Model --- p.82 / Chapter 6.3 --- The Relative Importance of Each Set of Features --- p.84 / Chapter 6.4 --- The Effect of Removing Timing Information --- p.92 / Chapter 6.5 --- Chapter Summary --- p.96 / Chapter 7 --- Conclusions and Future Work --- p.98 / Chapter 7.1 --- Contributions --- p.98 / Chapter 7.2 --- Future Works --- p.100 / Chapter 7.2.1 --- Further Extension of the Framework --- p.100 / Chapter 7.2.2 --- Wider Applications of the Framework --- p.105 / Bibliography --- p.106

This research is concerned with the reliable delivery of scalable compressed data over lossy communication channels. Recent works proposed several strategies for assigning optimal code redundancies to elements of scalable data, which form a linear structure of dependency, under the assumption that all source elements are encoded onto a common group of network packets. Given large data and small network packets, such schemes require very long channel codes with high computational complexity. In networks with high loss, small packets are more desirable than long packets. The first contribution of this thesis is to propose a strategy for optimally assigning elements of the scalable data to clusters of packets, subject to constraints on packet size and code complexity. Given a packet cluster arrangement, the scheme then assigns optimal code redundancies to the source elements, subject to a constraint on transmission length. Experimental results show that the proposed strategy can outperform the previous code assignment schemes subject to the above-mentioned constraints, particularly at high channel loss rates. Secondly, we modify these schemes to accommodate complex structures of dependency. Source elements are allocated to clusters of packets according to their dependency structure, subject to constraints on packet size and channel codeword length. Given a packet cluster arrangement, the proposed schemes assign optimal code redundancies to the source elements, subject to a constraint on transmission length. Experimental results demonstrate the superiority of the proposed strategies for correctly modelling the dependency structure. The last contribution of this thesis is to propose a scheme for optimizing protection of scalable data where limited retransmission is possible. Previous work assumed that retransmission is not possible. For most real-time or interactive applications, however, retransmission of lost data may be possible up to some limit. In the present work we restrict our attention to streaming sources (e.g., video) where each source element can be transmitted in one or both of two time slots. An optimization algorithm determines the transmission and level of protection for each source element, using information about the success of earlier transmissions. Experimental results confirm the benefit of limited retransmission.

Cette thèse concerne la question de l'accès aux textes numériques, en particulier de l'accès à leur " contenu informationnel ", vu sous l'angle de l'ancrage temporel. Conciliant une approche linguistique et une approche applicative, ils visent à contribuer à l'élaboration de nouveaux outils pour la fouille de textes, la recherche d'information et la gestion des connaissances - nouveaux outils en mesure de tirer parti de la sémantique des informations relatives au repérage temporel exprimées dans les textes. Il s'agit ainsi à la fois de mettre en œuvre des systèmes d'interaction avec les utilisateurs et de parvenir à modéliser la sémantique des unités textuelles qui contribuent de façon saillante à l'ancrage dans le temps des situations décrites dans les textes : les adverbiaux de localisation temporelle. La représentation formelle que l'on en propose, qui procède d'une analyse linguistique, les décrit sous la forme d'une succession d'opérations sémantiques. Cette représentation permet de pouvoir décrire des informations présentant un certain degré d'indétermination sans en fermer l'interprétation (" jusque vers la fin des années 30 "). Elle permet également d'exprimer des informations en intension (" de février à août, tous les jours sauf le dimanche, de 10h à 19h "). Cette représentation est ainsi plus expressive que les modèles généralement utilisés en ingénierie des connaissances - modèles qui, le plus souvent, représentent un repère temporel sous la forme d'une date ou d'un intervalle de dates. Articulant notre proposition de modélisation avec les modèles standards des intervalles de dates, nous montrons qu'il devient possible d'élaborer de nouveaux systèmes de recherche d'information, susceptibles de traiter des requêtes associant un critère calendaire avec un ensemble de mots-clés, telles que " les universités au début du XIIe siècle " ou " le vote des femmes depuis 1900 ", par exemple. S'appuyant sur les outils développés en ce sens, on montre qu'il devient également possible d'interagir avec des données structurées décrivant des informations temporelles, à la fois pour les interroger et pour les enrichir de façon semi-automatique, afin, par exemple, de constituer des bases de connaissances.

Dans ce mémoire, nous nous attachons à retracer les différents travaux de recherche que nous avons menés depuis plus de 10 ans. L'un de nos objectifs principaux a été d'améliorer la finesse linguistique de différentes tâches du TAL en prenant en compte les expressions multi-mots. En particulier, notre idée directrice a été d'exploiter des ressources lexicales riches et de les coupler à différents modèles probabilistes ou différentes procédures hybrides. Nos travaux peuvent se découper en trois axes. Le premier axe porte sur l'étiquetage morphosyntaxique et l'analyse syntaxique. L'intégration de la reconnaissance des expressions multi-mots dans telles tâches a essentiellement consisté à adapter divers modèles probabilistes dédiés à ces tâches. Comme ces expressions sont, par définition, difficilement prédictibles, l'exploitation de ressources lexicales est primordiale pour leur reconnaissance. Nous avons donc été amené à trouver des stratégies d'intégration de ressources symboliques externes dans nos modèles. Le deuxième axe consiste à intégrer la reconnaissance d'expressions multi-mots dans des applications. Nous avons, en particulier, développé des applications liées au monde privé (extraction d'informations, classification) ou liées au monde académique (aide à la construction de lexiques bilingues ou à des études linguistiques). Dans tous les cas, nous nous sommes basé sur des prétraitements fins alimentés par des ressources lexicales riches. Le troisième axe concerne la construction de ressources linguistiques. En effet, le développement des outils décrits ci-dessus n'est possible que grâce à l'existence de ressources (corpus annotés ou lexiques). Or, les ressources autour des expressions multi-mots manquent cruellement ou sont incomplètes. Pour toutes les ressources développées, nous avons mené des études linguistiques fines et systématiques. Nous avons également mis en place un outillage informatique pour les gérer et les appliquer à des textes.

Malgré l'entrée récente de notre monde dans l'ère du tout numérique, de nombreux documents manuscrits continuent à s'échanger, obligeant nos sociétés et administrations à faire face au traitement de ces masses de documents. Le traitement automatique de ces documents nécessite d'accéder à un échantillon inconnu mais pertinent de leur contenu et implique de prendre en compte trois points essentiels : la segmentation du document en entités comparable à l'information recherchée, la reconnaissance de ces entités recherchées et le rejet des entités non pertinentes. Nous nous démarquons des approches classiques de lecture complète de documents et de détection de mots clés en parallélisant ces trois traitements en une approche d'extraction d'information. Une première contribution réside dans la conception d'un modèle de ligne générique pour l'extraction d'information et l'implémentation d'un système complet à base de modèles de Markov cachés (MMC) construit autour de ce modèle. Le module de reconnaissance cherche, en une seule passe, à discriminer l'information pertinente, caractérisée par un ensemble de requêtes alphabétiques, numériques ou alphanumériques, de l'information non pertinente, caractérisée par un modèle de remplissage. Une seconde contribution réside dans l'amélioration de la discrimination locale des observations des lignes par l'utilisation d'un réseau de neurones profond. Ce dernier permet également d'inférer une représentation de haut niveau des observations et donc d'automatiser le processus d'extraction des caractéristiques. Il en résulte un système complet, générique et industrialisable, répondant à des besoins émergents dans le domaine de la lecture automatique de documents manuscrits : l'extraction d'informations complexes dans des documents non-contraints.

In a variety of text document editing and processing applications, it is necessary to keep track of the revision history of text documents by recording changes and the metadata of those changes (e.g., user names and modification timestamps). The recent Web 2.0 document editing and processing applications, such as real-time collaborative note taking and wikis, require fine-grained shared access to collaborative text documents as well as efficient retrieval of metadata associated with different parts of collaborative text documents. Current revision control techniques only support coarse-grained shared access and are inefficient to retrieve metadata of changes at the sub-document granularity. In this dissertation, we design and implement partial persistent sequences (PPSs) to support real-time collaborations and manage metadata of changes at fine granularities for collaborative text document editing and processing applications. As a persistent data structure, PPSs have two important features. First, items in the data structure are never removed. We maintain necessary timestamp information to keep track of both inserted and deleted items and use the timestamp information to reconstruct the state of a document at any point in time. Second, PPSs create unique, persistent, and ordered identifiers for items of a document at fine granularities (e.g., a word or a sentence). As a result, we are able to support consistent and fine-grained shared access to collaborative text documents by detecting and resolving editing conflicts based on the revision history as well as to efficiently index and retrieve metadata associated with different parts of collaborative text documents. We demonstrate the capabilities of PPSs through two important problems in collaborative text document editing and processing applications: data consistency control and fine-grained document provenance management. The first problem studies how to detect and resolve editing conflicts in collaborative text document editing systems. We approach this problem in two steps. In the first step, we use PPSs to capture data dependencies between different editing operations and define a consistency model more suitable for real-time collaborative editing systems. In the second step, we extend our work to the entire spectrum of collaborations and adapt transactional techniques to build a flexible framework for the development of various collaborative editing systems. The generality of this framework is demonstrated by its capabilities to specify three different types of collaborations as exemplified in the systems of RCS, MediaWiki, and Google Docs respectively. We precisely specify the programming interfaces of this framework and describe a prototype implementation over Oracle Berkeley DB High Availability, a replicated database management engine. The second problem of fine-grained document provenance management studies how to efficiently index and retrieve fine-grained metadata for different parts of collaborative text documents. We use PPSs to design both disk-economic and computation-efficient techniques to index provenance data for millions of Wikipedia articles. Our approach is disk economic because we only save a few full versions of a document and only keep delta changes between those full versions. Our approach is also computation-efficient because we avoid the necessity of parsing the revision history of collaborative documents to retrieve fine-grained metadata. Compared to MediaWiki, the revision control system for Wikipedia, our system uses less than 10% of disk space and achieves at least an order of magnitude speed-up to retrieve fine-grained metadata for documents with thousands of revisions.

Thesis (M.S.)--State University of New York at Binghamton, Thomas J. Watson School of Engineering and Applied Science, Department of Electrical and Computer Engineering, 2009. / Includes bibliographical references.

L'augmentation de la production des documents électroniques disponibles sous forme du texte ou d'audio (journaux, radio, enregistrements audio de télévision, etc.) nécessite le développement d'outils automatisés pour le suivi et la navigation. Il devrait être possible, par exemple, lors de la lecture d'un article d'un journal en ligne, d'accéder à des émissions radio correspondant à la lecture en cours. Cette navigation fine entre les différents médias exige l'alignement des "passages" avec un contenu similaire dans des documents issus de différentes modalités monolingues et comparables. Notre travail se concentre sur ce problème d'alignement de textes courts dans un contexte comparable monolingue et multimodal. Le problème consiste à trouver des similitudes entre le texte court et comment extraire les caractéristiques de ces textes pour nous aider à trouver les similarités pour le processus d'alignement. Nous contributions à ce problème en trois parties. La première partie tente de définir la similitude qui est la base du processus d'alignement. La deuxième partie vise à développer une nouvelle représentation de texte afin de faciliter la création du corpus de référence qui va servir à évaluer les méthodes d'alignement. Enfin, la troisième contribution est d'étudier différentes méthodes d'alignement et l'effet de ses composants sur le processus d'alignement. Ces composants comprennent différentes représentations textuelles, des poids et des mesures de similarité.