Massive Open Online Courses are becoming popular educational vehicles through which universities reach out to non-traditional audiences. Many enrolees hail from other countries and cultures, and struggle to cope with the English language in which these courses are invariably offered. Moreover, most such learners have a strong desire and motivation to extend their knowledge of academic English, particularly in the specific area addressed by the course. Online courses provide a compelling opportunity for domain-specific language learning. They supply a large corpus of interesting linguistic material relevant to a particular area, including supplementary images (slides), audio and video. We contend that this corpus can be automatically analysed, enriched, and transformed into a resource that learners can browse and query in order to extend their ability to understand the language used, and help them express themselves more fluently and eloquently in that domain. To illustrate this idea, an existing online corpus-based language learning tool (FLAX) is applied to a Coursera MOOC entitled Virology 1: How Viruses Work, offered by Columbia University.

Document similarity measures are crucial components of many text‐analysis tasks, including information retrieval, document classification, and document clustering. Conventional measures are brittle: They estimate the surface overlap between documents based on the words they mention and ignore deeper semantic connections. We propose a new measure that assesses similarity at both the lexical and semantic levels, and learns from human judgments how to combine them by using machine‐learning techniques. Experiments show that the new measure produces values for documents that are more consistent with people's judgments than people are with each other. We also use it to classify and cluster large document sets covering different genres and topics, and find that it improves both classification and clustering performance.

Summary form only given. With petascale systems becoming broadly available in high end computing, attention is now focused on the challenges associated with the next major performance milestone: exascale computing. Demand for computational capability grows unabated, with areas of national and commercial interest including global climate change, alternative energy sources, defense and medicine, as well as basic science. Past growth in the high end has relied on a combination of faster clock speeds and larger systems, but the clock speed benefits of Moore's Law have ended, and 200-cabinet petascale machines are near a practical limit. Future system designs will instead be constrained by power density and total system power demand, resulting in radically different architectures. The challenges associated with exascale computing will require broad research activities across computer science, including the development of new algorithms, programming models, system software and computer architecture.

Wikipedia is a goldmine of information; not just for its many readers, but also for the growing community of researchers who recognize it as a resource of exceptional scale and utility. It represents a vast investment of manual effort and judgment: a huge, constantly evolving tapestry of concepts and relations that is being applied to a host of tasks. This talk focuses on the process of ”wikification”; that is, automatically and judiciously augmenting a plain-text document with pertinent hyperlinks to Wikipedia articlesas though the document were itself a Wikipedia article. I first describe how Wikipedia can be used to determine semantic relatedness between concepts. Then I explain how to wikify documents by exploiting Wikipedia’s internal hyperlinks for relational information and their anchor texts as lexical information. Data mining techniques are used throughout to optimize the models involved.

This paper describes how to automatically cross-reference documents with Wikipedia: the largest knowledge base ever known. It explains how machine learning can be used to identify significant terms within unstructured text, and enrich it with links to the appropriate Wikipedia articles. The resulting link detector and disambiguator performs very well, with recall and precision of almost 75%. This performance is constant whether the system is evaluated on Wikipedia articles or "real world" documents.

Wikipedia has been applied as a background knowledge base to various text mining problems, but very few attempts have been made to utilize it for document clustering. In this paper we propose to exploit the semantic knowledge in Wikipedia for clustering, enabling the automatic grouping of documents with similar themes. Although clustering is intrinsically unsupervised, recent research has shown that incorporating supervision improves clustering performance, even when limited supervision is provided. The approach presented in this paper applies supervision using active learning. We first utilize Wikipedia to create a concept-based representation of a text document, with each concept associated to a Wikipedia article. We then exploit the semantic relatedness between Wikipedia concepts to find pair-wise instance-level constraints for supervised clustering, guiding clustering towards the direction indicated by the constraints. We test our approach on three standard text document datasets. Empirical results show that our basic document representation strategy yields comparable performance to previous attempts; and adding constraints improves clustering performance further by up to 20%.

Abstract Keyphrases are widely used in both physical and digital libraries as a brief, but precise, summary of documents. They help organize material based on content, provide thematic access, represent search results, and assist with navigation. Manual assignment is expensive because trained human indexers must reach an understanding of the document and select appropriate descriptors according to defined cataloging rules. We propose a new method that enhances automatic keyphrase extraction by using semantic information about terms and phrases gleaned from a domain‐specific thesaurus. The key advantage of the new approach is that it performs well with very little training data. We evaluate it on a large set of manually indexed documents in the domain of agriculture, compare its consistency with a group of six professional indexers, and explore its performance on smaller collections of documents in other domains and of French and Spanish documents.

This paper describes Koru, a new search interface that offers effective domain-independent knowledge-based information retrieval. Koru exhibits an understanding of the topics of both queries and documents. This allows it to (a) expand queries automatically and (b) help guide the user as they evolve their queries interactively. Its understanding is mined from the vast investment of manual effort and judgment that is Wikipedia. We show how this open, constantly evolving encyclopedia can yield inexpensive knowledge structures that are specifically tailored to expose the topics, terminology and semantics of individual document collections. We conducted a detailed user study with 12 participants and 10 topics from the 2005 TREC HARD track, and found that Koru and its underlying knowledge base offers significant advantages over traditional keyword search. It was capable of lending assistance to almost every query issued to it; making their entry more efficient, improving the relevance of the documents they return, and narrowing the gap between expert and novice seekers.

