linguagem é uma marca da humanidade e da consciência, sendo a conversação (ou diálogo) uma das maneiras de comunicacão mais fundamentais que aprendemos quando crianças. Por isso uma forma de fazer um computador mais atrativo para interação com usuários é usando linguagem natural. Dos sistemas com algum grau de capacidade de linguagem desenvolvidos, o chatterbot Eliza é, provavelmente, o primeiro sistema com foco em diálogo. Com o objetivo de tornar a interação mais interessante e útil para o usuário há outras aplicações alem de chatterbots, como agentes conversacionais. Estes agentes geralmente possuem, em algum grau, propriedades como: corpo (com estados cognitivos, incluindo crenças, desejos e intenções ou objetivos); incorporação interativa no mundo real ou virtual (incluindo percepções de eventos, comunicação, habilidade de manipular o mundo e comunicar com outros agentes); e comportamento similar ao humano (incluindo habilidades afetivas). Este tipo de agente tem sido chamado de diversos nomes como agentes animados ou agentes conversacionais incorporados. Um sistema de diálogo possui seis componentes básicos. (1) O componente de reconhecimento de fala que é responsável por traduzir a fala do usuário em texto. (2) O componente de entendimento de linguagem natural que produz uma representação semântica adequada para diálogos, normalmente utilizando gramáticas e ontologias. (3) O gerenciador de tarefa que escolhe os conceitos a serem expressos ao usuário. (4) O componente de geração de linguagem natural que define como expressar estes conceitos em palavras. (5) O gerenciador de diálogo controla a estrutura do diálogo. (6) O sintetizador de voz é responsável por traduzir a resposta do agente em fala. No entanto, não há consenso sobre os recursos necessários para desenvolver agentes conversacionais e a dificuldade envolvida nisso (especialmente em línguas com poucos recursos disponíveis). Este trabalho foca na influência dos componentes de linguagem natural (entendimento e gerência de diálogo) e analisa em especial o uso de sistemas de análise sintática (parser) como parte do desenvolvimento de agentes conversacionais com habilidades de linguagem mais flexível. Este trabalho analisa quais os recursos do analisador sintático contribuem para agentes conversacionais e aborda como os desenvolver, tendo como língua alvo o português (uma língua com poucos recursos disponíveis). Para isto, analisamos as abordagens de entendimento de linguagem natural e identificamos as abordagens de análise sintática que oferecem um bom desempenho. Baseados nesta análise, desenvolvemos um protótipo para avaliar o impacto do uso de analisador sintático em um agente conversacional. / Language is a mark of humanity and conscience, with the conversation (or dialogue) as one of the most fundamental manners of communication that we learn as children. Therefore one way to make a computer more attractive for interaction with users is through the use of natural language. Among the systems with some degree of language capabilities developed, the Eliza chatterbot is probably the first with a focus on dialogue. In order to make the interaction more interesting and useful to the user there are other approaches besides chatterbots, like conversational agents. These agents generally have, to some degree, properties like: a body (with cognitive states, including beliefs, desires and intentions or objectives); an interactive incorporation in the real or virtual world (including perception of events, communication, ability to manipulate the world and communicate with others); and behavior similar to a human (including affective abilities). This type of agents has been called by several terms, including animated agents or embedded conversational agents (ECA). A dialogue system has six basic components. (1) The speech recognition component is responsible for translating the user’s speech into text. (2) The Natural Language Understanding component produces a semantic representation suitable for dialogues, usually using grammars and ontologies. (3) The Task Manager chooses the concepts to be expressed to the user. (4) The Natural Language Generation component defines how to express these concepts in words. (5) The dialog manager controls the structure of the dialogue. (6) The synthesizer is responsible for translating the agents answer into speech. However, there is no consensus about the necessary resources for developing conversational agents and the difficulties involved (especially in resource-poor languages). This work focuses on the influence of natural language components (dialogue understander and manager) and analyses, in particular the use of parsing systems as part of developing conversational agents with more flexible language capabilities. This work analyses what kind of parsing resources contributes to conversational agents and discusses how to develop them targeting Portuguese, which is a resource-poor language. To do so we analyze approaches to the understanding of natural language, and identify parsing approaches that offer good performance, based on which we develop a prototype to evaluate the impact of using a parser in a conversational agent.

