Submitted by Livia Mello (liviacmello@yahoo.com.br) on 2016-09-30T19:20:49Z No. of bitstreams: 1 DissACIZ.pdf: 2734710 bytes, checksum: bf061fead4f2a8becfcbedc457a68b25 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T16:19:10Z (GMT) No. of bitstreams: 1 DissACIZ.pdf: 2734710 bytes, checksum: bf061fead4f2a8becfcbedc457a68b25 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-20T16:19:17Z (GMT) No. of bitstreams: 1 DissACIZ.pdf: 2734710 bytes, checksum: bf061fead4f2a8becfcbedc457a68b25 (MD5) / Made available in DSpace on 2016-10-20T16:19:25Z (GMT). No. of bitstreams: 1 DissACIZ.pdf: 2734710 bytes, checksum: bf061fead4f2a8becfcbedc457a68b25 (MD5) Previous issue date: 2016-03-29 / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / The Automatic Multi-Document Summarization (MDS) aims at creating a single summary, coherent and cohesive, from a collection of different sources texts, on the same topic. The creation of these summaries, in general extracts (informative and generic), requires the selection of the most important sentences from the collection. Therefore, one may use superficial linguistic knowledge (or statistic) or deep knowledge. It is important to note that deep methods, although more expensive and less robust, produce more informative extracts and with more linguistic quality. For the Portuguese language, the sole deep methods that use lexical-conceptual knowledge are based on the frequency of the occurrence of the concepts in the collection for the selection of a content. Considering the potential for application of semantic-conceptual knowledge, the proposition is to investigate MDS methods that start with representation of lexical concepts of source texts in a hierarchy for further exploration of certain hierarchical properties able to distinguish the most relevant concepts (in other words, the topics from a collection of texts) from the others. Specifically, 3 out of 50 CSTNews (multi-document corpus of Portuguese reference) collections were selected and the names that have occurred in the source texts of each collection were manually indexed to the concepts of the WordNet from Princenton (WN.Pr), engendering at the end, an hierarchy with the concepts derived from the collection and other concepts inherited from the WN.PR for the construction of the hierarchy. The hierarchy concepts were characterized in 5 graph metrics (of relevancy) potentially relevant to identify the concepts that compose a summary: Centrality, Simple Frequency, Cumulative Frequency, Closeness and Level. Said characterization was analyzed manually and by machine learning algorithms (ML) with the purpose of verifying the most suitable measures to identify the relevant concepts of the collection. As a result, the measure Centrality was disregarded and the other ones were used to propose content selection methods to MDS. Specifically, 2 sentences selection methods were selected which make up the extractive methods: (i) CFSumm whose content selection is exclusively based on the metric Simple Frequency, and (ii) LCHSumm whose selection is based on rules learned by machine learning algorithms from the use of all 4 relevant measures as attributes. These methods were intrinsically evaluated concerning the informativeness, by means of the package of measures called ROUGE, and the evaluation of linguistic quality was based on the criteria from the TAC conference. Therefore, the 6 human abstracts available in each CSTNews collection were used. Furthermore, the summaries generated by the proposed methods were compared to the extracts generated by the GistSumm summarizer, taken as baseline. The two methods got satisfactory results when compared to the GistSumm baseline and the CFSumm method stands out upon the LCHSumm method. / Na Sumarização Automática Multidocumento (SAM), busca-se gerar um único sumário, coerente e coeso, a partir de uma coleção de textos, de diferentes fontes, que tratam de um mesmo assunto. A geração de tais sumários, comumente extratos (informativos e genéricos), requer a seleção das sentenças mais importantes da coleção. Para tanto, pode-se empregar conhecimento linguístico superficial (ou estatística) ou conhecimento profundo. Quanto aos métodos profundos, destaca-se que estes, apesar de mais caros e menos robustos, produzem extratos mais informativos e com mais qualidade linguística. Para o português, os únicos métodos profundos que utilizam conhecimento léxico-conceitual baseiam na frequência de ocorrência dos conceitos na coleção para a seleção de conteúdo. Tendo em vista o potencial de aplicação do conhecimento semântico-conceitual, propôs-se investigar métodos de SAM que partem da representação dos conceitos lexicais dos textos-fonte em uma hierarquia para a posterior exploração de certas propriedades hierárquicas capazes de distinguir os conceitos mais relevantes (ou seja, os tópicos da coleção) dos demais. Especificamente, selecionaram-se 3 das 50 coleções do CSTNews, corpus multidocumento de referência do português, e os nomes que ocorrem nos textos-fonte de cada coleção foram manualmente indexados aos conceitos da WordNet de Princeton (WN.Pr), gerando, ao final, uma hierarquia com os conceitos constitutivos da coleção e demais conceitos herdados da WN.Pr para a construção da hierarquia. Os conceitos da hierarquia foram caracterizados em função de 5 métricas (de relevância) de grafo potencialmente pertinentes para a identificação dos conceitos a comporem um sumário: Centrality, Simple Frequency, Cumulative Frequency, Closeness e Level. Tal caracterização foi analisada de forma manual e por meio de algoritmos de Aprendizado de Máquina (AM) com o objetivo de verificar quais medidas seriam as mais adequadas para identificar os conceitos relevantes da coleção. Como resultado, a medida Centrality foi descartada e as demais utilizadas para propor métodos de seleção de conteúdo para a SAM. Especificamente, propuseram-se 2 métodos de seleção de sentenças, os quais compõem os métodos extrativos: (i) CFSumm, cuja seleção de conteúdo se baseia exclusivamente na métrica Simple Frequency, e (ii) LCHSumm, cuja seleção se baseia em regras aprendidas por algoritmos de AM a partir da utilização em conjunto das 4 medidas relevantes como atributos. Tais métodos foram avaliados intrinsecamente quanto à informatividade, por meio do pacote de medidas ROUGE, e qualidade linguística, com base nos critérios da conferência TAC. Para tanto, utilizaram-se os 6 abstracts humanos disponíveis em cada coleção do CSTNews. Ademais, os sumários gerados pelos métodos propostos foram comparados aos extratos gerados pelo sumarizador GistSumm, tido como baseline. Os dois métodos obtiveram resultados satisfatórios quando comparados ao baseline GistSumm e o método CFSumm se sobressai ao método LCHSumm. / FAPESP 2014/12817-4

