So far, the task of Scientific Query-Focused Summarization (Sci-QFS) has lagged in development when compared to other areas of Scientific Natural Language Processing because of the lack of data. In this work, we propose a methodology to take advantage of existing collections of academic papers to obtain large-scale datasets for this task automatically. After applying it to the papers from our reading group, we introduce a novel dataset for Sci-QFS composed of 8,695 examples, each one with a query, the sentences of the full text from a paper and the relevance labels for each. After testing several classical and state-of-the-art embedding models on this data, we found that the task of Sci-QFS is far from being solved, although it is relatively straightforward for humans. Surprisingly, we found that classical methods outperformed modern pre-trained Deep Language Models (sometimes by a large margin), showing the need for large datasets to better fine-tune the latter. We share our experiments, data and models at https://github.com/jarobyte91/rouge_sciqfs.

Dimensionality Reduction (DR) methods have become essential tools for the data analysis toolbox. Typically, DR methods combine features of a multivariate dataset to produce dimensions in a reduced space, preserving some data properties, usually pairwise distances or local neighborhoods. Preserving such properties makes DR methods attractive, but it is also one of their weaknesses. When calculating the embedded dimensions, usually through non-linear strategies, the original feature values are lost and not explicitly represented in the spatialization of the produced layouts, making it challenging to interpret the results and understand the features’ contributions to the attained representations. Some strategies have been proposed to tackle this issue, such as coloring the DR layouts or generating explanations. Still, they are post-processes, so specific features (values) are not guaranteed to be preserved or represented. This paper proposes DimenFix , a novel meta-DR strategy that explicitly preserves the values of a particular user-defined feature or external data (not used to generate a layout) in one of the embedded axes. DimenFix can be used to preserve ordinal (e.g., numerical measures) and nominal (e.g., labels) values and works with virtually any gradient-descent DR method. It requires minimum changes to the underlying DR technique, running in linear time considering the number of data instances. In our results, involving Force Scheme and t-SNE adaptations, DimenFix was capable of representing features without heavily impacting distance or neighborhood preservation, allowing for creating hybrid layouts that join characteristics of scatter plots and DR methods.

Knowledge Graphs (KGs), such as DBpedia and ConceptNet, enhance Natural Language Processing (NLP) applications by providing structured information. However, extracting accurate data from KGs is challenging due to issues in entity detection, disambiguation, and relation classification, which often lead to errors and inefficiencies. We introduce Attention2Query (A2Q) , an attention-driven approach that directly ranks and selects the most relevant facts, thus minimizing error propagation. A2Q centres on three key contributions: (1) Focused Node Selection , which streamlines graph traversal; (2) Global Attention Alignment , improving retrieval by comparing facts against the query text; and (3) Contextual Re-ranking , enabling on-the-fly adjustments of fact importance based on evolving query context. Experimental results across multiple tasks and datasets show that A2Q substantially outperforms baseline methods, including those in zero-shot settings, achieving higher retrieval accuracy with reduced computational overhead. • Novel on-the-go fact retrieval framework for KGs using attention mechanisms. • The reranking strategy improves retrieval accuracy with minimal context. • A versatile approach reduces retrieval of non-relevant data from KGs. • A2Q outperforms baselines in data quality and efficiency in zero-shot settings.

Social media platforms are rich sources of opinionated content. Stance detection allows the automatic extraction of users’ opinions on various topics from such content. We focus on zero-shot stance detection, where the model’s success relies on (a) having knowledge about the target topic; and (b) learning general reasoning strategies that can be employed for new topics. We present Stance Reasoner, an approach to zero-shot stance detection on social media that leverages explicit reasoning over background knowledge to guide the model’s inference about the document’s stance on a target. Specifically, our method uses a pre-trained language model as a source of world knowledge, with the chain-of-thought in-context learning approach to generate intermediate reasoning steps. Stance Reasoner outperforms the current state-of-the-art models on 3 Twitter datasets, including fully supervised models. It can better generalize across targets, while at the same time providing explicit and interpretable explanations for its predictions.

Despite their remarkable successes, state-of-the-art large language models (LLMs), including vision-and-language models (VLMs) and unimodal language models (ULMs), fail to understand precise semantics. For example, semantically equivalent sentences expressed using different lexical compositions elicit diverging representations. The degree of this divergence and its impact on encoded semantics is not very well understood. In this paper, we introduce the SUGARCREPE++ dataset to analyze the sensitivity of VLMs and ULMs to lexical and semantic alterations. Each sample in SUGARCREPE++ dataset consists of an image and a corresponding triplet of captions: a pair of semantically equivalent but lexically different positive captions and one hard negative caption. This poses a 3-way semantic (in)equivalence problem to the language models. We comprehensively evaluate VLMs and ULMs that differ in architecture, pre-training objectives and datasets to benchmark the performance of SUGARCREPE++ dataset. Experimental results highlight the difficulties of VLMs in distinguishing between lexical and semantic variations, particularly to object attributes and spatial relations. Although VLMs with larger pre-training datasets, model sizes, and multiple pre-training objectives achieve better performance on SUGARCREPE++, there is a significant opportunity for improvement. We demonstrate that models excelling on compositionality datasets may not perform equally well on SUGARCREPE++. This indicates that compositionality alone might not be sufficient to fully understand semantic and lexical alterations. Given the importance of the property that the SUGARCREPE++ dataset targets, it serves as a new challenge to the vision-and-language community. Data and code is available at https://github.com/Sri-Harsha/scpp.

This paper presents MOD-kt, a modular framework designed to bridge the gap between modern language models and key-term-based document clustering. One of the main challenges of using neural language models for key-term-based clustering is the mismatch between the interpretability of the underlying document representation (i.e. document embeddings) and the more intuitive semantic elements that allow the user to guide the clustering process (i.e. key-terms). Our framework acts as a communication layer between word and document models, enabling key-term-based clustering in the context of document and word models with a flexible and adaptable architecture. We report a comparison of the performance of multiple neural language models on clustering, considering a selected range of relevance metrics. Additionally, a qualitative user study was conducted to illustrate the framework's potential for intuitive user-guided quality clustering of document collections.

This study focuses on the importance of well-designed online matching systems for job seekers and employers. We treat resumes and job descriptions as documents. Then, calculate their similarity to determine the suitability of applicants, and rank a set of resumes based on their similarity to a specific job description. We employ Siamese Neural Networks, comprised of identical sub-network components, to evaluate the semantic similarity between documents. Our novel architecture integrates various neural network architectures, where each sub-network incorporates multiple layers such as CNN, LSTM and attention layers to capture sequential, local and global patterns within the data. The LSTM and CNN components are applied concurrently and merged together. The resulting output is then fed into a multi-head attention layer. These layers extract features and capture document representations. The extracted features are then combined to form a unified representation of the document. We leverage pre-trained language models to obtain embeddings for each document, which serve as a lower-dimensional representation of our input data. The model is trained on a private dataset of 268,549 real resumes and 4,198 job descriptions from twelve industry sectors, resulting in a ranked list of matched resumes. We performed a comparative analysis involving our model, Siamese CNN (S-CNNs), Siamese LSTM with Manhattan distance, and a BERT-based sentence transformer model. By combining the power of language models and the novel Siamese architecture, this approach leverages both strengths to improve document ranking accuracy and enhance the matching process between job descriptions and resumes. Our experimental results demonstrate that our model outperforms other models in terms of performance.

Abstract Retrieving information from document collections is necessary in many contexts, e.g. researchers search for papers on a topic, physicians search for records of patients with a certain condition and police investigators seek relationships between different criminal reports. Finding relevant textual content in a corpus can be challenging in scenarios where the users expect a retrieval process with high recall. Visual Analytics (VA) systems that integrate interactive visualizations and machine learning algorithms are often advocated to support retrieval tasks in such complex scenarios. However, few studies report an end-user perspective on the utility of such systems. We present results from observational studies on VA-supported information retrieval conducted with graduate students and researchers using a system to explore collections of scientific papers. While users have, in general, positive views of the system’s potential to facilitate their retrieval tasks, some faced practical difficulties in using it effectively, and we found considerable variation in their assessment of specific functionalities. Our findings reinforce the potential of VA systems and also the importance of carefully informing users of the underlying conceptual models in such systems and their limitations.

In this paper, we propose a novel method to extend sequence-to-sequence models to accurately process sequences much longer than the ones used during training while being sample- and resource-efficient, supported by thorough experimentation. To investigate the effectiveness of our method, we apply it to the task of correcting documents already processed with Optical Character Recognition (OCR) systems using sequence-to-sequence models based on characters. We test our method on nine languages of the ICDAR 2019 competition on post-OCR text correction and achieve a new state-of-the-art performance in five of them. The strategy with the best performance involves splitting the input document in character n-grams and combining their individual corrections into the final output using a voting scheme that is equivalent to an ensemble of a large number of sequence models. We further investigate how to weigh the contributions from each one of the members of this ensemble. Our code for post-OCR correction is shared at https://github.com/jarobyte91/post_ocr_correction.

Clustering is a crucial text mining technique for organizing digital document sets, enabling users to understand their data better. It has been demonstrated that involving users can often significantly improve clustering quality. We propose a novel system that combines deep language models (SBERT, Infer-Sent, and Universal Sentence Encoder) with interactive clustering enabling users to steer the clustering algorithm towards results meaningful to them through interactive document and cluster visualizations. Our system is comprised of several visual components, each of which allows the user to apply their domain knowledge to the clustering process. The use of deep language models for representing sentences addresses the vocabulary mismatch problem that affects bag-of-words representations of documents. We employ sentence embeddings to obtain document embeddings as an input to the clustering algorithm, a modified version of K-means. We conduct a two-stage evaluation of our system. First, we evaluate the proposed clustering models in automatic clustering of various publicly available data sets, and we confirm that they are competitive with state-of-the-art. Second, we conduct a formal expert study of a specific data set consisting of our research group’s readings (research papers in machine learning, text mining, and natural language processing) over several years. The domain expert is a graduate student whose thesis is in the above field. The expert study concludes that our system is significantly better at producing meaningful clusters than the baseline system (Vis-Kt).