abstract: Text classification, in the artificial intelligence domain, is an activity in which text documents are automatically classified into predefined categories using machine learning techniques. An example of this is classifying uncategorized news articles into different predefined categories such as "Business", "Politics", "Education", "Technology" , etc. In this thesis, supervised machine learning approach is followed, in which a module is first trained with pre-classified training data and then class of test data is predicted. Good feature extraction is an important step in the machine learning approach and hence the main component of this text classifier is semantic triplet based features in addition to traditional features like standard keyword based features and statistical features based on shallow-parsing (such as density of POS tags and named entities). Triplet {Subject, Verb, Object} in a sentence is defined as a relation between subject and object, the relation being the predicate (verb). Triplet extraction process, is a 5 step process which takes input corpus as a web text document(s), each consisting of one or many paragraphs, from RSS feeds to lists of extremist website. Input corpus feeds into the "Pronoun Resolution" step, which uses an heuristic approach to identify the noun phrases referenced by the pronouns. The next step "SRL Parser" is a shallow semantic parser and converts the incoming pronoun resolved paragraphs into annotated predicate argument format. The output of SRL parser is processed by "Triplet Extractor" algorithm which forms the triplet in the form {Subject, Verb, Object}. Generalization and reduction of triplet features is the next step. Reduced feature representation reduces computing time, yields better discriminatory behavior and handles curse of dimensionality phenomena. For training and testing, a ten- fold cross validation approach is followed. In each round SVM classifier is trained with 90% of labeled (training) data and in the testing phase, classes of remaining 10% unlabeled (testing) data are predicted. Concluding, this paper proposes a model with semantic triplet based features for story classification. The effectiveness of the model is demonstrated against other traditional features used in the literature for text classification tasks. / Dissertation/Thesis / M.S. Computer Science 2013