Orientador: Jacques Wainer / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-16T05:40:57Z (GMT). No. of bitstreams: 1 Billa_CleoZanella_D.pdf: 3316703 bytes, checksum: 82c6b703f196ad4980b583703c56be1f (MD5) Previous issue date: 2009 / Resumo: Atualmente, o uso da computação na medicina vem crescendo cada vez mais, e um dos temas mais discutidos é o prontuário clínico eletrônico. é consenso que a utilização de um prontuário eletrônico pode facilitar o trabalho do profissional de saúde e melhorar ainda mais a qualidade do cuidado em saúde, porém ainda existe muita discussão sobre como ele deve ser e quais ferramentas deve oferecer. Este trabalho propõe duas novas formas de visualização do prontuário. A primeira é um sumário com as informações mais relevantes do paciente. A segunda é a representação dos dados do paciente através de um diagrama, onde o profissional de saúde pode expressar o design rationale (DR) da consulta. A área de sumarização automática é um problema altamente complexo, e apesar de terem sido usados procedimentos muito simples, o experimento realizado mostrou que o processo foi suficiente para construir um sumário com o mínimo de informações necessárias para que o quadro clínico do paciente pudesse ser entendido. Alguns estudos apontam que a falta de informação sobre o processo de diagnóstico e sobre o planejamento do tratamento é uma das principais falhas de um sistema de prontuário eletrônico. Por isso, foi sugerida uma representação que utiliza diagramas para armazenar e visualizar, além dos dados do paciente, o raciocínio do profissional de saúde durante uma consulta. Essa técnica é conhecida como design rationale, e é usada, principalmente, na área de engenharia de software. Além de propor essas duas novas formas de visualização do prontuário clínico, foi realizado um experimento formal com o objetivo de testar o sumário e o diagrama com DR na prática. O experimento ocorreu em um ambulatório de clínica geral da Unifesp, onde alunos do curso de medicina recebiam o sumário, ou o diagrama com DR, ou o prontuário clínico tradicional e respondiam questões sobre um determinado caso. Os resultados do experimento mostram que o sumário continha informações suficientes para avaliar o quadro clínico do paciente; porém, eles também mostram que o diagrama com DR provavelmente não apresentou nenhuma vantagem em relação ao prontuário tradicional / Abstract: Collaboration between computer science and medicine is growing day by day, and one of the most controversial topics is the electronic patient record (EPR). Despite all scientists agree that the EPR can improve health care quality, how it should behave, or what tools it should provide are still open questions. This work suggests two ways to visualize the EPR. The first is through a summary, with the most important information of the patient. And, the second, is a diagram where the physician is able to express his design rationale. Summarization is a complex problem, and despite very simple procedures were used, the experimental evaluation shows that the summary contains as much information as the traditional EPR. The idea of diagrams to visualize the EPR was originated in a technique called design rationale (DR), used, mostly, in Software Engineering. Its major goal is to reproduce the rationale during a project design. Some researches pointed out that one of the major limitations of EPR is the lack of information about diagnosis processes, and treatment planning. To evaluate these new ways of visualization of the EPR, an experimental evaluation was performed to test the summary and the diagram in real practice. The experiment was conduct in a outpatient care clinic at Unifesp, where medical students use the summary, or the diagram, or the traditional EPR to answer questions about specific patients. The results of the experiment show that the summary was equivalent to the traditional EPR, and that the diagram no not show any leverage to the traditional EPR / Doutorado / Informática Médica / Doutor em Ciência da Computação