With the consolidation of deep learning in drug discovery, several novel algorithms for learning molecular representations have been proposed. Despite the interest of the community in developing new methods for learning molecular embeddings and their theoretical benefits, comparing molecular embeddings with each other and with traditional representations is not straightforward, which in turn hinders the process of choosing a suitable representation for Quantitative Structure-Activity Relationship (QSAR) modeling. A reason behind this issue is the difficulty of conducting a fair and thorough comparison of the different existing embedding approaches, which requires numerous experiments on various datasets and training scenarios. To close this gap, we reviewed the literature on methods for molecular embeddings and reproduced three unsupervised and two supervised molecular embedding techniques recently proposed in the literature. We compared these five methods concerning their performance in QSAR scenarios using different classification and regression datasets. We also compared these representations to traditional molecular representations, namely molecular descriptors and fingerprints. As opposed to the expected outcome, our experimental setup consisting of over $25 000$ trained models and statistical tests revealed that the predictive performance using molecular embeddings did not significantly surpass that of traditional representations. Although supervised embeddings yielded competitive results compared with those using traditional molecular representations, unsupervised embeddings tended to perform worse than traditional representations. Our results highlight the need for conducting a careful comparison and analysis of the different embedding techniques prior to using them in drug design tasks and motivate a discussion about the potential of molecular embeddings in computer-aided drug design.

Multi-Task Learning (MTL) for text classification takes advantage of the data to train a single shared model with multiple task-specific layers on multiple related classification tasks to improve its generalization performance. We choose pre-trained language models (BERT-family) as the shared part of this architecture. Although they have achieved noticeable performance in different downstream NLP tasks, their performance in an MTL setting for the biomedical domain is not thoroughly investigated. In this work, we investigate the performance of BERT-family models in different MTL settings with Open-I (radiology reports) and OHSUMED (PubMed abstracts) datasets. We introduce the MTLV (Multi-Task Learning Visualizer) library for building Multi-task learning-related architectures which use existing infrastructure (e.g., Hugging Face Transformers and MLflow Tracking). Following previous work in computer vision, we clustered tasks and trained a separate model on each cluster (Grouped Multi-Task Learning (GMTL)). Contextual representation of the class labels (Tasks) and their descriptions was used by the library as features to cluster the tasks. We observed that grouping tasks for training with few models (GMTL) outperforms the MTL also GMTL is computationally more efficient than the STL setting (a separate model is trained for each task).

Short text stream clustering is an important but challenging task since massive amount of text is generated from different sources such as micro-blogging, question-answering, and social news aggregation websites. The two major challenges of clustering such massive amount of text is to cluster them within a reasonable amount of time and to achieve better clustering result. To overcome these two challenges, we propose an efficient short text stream clustering algorithm (called EStream) consisting of two modules: online and offline. The online module of EStream algorithm assigns a text to a cluster one by one as it arrives. To assign a text to a cluster it computes similarity between a text and a selected number of clusters instead of all clusters and thus significantly reduces the running time of the clustering of short text streams. EStream assigns a text to a cluster (new or existing) using the dynamically computed similarity thresholds. Thus EStream efficiently deals with the concept drift problem. The offline module of EStream algorithm enhances the distributions of texts in the clusters obtained by the online module so that the upcoming short texts can be assigned to the appropriate clusters.

Twitter is one of the social media platforms that people express themselves freely. Harassment is one consequence of these such platforms, which is hard to obstruct. Text categorization and classification is a task that aims to solve this problem. Several studies applied classical machine learning methods and recent deep neural networks to categorize the text. However, only a few studies have explored graph convolutional neural networks while using classical approaches to categorize harassment Tweets. In this work, we propose using graph convolutional networks (GCN) for tweet categorization. Second, we explore this categorization task using classical machine learning approaches and compare the results with the GCN model. Third, we show the effectiveness of the GCN model on this problem by the other evaluation of the model on fewer sample datasets. In addition, we used different embedding approaches to find the best representation for the dataset in each of the models and represent the best embedding approach to use in this problem.

Positive and Unlabeled Learning (PUL) uses unlabeled documents and a few positive documents for retrieving a set of "interest" documents from a text collection. Usually, PUL approaches are based on the vector space model. However, when dealing with semi-supervised learning for text classification or information retrieval, graph-based approaches have been proved to outperform vector space model-based approaches. So, in this article, a graph-based approach for PUL is proposed: Label Propagation for Positive and Unlabeled Learning (LP-PUL). The proposed framework consists of three steps: (i) building a similarity graph, (ii) identifying reliable negative documents, and (iii) performing label propagation to classify the remaining unlabeled documents as positive or negative. We carried out experiments to measure the impact of the different choices in each step of the proposed framework. We also demonstrated that the proposal surpasses the classification performance of other PUL (RC-SVM, PU-LP, and PE-PUC) or one-class learning (k-NN-based, k-Means-based, and Dense Autoencoder) algorithms in terms of F1. Considering the best results of any algorithm used in the experimental evaluation, PU-PUL can improve the classification performance from 2%, when using only 1 labeled document, to 28%, when 30 labeled documents are employed.

Abstract Technical writing in professional environments, such as user manual authoring, requires the use of uniform language. Nonuniform language refers to sentences in a technical document that are intended to have the same meaning within a similar context, but use different words or writing style. Addressing this nonuniformity problem requires the performance of two tasks. The first task, which we named nonuniform language detection (NLD), is detecting such sentences. We propose an NLD method that utilizes different similarity algorithms at lexical, syntactic, semantic and pragmatic levels. Different features are extracted and integrated by applying a machine learning classification method. The second task, which we named nonuniform language correction (NLC), is deciding which sentence among the detected ones is more appropriate for that context. To address this problem, we propose an NLC method that combines contraction removal, near-synonym choice, and text readability comparison. We tested our methods using smartphone user manuals. We finally compared our methods against state-of-the-art methods in paraphrase detection (for NLD) and against expert annotators (for both NLD and NLC). The experiments demonstrate that the proposed methods achieve performance that matches expert annotators.

Interactive clustering techniques play a key role by putting the user in the clustering loop, allowing her to interact with document group abstractions instead of full-length documents. It allows users to focus on corpus exploration as an incremental task. To explore Information Discovery's incremental aspect, this article proposes a visual component to depict clustering membership changes throughout a clustering iteration loop in both static and dynamic data sets. The visual component is evaluated with an expert user and with an experiment with data streams.

In this paper we describe a framework to uncover potential causal relations between event mentions from streaming text of news media. This framework relies on a dataset of manually labeled events to train a recurrent neural network for event detection. It then creates a time series of event clusters, where clusters are based on BERT contextual word embedding representations of the identified events. Using these time series dataset, we assess four methods based on Granger causality for inferring causal relations. Granger causality is a statistical concept of causality that is based on forecasting. It states that a cause occurs before the effect, and the cause produces unique changes in the effect, so past values of the cause help predict future values of the effect. The four analyzed methods are the pairwise Granger test, VAR(1), BigVar and SiMoNe. The framework is applied to the New York Times dataset, which covers news for a period of 246 months. This preliminary analysis delivers important insights into the nature of each method, identifies differences and commonalities, and points out some of their strengths and weaknesses.

Short text stream clustering is an important but challenging task since massive amounts of text are generated from different social media. Given streams of texts, the proposed method clusters the streams of texts based on the frequently occurring word pairs (not necessarily consecutive) in texts. It detects outliers in the clusters and reassigns the outliers to appropriate clusters using the semantic similarity between the outliers and the clusters based on the dynamically computed similarity thresholds. Thus the proposed method efficiently deals with the concept drift problem. Experimental results demonstrate that the proposed approach outperforms the state-of-the-art short text stream clustering algorithms by a statistically significant margin on several short text datasets.

Word Sense Disambiguation (WSD) is a well-known problem in the field of Natural Language Processing (NLP) related to automatically determining the most appropriate sense of words in context. Several machine learning-based approaches have been proposed to tackle the ambiguity of language, but the lack of labeled data to train supervised models made semi-supervised learning (SSL) appear as an attractive option. Furthermore, the use of word embeddings to enhance the results of NLP tasks was shown to be an efficient strategy. Thus, this paper aims at adapting semi-supervised algorithms for WSD using word embeddings from Word2Vec, FastText, and BERT models combined with part-of-speech tags as input. We conduct a systematic evaluation of four graph-based SSL models analyzing the influence of their hyperparameters on the results, as well as the distances to build the graphs, the percentages of labeled data, and the word embeddings architectural variations. As a result, we show that SSL algorithms which received 10% of labeled data are strong baselines on the subsets of nouns and adjectives. Additionally, these algorithms do not need further training to disambiguate new words, hence being competitive to supervised systems.

Document clustering is a necessary step in various analytical and automated activities. When guided by the user, algorithms are tailored to imprint a perspective on the clustering process that reflects the user’s understanding of the dataset. More than just allow for customized adjustment of the clusters, a visual analytics approach will provide tools for the user to draw new insights on the collection. While contributing his or her perspective, the user will also acquire a deeper understanding of the data set. To that effect, we propose a novel visual analytics system for interactive document clustering. We built our system on top of clustering algorithms that can adapt to user’s feedback. In the proposed system, initial clustering is created based on the user-defined number of clusters and the selected clustering algorithm. A set of coordinated visualizations allow the examination of the dataset and the results of the clustering. The visualization provides the user with the highlights of individual documents and understanding of the evolution of documents over the time period to which they relate. The users then interact with the process by means of changing key-terms that drive the process according to their knowledge of the documents domain. In key-term-based interaction, the user assigns a set of key-terms to each target cluster to guide the clustering algorithm. We have improved that process with a novel algorithm for choosing proper seeds for the clustering. Results demonstrate that not only the system has improved considerably its precision, but also its effectiveness in the document-based decision making. A set of quantitative experiments and a user study have been conducted to show the advantages of the approach for document analytics based on clustering. We performed and reported on the use of the framework in a real decision-making scenario that relates users discussion by email to decision making in improving patient care. Results show that the framework is useful even for more complex data sets such as email conversations.

Genetic Programming techniques have demonstrated great potential in dealing with the problem of query generation. This work explores different Multi-Objective Genetic Programming strategies for evolving a collection of topic-based Boolean queries. It compares three approaches to build topical Boolean queries: using terms, incorporating Wikipedia semantics (Wikipedia concepts) and a hybrid approach, using a combination of both terms and concepts. In addition, different fitness functions are combined giving rise to seven multi-objective schemes. In particular, we investigate the use of the proposed strategies in conjunction with novel fitness functions aimed at attaining high diversity based on the information-theoretic notion of entropy and Jaccard similarity. Experiments were completed using 25 topics from a dataset consisting of approximately 350,000 webpages classified into 448 topics. The results reveal that the use of Wikipedia concepts does not result in statistically significant improvements in precision, global recall or diversity when compared to the term-based approaches. However, the use of concepts has a positive effect on query interpretability since the use of terms leads to artificial queries that are hard to interpret by humans. In the meantime, concept-based queries contain a smaller number of operands than the term-based ones, hence resulting in better execution times without a loss in retrieval performance.