We describe an algorithm that detects a lack of correspondence between speech and lip motion by detecting and monitoring the degree of synchrony between live audio and visual signals. It is simple, effective, and computationally inexpensive; providing a useful degree of robustness against basic replay attacks and against speech or image forgeries. The method is based on a cross-correlation analysis between two streams of features, one from the audio signal and the other from the image sequence. We argue that such an algorithm forms an effective first barrier against several kinds of replay attack that would defeat existing verification systems based on standard multimodal fusion techniques. In order to provide an evaluation mechanism for the new technique we have augmented the protocols that accompany the BANCA multimedia corpus by defining new scenarios. We obtain 0% equal-error rate (EER) on the simplest scenario and 35% on a more challenging one

Domain-specific thesauri are high-cost, high-maintenance, high-value knowledge structures. We show how the classic thesaurus structure of terms and links can be mined automatically from Wikipedia. In a comparison with a professional thesaurus for agriculture we find that Wikipedia contains a substantial proportion of its concepts and semantic relations; furthermore it has impressive coverage of contemporary documents in the domain. Thesauri derived using our techniques capitalize on existing public efforts and tend to reflect contemporary language usage better than their costly, painstakingly-constructed manual counterparts

UNLABELLED: The Weka machine learning workbench provides a general-purpose environment for automatic classification, regression, clustering and feature selection-common data mining problems in bioinformatics research. It contains an extensive collection of machine learning algorithms and data pre-processing methods complemented by graphical user interfaces for data exploration and the experimental comparison of different machine learning techniques on the same problem. Weka can process data given in the form of a single relational table. Its main objectives are to (a) assist users in extracting useful information from data and (b) enable them to easily identify a suitable algorithm for generating an accurate predictive model from it. AVAILABILITY: http://www.cs.waikato.ac.nz/ml/weka.

‘Familiar’ is a tool that helps end-users automate iterative tasks in their applications by showing examples of what they want to do. It observes the user's actions, predicts what they will do next, and then offers to complete their task. Familiar learns in two ways. First, it creates a model, based on data gathered from training tasks, that selects the best prediction from among several candidates. Experiments show that decision trees outperform heuristic methods, and can be further improved by incrementally updating the classifier at task time. Second, it uses decision stumps inferred from analogous examples in the event trace to predict the parameters of conditional rules. Because data is sparse—for most users balk at giving more than a few training examples—permutation tests are used to calculate the statistical significance of each stump, successfully eliminating bias towards attributes with many different values.

This paper is about inferring markup information, a generalization of part-of-speech tagging. We use compression models based on a marked-up training corpus and apply them to fresh, unmarked, text. In effect, this technique builds filters that extract information from text in a way that is generalized because it depends on training text rather than preprogrammed heuristics. As illustrated, we use SGML tags to represent the extracted information. However, we work in a more controlled textual environment: we use bibliographic text rather than plain English and mark up entities such as author, date, and titles rather than syntactic parts of speech. Such entities are generically called "metadata"-data about data-and form an important component of the information present in a bibliography. The aim of our work is to automatically enhance bibliographies with metadata tags, based on a training corpus of annotated bibliography entries.

Summary form only given. Test categorization is the assignment of natural language texts to predefined categories based on their concept. The use of predefined categories implies a "supervised learning" approach to categorization, where already-classified articles which effectively define the categories are used as "training data" to build a model that can be used for classifying new articles that comprise "the data". Typical approaches extract features from articles and use the feature vectors as input to a machine learning scheme that learns how to classify articles. The features are generally words. It has often been observed that compression seems to provide a very promising alternative approach to categorization. The overall compression of an article with respect to different models can be compared to see which one it fits most closely. Such a scheme has several potential advantages: it yields an overall judgement on the document as a whole, rather than discarding information by pre-selecting features it avoids the messy and rather artificial problem of defining word boundaries; it deals uniformly with morphological variants of words; depending on the model (and its order), it can take account of phrasal effects that span word boundaries; it offers a uniform way of dealing with different types of documents for example, arbitrary files in a computer system; it generally minimizes arbitrary decisions that inevitably need to be taken to render any learning scheme practical.

Summary form only given. Finding acronyms and their definitions in free text is useful for many purposes. We have developed a new method that uses several PPM models to encode the acronym in terms of its definition. Four different attributes of each acronym are encoded using a PPMD order 5 model: (a) whether the acronym occurred before or after its definition (direction); (b) the distance between the acronym and the definition (first-word offset); (c) the pattern of words in the definition with letters in the acronym (subsequent-word offsets); and (d) the number of letters taken from each of those words. These models, taken together, give a complete encoding of the acronym in terms of its definition. The models were trained on 1080 acronyms extracted from 150 documents. A model of plain text was trained using 100 independent documents from the same collection.

Chinese is written without using spaces or other word delimiters. Although a text may be thought of as a corresponding sequence of words, there is considerable ambiguity in the placement of boundaries. Interpreting a text as a sequence of words is beneficial for some information retrieval and storage tasks: for example, full-text search, word-based compression, and keyphrase extraction. We describe a scheme that infers appropriate positions for word boundaries using an adaptive language model that is standard in text compression. It is trained on a corpus of presegmented text, and when applied to new text, interpolates word boundaries so as to maximize the compression obtained. This simple and general method performs well with respect to specialized schemes for Chinese language segmentation.