Les fiches de synthèse multi-documents sont considérées comme une représentation textuelle organisée et structurée des segments textuels. La construction de ces fiches repose sur l’annotation sémantique des publications scientifiques suivant un ensemble de catégories discursives qu’on appelle des points de vue de fouille (comme les hypothèses plausibles, les résultats, ou les conclusions,…). L’annotation sémantique est réalisée automatiquement par la méthode de l’Exploration Contextuelle. Il s’agit d’une méthode linguistique computationnelle, implémentée par un moteur d’annotation sémantique, qui repose sur un ensemble de marqueurs linguistiques associés à des points de vue de fouille. Afin de pouvoir expérimenter la pertinence des résultats de notre système, nous avons procédé à l’évaluation des annotations automatiques sur des textes en biologie. La notion des spéculations (hypothèses plausibles), particulièrement décrite dans ce travail, a été évaluée sur le corpus BioScope annoté manuellement pour les spéculations et les négations. Nous proposons une application informatique qui permet aux utilisateurs d’obtenir des fiches de synthèse organisées suivant des critères sémantiques paramétrables par l’utilisateur. / Multi-documents thematic sheets are considered as an organized and structured textual representationof textual segments. The thematic sheets construction is based on the semantic annotation ofscientific publications according to a set of discursive categories called search view points (such asspeculation, results or conclusions, ?). The semantic annotation is performed automatically by theContextual Exploration process. It is a computational linguistic method based on a set of linguisticmarkers associated with search view points. This method is implemented by a semantic annotationengine. In order to evaluate the relevance of the results of our system, we used biological papers toevaluate the automatic annotation. The concept of speculation (plausible hypothesis), specificallydescribed in this work, was evaluated on the Bioscope corpus which is manually annotated forspeculation and negation. We propose an application that allows users to obtain thematic sheetsorganized according to semantic criteria configurable by the user.