In this paper, we propose TRIVIR, a novel interactive visualization tool powered by an Information Retrieval (IR) engine that implements an active learning protocol to support IR with high recall. The system integrates multiple graphical views in order to assist the user identifying the relevant documents in a collection, including a content-based similarity map obtained with multidimensional projection techniques. Given representative documents as queries, users can interact with the views to label documents as relevant/not relevant, and this information is used to train a machine learning (ML) algorithm which suggests other potentially relevant documents on demand. TRIVIR offers two major advantages over existing visualization systems for IR. First, it merges the ML algorithm output into the visualization, while supporting several user interactions in order to enhance and speed up its convergence. Second, it tackles the problem of vocabulary mismatch, by providing term's synonyms and a view that conveys how the terms are used within the collection. Besides, TRIVIR has been developed as a flexible front-end interface that can be associated with distinct text representations and multidimensional projection techniques. We describe two use cases conducted with collaborators who are potential users of TRIVIR. Results show that the system simplified the search for relevant documents in large collections, based on the context in which the terms occur.

In this paper, we propose a high recall active document retrieval system for a class of applications involving query documents, as opposed to key terms, and domain-specific document corpora. The output of the model is a list of documents retrieved based on the domain expert feedback collected during training. A modified version of Bag of Word (BoW) representation and a semantic ranking module, based on Google n-grams, are used in the model. The core of the system is a binary document classification model which is trained through a continuous active learning strategy. In general, finding or constructing training data for this type of problem is very difficult due to either confidentiality of the data, or the need for domain expert time to label data. Our experimental results on the retrieval of Call For Papers based on a manuscript demonstrate the efficacy of the system to address this application and its performance compared to other candidate models.

Attention guides computation to focus on important parts of the input data. For pairwise input, existing attention approaches tend to bias towards trivial repetitions (e.g. punctuations and stop words) between two texts, and thus failed to contribute reasonable guidance to model predictions. As a remedy, we suggest taking into account the corpus-level information via global-aware attention. In this paper, we propose an attention mechanism that makes use of intratext, inter-text and global contextual information. We undertake an ablation study on paraphrase identification, and demonstrate that the proposed attention mechanism can obviate the downsides of trivial repetitions and provide interpretable word weightings.

Short text clustering is an important but challenging task. We investigate impact of similarity matrix sparsification on the performance of short text clustering. We show that two sparsification methods (the proposed Similarity Distribution based, and k-nearest neighbors) that aim to retain a prescribed number of similarity elements per text, improve hierarchical clustering quality of short texts for various text similarities. These methods using a word embedding based similarity yield competitive results with state-of-the-art methods for short text clustering especially for general domain, and are faster than the main state-of-the-art baseline.

Document clustering is an efficient way to get insight into large text collections. Due to the personalized nature of document clustering, even the best fully automatic algorithms cannot create clusters that accurately reflect the user»s perspectives. To incorporate the user»s perspective in the clustering process and, at the same time, effectively visualize document collections to enhance user's sense-making of data, we propose a novel visual analytics system for interactive document clustering. We built our system on top of clustering algorithms that can adapt to user's feedback. First, the initial clustering is created based on the user-defined number of clusters and the selected clustering algorithm. Second, the clustering result is visualized to the user. A collection of coordinated visualization modules and document projection is designed to guide the user towards a better insight into the document collection and clusters. The user changes clusters and key-terms iteratively as a feedback to the clustering algorithm until the result is satisfactory. In key-term based interaction, the user assigns a set of key-terms to each target cluster to guide the clustering algorithm. A set of quantitative experiments, a use case, and a user study have been conducted to show the advantages of the approach for document analytics based on clustering.

Abstract Text is composed of words and phrases. In the bag‐of‐words model, phrases in text are split into words. This may discard the semantics of phrases, which, in turn, may give an inconsistent relatedness score between 2 texts. Our objective is to apply phrase relatedness in conjunction with word relatedness on the text relatedness task to improve text relatedness performance. We adopt 2 existing word relatedness measures based on Google n‐gram and Global Vectors for Word Representation, respectively, and incorporate them differently with an existing Google n‐gram–based phrase relatedness method to compute text relatedness. The combination of Google n‐gram–based word and phrase relatedness performs better than Google n‐gram–based word relatedness alone, by achieving the higher weighted mean of Pearson's r, ie, 0.639 and 0.619, respectively, on the 14 data sets from the series of Semantic Evaluation workshops SemEval‐2012, SemEval‐2013, and SemEval‐2015. Similarly, the combination of GloVe‐based word relatedness and Google n‐gram–based phrase relatedness performs better than GloVe‐based word relatedness alone, by achieving the higher weighted mean of Pearson's r, ie, 0.619 and 0.605, respectively, on the same 14 data sets. On the SemEval‐2012, SemEval‐2013, and SemEval‐2015 data sets, the text relatedness results obtained from the combination of Google n‐gram–based word and phrase relatedness ranked 24, 3, and 31 out of 89, 90, and 73 text relatedness systems, respectively.

The keyterm-based approach is arguably intuitive for users to direct text-clustering processes and adapt results to various applications in text analysis. Its way of markedly influencing the results, for instance, by expressing important terms in relevance order, requires little knowledge of the algorithm and has predictable effect, speeding up the task. This article first presents a text-clustering algorithm that can easily be extended into an interactive algorithm. We evaluate its performance against state-of-the-art clustering algorithms in unsupervised mode. Next, we propose three interactive versions of the algorithm based on keyterm labeling, document labeling, and hybrid labeling. We then demonstrate that keyterm labeling is more effective than document labeling in text clustering. Finally, we propose a visual approach to support the keyterm-based version of the algorithm. Visualizations are provided for the whole collection as well as for detailed views of document and cluster relationships. We show the effectiveness and flexibility of our framework, Vis-Kt , by presenting typical clustering cases on real text document collections. A user study is also reported that reveals overwhelmingly positive acceptance toward keyterm-based clustering.

The worldwide adoption of Twitter turned it into one of the most popular platforms for content analysis as it serves as a gauge of the public’s feeling and opinion on a variety of topics. This is particularly true of political discussions and lawmakers’ actions and initiatives. Yet, one common but unrealistic assumption is that the data of interest for analysis is readily available in a comprehensive and accurate form. Data need to be retrieved, but due to the brevity and noisy nature of Twitter content, it is difficult to formulate user queries that match relevant posts that use different terminology without introducing a considerable volume of unwanted content. This problem is aggravated when the analysis must contemplate multiple and related topics of interest, for which comments are being concurrently posted. This article presents Active Tweet Retrieval Visualization (ATR-Vis), a user-driven visual approach for the retrieval of Twitter content applicable to this scenario. The method proposes a set of active retrieval strategies to involve an analyst in such a way that a major improvement in retrieval coverage and precision is attained with minimal user effort. ATR-Vis enables non-technical users to benefit from the aforementioned active learning strategies by providing visual aids to facilitate the requested supervision. This supports the exploration of the space of potentially relevant tweets, and affords a better understanding of the retrieval results. We evaluate our approach in scenarios in which the task is to retrieve tweets related to multiple parliamentary debates within a specific time span. We collected two Twitter datasets, one associated with debates in the Canadian House of Commons during a particular week in May 2014, and another associated with debates in the Brazilian Federal Senate during a selected week in May 2015. The two use cases illustrate the effectiveness of ATR-Vis for the retrieval of relevant tweets, while quantitative results show that our approach achieves high retrieval quality with a modest amount of supervision. Finally, we evaluated our tool with three external users who perform searching in social media as part of their professional work.

TrWP is a text relatedness measure that computes semantic similarity between words and phrases utilizing aggregated statistics from the Google Web 1T 5-gram corpus. The phrase similarity computation in TrWP is costly in terms of both time and space, making the existing implementation of TrWP impractical for real-world usage. In this work, we present an in-memory computational framework for TrWP, which optimizes the corpus search using perfect hashing and minimizes the required memory cost using variable length encoding. Evaluated using the Google Web 1T 5-gram corpus, we demonstrate that the computational speed of our framework outperforms a file-based implementation by several orders of magnitude.

We introduce a (semi-)automatic OCR post-processing system that utilizes web-scale linguistic corpora in providing high-quality correction. This paper is a comprehensive system overview with the focus on the computational procedures, applied linguistic analysis, and processing optimization.

Radiology reports are one of the most important medical documents that a diagnostician looks into, especially in the emergency context. They provide the emergency physicians with critical information regarding the condition of the patient and help the physicians take immediate action on urgent conditions. However, the reports are in the form of unstructured text, which makes them time consuming for humans to interpret. We have developed a machine learning system to (a) efficiently extract the clinically significant parts and their level of importance in radiology reports, and (b) to classifies the overall report into critical or non-critical categories which help doctors to identify potential high priority reports. As a starting point, the system uses anonymized chest X-RAY reports of adults and provides three levels of importance for medical phrases. We used the Conditional Random Field (CRF) model to identify clinically significant phrases with an average f1-score of 0.75. The proposed system includes a web-based interface which highlights the medical phrases, and their level of importance to the emergency physician. The overall classification of the report is performed using the phrases extracted from the CRF model as features for the classifier. Average accuracy achieved is 85%.

As the spread of rumours has been increasing every day in online social networks (OSNs), it is important to analyze and understand this phenomenon. Damage caused by the spread of rumours is difficult to handle without a full understanding of the dynamics behind it. One of the central steps of understanding rumour spread is to analyze who spread rumours online, why, and how. In this research, we focus on the steps who and why by describing, implementing, and evaluating an approach that studies whether or not a group of users is actively involved in rumour discussions, and assesses rumour-spreading personality types in OSNs. We implement this general approach using Reddit data, and demonstrate its use by determining which users engage with a recurring rumour, and analyzing their comments using qualitative methods. We find that we can reliably classify users into one of three categories: (1) “Generally support a false rumour”, (2) “Generally refute a false rumour”, or (3) “Generally joke about a false rumour”. Combining text mining techniques, such as text classification, sentiment analysis, and social network analysis, we aim to identify and classify those rumour-spreading user categories automatically and provide a more holistic view of rumour spread in OSNs.

Twitter has become one of the most important platforms for gathering information, where users follow breaking news, track ongoing events and learn about their topics of interest. Considering the sheer volume of Twitter data and the ever-growing number of users, it is of great importance to have real-time systems that can monitor and recommend relevant and non-redundant tweets with respect to users' interests. In this paper, we propose a framework using language models as a basis for analyzing strategies and techniques for tweet recommendation based on user interest profiles. Results show that identifying named entities in profiles has a major impact on the accuracy of the recommender. We also performed a thorough comparison to investigate whether state-of-the-art semantic relatedness techniques have a positive impact on the precision of the recommended tweets. The TREC 2015 Microblog track dataset is used for comparison and evaluation throughout this paper.