The field of Human Computer Interaction (HCI) has suggested various methods for evaluating systems in order to improve their usability and User eXperience (UX). The advent of Web 2.0 has allowed the development of applications marked by collaboration, communication and interaction among their users in a way and on a scale never seen before. Social Systems (SS) (e.g. Twitter, Facebook, MySpace, LinkedIn etc.) are examples of such applications and have features such as: frequent exchange of messages, spontaneity and expression of feelings. The opportunities and challenges posed by these types of applications require the traditional evaluation methods to be reassessed, taking into consideration these new characteristics. For instance, the postings of users on SS reveal their opinions on various issues, including on what they think of the system. This work aims to test the hypothesis that the postings of users in SS provide relevant data for evaluation of the usability and of UX in SS. While researching through literature, we have not identified any evaluation model intending to collect and interpret texts from users in order to assess the user experience and system usability. Thus, this thesis proposes MALTU - Model for evaluation of interaction in social systems from the Users Textual Language. In order to provide a basis for the development of the proposed model, we conducted a study of how users express their opinions on the system in natural language. We extracted postings of users from four SS of different contexts. HCI experts classified, studied and processed such postings by using Natural Language Processing (PLN) techniques and data mining, and then analyzed them in order to obtain a generic model. The MALTU was applied in two SS: an entertainment and an educational SS. The results show that is possible to evaluate a system from the postings of users in SS. Such assessments are aided by extraction patterns related to the use, to the types of postings and to HCI factors used in system. / A Ãrea de InteraÃÃo Humano-Computador (IHC) tem sugerido muitas formas para avaliar sistemas a fim de melhorar sua usabilidade e a eXperiÃncia do UsuÃrio (UX). O surgimento da web 2.0 permitiu o desenvolvimento de aplicaÃÃes marcadas pela colaboraÃÃo, comunicaÃÃo e interatividade entre seus usuÃrios de uma forma e em uma escala nunca antes observadas. Sistemas Sociais (SS) (e.g., Twitter, Facebook, MySpace, LinkedIn etc.) sÃo exemplos dessas aplicaÃÃes e possuem caracterÃsticas como: frequente troca de mensagens e expressÃo de sentimentos de forma espontÃnea. As oportunidades e os desafios trazidos por esses tipos de aplicaÃÃes exigem que os mÃtodos tradicionais de avaliaÃÃo sejam repensados, considerando essas novas caracterÃsticas. Por exemplo, as postagens dos usuÃrios em SS revelam suas opiniÃes sobre diversos assuntos, inclusive sobre o que eles pensam do sistema em uso. Esta tese procura testar a hipÃtese de que as postagens dos usuÃrios em SS fornecem dados relevantes para avaliaÃÃo da Usabilidade e da UX (UUX) em SS. Durante as pesquisas realizadas na literatura, nÃo foi identificado nenhum modelo de avaliaÃÃo que tenha direcionado seu foco na coleta e anÃlise das postagens dos usuÃrios a fim de avaliar a UUX de um sistema em uso. Sendo assim, este estudo propÃe o MALTU â Modelo para AvaliaÃÃo da interaÃÃo em sistemas sociais a partir da Linguagem Textual do UsuÃrio. A fim de fornecer bases para o desenvolvimento do modelo proposto, foram realizados estudos de como os usuÃrios expressam suas opiniÃes sobre o sistema em lÃngua natural. Foram extraÃdas postagens de usuÃrios de quatro SS de contextos distintos. Tais postagens foram classificadas por especialistas de IHC, estudadas e processadas utilizando tÃcnicas de Processamento da Linguagem Natural (PLN) e mineraÃÃo de dados e, analisadas a fim da obtenÃÃo de um modelo genÃrico. O MALTU foi aplicado em dois SS: um de entretenimento e um SS educativo. Os resultados mostram que à possÃvel avaliar um sistema a partir das postagens dos usuÃrios em SS. Tais avaliaÃÃes sÃo auxiliadas por padrÃes de extraÃÃo relacionados ao uso, aos tipos de postagens e Ãs metas de IHC utilizadas na avaliaÃÃo do sistema.

Submitted by Geandra Rodrigues (geandrar@gmail.com) on 2018-01-29T16:52:29Z No. of bitstreams: 0 / Rejected by Adriana Oliveira (adriana.oliveira@ufjf.edu.br), reason: on 2018-01-30T14:50:12Z (GMT) / Submitted by Geandra Rodrigues (geandrar@gmail.com) on 2018-01-30T16:08:06Z No. of bitstreams: 0 / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2018-03-21T19:26:08Z (GMT) No. of bitstreams: 0 / Made available in DSpace on 2018-03-21T19:26:08Z (GMT). No. of bitstreams: 0 Previous issue date: 2017-08-31 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Com o acúmulo de informações digitais armazenadas ao longo do tempo, alguns esforços precisam ser aplicados para facilitar a busca e indexação de conteúdos. Recursos como vídeos e áudios, por sua vez, são mais difíceis de serem tratados por mecanismos de busca. A anotação de vídeos é uma forma considerável de resumo do vídeo, busca e classificação. A parcela de vídeos que possui anotações atribuídas pelo próprio autor na maioria das vezes é muito pequena e pouco significativa, e anotar vídeos manualmente é bastante trabalhoso quando trata-se de bases legadas. Por esse motivo, automatizar esse processo tem sido desejado no campo da Recuperação de Informação. Em repositórios de videoaulas, onde a maior parte da informação se concentra na fala do professor, esse processo pode ser realizado através de anotações automáticas de transcritos gerados por sistemas de Reconhecimento Automático de Fala. Contudo, essa técnica produz textos ruidosos, dificultando a tarefa de anotação semântica automática. Entre muitas técnicas de Processamento de Linguagem de Natural utilizadas para anotação, não é trivial a escolha da técnica mais adequada a um determinado cenário, principalmente quando trata-se de anotar textos com ruídos. Essa pesquisa propõe analisar um conjunto de diferentes técnicas utilizadas para anotação automática e verificar o seu impacto em um mesmo cenário, o cenário de similaridade entre vídeos. / With the accumulation of digital information stored over time, some efforts need to be applied to facilitate search and indexing of content. Resources such as videos and audios, in turn, are more difficult to handle with by search engines. Video annotation is a considerable form of video summary, search and classification. The share of videos that have annotations attributed by the author most often is very small and not very significant, and annotating videos manually is very laborious when dealing with legacy bases. For this reason, automating this process has been desired in the field of Information Retrieval. In video lecture repositories, where most of the information is focused on the teacher’s speech, this process can be performed through automatic annotations of transcripts gene-rated by Automatic Speech Recognition systems. However, this technique produces noisy texts, making the task of automatic semantic annotation difficult. Among many Natural Language Processing techniques used for annotation, it is not trivial to choose the most appropriate technique for a given scenario, especially when writing annotated texts. This research proposes to analyze a set of different techniques used for automatic annotation and verify their impact in the same scenario, the scenario of similarity between videos.