A sumarização multidocumento consiste na tarefa de produzir automaticamente um único sumário a partir de um conjunto de textos derivados de um mesmo assunto. É imprescindível que seja feito o tratamento de fenômenos que ocorrem neste cenário, tais como: (i) a redundância, a complementaridade e a contradição de informações; (ii) a uniformização de estilos de escrita; (iii) tratamento de expressões referenciais; (iv) a manutenção de focos e perspectivas diferentes nos textos; (v) e a ordenação temporal das informações no sumário. O tratamento de tais fenômenos contribui significativamente para que seja produzido ao final um sumário informativo e coerente, características difíceis de serem garantidas ainda que por um humano. Um tipo particular de coerência estudado nesta tese é a coerência local, a qual é definida por meio de relações entre enunciados (unidades menores) em uma sequência de sentenças, de modo a garantir que os relacionamentos contribuirão para a construção do sentido do texto em sua totalidade. Partindo do pressuposto de que o uso de conhecimento discursivo pode melhorar a avaliação da coerência local, o presente trabalho propõe-se a investigar o uso de relações discursivas para elaborar modelos de coerência local, os quais são capazes de distinguir automaticamente sumários coerentes dos incoerentes. Além disso, um estudo sobre os erros que afetam a Qualidade Linguística dos sumários foi realizado com o propósito de verificar quais são os erros que afetam a coerência local dos sumários, se os modelos de coerência podem identificar tais erros e se há alguma relação entre os modelos de coerência e a informatividade dos sumários. Para a realização desta pesquisa foi necessário fazer o uso das informações semântico-discursivas dos modelos CST (Cross-document Structure Theory) e RST (Rhetorical Structure Theory) anotadas no córpus, de ferramentas automáticas, como o parser Palavras e de algoritmos que extraíram informações do córpus. Os resultados mostraram que o uso de informações semântico-discursivas foi bem sucedido na distinção dos sumários coerentes dos incoerentes e que os modelos de coerência implementados nesta tese podem ser usados na identificação de erros da qualidade linguística que afetam a coerência local. / Multi-document summarization is the task of automatically producing a single summary from a collection of texts derived from the same subject. It is essential to treat many phenomena, such as: (i) redundancy, complementarity and contradiction of information; (ii) writing styles standardization; (iii) treatment of referential expressions; (iv) text focus and different perspectives; (v) and temporal ordering of information in the summary. The treatment of these phenomena contributes to the informativeness and coherence of the final summary. A particular type of coherence studied in this thesis is the local coherence, which is defined by the relationship between statements (smallest units) in a sequence of sentences. The local coherence contributes to the construction of textual meaning in its totality. Assuming that the use of discursive knowledge can improve the evaluation of the local coherence, this thesis proposes to investigate the use of discursive relations to develop local coherence models, which are able to automatically distinguish coherent summaries from incoherent ones. In addition, a study on the errors that affect the Linguistic Quality of the summaries was conducted in order to verify what are the errors that affect the local coherence of summaries, as well as if the coherence models can identify such errors, and whether there is any relationship between coherence models and informativenessof summaries. For thisresearch, it wasnecessary theuseof semantic-discursive information of CST models (Cross-document Structure Theory) and RST (Rhetorical Structure Theory) annoted in the corpora, automatic tools, parser as Palavras, and algorithms that extract information from the corpus. The results showed that the use of semantic-discursive information was successful on the distinction between coherent and incoherent summaries, and that the information about coherence can be used in error detection of linguistic quality that affect the local coherence.

Due to the increasing amount and complexity of the data stored in the enterprises\' databases, the task of knowledge discovery is nowadays vital to support strategic decisions. However, the mining techniques used in the process usually have high computational costs that come from the need to explore several alternative solutions, in different combinations, to obtain the desired knowledge. The most common mining tasks include data classification, labeling and clustering, outlier detection and missing data prediction. Traditionally, the data are represented by numerical or categorical attributes in a table that describes one element in each tuple. Although the same tasks applied to traditional data are also necessary for more complex data, such as images, graphs, audio and long texts, the complexity and the computational costs associated to handling large amounts of these complex data increase considerably, making most of the existing techniques impractical. Therefore, especial data mining techniques for this kind of data need to be developed. This Ph.D. work focuses on the development of new data mining techniques for large sets of complex data, especially for the task of clustering, tightly associated to other data mining tasks that are performed together. Specifically, this Doctoral dissertation presents three novel, fast and scalable data mining algorithms well-suited to analyze large sets of complex data: the method Halite for correlation clustering; the method BoW for clustering Terabyte-scale datasets; and the method QMAS for labeling and summarization. Our algorithms were evaluated on real, very large datasets with up to billions of complex elements, and they always presented highly accurate results, being at least one order of magnitude faster than the fastest related works in almost all cases. The real data used come from the following applications: automatic breast cancer diagnosis, satellite imagery analysis, and graph mining on a large web graph crawled by Yahoo! and also on the graph with all users and their connections from the Twitter social network. Such results indicate that our algorithms allow the development of real time applications that, potentially, could not be developed without this Ph.D. work, like a software to aid on the fly the diagnosis process in a worldwide Healthcare Information System, or a system to look for deforestation within the Amazon Rainforest in real time / O crescimento em quantidade e complexidade dos dados armazenados nas organizações torna a extração de conhecimento utilizando técnicas de mineração uma tarefa ao mesmo tempo fundamental para aproveitar bem esses dados na tomada de decisões estratégicas e de alto custo computacional. O custo vem da necessidade de se explorar uma grande quantidade de casos de estudo, em diferentes combinações, para se obter o conhecimento desejado. Tradicionalmente, os dados a explorar são representados como atributos numéricos ou categóricos em uma tabela, que descreve em cada tupla um caso de teste do conjunto sob análise. Embora as mesmas tarefas desenvolvidas para dados tradicionais sejam também necessárias para dados mais complexos, como imagens, grafos, áudio e textos longos, a complexidade das análises e o custo computacional envolvidos aumentam significativamente, inviabilizando a maioria das técnicas de análise atuais quando aplicadas a grandes quantidades desses dados complexos. Assim, técnicas de mineração especiais devem ser desenvolvidas. Este Trabalho de Doutorado visa a criação de novas técnicas de mineração para grandes bases de dados complexos. Especificamente, foram desenvolvidas duas novas técnicas de agrupamento e uma nova técnica de rotulação e sumarização que são rápidas, escaláveis e bem adequadas à análise de grandes bases de dados complexos. As técnicas propostas foram avaliadas para a análise de bases de dados reais, em escala de Terabytes de dados, contendo até bilhões de objetos complexos, e elas sempre apresentaram resultados de alta qualidade, sendo em quase todos os casos pelo menos uma ordem de magnitude mais rápidas do que os trabalhos relacionados mais eficientes. Os dados reais utilizados vêm das seguintes aplicações: diagnóstico automático de câncer de mama, análise de imagens de satélites, e mineração de grafos aplicada a um grande grafo da web coletado pelo Yahoo! e também a um grafo com todos os usuários da rede social Twitter e suas conexões. Tais resultados indicam que nossos algoritmos permitem a criação de aplicações em tempo real que, potencialmente, não poderiam ser desenvolvidas sem a existência deste Trabalho de Doutorado, como por exemplo, um sistema em escala global para o auxílio ao diagnóstico médico em tempo real, ou um sistema para a busca por áreas de desmatamento na Floresta Amazônica em tempo real