This paper introduces a new large-scale n-gram corpus that is created specifically from social media text. Two distinguishing characteristics of this corpus are its monthly temporal attribute and that it is created from 1.65 billion comments of user-generated text in Reddit. The usefulness of this corpus is exemplified and evaluated by a novel Topic-based Latent Semantic Analysis (TLSA) algorithm. The experimental results show that unsupervised TLSA outperforms all the state-of-the-art unsupervised and semi-supervised methods in SEMEVAL 2015: paraphrase and semantic similarity in Twitter tasks.

By reflecting the degree of proximity or remoteness of documents, similarity measure plays the key role in text analytics. Traditional measures, e.g. cosine similarity, assume that documents are represented in an orthogonal space formed by words as dimensions.

Technical writing in professional environments, such as user manual authoring, requires uniform language. Non-uniform language detection is a novel task, which aims to guarantee the consistency for technical writing by detecting sentences in a document that are intended to have the same meaning within a similar context but use different words/writing style. This thesis proposes an approach that utilizes text similarity algorithms at lexical, syntactic, semantic and pragmatic levels. Different metrics are integrated by applying a machine learning classification method. We tested our method using smart phone user manuals, and compared the performance against the state-of-the-art methods in related area. The experiments demonstrate our approach is the most efficient solution to date.

Traditional semi‐supervised clustering uses only limited user supervision in the form of instance seeds for clusters and pairwise instance constraints to aid unsupervised clustering. However, user supervision can also be provided in alternative forms for document clustering, such as labeling a feature by indicating whether it discriminates among clusters. This article thus fills this void by enhancing traditional semi‐supervised clustering with feature supervision, which asks the user to label discriminating features during defining (labeling) the instance seeds or pairwise instance constraints. Various types of semi‐supervised clustering algorithms were explored with feature supervision. Our experimental results on several real‐world data sets demonstrate that augmenting the instance‐level supervision with feature‐level supervision can significantly improve document clustering performance.

The spread of "rumours" in Online Social Networks (OSNs) has grown at an alarming rate. Consequently, there is an increasing need to improve understanding of the social and technological processes behind this trend. The first step in detecting rumours is to identify and extract memes, a unit of information that can be spread from person to person in OSNs. This paper proposes four similarity scores and two novel strategies to combine those similarity scores for detecting the spread of memes in OSNs, with the end goal of helping researchers as well as members of various OSNs to study the phenomenon. The two proposed strategies include: (1) automatically computing the similarity score weighting factors for four elements of a submission and (2) allowing users to engage in the clustering process and filter out outlier submissions, modify submission class labels, or assign different similarity score weight factors for various elements of a submission using a visualization prototype. To validate our approach, we collect submissions on Reddit about five controversial topics and demonstrate that the proposed strategies outperform the baseline.

Measuring document relatedness using unsupervised co-occurrence based word relatedness methods is a processing-time and memory consuming task. This paper introduces the application of compact data structures for efficient computation of word relatedness based on corpus statistics. The data structure is used to efficiently lookup: (1) the corpus statistics for the Common Word Relatedness Approach, (2) the pairwise word relatedness for the Algorithm Specific Word Relatedness Approach. These two approaches significantly accelerate the processing time of word relatedness methods and reduce the space cost of storing co-occurrence statistics in memory, making text mining tasks like classification and clustering based on word relatedness practical.

Technical writing in professional environments, such as user manual authoring for new products, is a task that relies heavily on reuse of content. Therefore, technical content is typically created following a strategy where modular units of text have references to each other. One of the main challenges faced by technical authors is to avoid duplicating existing content, as this adds unnecessary effort, generates undesirable inconsistencies, and dramatically increases maintenance and translation costs. However, there are few computational tools available to support this activity. This paper investigates the use of different similarity methods for the task of identification of reuse opportunities in technical writing. We evaluated our results using existing ground truth as well as feedback from technical authors. Finally, we also propose a tool that combines text similarity algorithms with interactive visualizations to aid authors in understanding differences in a collection of topics and identifying reuse opportunities.

Users of microblogging social networks produce millions of short messages every day. Retrieving relevant information to a particular event from this sheer volume of data is not a trivial task. In this paper, we present a framework for the retrieval of Twitter posts that are relevant to a set of political debates. Our main contribution is the proposal of a set of strategies for involving the user in the retrieval process, so that by presenting to her meaningful posts to be labeled, the method achieves a noticeably higher accuracy. The correct retrieval or labeling could be provided by an external information source such as a domain expert, or simulated with an oracle. A key aspect of active retrieval methods is to request the labels of the instances that help improve the retrieval accuracy the most, while keeping the number of labeling requests to a minimum. The proposed strategies for selecting labeling requests make use of the textual content of tweets and their structural information. The experimental results show the advantages of the proposed methods and the effectiveness of the selection strategies for involving the user in the retrieval process.

Semi-structured documents are a common type of data containing free text in natural language (unstructured data) as well as additional information about the document, or meta-data, typically following a schema or controlled vocabulary (structured data). Simultaneous analysis of unstructured and structured data enables the discovery of hidden relationships that cannot be identified from either of these sources when analyzed independently of each other. In this work, we present a visual text analytics tool for semi-structured documents (ViTA-SSD), that aims to support the user in the exploration and finding of insightful patterns in a visual and interactive manner in a semi-structured collection of documents. It achieves this goal by presenting to the user a set of coordinated visualizations that allows the linking of the metadata with interactively generated clusters of documents in such a way that relevant patterns can be easily spotted. The system contains two novel approaches in its back end: a feature-learning method to learn a compact representation of the corpus and a fast-clustering approach that has been redesigned to allow user supervision. These novel contributions make it possible for the user to interact with a large and dynamic document collection and to perform several text analytical tasks more efficiently. Finally, we present two use cases that illustrate the suitability of the system for in-depth interactive exploration of semi-structured document collections, two user studies, and results of several evaluations of our text-mining components.

Online social streams such as Twitter timelines, forum discussions and email threads have emerged as important channels for information propagation. Mining transient stories and their correlations implicit in social streams is a challenging task, since these streams are noisy and surge quickly. In this paper, we propose CAST, which is a context-aware story-teller that discovers new stories from social streams and tracks their structural context on the fly to build a vein of stories. More precisely, we model the social stream as a capillary network, and define stories by a new cohesive subgraph type called (k,d)-Core in the capillary network. We propose deterministic and randomized context search to support the iceberg query, which builds the story vein as social streams flow. We perform detailed experimental study on real Twitter streams and the results demonstrate the creativity and value of our approach.

This paper presents P-GTM, a privacy-preserving text similarity algorithm that extends the Google Tri-gram Method (GTM). The Google Tri-gram Method is a high-performance unsupervised semantic text similarity method based on the use of context from the Google Web 1T n-gram dataset. P-GTM computes the semantic similarity between two input bag-of-words documents on public cloud hardware, without disclosing the documents' contents. Like the GTM, P-GTM requires the uni-gram and tri-gram lists from the Google Web 1T n-gram dataset as additional inputs. The need for these additional lists makes private computation of GTM text similarities a challenging problem. P-GTM uses a combination of pre-computation, encryption, and randomized preprocessing to enable private computation of text similarities using the GTM. We discuss the security of the algorithm and quantify its privacy using standard and real life corpora.

No abstract available.

Most text clustering algorithms represent a corpus as a document-term matrix in the bag of words model. The feature values are computed based on term frequencies in documents and no semantic relatedness between terms is considered. Therefore, two semantically similar documents may sit in different clusters if they do not share any terms. One solution to this problem is to enrich the document representation using an external resource like Wikipedia. We propose a new way to integrate Wikipedia concepts in partitional text document clustering in this work. A text corpus is first represented as a document-term matrix and a document-concept matrix. Terms that exist in the corpus are then clustered based on the document-term representation. Given the term clusters, we propose two methods, one based on the document-term representation and the other one based on the document-concept representation, to find two sets of seed documents. The two sets are then used in our text clustering algorithm in an ensemble approach to cluster documents. The experimental results show that even though the document-concept representations do not result in good document clusters per se, integrating them in our ensemble approach improves the quality of document clusters significantly.

Dynamic networks are commonly found in the current web age. In scenarios like social networks and social media, dynamic networks are noisy, are of large-scale and evolve quickly. In this paper, we focus on the cluster evolution tracking problem on highly dynamic networks, with clear application to event evolution tracking. There are several previous works on data stream clustering using a node-by-node approach for maintaining clusters. However, handling of bulk updates, i.e., a subgraph at a time, is critical for achieving acceptable performance over very large highly dynamic networks. We propose a subgraph-by-subgraph incremental tracking framework for cluster evolution in this paper. To effectively illustrate the techniques in our framework, we consider the event evolution tracking task in social streams as an application, where a social stream and an event are modeled as a dynamic post network and a dynamic cluster respectively. By monitoring through a fading time window, we introduce a skeletal graph to summarize the information in the dynamic network, and formalize cluster evolution patterns using a group of primitive evolution operations and their algebra. Two incremental computation algorithms are developed to maintain clusters and track evolution patterns as time rolls on and the network evolves. Our detailed experimental evaluation on large Twitter datasets demonstrates that our framework can effectively track the complete set of cluster evolution patterns from highly dynamic networks on the fly.

Unsupervised document clustering groups documents into clusters without any user effort. However, the clusters produced are often found not in accord with user's perception of the document collection. In this paper we describe a novel framework and e

We propose FSDC, an evolutionary algorithm for Feature Selective Double Clustering of text documents. We first cluster the terms existing in the document corpus. The term clusters are then fed into multiobjective genetic algorithms to prune non-informative terms and form sets of keyterms representing topics. Based on the topic keyterms found, representative documents for each topic are extracted. These documents are then used as seeds to cluster all documents in the dataset. FSDC is compared to some well-known co-clusterers on real text datasets. The experimental results show that our algorithm can outperform the competitors.

We propose an interactive text document method, which is based on term labeling. The algorithm asks the user to cluster the top keyterms associated with document clusters iteratively. The keyterm clusters are used to guide the clustering method. Rather than using standard clustering algorithms, we propose a new text clusterer using term clusters. Terms that exist in a document corpus are clustered. Using a greedy approach, the term clusters are distilled in order to remove non-discriminative general terms. We then present a heuristic approach to extract seed documents associated with each distilled term cluster. These seeds are finally used to cluster all documents. We compared our interactive term labeling to a baseline interactive term selection algorithm on some real standard text datasets. The experiments show that with a comparable amount of user effort, our term labeling is more effective than the baseline term selection method.