Submitted by Cláudia Bueno (claudiamoura18@gmail.com) on 2015-10-21T20:58:05Z No. of bitstreams: 2 Dissertação - Norton Coelho Guimarães - 2015.pdf: 2090183 bytes, checksum: 2d7f73048d14bf0ac9fbbe295972b668 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-10-22T12:22:39Z (GMT) No. of bitstreams: 2 Dissertação - Norton Coelho Guimarães - 2015.pdf: 2090183 bytes, checksum: 2d7f73048d14bf0ac9fbbe295972b668 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-10-22T12:22:39Z (GMT). No. of bitstreams: 2 Dissertação - Norton Coelho Guimarães - 2015.pdf: 2090183 bytes, checksum: 2d7f73048d14bf0ac9fbbe295972b668 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-04-22 / The research on ontology learning has been carried out in various areas of knowledge. Semi-automatic or automatic extraction of ontologies would assist in the acceleration of knowledge structuring of multiple domains. Semi-automatic approaches to ontology learning from texts are proposed in several scientific papers, mostly with the support of natural language processing techniques. This paper describes the construction of a computational framework for semi-automated ontology learning from texts in the Portuguese language. Axioms are not dealt with in this paper. The work done here originated from the proposal of Philipp Cimiano [18], along with mechanisms for standardization of texts, Natural Language Processing, identification of taxonomic relationships and structure of ontologies. This research resulted in the development of a set of classes concrete and a set of abstract classes that comprise a computational framework. In this work we also present a case study in the field public safety, proving the benefits of computational framework. / As pesquisas sobre aprendizagem de ontologias têm sido realizadas em várias áreas do conhecimento. A extração semi-automática ou automática de ontologias auxiliaria na aceleração da estruturação do conhecimento de diversos domínios. Abordagens semiautomáticas para a aprendizagem de ontologias a partir de textos são propostas em diversos trabalhos científicos, em sua maioria, com o apoio de técnicas de processamento da língua natural. Este trabalho descreve a construção de um arcabouço computacional para aprendizagem semi-automatizada de ontologias a partir de textos na língua portuguesa. Axiomas não são tratados neste trabalho. O trabalho desenvolvido aqui originouse da proposta de Philipp Cimiano [18], juntamente com mecanismos de padronização de textos, processamento de linguagem natural, identificação de relações taxonômicas e estruturação de ontologias. Esta pesquisa resultou no desenvolvimento de um conjunto de classes, concretas e abstratas, que compõem um arcabouço computacional. Neste trabalho, também foi feito um estudo de caso no domínio de segurança pública, comprovando os benefícios do arcabouço computacional.