The amount surveillance footage recorded each day is too large for human operators to analyze. A video summary system to process and refine this video data would prove beneficial in many instances. This work defines the problem in terms of its inputs, outputs and sub-problems, identifies suitable techniques and existing works as well as describes a design of such system. The system is implemented, and the results are examined.

En los últimos años, el consumo de noticias en medios impresos ha sido sustituido en gran medida por el acceso a estas en variados formatos a través de medios digitales y redes sociales. Los bajos costes de acceso a la información y la profusión de las plataformas de comunicación y dispositivos móviles han producido un cambio en los hábitos de consumo de información, la que es recibida desde múltiples fuentes y replicada con inmediatez en un ambiente global. En este contexto, se ha incrementado la desinformación, un problema originado en los albores de la prensa tradicional. En la última década, la desinformación ha alcanzado una escala inmanejable debido al gran volumen de información al que un ciudadano común está expuesto cada día. A esto se suma que la mayoría de estos medios digitales no son arbitrados, y permiten publicar y compartir cualquier tipo de información. En este ambiente es muy probable la proliferación de información engañosa que, en la mayoría de los casos, pretende influir en la opinión pública para perseguir un objetivo económico, social o político subyacente. Esto puede perjudicar a las organizaciones, a las marcas y a las personas, entre otros, derivando en muchas ocasiones en conclusiones precipitadas por parte de los usuarios que la consumen. En este contexto surge el término de la posverdad como una tendencia a priorizar la subjetividad de una interpretación a la verificación de hechos reales. El titular de una noticia está diseñado para resumir sucintamente su contenido, proporcionando al lector una comprensión clara de la misma. Desafortunadamente, en la era de la posverdad, los titulares están más enfocados en atraer la atención del lector que en presentar con precisión el contenido de la noticia. Esto abre una enorme oportunidad para difundir desinformación con la construcción de titulares falsos o distorsionados. Las técnicas tradicionales de verificación de hechos realizadas por humanos son definitivamente impracticables y obsoletas ante la cantidad de textos informativos que se generan incluso cada hora. En este trabajo se abordan soluciones novedosas utilizando Tecnologías de Lenguaje Humano (TLH) y técnicas de Inteligencia Artificial (IA). Esta investigación se ha desarrollado en un área donde se intersecan confusamente diferentes conceptos, herramientas y aproximaciones. Se parte de una ubicación en el estado del arte acerca de las principales soluciones relacionadas con la detección de titulares engañosos, detección de posturas, detección de contradicciones, interrelación entre estos elementos y verificación automática de hechos. A partir del problema enunciado y sus conceptos, se profundiza en diferentes estrategias de solución con la aspiración de proponer una aproximación que permita, con un enfoque suficientemente práctico, aportar a la detección de información engañosa en medios digitales lo que puede convertirse en una herramienta de alerta en el complejo ambiente antes descrito. Entre los elementos considerados, se valora la utilización de ML y de DL como técnicas tradicionales de trabajo en el espacio de estas soluciones, así como sus alcances y limitaciones. Además, se introduce la idea de sustituir el contenido de una noticia por un resumen suficientemente esencial y obtenido de manera automática. La memoria presenta de manera lógica el curso de la investigación que parte de lo conceptual y utiliza el pensamiento deductivo y experimental para alcanzar generalizaciones y aplicarlas deductivamente a la solución de problemas específicos. Con ello, se abordan determinadas tareas que pueden contribuir parcialmente a la solución de parte del problema planteado, se diseñan experimentos y se especifica la solución en el ámbito del idioma español donde no se reportan aportaciones similares. Se propone una arquitectura flexible para la detección de titulares engañosos que ha permitido implementar sobre ella dos prototipos cuyos resultados experimentales y documentados suponen un paso de avance hacia la automatización de esta tarea. Esta arquitectura alcanza resultados notables al ser aplicada sobre dos conjuntos de datos en idioma inglés y español. Siguiendo los principios y las experiencias adquiridas se presenta una aplicación de una arquitectura similar para la detección de noticias falsas, lo que hace presumir su posible generalidad. / Esta tesis ha sido financiada por la Generalitat Valenciana a través del proyecto “SIIA: Tecnologías del lenguaje humano para una sociedad inclusiva, igualitaria, y accesible” (PROMETEU/2018/089); y por FEDER/Ministerio de Ciencia e Innovación - Agencia Estatal de Investigación a través del proyecto “LIVINGLANG: Modelado del comportamiento de entidades digitales mediante tecnologías del lenguaje humano” (RTI2018-094653-B-C21 / C22).