It is often desirable to identify the concepts that are present in a corpus. A popular way to deal with this objective is to discover clusters of words or topics, for which many algorithms exist in the literature. Yet most of these methods lack the interpretability that would enable interaction with a user not familiar with their inner workings. The paper proposes a graph-based topic extraction algorithm, which can also be viewed as a soft-clustering of words present in a given corpus. Each topic, in the form of a set of words, represents an underlying concept in the corpus. The method allows easy interpretation of the clustering process, and hence enables the scope of user involvement at various steps. For a quantitative evaluation of the topics extracted, we use them as features to get a compact representation of documents for classification tasks. We compare the classification accuracy achieved by a reduced feature set obtained with our method versus other topic extraction techniques, namely Latent Dirichlet Allocation and Non-negative Matrix Factorization. While the results from all the three algorithms are comparable, the speed and easy interpretability of our algorithm makes it more appropriate to be used interactively by lay users.

We propose a model for assigning Wikipedia Concepts as scientific category labels to scientific documents where their terms are first grouped together using the well-known topic modelling method, Latent Dirichlet Allocation (LDA) and then assigned to Wikipedia Concepts by wikification. We wikify the terms of the topic model of a document to extract related concepts from Wikipedia. We experiment on two different datasets: the abstracts of the documents from the ACM Digital Library and the full papers of the UvT Collection. The ACM dataset includes Computer Science publications whereas UvT includes scientific publications from a range of topics. Domain specific taxonomies are used for evaluation. Results show that our approach is able to assign Wikipedia Concepts to the scientific publications in an automated manner, removing any need for human supervision.

Online social streams such as Twitter/Facebook timelines and forum discussions have emerged as prevalent channels for information dissemination. As these social streams surge quickly, information overload has become a huge problem. Existing keyword search engines on social streams like Twitter Search are not successful in overcoming the problem, because they merely return an overwhelming list of posts, with little aggregation or semantics. In this demo, we provide a new solution called \keysee by grouping posts into events, and track the evolution patterns of events as new posts stream in and old posts fade out. Noise and redundancy problems are effectively addressed in our system. Our demo supports refined keyword query on evolving events by allowing users to specify the time span and designated evolution pattern. For each event result, we provide various analytic views such as frequency curves, word clouds and GPS distributions. We deploy \keysee on real Twitter streams and the results show that our demo outperforms existing keyword search engines on both quality and usability.

The potential for semi-supervised techniques to produce personalized clusters has not been explored. This is due to the fact that semi-supervised clustering algorithms used to be evaluated using oracles based on underlying class labels. Although using oracles allows clustering algorithms to be evaluated quickly and without labor intensive labeling, it has the key disadvantage that oracles always give the same answer for an assignment of a document or a feature. However, different human users might give different assignments of the same document and/or feature because of different but equally valid points of view. In this paper, we conduct a user study in which we ask participants (users) to group the same document collection into clusters according to their own understanding, which are then used to evaluate semi-supervised clustering algorithms for user personalization. Through our user study, we observe that different users have their own personalized organizations of the same collection and a user's organization changes over time. Therefore, we propose that document clustering algorithms should be able to incorporate user input and produce personalized clusters based on the user input. We also confirm that semi-supervised algorithms with noisy user input can still produce better organizations matching user's expectation (personalization) than traditional unsupervised ones. Finally, we demonstrate that labeling keywords for clusters at the same time as labeling documents can improve clustering performance further compared to labeling only documents with respect to user personalization.

The ability to automatically discover error conditions with little human input is a feature lacking in most modern computer systems and networks. However, with the ever increasing size and complexity of modern systems, such a feature will become a necessity in the not too distant future. Our work proposes a hybrid framework that allows High Performance Clusters (HPC) to detect error conditions in their logs. Through the use of anomaly detection, the system is able to detect portions of the log that are likely to contain errors (anomalies). Via visualization, human administrators can inspect these anomalies and assign labels to clusters that correlate with error conditions. The system can then learn a signature from the confirmed anomalies, which it uses to detect future occurrences of the error condition. Our evaluations show the system is able to generate simple and accurate signatures using very little data.

A focused crawler is an efficient tool used to traverse the Web to gather documents on a specific topic. It can be used to build domain‐specific Web search portals and online personalized search tools. Focused crawlers can only use information obtained from previously crawled pages to estimate the relevance of a newly seen URL. Therefore, good performance depends on powerful modeling of context as well as the quality of the current observations. To address this challenge, we propose capturing sequential patterns along paths leading to targets based on probabilistic models. We model the process of crawling by a walk along an underlying chain of hidden states, defined by hop distance from target pages, from which the actual topics of the documents are observed. When a new document is seen, prediction amounts to estimating the distance of this document from a target. Within this framework, we propose two probabilistic models for focused crawling, Maximum Entropy Markov Model (MEMM) and Linear‐chain Conditional Random Field (CRF). With MEMM, we exploit multiple overlapping features, such as anchor text, to represent useful context and form a chain of local classifier models. With CRF, a form of undirected graphical models, we focus on obtaining global optimal solutions along the sequences by taking advantage not only of text content, but also of linkage relations. We conclude with an experimental validation and comparison with focused crawling based on Best‐First Search (BFS), Hidden Markov Model (HMM), and Context‐graph Search (CGS).

Message type or message cluster extraction is an important task in the analysis of system logs in computer networks. Defining these message types automatically facilitates the automatic analysis of system logs. When the message types that exist in a log file are represented explicitly, they can form the basis for carrying out other automatic application log analysis tasks. In this paper, we introduce a novel algorithm for carrying out message type extraction from event log files. IPLoM, which stands for Iterative Partitioning Log Mining, works through a 4-step process. The first three steps hierarchically partition the event log into groups of event log messages or event clusters. In its fourth and final stage, IPLoM produces a message type description or line format for each of the message clusters. IPLoM is able to find clusters in data irrespective of the frequency of its instances in the data, it scales gracefully in the case of long message type patterns and produces message type descriptions at a level of abstraction, which is preferred by a human observer. Evaluations show that IPLoM outperforms similar algorithms statistically significantly.

Self-awareness is an important attribute for any system to have before it is capable of self-management. A system needs to have a continuous stream of real-time data to analyze to allow it be aware of its internal state. To this end, previous approaches have utilized system performance metrics and system log data to characterize system internal state. In using system logs to characterize system internal state, the computation of strongly correlated message types is necessary. In this work, we show that strongly correlated message types can be easily discovered without much computation. Our work explores a natural behaviour of system logs where system log data partitioned using source and time information contain correlated message types. We demonstrate how the groups of partitions, which contain correlated message types, can be found by clustering the partitions based on their entropy-based information content. We evaluate our method using cluster cohesion, cluster separation and cluster conceptual purity as metrics. The results show that our proposed method not only produces well-formed clusters but also clusters that can be mapped to different alert states with a high degree of confidence.

Recent research efforts have highlighted the capability of entropy based approaches in the automatic discovery of alerts in system logs. In this work, we extend this research to present the evaluations of three entropy based approaches on new datasets not utilized in previous papers. We also extend the approach with the introduction of a Cluster Membership Anomaly score. This extension of the approach is intended to reduce the false positive rates required to detect all alerts. Previous work has shown that false positive rates required for the detection of all alerts for an entropy based approach could be very high. The results show that the Cluster Membership Anomaly score has value for the reduction of false positive rates.

We address the problem of evaluating the robustness of machine learning based detectors for deployment in real life networks. To this end, we employ Genetic Programming for evolving classifiers and Artificial Neural Networks as our machine learning paradigms under three different Denial-of-Service attacks at the Data Link layer (De-authentication, Authentication and Association attacks). We investigate their cross-platform robustness and cross-attack robustness. Cross-platform robustness is the ability to seamlessly port an Intrusion Detector trained on one network to another network with little or no change and without a drop in performance. Cross-attack robustness is the ability of a detector trained on one attack type to detect a different but similar attack on which it has not been trained. Our results show that the potential of a machine learning based detector can be significantly enhanced or limited by the representation of the training data for the learning algorithms.

Despite all of the advantages of tags as an easy and flexible information management approach, tagging is a cumbersome task. A set of descriptive tags has to be manually entered by users whenever they post a resource. This process can be simplified by the use of tag recommendation systems. Their objective is to suggest potentially useful tags to the user. We present a hybrid tag recommendation system together with a scalable, highly efficient system architecture. The system is able to utilize user feedback to tune its parameters to specific characteristics of the underlying tagging system and adapt the recommendation models to newly added content. The evaluation of the system on six real-life datasets demonstrated the system’s ability to combine tags from various sources (e.g., resource content or tags previously used by the user) to achieve the best quality of recommended tags. It also confirmed the importance of parameter tuning and content adaptation. A series of additional experiments allowed us to better understand the characteristics of the system and tagging datasets and to determine the potential areas for further system development.

The objective of a tag recommendation system is to propose a set of tags for a resource to ease the tagging process done manually by a user. Tag recommendation is an interesting and well defined research problem. However, while solving it, it is easy to forget about its practical implications. We discuss the practical aspects of tag recommendation and propose a system that successfully addresses the problem of learning in tag recommendation, without sacrificing efficiency. Learning is realized in two aspects: adaptation to newly added posts and parameter tuning. The content of each added post is used to update the resource and user profiles as well as associations between tags. Parameter tuning allows the system to automatically adjust the way tag sources (e.g., content related tags or user profile tags) are combined to match the characteristics of a specific collaborative tagging system. The evaluation on data from three collaborative tagging systems confirmed the importance of both learning methods. Finally, an architecture based on text indexing makes the system efficient enough to serve in real time collaborative tagging systems with number of posts counted in millions, given limited computing resources.

Size and complexity of data repositories collaboratively created by Web users generate a need for new processing approaches. In this paper, we study the problem of detection of fine-grained communities of users in social networks, which can be defined as clustering with a large number of clusters. The practical size of social networks makes the traditional evolutionary based clustering approaches, which represent the entire clustering solution as one individual, hard to apply. We propose an Agglomerative Clustering Genetic Algorithm (ACGA): a population of clusters evolves from the initial state in which each cluster represents one user to a high quality clustering solution. Each step of the evolutionary process is performed locally, engaging only a small part of the social network limited to two clusters and their direct neighborhood. This makes the algorithm practically useful independently of the size of the network. Evaluation on two social network models indicates that ACGA is potentially able to detect communities with accuracy comparable or better than two typical centralized clustering algorithms even though ACGA works under much stricter conditions.