Este trabalho apresenta um estudo sobre a utilização de dispositivos adaptativos para realizar tradução texto-voz. O foco do trabalho é a criação de um método para a tradução grafema-fonema para a língua portuguesa baseado em autômatos adaptativos e seu uso em um software de tradução texto-voz. O método apresentado busca mimetizar o comportamento humano no tratamento de regras de tonicidade, separação de sílabas e as influências que as sílabas exercem sobre suas vizinhas. Essa característica torna o método facilmente utilizável para outras variações da língua portuguesa, considerando que essas características são invariantes em relação à localidade e a época da variedade escolhida. A variação contemporânea da língua falada na cidade de São Paulo foi escolhida como alvo de análise e testes neste trabalho. Para essa variação, o modelo apresenta resultados satisfatórios superando 95% de acerto na tradução grafema-fonema de palavras, chegando a 90% de acerto levando em consideração a resolução de dúvidas geradas por palavras que podem possuir duas representações sonoras e gerando uma saída sonora inteligível aos nativos da língua por meio da síntese por concatenação baseada em sílabas. Como resultado do trabalho, além do modelo para tradução grafema-fonema de palavras baseado em autômatos adaptativos, foi criado um método para escolha da representação fonética correta em caso de ambigüidade e foram criados dois softwares, um para simulação de autômatos adaptativos e outro para a tradução grafema-fonema de palavras utilizando o modelo de tradução criado e o método de escolha da representação correta. Esse último software foi unificado ao sintetizador desenvolvido por Koike et al. (2007) para a criação de um tradutor texto-voz para a língua portuguesa. O trabalho mostra a viabilidade da utilização de autômatos adaptativos como base ou como um elemento auxiliar para o processo de tradução texto-voz na língua portuguesa. / This work presents a study on the use of adaptive devices for text-to-speech translation. The work focuses on the development of a grapheme-phoneme translation method for Portuguese based on Adaptive Automata and the use of this method in a text-to-speech translation software. The presented method resembles human behavior when handling syllable separation rules, syllable stress definition and influences syllables have on each other. This feature makes the method easy to use with different variations of Portuguese, since these characteristics are invariants of the language. Portuguese spoken nowadays in São Paulo, Brazil has been chosen as the target for analysis and tests in this work. The method has good results for such variation of Portuguese, reaching 95% accuracy rate for grapheme-phoneme translation, clearing the 90% mark after resolution of ambiguous cases in which different representations are accepted for a grapheme and generating phonetic output intelligible for native speakers based on concatenation synthesis using syllables as concatenation units. As final results of this work, a model is presented for grapheme-phoneme translation for Portuguese words based on Adaptive Automata, a methodology to choose the correct phonetic representation for the grapheme in ambiguous cases, a software for Adaptive Automata simulation and a software for grapheme-phoneme translation of texts using both the model of translation and methodology for disambiguation. The latter software was unified with the speech synthesizer developed by Koike et al. (2007) to create a text-to-speech translator for Portuguese. This work evidences the feasibility of text-to-speech translation for Portuguese using Adaptive Automata as the main instrument for such task.

Made available in DSpace on 2016-08-17T14:53:16Z (GMT). No. of bitstreams: 1 Jone dos Santos Sodre Correa.pdf: 2272440 bytes, checksum: e8708cabafde69a2eb7580860867bc89 (MD5) Previous issue date: 2011-05-06 / Ontologies are an approach for knowledge representation capable of expressing a set of entities and their relationships, constraints, axioms and vocabulary of a given domain. Manual construction of ontologies by domain experts and knowledge engineers is an expensive and time consuming task so, automatic and/or semi-automatic approaches are needed. Ontology Learning looks for automatically or semi-automatically identifying ontology elements like classes, taxonomic and non-taxonomic relationships, properties and axioms from textual resources. This work proposes a process for automatic learning of ontologies from text focusing on the application of natural language processing techniques to acquire taxonomic relationships. Some experiments using a legal corpus were conducted in order to evaluate it. Initial results are promising. / Ontologias são uma forma de representação de conhecimento capaz de expressar um conjunto de entidades e suas relações, restrições, axiomas e vocabulário de um determinado domínio. A construção manual de ontologias por especialistas de domínio e engenheiros de conhecimento é uma tarefa cara e demorada e a automatização/semi-automatização desta tarefa é uma necessidade. O aprendizado de ontologias visa automatizar ou semi-automatizar a identificação de elementos de uma ontologia como classes, relações taxonômicas e não-taxonômicas, propriedades e axiomas de fontes textuais. Este trabalho propõe um processo de aprendizagem automática de ontologias a partir de fontes textuais enfocando a aplicação de técnicas de processamento de linguagem natural para adquirir relações taxonômicas. Alguns experimentos utilizando um corpus jurídico foram realizados para a avaliação da abordagem proposta. Os resultados iniciais são promissores.