No description available.

In this thesis, we study the notion of graph summarization, which is a fundamental task of finding a compact representation of the original graph called the summary. Graph summarization can be used for reducing the footprint of the input graph, better visualization, anonymizing the identity of users, and query answering. There are two different frameworks of graph summarization we consider in this thesis, the utility-based framework and the correction set-based framework. In the utility-based framework, the input graph is summarized until a utility threshold is not violated. In the correction set-based framework a set of correction edges is produced along with the summary graph. In this thesis we propose two algorithms for the utility-based framework and one for the correction set-based framework. All these three algorithms are for static graphs (i.e. graphs that do not change over time). Then, we propose two more utility-based algorithms for fully dynamic graphs (i.e. graphs with edge insertions and deletions). Algorithms for graph summarization can be lossless (summarizing the input graph without losing any information) or lossy (losing some information about the input graph in order to summarize it more). Some of our algorithms are lossless and some lossy, but with controlled utility loss. Our first utility-driven graph summarization algorithm, G-SCIS, is based on a clique and independent set decomposition, that produces optimal compression with zero loss of utility. The compression provided is significantly better than state-of-the-art in lossless graph summarization, while the runtime is two orders of magnitude lower. Our second algorithm is T-BUDS, a highly scalable, utility-driven algorithm for fully controlled lossy summarization. It achieves high scalability by combining memory reduction using Maximum Spanning Tree with a novel binary search procedure. T-BUDS outperforms state-of-the-art drastically in terms of the quality of summarization and is about two orders of magnitude better in terms of speed. In contrast to the competition, we are able to handle web-scale graphs in a single machine without performance impediment as the utility threshold (and size of summary) decreases. Also, we show that our graph summaries can be used as-is to answer several important classes of queries, such as triangle enumeration, Pagerank and shortest paths. We then propose algorithm LDME, a correction set-based graph summarization algorithm that produces compact output representations in a fast and scalable manner. To achieve this, we introduce (1) weighted locality sensitive hashing to drastically reduce the number of comparisons required to find good node merges, (2) an efficient way to compute the best quality merges that produces more compact outputs, and (3) a new sort-based encoding algorithm that is faster and more robust. More interestingly, our algorithm provides performance tuning settings to allow the option of trading compression for running time. On high compression settings, LDME achieves compression equal to or better than the state of the art with up to 53x speedup in running time. On high speed settings, LDME achieves up to two orders of magnitude speedup with only slightly lower compression. We also present two lossless summarization algorithms, Optimal and Scalable, for summarizing fully dynamic graphs. More concretely, we follow the framework of G-SCIS, which produces summaries that can be used as-is in several graph analytics tasks. Different from G-SCIS, which is a batch algorithm, Optimal and Scalable are fully dynamic and can respond rapidly to each change in the graph. Not only are Optimal and Scalable able to outperform G-SCIS and other batch algorithms by several orders of magnitude, but they also significantly outperform MoSSo, the state-of-the-art in lossless dynamic graph summarization. While Optimal produces always the most optimal summary, Scalable is able to trade the amount of node reduction for extra scalability. For reasonable values of the parameter $K$, Scalable is able to outperform Optimal by an order of magnitude in speed, while keeping the rate of node reduction close to that of Optimal. An interesting fact that we observed experimentally is that even if we were to run a batch algorithm, such as G-SCIS, once for every big batch of changes, still they would be much slower than Scalable. For instance, if 1 million changes occur in a graph, Scalable is two orders of magnitude faster than running G-SCIS just once at the end of the 1 million-edge sequence. / Graduate