The importance of event logs, as a source of information in systems and network management cannot be overemphasized. With the ever increasing size and complexity of today's event logs, the task of analyzing event logs has become cumbersome to carry out manually. For this reason recent research has focused on the automatic analysis of these log files. In this paper we present IPLoM (Iterative Partitioning Log Mining), a novel algorithm for the mining of clusters from event logs. Through a 3-Step hierarchical partitioning process IPLoM partitions log data into its respective clusters. In its 4th and final stage IPLoM produces cluster descriptions or line formats for each of the clusters produced. Unlike other similar algorithms IPLoM is not based on the Apriori algorithm and it is able to find clusters in data whether or not its instances appear frequently. Evaluations show that IPLoM outperforms the other algorithms statistically significantly, and it is also able to achieve an average F-Measure performance 78% when the closest other algorithm achieves an F-Measure performance of 10%.

Abstract—Security and Intrusion detection in WiFi networks is currently an active area of research where WiFi specific Data Link layer attacks are an area of focus; particularly recent work has focused on producing machine learning based IDSs for these WiFi specific attacks. These proposed machine learning based IDSs come in addition to the already deployed signatures which are already in use in conventional intrusion detection systems like Snort-Wireless and Kismet. In this paper, we compare the detection capability of Snort-Wireless and a Genetic Programming (GP) based intrusion detector, based on the ability to adapt to modified attacks, ability to adapt to similar unknown attacks and infrastructure independent detection. Our results show that the GP based detection system is much more robust against modified attacks compared to Snort-Wireless. Moreover, by focusing on the method(s) used in feature preprocessing for presentation to learning algorithms, GP based IDSs can achieve infrastructure independent detection and can adapt to similar unknown attacks too. On the other hand, even though Snort-Wireless is an infrastructure independent detector, it cannot adapt to unknown attacks even if they are similar to others for which it has signatures on.

Event logs or log files form an essential part of any network management and administration setup. While log files are invaluable to a network administrator, the vast amount of data they sometimes contain can be overwhelming and can sometimes hinder rather than facilitate the tasks of a network administrator. For this reason several event clustering algorithms for log files have been proposed, one of which is the event clustering algorithm proposed by Risto Vaarandi, on which his simple log file clustering tool (SLCT) is based. The aim of this work is to develop a visualization tool that can be used to view log files based on the clusters produced by SLCT. The proposed visualization tool, which is called LogView, utilizes treemaps to visualize the hierarchical structure of the clusters produced by SLCT. Our results based on different application log files show that LogView can ease the summarization of vast amount of data contained in the log files. This in turn can help to speed up the analysis of event data in order to detect any security issues on a given application.

Image-based abstraction (or summarization) of a Web site is the process of extracting the most characteristic (or important) images from it. The criteria for measuring the importance of images in Web sites are based on their frequency of occurrence, characteristics of their content and Web link information. As a case study, this work focuses on logo and trademark images. These are important characteristic signs of corporate Web sites or of products presented there. The proposed method incorporates machine learning for distinguishing logo and trademarks from images of other categories (e.g., landscapes, faces). Because the same logo or trademark may appear many times in various forms within the same Web site, duplicates are detected and only unique logo and trademark images are extracted. These images are then ranked by importance taking frequency of occurrence, image content and Web link information into account. The most important logos and trademarks are finally selected to form the image-based summary of a Web site. Evaluation results of the method on real Web sites are also presented. The method has been implemented and integrated into a fully automated image-based summarization system which is accessible on the Web (www.intelligence.tuc.gr/websummarization)

Shrack is a peer-to-peer framework for document sharing and tracking. Shrack peers provide support to researchers in forming direct collaboration in autonomous sharing and keeping track of newly published documents based on their interests. We propose a pull-only information dissemination protocol for peers to distribute information about new documents among peers with similar interests. Each peer can use the disseminated information to build a local view of semantic overlay of peer interests in the network. Each peer can later use the semantic overlay to find new contact information about other peers with a particular interests, as well as search for documents archived by other peers. After presenting an overview architecture of the system and the dissemination protocol, we present the evaluation results of the system performance, based on a simulated environment. The results indicate that the Shrack protocol is scalable and reliable as the network size increases.

This paper presents a robust design for the general bilateral teleoperation system with Markov jumping parameters. Although passivity-based approach and robust design-based approach can stabilize the bilateral teleoperation system, sufficient conditions are too conservative. In this paper, requirements for a general bilateral teleoperation system are given first. Next, time delays on the internet are modeled by a Markov process with nine states, three for the forward communication branch and three for the backward communication branch. Based on the requirements of the master and the slave controllers, the standard robust design are carried out. Then, with the model of internet time delays, the bilateral teleoperation system is reconstructed by a Markov jumping system. Based on the mode-dependent stability conditions for the stochastic time delay system, the closed-loop controller is designed to obtain the less conservative stable system and to therefore improve the performance of tracking and transparency. Simulation has been carried out and the results verify the feasibility and efficiency of the proposed approach.

Modeling the acoustics of an environment is a complex and challenging task. Here we describe the sonel mapping approach to acoustical rendering. Sonel mapping is a Monte-Carlo-based approach to modeling diffuse, specular, absorption and diffraction effects in an efficient manner. The approach models many of the subtle interaction effects required for realistic acoustical modeling, and the approach is computationally efficient allowing it to be used to acoustically model interactive virtual environments

We present a generative model for simultaneously clustering documents and terms. Our model is a four-level hierarchical Bayesian model, in which each document is modeled as a random mixture of document topics , where each topic is a distribution over some segments of the text. Each of these segments in the document can be modeled as a mixture of word topics where each topic is a distribution over words. We present efficient approximate inference techniques based on Markov Chain Monte Carlo method and a moment-matching algorithm for empirical Bayes parameter estimation. We report results in document modeling, document and term clustering, comparing to other topic models, Clustering and Co-Clustering algorithms including latent Dirichlet allocation (LDA), model-based overlapping clustering (MOC), model-based overlapping co-clustering (MOCC) and information-theoretic co-clustering (ITCC).

Semantic Similarity relates to computing the similarity between conceptually similar but not necessarily lexically similar terms. Typically, semantic similarity is computed by mapping terms to an ontology and by examining their relationships in that ontology. We investigate approaches to computing the semantic similarity between natural language terms (using WordNet as the underlying reference ontology) and between medical terms (using the MeSH ontology of medical and biomedical terms). The most popular semantic similarity methods are implemented and evaluated using WordNet and MeSH. Building upon semantic similarity, we propose the Semantic Similarity based Retrieval Model (SSRM), a novel information retrieval method capable for discovering similarities between documents containing conceptually similar terms. The most effective semantic similarity method is implemented into SSRM. SSRM has been applied in retrieval on OHSUMED (a standard TREC collection available on the Web). The experimental results demonstrated promising performance improvements over classic information retrieval methods utilizing plain lexical matching (e.g., Vector Space Model) and also over state-of-the-art semantic similarity retrieval methods utilizing ontologies.

We propose a novel method for document clustering using character N-grams. In the traditional vector-space model, the documents are represented as vectors, in which each dimension corresponds to a word. We propose a document representation based on the most frequent character N-grams, with window size of up to 10 characters. We derive a new distance measure, which produces uniformly better results when compared to the word-based and term-based methods. The result becomes more significant in the light of the robustness of the N-gram method with no language-dependent preprocessing. Experiments on the performance of a clustering algorithm on a variety of test document corpora demonstrate that the N-gram representation with n=3 outperforms both word and term representations. The comparison between word and term representations depends on the data set and the selected dimensionality.

We describe recent results obtained with AQUA, a mobile robot capable of swimming, walking and amphibious operation. Designed to rely primarily on visual sensors, the AQUA robot uses vision to navigate underwater using servo-based guidance, and also to obtain high-resolution range scans of its local environment. This paper describes some of the pragmatic and logistic obstacles encountered, and provides an overview of some of the basic capabilities of the vehicle and its associated sensors. Moreover, this paper presents the first ever amphibious transition from walking to swimming.

We address the problem of globally consistent estimation of the trajectory of a robot arm moving in three dimensional space based on a sequence of binocular stereo images from a stereo camera mounted on the tip of the arm. Correspondence between 3D points from successive stereo camera positions is established through matching of 2D SIFT features in the images. We compare three different methods for solving this estimation problem, based on three distance measures between 3D points, Euclidean distance, Mahalanobis distance and a distance measure defined by a maximum likelihood formulation. Theoretical analysis and experimental results demonstrate that the maximum likelihood formulation is the most accurate. If the measurement error is guaranteed to be small, then Euclidean distance is the fastest, without significantly compromising accuracy, and therefore it is best for on-line robot navigation.

Image retrieval on the Web requires that important (authoritative) images satisfying the query selection criteria are assigned higher ranking over other relevant images. PicASHOW (Lempel and Soffer, 2002) achieves this goal using link information alone. This work proposes WPicASHOW (weighted PicASHOW), a weighted scheme for co-citation analysis that incorporates within the link analysis method of PicASHOW the text and image content of the queries and of the Web pages. WPicASHOW is implemented and integrated into a fully automated Web retrieval system for logo and trademark images.

This paper describes an underwater walking robotic system being developed under the name AQUA, the goals of the AQUA project, the overall hardware and software design, the basic hardware and sensor packages that have been developed, and some initial experiments. The robot is based on the RHex hexapod robot and uses a suite of sensing technologies, primarily based on computer vision and INS, to allow it to navigate and map clear shallow-water environments. The sensor-based navigation and mapping algorithms are based on the use of both artificial floating visual and acoustic landmarks as well as on naturally occurring underwater landmarks and trinocular stereo.

A focused crawler is designed to traverse the Web to gather documents on a specific topic. It is not an easy task to predict which links lead to good pages. In this paper, we present a new approach for prediction of the important links to relevant pages based on a learned user model. In particular, we first collect pages that a user visits during a learning session, where the user browses the Web and specifically marks which pages she is interested in. We then examine the semantic content of these pages to construct a concept graph, which is used to learn the dominant content and link structure leading to target pages using a Hidden Markov Model (HMM). Experiments show that with learned HMM from a user's browsing, the crawling performs better than Best-First strategy.

In this paper we present a probabilistic framework for the reduction in the uncertainty of a moving robot pose during exploration by using a second robot to assist. A Monte Carlo Simulation technique (specifically, a Particle Filter) is employed in order to model and reduce the accumulated odometric error. Furthermore, we study the requirements to obtain an accurate yet timely pose estimate. A team of two robots is employed to explore an indoor environment in this paper, although several aspects of the approach have been extended to larger groups. The concept behind our exploration strategy has been presented previously and is based on having one robot carry a sensor that acts as a "robot tracker" to estimate the position of the other robot. By suitable use of the tracker as an appropriate motion-control mechanism we can sweep areas of free space between the stationary and the moving robot and generate an accurate graph-based description of the environment. This graph is used to guide the exploration process. Complete exploration without any overlaps is guaranteed as a result of the guidance provided by the dual graph of the spatial decomposition (triangulation) of the environment. We present experimental results from indoor experiments in our laboratory and from more complex simulated experiments.