Made available in DSpace on 2016-08-17T16:54:32Z (GMT). No. of bitstreams: 1 Tese Carla.pdf: 23507425 bytes, checksum: b08fca6c8eacdc0fd5d075a385f235e5 (MD5) Previous issue date: 2013-06-05 / Knowledge systems are a suitable computational approach to solve complex problems and to provide decision support. Ontologies are an approach for knowledge representation about an application domain, allowing the semantic processing of information and, through more precise interpretation of information, turning systems more effective and usable. Ontology Population looks for instantiating the constituent elements of an ontology, like properties and non-taxonomic relationships. Manual population by domain experts and knowledge engineers is an expensive and time consuming task. Fast ontology population is critical for the success of knowledge-based applications. Thus, automatic or semi-automatic approaches are needed. This work proposes a generic process for Automatic Ontology Population by specifying its phases and the techniques used to perform the activities on each phase. It also proposes a domain-independent process for automatic population of ontologies (DIAOPPro) from text that applies natural language processing and information extraction techniques to acquire and classify ontology instances. This is a new approach for automatic ontology population that uses an ontology to automatically generate rules to extract instances from text and classify them in ontology classes. These rules can be generated from ontologies of any domain, making the proposed process domain independent. To evaluate DIAOP-Pro four case studies were conducted to demonstrate its effectiveness and feasibility. In the first one we evaluated the effectiveness of phase "Identification of Candidate instances" comparing the results obtained by applying statistical techniques with those of purely linguistic techniques. In the second experiment we evaluated the feasibility of the phase "Construction of a Classifier", through the automatic generation of a classifier. The last two experiments evaluated the effectiveness of DIAOP-Pro into two distinct domains: the legal and the tourism domains. The results indicate that our approach can extract and classify instances with high effectiveness with the additional advantage of domain independence. / A demanda por sistemas baseado em conhecimento é crescente considerando suas aptidões para a solução de problemas complexos e para a tomada de decisão. As ontologias são formalismos para a representação de conhecimento de um dado domínio, que permitem o processamento semântico das informações e, através de interpretações mais precisas das informações, os sistemas apresentam maior efetividade e usabilidade. O povoamento de ontologias visa a instanciação de propriedades e relacionamentos não taxonômicos de classes de ontologias. Entretanto, o povoamento manual de ontologias por especialistas de domínio e engenheiros do conhecimemto é uma tarefa cara e que consome muito tempo. O povoamento de ontologias rápido e com baixo custo é crucial para o sucesso de aplicações baseadas em conhecimento. Portanto, torna-se fundamental uma semi-automatização ou automatização desse processo. Esta tese propõe um processo genérico para o problema do Povoamento Automático de Ontologias, especificando suas fases e técnicas que podem ser aplicadas em cada uma delas. É também proposto um Processo Independente de Domínio para o Povoamento Automático de Ontologias (DIAOP-Pro) a partir de fontes textuais, que aplica técnicas de processamento da linguagem natural e extração de informação para adquirir e classificar instâncias de ontologias. O DIAOP-Pro se constitui em uma abordagem original uma vez que propõe o povoamento automático de ontologias utilizando uma ontologia para a geração automática de regras para extrair instâncias a partir de textos e classifica-as como instâncias de classes da ontologia. Estas regras podem ser geradas a partir de ontologias específicas de qualquer domínio, tornando o processo independente de domínio. Para avaliar o processo DIAOP-Pro foram conduzidos quatro estudos de caso de modo a demonstrar a sua efetividade e viabilidade. O primeiro estudo de caso foi realizado para avaliar a efetividade da fase Identificação de Instâncias Candidatas , no qual foram comparados os resultados obtidos com a aplicação de técnicas estatísticas e de técnicas puramente lingüísticas. O segundo estudo de caso foi realizado para avaliar a viabiliadade da fase Construção de um Classificador , através da experimentação com a geração automática do classificador. O terceiro e o quarto estudo de caso foram realizados para avaliar a efetividade do processo proposto em dois domínios distintos, o jurídico e o turístico. Os resultados indicam que o processo DIAOP-Pro povoa ontologias específicas de qualquer domínio com boa efetividade e com a vantagem adicional da independência do domínio.