Abstract. Despite its simplicity, the naive Bayes learning scheme performs well on most classification tasks, and is often significantly more accurate than more sophisticated methods. Although the probability estimates that it produces can be inaccurate, it often assigns maximum probability to the correct class. This suggests that its good performance might be restricted to situations where the output is categorical. It is therefore interesting to see how it performs in domains where the predicted value is numeric, because in this case, predictions are more sensitive to inaccurate probability estimates. This paper shows how to apply the naive Bayes methodology to numeric prediction (i.e., regression) tasks by modeling the probability distribution of the target value with kernel density estimators, and compares it to linear regression, locally weighted linear regression, and a method that produces “model trees”—decision trees with linear regression functions at the leaves. Although we exhibit an artificial dataset for which naive Bayes is the method of choice, on real-world datasets it is almost uniformly worse than locally weighted linear regression and model trees. The comparison with linear regression depends on the error measure: for one measure naive Bayes performs similarly, while for another it is worse. We also show that standard naive Bayes applied to regression problems by discretizing the target value performs similarly badly. We then present empirical evidence that isolates naive Bayes ’ independence assumption as the culprit for its poor performance in the regression setting. These results indicate that the simplistic statistical assumption that naive Bayes makes is indeed more restrictive for regression than for classification.

Hierarchical dictionary-based compression schemes form a grammar for a text by replacing each repeated string with a production rule. While such schemes usually operate on-line, making a replacement as soon as repetition is detected, off-line operation permits greater freedom in choosing the order of replacement. In this paper, we compare the on-line method with three off-line heuristics for selecting the next substring to replace: longest string first, most common string first, and the string that minimizes the size of the grammar locally. Surprisingly, two of the off-line techniques, like the on-line method, run in time linear in the size of the input. We evaluate each technique on artificial and natural sequences. In general, the locally-most-compressive heuristic performs best, followed by most frequent, the on-line technique, and, lagging by some distance, the longest-first technique.

New methods of acquiring structural information in text documents may support better compression by identifying an appropriate prediction context for each symbol. The method of “lexical attraction” infers syntactic dependency structures from statistical analysis of large corpora. We describe the generation of a lexical attraction model, discuss its application to text compression, and explore its potential to outperform fixed-context models such as word-level PPM. Perhaps the most exciting aspect of this work is the prospect of using compression as a metric for structure discovery in text.

Life is based on two polymers, DNA and protein, whose properties can be described in a simple text file. It is natural to expect that standard text compression techniques would work on biological sequences as they do on English text. But biological sequences have a fundamentally different structure from linguistic ones, and standard compression schemes exhibit disappointing performance on them. We describe a new approach to compression that takes account of the underlying biochemical principles. This gives rise to a generalization of blending for statistical compressors where every context is used, weighted by its similarity to the current context. Results support what research in bioinformatics has shown, that there is little Markov dependency in protein. This cripples data compression schemes and reduces them to order zero models.

Data mining, a burgeoning new technology, is about looking for patterns in data. Likewise, text mining is about looking for patterns in text. Text mining is possible because you do not have to understand text in order to extract useful information from it. Here are four examples. First, if only names could be identified, links could be inserted automatically to other places that mention the same name, links that are "dynamically evaluated" by calling upon a search engine to bind them at click time. Second, actions can be associated with different types of data, using either explicit programming or programming-by-demonstration techniques. A day/time specification appearing anywhere within one's E-mail could be associated with diary actions such as updating a personal organizer or creating an automatic reminder, and each mention of a day/time in the text could raise a popup menu of calendar-based actions. Third, text could be mined for data in tabular format, allowing databases to be created from formatted tables such as stock-market information on Web pages. Fourth, an agent could monitor incoming newswire stories for company names and collect documents that mention them, an automated press clipping service. This paper aims to promote text compression as a key technology for text mining.