This paper presents a first detailed case study of collaborative exploration of a substantial environment. We use a pair of cooperating robots to test multi-robot environment mapping algorithms based on triangulation of free space. The robots observe one another using a robot tracking sensor based on laser range sensing (LIDAR). The environment mapping itself is accomplished using sonar sensing. The results of this mapping are compared to those obtained using scanning laser range sensing and the scan matching algorithm. We show that with appropriate outlier rejection policies, the sonar-based map obtained using collaborative localization can be as good or, in fact, better than that obtained using what is typically considered to be a superior sensing technology.

This paper examines the tradeoffs between different classes of sensing strategy and motion control strategy in the context of terrain mapping with multiple robots. We consider a larger group of robots that can mutually estimate one another's position (in 2D or 3D) and uncertainty using a sample-based (particle filter) model of uncertainty. Our prior work has dealt with a pair of robots that estimate one another's position using visual tracking and coordinated motion. Here we extend these results and consider a richer set of sensing and motion options. In particular, we focus on issues related to confidence estimation for groups of more than two robots.

We propose an approach for matching distorted and possibly occluded shapes using dynamic programming (DP). We distinguish among various cases of matching such as cases where the shapes are scaled with respect to each other and cases where an open shape matches the whole or only a part of another open or closed shape. Our algorithm treats noise and shape distortions by allowing matching of merged sequences of consecutive small segments in a shape with larger segments of another shape, while being invariant to translation, scale, orientation, and starting point selection. We illustrate the effectiveness of our algorithm in retrieval of shapes on two data sets of two-dimensional open and closed shapes of marine life species. We demonstrate the superiority of our approach over traditional approaches to shape matching and retrieval based on Fourier descriptors and moments. We also compare our method with SQUID, a well-known method which is available on the Internet. Our evaluation is based on human relevance judgments following a well-established methodology from the information retrieval field.

We present a robust and portable visual-based skin and face detection system developed for use in a multiple speaker teleconferencing system, employing both audio and video cues. An omni-directional video sensor is used to provide a view of the entire visual hemisphere, thereby allowing for multiple dynamic views of all the participants. Regions of skin are detected using simple statistical methods, along with histogram color models for both skin and non-skin color classes. Regions of skin belonging to the same person are grouped together, and using simple spatial properties, the position of each person's face is inferred. Preliminary results suggest the system is capable of detecting human faces present in an omni-directional image despite the poor resolution inherent with such an omni-directional sensor.

We examine the problem of learning a visual map of the environment while maintaining an accurate pose estimate. Our approach is based on using two robots in a simple collaborative scheme. Without outside information, as a robot collects training images, its position estimate accumulates errors, thus corrupting its knowledge of the positions from which observations are taken. We address this problem by deploying a second robot to observe the first one as it explores, thereby establishing a virtual tether, and enabling an accurate estimate of the robot's position while it constructs the map. We refer to this process as cooperative localization. The images collected during this process are assembled into a representation that allows vision-based position estimation from a single image at a later date. In addition to developing a formalism and concept, we validate our results experimentally and present quantitative results demonstrating the performance of the method in over 90 trials.

We propose an approach for matching deformed and occluded shapes using dynamic programming. Our algorithms handle noise and shape distortions by allowing matching of merged sequences of consecutive small segments in a shape, with larger segments of another shape, while being invariant to translation, scale and orientation transformations of shapes. We illustrate the effectiveness of our algorithms in retrieval of shapes on two different two-dimensional datasets: one of static hand gesture shapes and another of marine life shapes.

This paper presents a new sensing modality and stratagem for multirobot exploration. The approach is based on using pairs of robots that observe each other's behavior, acting in concert to reduce odometry errors. We assume the robots can both directly sense nearby obstacles and see each other. This allows the robots to obtain a map of higher accuracy than would be possible with robots acting independently by reducing inaccuracies that occur over time from dead reckoning errors. Furthermore, by exploiting the ability of the robots to see each other, we can detect opaque obstacles in the environment independently of their surface reflectance properties. Two different algorithms, based on the size of the environment, are introduced with a complexity analysis, and experimental results in simulation and with real robots.

We propose a shape matching algorithm for deformed shapes based on dynamic programming. Our algorithm is capable of grouping together segments at finer scales in order to come up with appropriate correspondences with segments at coarser scales. We illustrate the effectiveness of our algorithm in retrieval of shapes by content on two different two-dimensional (2-D) datasets, one of static hand gesture shapes and another of marine life shapes. We also demonstrate the superiority of our approach over traditional approaches to shape matching and retrieval, such as Fourier descriptors and geometric and sequential moments. Our evaluation is based on human relevance judgments following a well-established methodology from the information retrieval field.

We consider the problem of consistent range data registration in modeling an unknown environment. The problem is expressed as the optimal estimation of pose variables under the maximum likelihood criterion. By treating all the history of robot poses as variables and solving them simultaneously, consistency is enforced. We formulate relative pose constraints from both matched scans and odometry measurements to construct a network of measurements. Then we derive closed-form pose estimates as well as their covariance matrices. Examples of global scan registration using both real and simulated data are presented.

An approach to perception-based position estimation is presented. The approach employs a representation of positional information which is based on a global, curvilinear coordinate system which is grounded in the real world. This coordinate system is spanned by the contours of visible objects and by so-called equidistance lines which are constructed from the object contours. Equidistance lines can be computed from arbitrarily curved contours and do not require an analytical representation of these contours. The main advantage of a spatial representation based on equidistance lines is that it does not depend on the existence of salient spatial features in the environment. Furthermore, the global curvilinear coordinate system allows a straightforward transition between the local frames of reference associated with local perceptions. To estimate the position of a robot vehicle over a sequence of local sensor images requires only a minimal number of object contours to be visible or partially visible in these images and a qualitative correspondence of these object contours to be maintained.

This paper deals with coordinating behaviour in a multi-autonomous robot system. When two or more autonomous robots must interact in order to accomplish some common goal, communication between the robots is essential. Different inter-robot communications strategies give rise to different overall system performance and reliability. After a brief consideration of some theoretical approaches to multiple robot collections, we present concrete implementations of different strategies for convoy-like behaviour. The convoy system is based around two RWI B12 mobile robots and uses only passive visual sensing for inter-robot communication. The issues related to different communication strategies are considered.

We develop two algorithms to register a range scan to a previous scan so as to compute relative robot positions in an unknown environment. The first algorithm is used on matching tangent lines defined on two scans and minimizing a distance function. The second algorithm iteratively establishes correspondences between points in the two scans and then solves the point-to-point least-squares problem to compute the relative pose. Our methods avoid the use of localized features. They work in curved environments and can handle partial occlusions.>

This paper describes research on the ARK (Autonomous Mobile Robot in a Known Environment) project. The technical objective of the project is to build a robot that can navigate and carry out survey/inspection tasks in a complex but known industrial environment. Rather than altering the robots environment by adding easily identifiable beacons the robot relies on naturally occurring objects to use as visual landmarks for navigation. The robot is equipped with various sensors that are used to detect unmapped obstacles, landmarks and objects. This paper describes the robot's industrial environment, it's control architecture, and some results in processing the robot's range and vision sensor data for navigation.>

An approach to motion planning amongst arbitrarily moving unknown objects is presented. As opposed to other approaches to motion planning we avoid the assumption that the motion parameters and the shape of moving objects are known a priori or can be predicted over longer time intervals. By giving up this assumption, traditional methods such as space-time representation and search in space-time no longer apply. Our approach is based on a massively parallel network of simple processing elements. A relaxation process, which is driven by the simultaneous execution of a simple formula in these processing elements, creates a two-dimensional distribution of real numbers, denoted as potentials, which encodes information about collision-free trajectories. Our approach is different from classical algorithmic motion planning in that we do not employ an analytical planning or search algorithm. Instead, desired behaviors, such as the avoidance of moving objects, are achieved through adroit manipulation of the two-dimensional potential distribution.>

A commonly used approach to self-location is for the robot to use point features or landmarks. Landmarks are typically difficult to detect and track with video or range sensors, and hence it is sensible to try to minimize the number of times the robot abandons the tracking of an already detected landmark to detect and pursue another. The problem addressed is how to select the landmarks that the robot is to detect and track over different parts of a given path. Several algorithms with different amounts of flexibility, generality and complexity are proposed. The authors address the uniform cost case (all landmarks have equal cost of detection and tracking), and the weighted cost case (each landmark has its own cost). The case of different sets of landmarks having different utility measures is also treated. The algorithm complexity is low-order polynomial in the number of landmarks k, the number of straight line segments of the path, and the number of shadows cast on the path by each landmark, except when taking into account the usefulness of landmarks in groups, which is exponential in k.

In many cases several mobile robots (autonomous agents) can be used together to accomplish tasks that would be either more difficult or impossible for a robot acting alone. Many different models have been suggested for the makeup of such collections of robots. In this paper the authors present a taxonomy of the different ways in which such a collection of autonomous robotic agents can be structured. It is shown that certain swarms provide little or no advantage over having a single robot, while other swarms can obtain better than linear speedup over a single robot. There exist both trivial and non-trivial problems for which a swarm of robots can succeed where a single robot will fail. Swarms are more than just networks of independent processors - they are potentially reconfigurable networks of communicating agents capable of coordinated sensing and interaction with the environment.

ARK (Autonomous Robot for a Known environment), is a visually-guided mobile robot which is being constructed as part of the Precarn project in mobile robotics. ARK operates in a previously mapped environment and navigates with respect to visual landmarks that have been previously located. While the robot moves, it utilizes an active vision sensor to register the robot with respect to these landmarks. As the landmarks may be scarce in certain regions of its environment, ARK plans paths which minimize both path length and path uncertainty. The global path planner assumes that the robot will use a Kalman filter to integrate landmark information with odometry data to correct path deviations as the robot moves, and then uses this information to choose a path which reduces the expected path deviation.

We present the design of a controllable stereo vision head. TRISH (The Toronto IRIS Stereo Head) is a binocular camera mount, consisting of two fixed focal length color cameras with automatic gain control forming a verging stereo pair. TRISH is capable of version (rotation of the eyes about the vertical axis so as to maintain a constant disparity), vergence (rotation of each eye about the vertical axis so as to change the disparity), pan (rotation of the entire head about the vertical axis), and tilt (rotation of each eye about the horizontal axis). One novel characteristic of the design is that each camera can rotate about its own optical axis (torsion). Torsional movement makes it possible to minimize the vertical component of the two-dimensional search which is associated with stereo processing in verging stereo systems.