Orientador: Jacques Wainer / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:42:33Z (GMT). No. of bitstreams: 1 Passos_AlexandreTachard_D.pdf: 2615030 bytes, checksum: 93841a46120b968f6da6c9aea28953b7 (MD5) Previous issue date: 2013 / Resumo: Em processamento de linguagem natural, e em aprendizado de máquina em geral, é comum o uso de modelos gráficos probabilísticos (probabilistic graphical models). Embora estes modelos sejam muito convenientes, possibilitando a expressão de relações complexas entre várias variáveis que se deseja prever dado uma sentença ou um documento, algoritmos comuns de aprendizado e de previsão utilizando estes modelos são frequentemente ineficientes. Por isso têm-se explorado recentemente o uso de relaxações usando programação linear deste problema de inferência. Esta tese apresenta duas contribuições para a teoria e prática de relaxações de programação linear para inferência em modelos probabilísticos gráficos. Primeiro, apresentamos um novo algoritmo, baseado na técnica de geração de colunas (dual à técnica dos planos de corte) que acelera a execução do algoritmo de Viterbi, a técnica mais utilizada para inferência em modelos lineares. O algoritmo apresentado também se aplica em modelos que são árvores e em hipergrafos. Em segundo mostramos uma nova relaxação linear para o problema de inferência conjunta, quando se quer acoplar vários modelos, em cada qual inferência é eficiente, mas em cuja junção inferência é NP-completa. Esta tese propõe uma extensão à técnica de decomposição dual (dual decomposition) que permite além de juntar vários modelos a adição de fatores que tocam mais de um submodelo eficientemente / Abstract: In natural language processing, and in general machine learning, probabilistic graphical models (and more generally structured linear models) are commonly used. Although these models are convenient, allowing the expression of complex relationships between many random variables one wants to predict given a document or sentence, most learning and prediction algorithms for general models are inefficient. Hence there has recently been interest in using linear programming relaxations for the inference tasks necessary when learning or applying these models. This thesis presents two contributions to the theory and practice of linear programming relaxations for inference in structured linear models. First we present a new algorithm, based on column generation (a technique which is dual to the cutting planes method) to accelerate the Viterbi algorithm, the most popular exact inference technique for linear-chain graphical models. The method is also applicable to tree graphical models and hypergraph models. Then we present a new linear programming relaxation for the problem of joint inference, when one has many submodels and wants to predict using all of them at once. In general joint inference is NP-complete, but algorithms based on dual decomposition have proven to be efficiently applicable for the case when the joint model can be expressed as many separate models plus linear equality constraints. This thesis proposes an extension to dual decomposition which allows also the presence of factors which score parts that belong in different submodels, improving the expressivity of dual decomposition at no extra computational cost / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

This master thesis treats about Event Recognition in the reports of Polish stockholders. Event Recognition is one of the Information Extraction tasks. This thesis provides a comparison of two approaches to Event Recognition: manual and automatic. In the manual approach regular expressions are used. Regular expressions are used as a baseline for the automatic approach. In the automatic approach three Machine Learning methods were applied. In the initial experiment the Decision Trees, naive Bayes and Memory Based Learning methods are compared. A modification of the standard Memory Based Learning method is presented which goal is to create a classifier that uses only positives examples in the classification task. The performance of the modified Memory Based Learning method is presented and compared to the baseline and also to other Machine Learning methods. In the initial experiment one type of annotation is used and it is the meeting date annotation. The final experiment is conducted using three types of annotations: the meeting time, the meeting date and the meeting place annotation. The experiments show that the classification can be performed using only one class of instances with the same level of performance. / (+48)669808616