Stacked generalization is a general method of using a high-level model to combine lower-level models to achieve greater predictive accuracy. In this paper we address two crucial issues which have been considered to be a `black art' in classification tasks ever since the introduction of stacked generalization in 1992 by Wolpert: the type of generalizer that is suitable to derive the higher-level model, and the kind of attributes that should be used as its input. We find that best results are obtained when the higher-level model combines the confidence (and not just the predictions) of the lower-level ones. We demonstrate the effectiveness of stacked generalization for combining three different types of learning algorithms for classification tasks. We also compare the performance of stacked generalization with majority vote and published results of arcing and bagging.

Text compression by inferring a phrase hierarchy from the input is a technique that shows promise as a compression scheme and as a machine learning method that extracts some comprehensible account of the structure of the input text. Its performance as a data compression scheme outstrips other dictionary schemes, and the structures that it learns from sequences have been put to such eclectic uses as phrase browsing in digital libraries, music analysis, and inferring rules for fractal images. We focus attention on the memory requirements of the method. Since the algorithm operates in linear time, the space it consumes is at most linear with input size. The space consumed does in fact grow linearly with the size of the inferred hierarchy, and this makes operation on very large files infeasible. We describe two elegant ways of curtailing the space complexity of hierarchy inference, one of which yields a bounded space algorithm. We begin with a review of the hierarchy inference procedure that is embodied in the SEQUITUR program. Then we consider its performance on quite large files, and show how the compression performance improves as the file size increases.

We outline the need for search engines to provide user feedback on the expected time for a query, describe a scheme for learning a model of query time by observing sample queries, and discuss the results obtained for a set of actual user queries on a document collection using the MG search engine.

Researchers in machine learning primarily use decision trees, production rules, and decision graphs for visualizing classification data, with the graphic form in which a structure is portrayed as having a strong influence on comprehensibility. We analyze the questions that, in our experience, end users of machine learning tend to ask of the structures inferred from their empirical data. By mapping these questions onto visualization tasks, we have created new graphical representations that show the flow of examples through a decision structure. These knowledge visualization techniques are particularly appropriate in helping to answer the questions that users typically ask, and we describe their use in discovering new properties of a data set. In the case of decision trees, an automated software tool has been developed to construct the visualizations.

We show how to extract plain text from PostScript files. A textual scan is inadequate because PostScript interpreters can generate characters on the page that do not appear in the source file. Furthermore, word and line breaks are implicit in the graphical rendition, and must be inferred from the positioning of word fragments. We present a robust technique for extracting text and recognizing words and paragraphs. The method uses a standard PostScript interpreter but redefines several PostScript operators, and simple heuristics are employed to locate word and line breaks. The scheme has been used to create a full-text index, and plain-text versions, of 40,000 technical reports (34 Gbytes of PostScript). Other text-extraction systems are reviewed: none offer the same combination of robustness and simplicity. © 1998 John Wiley & Sons, Ltd.

Over the last decade, arithmetic coding has emerged as an important compression tool. It is now the method of choice for adaptive coding on myltisymbol alphabets because of its speed, low storage requirements, and effectiveness of compression. This article describes a new implementation of arithmetic coding that incorporates several improvements over a widely used earlier version by Witten, Neal, and Cleary, which has become a de facto standard. These improvements include fewer multiplicative operations, greatly extended range of alphabet sizes and symbol probabilities, and the use of low-precision arithmetic, permitting implementation by fast shift/add operations. We also describe a modular structure that separates the coding, modeling, and probability estimation components of a compression system. To motivate the improved coder, we consider the needs of a word-based text compression program. We report a range of experimental results using this and other models. Complete source code is available.

Data compression and learning are, in some sense, two sides of the same coin. If we paraphrase Occam's razor by saying that a small theory is better than a larger theory with the same explanatory power, we can characterize data compression as a preoccupation with small, and learning as a preoccupation with better. Nevill-Manning et al. (see Proc. Data Compression Conference, Los Alamitos, CA, p.244-253, 1994) presented an algorithm, since dubbed SEQUITUR, that presents both faces of the compression/learning coin. Its performance as a data compression scheme outstrips other dictionary schemes, and the structures that it learns from sequences as diverse as DNA and music are intuitively compelling. We present three new results that characterize SEQUITUR's computational and compression performance. First, we prove that SEQUITUR operates in time linear in n, the length of the input sequence, despite its ability to build a hierarchy as deep as log(n). Second, we show that a sequence can be compressed incrementally, improving on the non-incremental algorithm that was described by Nevill-Manning et al., and making on-line compression feasible. Third, we present an intriguing result that emerged during benchmarking; whereas PPMC outperforms SEQUITUR on most files in the Calgary corpus, SEQUITUR regains the lead when tested on multimegabyte sequences. We make some tentative conclusions about the underlying reasons for this phenomenon, and about the nature of current compression benchmarking.

This paper describes a system that uses visualisation to assist a user in dealing with the information returned from a search engine. The user's queries, and the documents they return, are represented by a 3D spatial structure that shows their relationships and provides a way of accessing and exploring the documents retrieved. It is implemented to work with the New Zealand Digital Library, a set of large document collections that is available over the Web. The visualisation scheme is a Java applet that is updated dynamically whenever the user makes a new search, and can be browsed alongside the search engine.

SEQUITUR is an algorithm that infers a hierarchical structure from a sequence of discrete symbols by replacing repeated phrases with a grammatical rule that generates the phrase, and continuing this process recursively. The result is a hierarchical representation of the original sequence, which offers insights into its lexical structure. The algorithm is driven by two constraints that reduce the size of the grammar, and produce structure as a by-product. SEQUITUR breaks new ground by operating incrementally. Moreover, the method's simple structure permits a proof that it operates in space and time that is linear in the size of the input. Our implementation can process 50,000 symbols per second and has been applied to an extensive range of real world sequences.

Arithmetic coding for data compression has gained widespread acceptance as the right method for optimum compression when used with a suitable source model. A technique to implement error detection as part of the arithmetic coding process is described. Heuristic arguments are given to show that a small amount of extra redundancy can be very effective in detecting errors very quickly, and practical tests confirm this prediction.

Most bi-level images stored on computers today comprise scanned text, and are stored using generic bi-level image technology based either on classical run-length coding, such as the CCITT Group 4 method, or on modern schemes such as JBIG that predict pixels from their local image context. However, image compression methods that are tailored specifically for images known to contain printed text can provide noticeably superior performance because they effectively enlarge the context to the character level, at least for those predictions for which such a context is relevant. To deal effectively with general documents that contain text and pictures, it is necessary to detect layout and structural information from the image, and employ different compression techniques for different parts of the image. The authors extend previous work in document image compression in two ways. First, we include automatic discrimination between text and non-text zones in an image. Second, the system is tested on a large real-world image corpus.

This paper takes a compression scheme that infers a hierarchical grammar from its input, and investigates its application to semi-structured text. Although there is a huge range and variety of data that comes within the ambit of "semi-structured", we focus attention on a particular, and very large, example of such text. Consequently the work is a case study of the application of grammar-based compression to a large-scale problem. We begin by identifying some characteristics of semi-structured text that have special relevance to data compression. We then give a brief account of a particular large textual database, and describe a compression scheme that exploits its structure. In addition to providing compression, the system gives some insight into the structure of the database. Finally we show how the hierarchical grammar can be generalized, first manually and then automatically, to yield further improvements in compression performance.

The prediction by partial matching (PPM) data compression scheme has set the performance standard in lossless compression of text throughout the past decade. The original algorithm was first published in 1984 by Cleary and Witten, and a series of improvements was described by Moffat (1990), culminating in a careful implementation, called PPMC, which has become the benchmark version. This still achieves results superior to virtually all other compression methods, despite many attempts to better it. PPM, is a finite-context statistical modeling technique that can be viewed as blending together several fixed-order context models to predict the next character in the input sequence. Prediction probabilities for each context in the model are calculated from frequency counts which are updated adaptively; and the symbol that actually occurs is encoded relative to its predicted distribution using arithmetic coding. The paper describes a new algorithm, PPM*, which exploits contexts of unbounded length. It reliably achieves compression superior to PPMC, although our current implementation uses considerably greater computational resources (both time and space). The basic PPM compression scheme is described, showing the use of contexts of unbounded length, and how it can be implemented using a tree data structure. Some results are given that demonstrate an improvement of about 6% over the old method.

During its long gestation in the 1970s and early 1980s, arithmetic coding was widely regarded more as an academic curiosity than a practical coding technique. One factor that helped it gain the popularity it enjoys today was the publication in 1987 of source code for a multi symbol arithmetic coder in Communications of the ACM. Now (1995), our understanding of arithmetic coding has further matured, and it is timely to review the components of that implementation and summarise the improvements that we and other authors have developed since then. We also describe a novel method for performing the underlying calculation needed for arithmetic coding. Accompanying the paper is a "Mark II" implementation that incorporates the improvements we suggest. The areas examined include: changes to the coding procedure that reduce the number of multiplications and divisions and permit them to be done to low precision; the increased range of probability approximations and alphabet sizes that can be supported using limited precision calculation; data structures for support of arithmetic coding on large alphabets; the interface between the modelling and coding subsystems; the use of enhanced models to allow high performance compression. For each of these areas, we consider how the new implementation differs from the CACM package.

We have built some simple, but useful, cooperative artificial life agents. Based on this experience and by contrasting our work with computer viruses, we argue that artificial life (the simulation of life including evolution) can only remain reliably and indefinitely cooperative if it adheres to explicitly-specified social conventions. Breaking or neglecting these conventions results in systems that are worse than useless; in fact, malicious with respect to human social values.>

Textual image compression is a method of both lossy and lossless image compression that is particularly effective for images containing repeated sub-images, notably pages of text. This paper addresses the problem of pattern comparison by using an information or compression based approach. Following Mohiuddin et al. ( 1984), the authors use the amount of uncertainty or entropy between marks as the criterion for the matching process. The entropy model they use is the context-based compression model proposed by Langdon and Rissanen (1981) and further developed by Moffat (1991). There are two principal issues to investigate when studying template matching methods: their susceptibility to different kinds of noise, and how they respond to errors in the initial registration. Because of the computation-intensive nature of the comparison operation, many schemes have been devised to pre-filter or screen the marks in advance to determine those that will surely fail the match. They present a novel method of screening which uses a quad-tree decomposition and finds local centroids at each tree level.>

The paper describes a technique that constructs models of symbol sequences in the form of small, human-readable, hierarchical grammars. The grammars are both semantically plausible and compact. The technique can induce structure from a variety of different kinds of sequence, and examples are given of models derived from English text, C source code and a sequence of terminal control codes. It explains the grammatical induction technique, demonstrates its application to three very different sequences, evaluates its compression performance, and concludes by briefly discussing its use as a method for knowledge acquisition.>

The complementary paradigms of text compression and image compression suggest that there may be potential for applying methods developed for one domain to the other. In image coding, lossy techniques yield compression factors that are vastly superior to those of the best lossless schemes and we show that this is also the case for text. This paper investigates the resulting trade-off between subjective quality of the transmission and its compression factor. Two different methods are described, which can be combined into an extremely effective technique that provides far better compression than the present state of the art and yet preserves a reasonable degree of perceived match between the original and received text. The major challenge for lossy text compression is the quantitative evaluation of the quality of this match.

Programming by example is a powerful way of bestowing on nonprogrammers the ability to communicate tasks to a computer. When creating procedures from examples it is necessary to be able to infer the existence of variables, conditional branches, and loops. This article explores the role of empirical or “similarity-based” learning in this process. For a concrete example of a procedure induction system, we use an existing scheme called METAMOUSE which allows graphical procedures to be specified from examples of their execution. A procedure is induced from the first example, and can be generalized in accordance with examples encountered later on. We describe how the system can be enhanced with Mitchell's candidate elimination algorithm, one of the simplest empirical learning techniques, to improve its ability to recognize constraints in a comprehensive and flexible manner. Procedure induction is, no doubt, a very complex task. This work revealed usefulness and effectiveness of empirical learning in procedure induction, although it cannot be a complete substitute for specific preprogrammed, domain knowledge in situations where this is readily available. However, in domains such as graphical editing, where knowledge is incomplete and/or incorrect, the best way to pursue may prove to be a combination of similarity- and explanation-based learning. © 1994 John Wiley & Sons, Inc.

Text compression methods can be divided into two classes: symbolwise and parsing . Symbolwise methods assign codes to individual symbols, while parsing methods assign codes to groups of consecutive symbols (phrases). The set of phrases available to a parsing method is referred to as a dictionary . The vast majority of parsing methods in the literature use greedy parsing (including nearly all variations of the popular Ziv-Lempel methods). When greedy parsing is used, the coder processes a string from left to right, at each step encoding as many symbols as possible with a phrase from the dictionary. This parsing strategy is not optimal, but an optimal method cannot guarantee a bounded coding delay. An important problem in compression research has been to establish the relationship between symbolwise methods and parsing methods. This paper extends prior work that shows that there are symbolwise methods that simulate a subset of greedy parsing methods. We provide a more general algorithm that takes any nonadaptive greedy parsing method and constructs a symbolwise method that achieves exactly the same compression. Combined with the existence of symbolwise equivalents for two of the most significant adaptive parsing methods, this result gives added weight to the idea that research aimed at increasing compression should concentrate on symbolwise methods, while parsing methods should be chosen for speed or temporary storage considerations.

A two-stage method for compressing bilevel images is described that is particularly effective for images containing repeated subimages, notably text. In the first stage, connected groups of pixels, corresponding approximately to individual characters, are extracted from the image. These are matched against an adaptively constructed library of patterns seen so far, and the resulting sequence of symbol identification numbers is coded and transmitted. From this information, along with the library itself and the offset from one mark to the next, an approximate image can be reconstructed. The result is a lossy method of compression that outperforms other schemes. The second stage employs the reconstructed image as an aid for encoding the original image using a statistical context-based compression technique. This yields a total bandwidth for exact transmission appreciably undercutting that required by other lossless binary image compression methods. Taken together, the lossy, and lossless methods provide an effective two-stage progressive transmission capability for textual images which has application for legal, medical, and historical purposes, and to archiving in general.>

The authors examine the resource requirements and compression efficiency of the coding phase, concentrating on applications with medium and large alphabets. When semi-static two-pass encoding can be used, Huffman coding is two to four times faster than arithmetic coding, and sometimes results in superior compression. When an adaptive coder is required the difference in speed is smaller, but Gallager's implementation of dynamic Huffman coding is still faster than arithmetic coding in most situations. The compression loss through the use of Huffman codes is negligible in all but extreme circumstances. Where very high speed is necessary splay coding is also worth considering, although it yields poorer compression.>

article Free Access Share on Getting research students started: a tale of two courses Authors: Ian H. Witten Department of Computer Science, University of Waikato, Hamilton, New Zealand Department of Computer Science, University of Waikato, Hamilton, New ZealandView Profile , Timothy C. Bell Department of Computer Science, University of Canterbury, Christchurch, New Zealand Department of Computer Science, University of Canterbury, Christchurch, New ZealandView Profile Authors Info & Claims ACM SIGCSE BulletinVolume 25Issue 1March 1993 pp 165–169https://doi.org/10.1145/169073.169385Online:01 March 1993Publication History 10citation480DownloadsMetricsTotal Citations10Total Downloads480Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

When data compression is applied to full-text retrieval systems, intricate relationships emerge between the amount of compression, access speed, and computing resources required. We propose compression methods, and explore corresponding tradeoffs, for all components of static full-text systems such as text databases on CD-ROM. These components include lexical indexes, inverted files, bitmaps, signature files, and the main text itself. Results are reported on the application of the methods to several substantial full-text databases, and show that a large, unindexed text can be stored, along with indexes that facilitate fast searching, in less than half its original size—at some appreciable cost in primary memory requirements. © 1993 John Wiley & Sons, Inc.

Abstract This paper shows how trees can be stored in a very compact form, called ‘Bonsai’, using hash tables. A method is described that is suitable for large trees that grow monotonically within a predefined maximum size limit. Using it, pointers in any tree can be represented within 6 + [log2n] bits per node where n is the maximum number of children a node can have. We first describe a general way of storing trees in hash tables, and then introduce the idea of compact hashing which underlies the Bonsai structure. These two techniques are combined to give a compact representation of trees, and a practical methodology is set out to permit the design of these structures. The new representation is compared with two conventional tree implementations in terms of the storage required per node. Examples of programs that must store large trees within a strict maximum size include those that operate on trie structures derived from natural language text. We describe how the Bonsai technique has been applied to the trees that arise in text compression and adaptive prediction, and include a discussion of the design parameters that work well in practice.

The authors describe a method for lossless compression of images that contain predominantly typed or typeset text-they call these textual images. An increasingly popular application is document archiving, where documents are scanned by a computer and stored electronically for later retrieval. Their project was motivated by such an application: Trinity College in Dublin, Ireland, are archiving their 1872 printed library catalogues onto disk, and in order to preserve the exact form of the original document, pages are being stored as scanned images rather than being converted to text. The test images are taken from this catalogue. These typeset documents have a rather old-fashioned look, and contain a wide variety of symbols from several different typefaces-the five test images used contain text in English, Flemish, Latin and Greek, and include italics and small capitals as well as roman letters. The catalogue also contains Hebrew, Syriac, and Russian text.>

Metarnouse is a demonstrational interface for graphical editing tasks within a drawing program. The user specifies a procedure by performing an example execution trace and creating graphical tools where necessary to help make constraints explicit. The system generalizes the user's action sequence, identifying key features of individual steps and disregarding coincidental events. It creates a program with loops and conditional branches as appropriate and predicts upcoming actions, thereby reducing the tedium of repetitive and precise graphical editing. It uses default reasoning about graphical constraints to make initial generalizations and enables the user to correct these hypotheses either by rejecting its predictions or by editing iconic descriptors it displays after each action.

This paper explores the application of arithmetic coding to systems involving the storage of a large body of text, along with a lexicon that lists the words and a concordance that indicates the exact locations at which each word can be found. A typical query might seek all sentences that contain a particular word or combination of words. The random-access requirement means that many current compression techniques are not directly applicable-particularly those using adaptive modelling. However, the static nature of the text and the existence of a lexicon give help that is not available in other compression scenarios. A number of different kinds of model developed for different parts of a full-text retrieval system are presented and evaluated.>

The paper explores the application of predictive text generation to the human-computer interface. Predictive techniques exploit the statistical redundancy of language to accelerate and amplify user inputs. Acceleration is achieved by making more likely language elements faster to select, while amplification is accomplished by selection of concatenated elements. The language models used are created adaptively, decoupling the prediction mechanism from the application domain and user's vocabulary, and conforming automatically to whatever kind of text is entered. A device called the ‘reactive keyboard’ is described along with two user interface implementations, one for keyboard entry and the other for a mouse/window environment. A clear separation is made between the system's user interface and the underlying model it employs, and the two versions share the same prediction technique and adaptive modelling mechanism. The basic idea is to order context-conditioned candidate strings, which are predicted by the model, according to frequency and display them for selection.

Approaches to the zero-frequency problem in adaptive text compression are discussed. This problem relates to the estimation of the likelihood of a novel event occurring. Although several methods have been used, their suitability has been on empirical evaluation rather than a well-founded model. The authors propose the application of a Poisson process model of novelty. Its ability to predict novel tokens is evaluated, and it consistently outperforms existing methods. It is applied to a practical statistical coding scheme, where a slight modification is required to avoid divergence. The result is a well-founded zero-frequency model that explains observed differences in the performance of existing methods, and offers a small improvement in the coding efficiency of text compression over the best method previously known.>

CSCW (computer-supported cooperative work) is an active research area with many promising applications and benefits. We argue that the plight of the individual user can also be viewed as a CSCW problem, for the individual frequently acts as multiple persona: performing many independent tasks, perhaps in several places. We propose reflexive CSCW to address such issues. Solutions in the reflexive case will of course be of benefit to users even if they are working in a conventional multi-user CSCW context; proposed solutions in CSCW can be re-presented for individual users.

Inducing functions from examples is an important requirement in many learning systems. Blind search is the most general approach, but is vastly less efficient than specialized problem-solving methods. This paper presents a new strategy to accelerate search without sacrificing generality. Experiments with numeric functions show several orders of magnitude performance increase over the standard search technique. Two factors account for this improvement. First, the new strategy manipulates functions in groups instead of singly, so that many can be selected or discarded with only one comparison. Second, functional equivalence is handled automatically by the internal organization of search space.

End users who need to program within highly interactive direct-manipulation interfaces should be able to communicate their intentions through concrete demonstration rather than in terms of symbolic abstraction. This paper describes a system that learns procedures in interactive graphics taught to it “by example” by minimally trained users. It shows how techniques of machine learning and reactive interfaces can support one another—the former providing generalization heuristics to identify constraints implicit in user actions, the latter offering immediate feedback to help the user clarify hidden constraints and correct errors before they are planted into the procedure. The teacher's attention is focused on the learning system's perceptual and inferential shortcomings through a metaphorical apprentice called Metamouse, which generalizes action sequences on the fly and eagerly carries out any actions it can predict. The success of the induction process is assessed quantitatively by counting erroneous predictions made during example tasks.

Metamouse is a device enabling the user of a drawing program to specify graphical procedures by supplying example execution traces. The user manipulates objects directly on the screen, creating graphical tools where necessary to help make constraints explicit; the system records the sequence of actions and induces a procedure. Generalization is used both to identify the key features of individual program steps, disregarding coincidental events; and to connect the steps into a program graph, creating loops and conditional branches as appropriate. Metamouse operates within a 2D click-and-drag drafting package, and incorporates a strong model of the relative importance of different types of graphical constraint. Close attention is paid to user interface aspects, and Metamouse helps the user by predicting and performing actions, thus reducing the tedium of repetitive graphical editing tasks.

‘Explanation-based’ learning is a semantically-driven. knowledge-intensive paradigm for machine learning which contrasts sharply with syntactic or ‘similarity-based’ approaches. This paper redevelops the foundations of EBL from the perspective of problem-solving. Viewed in this light, the technique is revealed as a simple modification to an inference engine which gives it the ability to generalize the conditions under which the solution to a particular problem holds. We show how to embed generalization invisibly within the problem solver, so that it is accomplished as inference proceeds rather than as a separate step. The approach is also extended to the more complex domain of planning to illustrate that it is applicable to a variety of logic-based problem-solvers and is by no means restricted to only simple ones. We argue against the current trend to isolate learning from other activity and study it separately, preferred instead to integrate it into the very heart of problem solving.

An integrative framework is developed for describing concept learning techniques that makes it possible to evaluate their relevance to knowledge engineering. The framework provides a general basis for relating concept learning to knowledge acquisition and is a starting point for the development of formal design rules. First, concept learning is framed in the context of knowledge acquisition. Then the general forms of input and concept representation such as logic, functions and procedures are discussed. Next, methods of biasing the search for a suitable concept are described and illustrated including: background knowledge, conceptual bias, composition bias, and preference orderings. Finally, modes of teacher interaction are reviewed, including the nature of examples given and the method of presenting them. The framework is illustrated by applying it to the better-documented concept learning systems.>

Several striking characteristics of how often people repeat their actions on interactive systems are abstracted from usage data gleaned from many users of different classes over a period of months. Reformulated as empirically-based general principles, these provide design guidelines for history mechanisms specifically and modern user interfaces generally. Particular attention is paid to the repetition of command lines, and to the probability distribution of the next line given a sequential “history list” of previous ones. Several ways are examined of conditioning this distribution to enhance predictive power. A brief case study of actual use of a widely-used history system is also included.

A final-year undergraduate course on Expert Systems, designed for Electrical Engineering students, is described. To cater for this audience the course has a highly practical nature, despite the students' lack of relevant prerequisites in Computer Science. This is achieved by emphasizing logic programming throughout to illustrate all concepts taught; weekly, scheduled laboratory sessions; and a carefully-graded series of assignments.

The recently developed technique of arithmetic coding, in conjunction with a Markov model of the source, is a powerful method of data compression in situations where a linear treatment is inappropriate. Adaptive coding allows the model to be constructed dynamically by both encoder and decoder during the course of the transmission, and has been shown to incur a smaller coding overhead than explicit transmission of the model's statistics. But there is a basic conflict between the desire to use high-order Markov models and the need to have them formed quickly as the initial part of the message is sent. This paper describes how the conflict can be resolved with partial string matching, and reports experimental results which show that mixed-case English text can be coded in as little as 2.2 bits/ character with no prior knowledge of the source.

The problem of noiselessly encoding a message when prior statistics are known is considered. The close relationship of arithmetic and enumerative coding for this problem is shown by computing explicit arithmetic coding probabilities for various enumerative coding examples. This enables a comparison to be made of the coding efficiency of Markov models and enumerative codes as well as a new coding scheme intermediate between the two. These codes are then extended to messages whose statistics are not known {\em a priori} Two adaptive codes are described for this problem whose coding efficiency is upper-bounded by the extended enumerative codes. On some practical examples the adaptive codes perform significantly better than the nonadaptive ones.

Computer typesetting systems can produce high quality printed pages suitable for the production of books, journals and newspapers in final form. Little effort to date has been applied to the problem of including and placing arbitrary graphic figures within processed text. In this paper we describe a system, constructed around existing typesetting software, which allows figure definition and placement. Key features of the system are a wide range of figure sources; figure preview facilities; figures-only output and compatibility with non-graphic printing devices, where figures are plotted separately; support of a figure language for in-line figure definition; and figure placement algorithms which are changeable at the user level.

Abstract This note illustrates the power of software interrupts (traps) and text diversions in document preparation languages by considering three difficult problems in typesetting: figure placement; setting text in arbitrary shapes; and balancing final columns in multi‐column layout. The solution of each of these in the nroff document preparation system is discussed, and an Appendix gives the nroff macros which accomplish the tasks.

A scheme is described which enables users to interact with a timesharing computer in an ideographic language such as Chinese. The host computer runs a completely unmodified English-based operating system, the necessary translation being performed by a preprocessing microcomputer which constitutes the ideographic terminal. The two systems communicate through a serial line, and the host sees the preprocessor as an ordinary (English) terminal. After brief consideration of the terminal's keyboard and display, we examine the software problems of translation for five examples subsystems – an interpreted programming language, text editor, document preparation software, interactive data base management system, and the command level of the operating system itself.

It is shown that an adaptive threshold logic element (ATLE) whose weight vector is perturbed reconverges without error provided its threshold is large compared with the perturbation. This result is generalized to a criterion of convergence, based on admissibility, for the nonseparable case. It is shown that conventional ATLE's cannot cope with nonseparability even according to this very weak criterion.

A class of asymptotically ε-optimal two-armed bandit controllers is given, and two criteria for comparing thelong-term finite-time performance of controllers in this class are proposed. The performances of three particular controllers are compared using the criteria, and the analysis is confirmed by computer iteration if the appropriate probability recurrence relations.

In the above paper,1 an optimal method of self-optimization of certain system parameters using noisy binary-valued performance feedback is extended, without losing optimality, to situations with many-valued performance feedback. The effect of time-varying feedback mechanisms is briefly considered.