In this paper we propose representa- tions of two-dimensional curves that capture curve orientation and spatial occupancy, and we demon- strate their use in two-dimensional contour match- ing. To explicitly represent curve orientation, we generalize the notion of extended circular image to a non-convex curve, by representing such a curve as the sequence of the extended circular images of its convex and concave parts. Evaluating the sim- ilarity of two curves can then be reduced to eval- uating the similarity of corresponding segments by directly correlating their extended circular im- ages. To explicitly represent spatial occupancy in a manner that can be used in shape matching, we blur the two-dimensional binary image obtained from the curve. Two curves that are similar in both shape and size and optimally aligned with respect to each other in both position and orienta- tion will then result in a value close to one of the correlation coefficient obtained from the respec- tive binary images. Empirical results using real data are collected and analyzed, to determine the strength of the resulting technique in practice.

Learning from examples uses specific instances (examples and counterexamples) to produce general rules. It is a convenient learning scheme in cases where the process of interviewing human experts and analyzing and formalizing their decision is very difficult or time consuming. The system proposed is capable of obtaining the rules that fit a set of examples and counterexamples based on the minimal entropy (ME) criterion. The system proposed can also set various parameters of the rule (e.g., thresholds) in such a way that entropy is minimized. The system can also handle incremental learning from examples. Applications of the proposed system to seismic image analysis are included.>

The problem of how to model a given planar curve by local splines defined by a number of knot points which is much smaller than the number of points defining the curve is addressed. To solve the problem an optimization technique is applied that minimizes an error norm, which reflects the discrepancy of the splines to the original curve. The error norm is defined as the total squared distance of the sample points from the local spline model. The objective function for the optimization process is the above error norm plus a term which ensures convergence to the correct solution. The objective function is minimized with respect to a set of independent variables, which are the locations of the knot points defining the local spline model. The initial locations of the knot points are selected heuristically. Experimental results show that the method converges to a solution that compares favorably with previous techniques.>

The authors address the problem of passive acoustic tracking from closest point of approach (CPA) time, amplitude and frequency data at spatially distributed sensors in the case of finite sound propagation delay. A method is presented for the computation of source velocity (speed and direction) from the CPA times at three noncollinear sensors that lie on the same side of the source path. The method reduces the problem to the solution of a linear trigonometric equation, and can be used as the basis for robust localization of a straight source path using a square grid of calibrated sensors. In the case of a maneuvering source, qualitative relations are stated between the local shape of the source path, its relative position with respect to an acoustic sensor, and whether amplitude and frequency increase or decrease monotonically with (source) time at that sensor. These qualitative relations from multiple sensors are then used to segment the source path into straight and maneuvering segments (under negligible propagation delay).>

Addressed is the problem of robotic exploration of a graphlike world, where no distance or orientation metric is assumed of the world. The robot is assumed to be able to autonomously traverse graph edges, recognize when it has reached a vertex, and enumerate edges incident upon the current vertex relative to the edge via which it entered the current vertex. The robot cannot measure distances, and it does not have a compass. It is demonstrated that this exploration problem is unsolvable in general without markers, and, to solve it, the robot is equipped with one or more distinct markers that can be put down or picked up at will and that can be recognized by the robot if they are at the same vertex as the robot. An exploration algorithm is developed and proven correct. Its performance is shown on several example worlds, and heuristics for improving its performance are discussed.>

In this paper we solve the problem of reconstructing a color image from sparse, noisy, and nonuniformly distributed color measurements. We apply a method for reconstructing a surface from sparse depth measurements to each of the R, G and B components of the color data, by treating each as a surface, with depth measurements being the R, G and B values. We apply this method to the reconstruction of nonuniformly distributed sparse color data from even 12.5% of the pixels, if no discontinuities are given and from 6.25% of the pixels, if the discontinuities are given. Also we present results of reconstructing a corrupted version of the original image with Gaussian noise of zero-mean and standard deviation 30 from 25% of the data, for color levels between 0 and 255. The applicability of the method is independent of the choice of the color space used.

The problem of matching range images of human faces for the purpose of establishing a correspondence between similar features of two faces is addressed. Distinct facial features correspond to convex regions of the range image of the face, which is obtained by a segmentation of the range image based on the sign of the mean and Gaussian curvature at each point. Each convex region is represented by its extended Gaussian image, a 1-1 mapping between points of the region and points on the unit sphere that have the same normal. Several issues are examined that are associated with the difficult problem of interpolation of the values of the extended Gaussian image and its representation. A similarity measure between two regions is obtained by correlating their extended Gaussian images. To establish the optimal correspondence, a graph matching algorithm is applied. It uses the correlation matrix between convex regions of the two faces and incorporates additional relational constraints that account for the relative spatial locations of the convex regions in the domain of the range image.>

Describes the design and implementation of an automated system for interpreting impulse radar signals for ice thickness profiling. The authors have adopted an integrated approach which includes numeric computation in the form of deconvolution filtering with rule-based classification of signal features at multiple levels. Noise reduction and deconvolution techniques are used to enhance the radar signals for better resolution of overlapping events. Motivated by human perceptual (visual) knowledge, a hierarchy of data structures is constructed as representations of signal characteristics at various levels of abstraction. Classification rules, based on the protocols collected from an expert, physical constraints on the helicopter motion and the nature of the radar signals are used to produce the current signal interpretation. A prototype system has been implemented on the Symbolics Lisp Machine and tested on real data.>

The problem of matching two smooth closed contours which are related by deformations that alter their curvature structure is discussed. Deformations typically include protrusions, a result of internal resistance, and indentations, a result of squashing. The author's algorithm establishes correspondences between segments that have not drastically deformed (in the sense of introducing or eliminating protrusions and indentations), and recovers productions that explain how the remaining segments have deformed. Criteria involving metric information, such as the correlation between extended circular images of segments of constant curvature sign, are imposed to select the preferred interpretation.>

Interpretation of deforming shapes involves the qualitative description of deformation. A new representation of a closed 2D shape is introduced as a cyclic sequence of the extended circular images of the convex and concave segments of its contour. A measure of similarity between two segments that accounts for both shape and orientation is defined that depends on the correlation coefficient of their extended circular images. Dynamic programming based on this similarity measure is used to establish correspondences between segments of the two contours. Finally, a qualitative description of the deformation between the two shapes is computed by accounting for unassociated segments via curvature processes. The result is shown of the application of the deformation recovery scheme to dynamic cloud silhouette analysis using hand-traced input from real satellite images.

Many signal-processing systems can be viewed as transforming their input signals into a representation of the real-world scenario from which the signals originated. Such systems usually have parameters whose settings are selected on the basis of the class of expected input scenarios. Finding the appropriate parameter settings for a class of input scenarios usually involves testing the system against typical and/or important input scenarios from that class. Whenever the system output does not match the input scenario, the parameter settings responsible for the fault are identified. The system user can then adjust the system parameters to ensure correct system behavior for such scenarios. The diagnostic process of identifying the parameters responsible for system faults is generally difficult because the signal-processing system carries out a complicated mathematical transformation involving a multistage algorithm that generates an enormous amount of intermediate data. A new approach to the diagnosis of such systems is developed. The approach is based on the availability of an abstract and possibly qualitative description of the input scenario and the use of an alternative system model derived from the underlying mathematical theory that explicitly represents the phenomena responsible for any incorrect processing. This approach to diagnosis models a system as a combination of processes that transform the user-specified abstract description of the input scenario into the system output. Whenever the correct answer is obtained at the system output, each process reduces to an identity transformation at the level of abstraction of the system output.

Signal processing systems usually have parameters whose settings are selected on the basis of the class of expected input signals. Finding the appropriate parameter settings for a class of inputs usually involves testing the system against typical and/or important inputs from that class. Whenever the system produces an incorrect output, the parameter settings responsible for the fault are identified. The system user can then adjust the system parameters in order to ensure correct system behavior. The diagnostic process of identifying the parameters responsible for system faults is generally difficult because the signal processing system carries out a complicated mathematical transformation involving a multi-stage algorithm that generates an enormous amount of intermediate data. We develop a new approach to the diagnosis of such systems. The approach is based on the availability of an abstract and possibly qualitative description of the input scenario and the use of an alternative system model derived from the underlying mathematical theory that explicitly represents the phenomena responsible for any incorrect processing.

A signal processing system which integrates signal and symbol processing was designed and initial implementation experiments were performed. The system design was derived from the systematic observation (protocol collection) and analysis of human signal processing activity. The resulting system consists of (i) expert rules, which process symbolic representations of signal characteristics at various levels of abstraction, and (ii) signal processing operators, which are invoked by the rules to extract signal features. This design parallels the apparent operational mode of a human analyst. The signal processing operators include those used by the human expert (e.g. FFT) and others that perform perceptual feature extraction normally done by the expert while reviewing plots of numeric algorithmic outputs. In comparison to previous signal/symbol processing systems, which relied mostly on symbol processing, our system is based on the concept that a small amount of planned signal processing can save a lot of symbol processing.

A fast algorithm with reduced memory requirements for updating in time the covariance autoregressive model of a time series with constant memory is proposed. The "algorithm is derived using elementary linear algebra concepts and manipulations and is based on the special structure of the covariance matrix characterizing the underlying linear equations. The algorithm is extended to updating the all-zero (or all-pole) least-squares model of a system, computed from its input and output signals.

Recent work has demonstrated the perceptual importance of the long-time phase of speech. In this paper, the possibility of using the long-time phase of the LPC residual signal in speech synthesis is investigated. The perceptual importance of the various parts of the long-time spectrum of the residual is also suggested.

The purpose of this paper is to give reduced complexity algorithms in order to compute linear models in situations of non-stationnary signals. The case of impulse response identification is examined as well as the case of pure AR-modeling. Both problems lead to a linear system which must be solved to give the unknown AR-model or the unknown impulse response. Furthermore the linear systems that occur in both cases have an identical left hand side member characterized by a symmetric matrix having the supplementary property of being the product of two non-symmetric Toeplitz matrices. The "near to Toeplitz" structure of this matrix permits the fast solution of the system with specially adapted algorithms to this situation. Many properties of the near to Toeplitz matrices are outlined as the key formulas for the derivation of all fast schemes. Order, time and order-time recursive methods are derived using a unified theoretical framework. The methodology used here is similar to that used by Morf et al. The algorithms presented are new and can be converted to efficient and automated computer packages.