Cette étude présente une nouvelle approche pour la génération automatique de résumés, un des principaux défis du Traitement de la Langue Naturelle. Ce sujet, traité pendant un demi-siècle par la recherche, reste encore actuel car personne n’a encore réussi à créer automatiquement des résumés comparables, en qualité, avec ceux produits par des humains. C’est dans ce contexte que la recherche en résumé automatique s’est divisée en deux grandes catégories : le résumé par extraction et le résumé par abstraction. Dans le premier, les phrases sont triées de façon à ce que les meilleures conforment le résumé final. Or, les phrases sélectionnées pour le résumé portent souvent des informations secondaires, une analyse plus fine s’avère nécessaire.Nous proposons une méthode de compression automatique de phrases basée sur l’élimination des fragments à l’intérieur de celles-ci. À partir d’un corpus annoté, nous avons créé un modèle linéaire pour prédire la suppression de ces fragments en fonction de caractéristiques simples. Notre méthode prend en compte trois principes : celui de la pertinence du contenu, l’informativité ; celui de la qualité du contenu, la grammaticalité, et la longueur, le taux de compression. Pour mesurer l’informativité des fragments,nous utilisons une technique inspirée de la physique statistique : l’énergie textuelle.Quant à la grammaticalité, nous proposons d’utiliser des modèles de langage probabilistes.La méthode proposée est capable de générer des résumés corrects en espagnol.Les résultats de cette étude soulèvent divers aspects intéressants vis-à- vis du résumé de textes par compression de phrases. On a observé qu’en général il y a un haut degré de subjectivité de la tâche. Il n’y a pas de compression optimale unique mais plusieurs compressions correctes possibles. Nous considérons donc que les résultats de cette étude ouvrent la discussion par rapport à la subjectivité de l’informativité et son influence pour le résumé automatique. / This dissertation presents a novel approach to automatic text summarization, one of the most challenging tasks in Natural Language Processing (NLP). Until now, no one had ever created a summarization method capable of producing summaries comparable in quality with those produced by humans. Even many of state-of-the-art approaches form the summary by selecting a subset of sentences from the original text. Since some of the selected sentences might still contain superfluous information, a finer analysis is needed. We propose an Automatic Sentence Compression method based on the elimination of intra-phrase discourse segments. Using a manually annotated big corpus, we have obtained a linear model that predicts the elimination probability of a segment on the basis of three simple three criteria: informativity, grammaticality and compression rate. We discuss the difficulties for automatic assessment of these criteria in documents and phrases and we propose a solution based on existing techniques in NLP literature, one applying two different algorithms that produce summaries with compressed sentences. After applying both algorithms in documents in Spanish, our method is able to produce high quality results. Finally, we evaluate the produced summaries using the Turing test to determine if human judges can distinguish between human-produced summaries and machine-produced summaries. This dissertation addresses many previously ignored aspects of NLP, namely the subjectivity of informativity, the sentence compression in Spanish documents, and the evaluation of NLP using the Turing test.