Modern systems can augment people’s capabilities by using machine-learned models to surface intelligent behaviors. Unfortunately, building these models remains challenging and beyond the reach of non-machine learning experts. We describe interactive machine teaching (IMT) and its potential to simplify the creation of machine-learned models. One of the key characteristics of IMT is its iterative process in which the human-in-the-loop takes the role of a teacher teaching a machine how to perform a task. We explore alternative learning theories as potential theoretical foundations for IMT, the intrinsic human capabilities related to teaching, and how IMT systems might leverage them. We argue that IMT processes that enable people to leverage these capabilities have a variety of benefits, including making machine learning methods accessible to subject-matter experts and the creation of semantic and debuggable machine learning (ML) models. We present an integrated teaching environment (ITE) that embodies principles from IMT, and use it as a design probe to observe how non-ML experts do IMT and as the basis of a system that helps us study how to guide teachers. We explore and highlight the benefits and challenges of IMT systems. We conclude by outlining six research challenges to advance the field of IMT.

When building a classifier in interactive machine learning (iML), human knowledge about the target class can be a powerful reference to make the classifier robust to unseen items. The main challenge lies in finding unlabeled items that can either help discover or refine concepts for which the current classifier has no corresponding features (i.e., it has feature blindness ). Yet it is unrealistic to ask humans to come up with an exhaustive list of items, especially for rare concepts that are hard to recall. This article presents AnchorViz , an interactive visualization that facilitates the discovery of prediction errors and previously unseen concepts through human-driven semantic data exploration. By creating example-based or dictionary-based anchors representing concepts, users create a topology that (a) spreads data based on their similarity to the concepts and (b) surfaces the prediction and label inconsistencies between data points that are semantically related. Once such inconsistencies and errors are discovered, users can encode the new information as labels or features and interact with the retrained classifier to validate their actions in an iterative loop. We evaluated AnchorViz through two user studies. Our results show that AnchorViz helps users discover more prediction errors than stratified random and uncertainty sampling methods. Furthermore, during the beginning stages of a training task, an iML tool with AnchorViz can help users build classifiers comparable to the ones built with the same tool with uncertainty sampling and keyword search, but with fewer labels and more generalizable features. We discuss exploration strategies observed during the two studies and how AnchorViz supports discovering, labeling, and refining of concepts through a sensemaking loop.

When building a classifier in interactive machine learning, human knowledge about the target class can be a powerful reference to make the classifier robust to unseen items. The main challenge lies in finding unlabeled items that can either help discover or refine concepts for which the current classifier has no corresponding features (i.e., it has feature blindness). Yet it is unrealistic to ask humans to come up with an exhaustive list of items, especially for rare concepts that are hard to recall. This paper presents AnchorViz, an interactive visualization that facilitates error discovery through semantic data exploration. By creating example-based anchors, users create a topology to spread data based on their similarity to the anchors and examine the inconsistencies between data points that are semantically related. The results from our user study show that AnchorViz helps users discover more prediction errors than stratified random and uncertainty sampling methods.

Model building in machine learning is an iterative process. The performance analysis and debugging step typically involves a disruptive cognitive switch from model building to error analysis, discouraging an informed approach to model building. We present ModelTracker, an interactive visualization that subsumes information contained in numerous traditional summary statistics and graphs while displaying example-level performance and enabling direct error examination and debugging. Usage analysis from machine learning practitioners building real models with ModelTracker over six months shows ModelTracker is used often and throughout model building. A controlled experiment focusing on ModelTracker's debugging capabilities shows participants prefer ModelTracker over traditional tools without a loss in model performance.

With advances in pen-based computing devices, handwriting has become an increasingly popular input modality. Researchers have put considerable effort into building intelligent recognition systems that can translate handwriting to text with increasing accuracy. However, handwritten input is inherently ambiguous, and these systems will always make errors. Unfortunately, work on error recovery mechanisms has mainly focused on interface innovations that allow users to manually transform the erroneous recognition result into the intended one. In our work, we propose a mixed-initiative approach to error correction. We describe CueTIP, a novel correction interface that takes advantage of the recognizer to continually evolve its results using the additional information from user corrections. This significantly reduces the number of actions required to reach the intended result. We present a user study showing that CueTIP is more efficient and better preferred for correcting handwriting recognition errors. Grounded in the discussion of CueTIP, we also present design principles that may be applied to mixed-initiative correction interfaces in other domains.

HIPs, or Human Interactive Proofs, are challenges meant to be easily solved by humans, while remaining too hard to be economically solved by computers. HIPs are increasingly used to protect services against automatic script attacks. To be effective, a HIP must be difficult enough to discourage script attacks by raising the computation and/or development cost of breaking the HIP to an unprofitable level. At the same time, the HIP must be easy enough to solve in order to not discourage humans from using the service. Early HIP designs have successfully met these criteria [1]. However, the growing sophistication of attackers and correspondingly increasing profit incentives have rendered most of the currently deployed HIPs vulnerable to attack [2,7,12]. Yet, most companies have been reluctant to increase the difficulty of their HIPs for fear of making them too complex or unappealing to humans. The purpose of this study is to find the visual distortions that are most effective at foiling computer attacks without hindering humans. The contribution of this research is that we discovered that 1) automatically generating HIPs by varying particular distortion parameters renders HIPs that are too easy for computer hackers to break, yet humans still have difficulty recognizing them, and 2) it is possible to build segmentation-based HIPs that are extremely difficult and expensive for computers to solve, while remaining relatively easy for humans.

We present a promising new framework for improving boosting performance with transductive inference when training an automatic text detector. The resulting detector is fast and efficient, and it exhibits high accuracy on a large test set.

This paper proposes a glyph hashing approach to optical character recognition with applications in document conversion. The viability and efficiency of the approach is tested through its implementation in a print driver on 68,987 PDF documents containing 1.15 billion characters. Results indicate that a hash table with (a) 3.2 million hashes is sufficient to represent all characters from these documents, and (b) 480 fonts are sufficient to cover over 90% of these documents. Glyph recognizing experiments indicate that 80% of unique character glyphs and over 96% of all characters from unseen documents can be found in a hash table built using all 68,987 documents. The hashing approach is used to not only recognize the character codes but also, size, style (bold, italic, etc), and font name. We found that the hashing approach can scale to hundreds of fonts and thousands of characters per font. Further, it is extremely fast and can recognize over 100,000 characters per second. Owing to its speed, such a hashing approach can complement any existing OCR system by acting as a pre-filter to produce a 4-5 times speedup during document conversion.

Cheap and versatile cameras make it possible to easily and quickly capture a wide variety of documents. However, low resolution cameras present a challenge to OCR because it is virtually impossible to do character segmentation independently from recognition. In this paper we solve these problems simultaneously by applying methods borrowed from cursive handwriting recognition. To achieve maximum robustness, we use a machine learning approach based on a convolutional neural network. When our system is combined with a language model using dynamic programming, the overall performance is in the vicinity of 80-95% word accuracy on pages captured with a 1024/spl times/768 webcam and 10-point text.

Handwriting recognition is difficult because of the high variability of handwriting and because of segmentation errors. We propose an approach that reduces this variability without requiring letter segmentation. We build an ink extrema classifier which labels local minima of ink as {bottom, baseline, other} and maxima as {midline, top, other}. Despite the high variability of ink, the classifier is 86% accurate (with 0% rejection). We use the classifier information to normalize the ink. This is done by applying a "rubber sheet" warping followed by a "rubber rod" warping. Both warpings are computed using conjugate gradient methods. We display the normalization results on a few examples. This paper illustrates the pitfalls of ink normalization and "beautification ", when solved independently of letter recognition.

Using dedicated hardware to do machine learning typically ends up in disaster because of cost, obsolescence, and poor software. The popularization of graphic processing units (GPUs), which are now available on every PC, provides an attractive alternative. We propose a generic 2-layer fully connected neural network GPU implementation which yields over 3/spl times/ speedup for both training and testing with respect to a 3 GHz P4 CPU.

Many bitmap documents are composed by the superposition of layers with pictures and text. These documents do not compress well using image compression algorithms such as JPEG-2000, because text introduces sharp edges on top of the smooth surfaces typically found in natural images. Similarly, compression algorithms for text facsimiles, such as JBIG2, are not suited for color or gray level images. In this paper the SLIm system for separating text and line drawing from background images, in order to compress both more effectively is proposed. This approach differ from previous ones such as DjVu, Tiff-FX, and MRC, by being extremely simple and fast, while yielding close to state-of-the-art compression performance. Results show that the SLIm compression performance is attractive for many applications.

Activity detection on binary images can be a useful part of image processing for detecting noise, texture, printed text, or dithering. We present an image activity detector based on computing a density of selected connected components (CCs). Connectedness is a useful property because it is present in individual printed letters, lines, and edges. In contrast, salt-and-pepper noise and dithering are typically composed of a large number of disconnected patterns. By filtering the CCs based on size, we can measure different kinds of activities, and segment or filter the image accordingly. The activity detector is extremely efficient and can be run in a fraction of the time it takes to compute a run-length encoding version of the image. As an example, we built a noise removal filter based on the density of CCs, which is both faster and better than a conventional median filter.

Machine learning is often used to automatically solve human tasks. In this paper, we look for tasks where machine learning algorithms are not as good as humans with the hope of gaining insight into their current limitations. We studied various Human Interactive Proofs (HIPs) on the market, because they are systems designed to tell computers and humans apart by posing challenges presumably too hard for computers. We found that most HIPs are pure recognition tasks which can easily be broken using machine learning. The harder HIPs use a combination of segmentation and recognition tasks. From this observation, we found that building segmentation tasks is the most effective way to confuse machine learning algorithms. This has enabled us to build effective HIPs (which we deployed in MSN Passport), as well as design challenging segmentation tasks for machine learning algorithms.

Many image coders map the input image to a transform domain, and encode coefficients in that domain. Usually, encoders use previously transmitted samples to help estimate the probabilities for the next sample to be encoded. This backward probability estimation provides a better PDF estimation, without need to send any side information. A new method of encoding was proposed that goes one step further: besides past samples, it also uses information about the current sample in computing the PDF for the current sample. Yet, no side information was transmitted. The initial PDF estimate is based on a Tarp filter, but probabilities are then progressively refined for non-zero samples. Results are superior to JPEG2000, and to bit-plane Tarp.

This paper presents an integrated approach to parsing textual structure in freeform handwritten notes. Text-graphics classification and text layout analysis are classical problems in printed document analysis, but the irregularity in handwriting and content in freeform notes reveals limitations in existing approaches. We advocate an integrated technique that solves the layout analysis and classification problems simultaneously: the problems are so tightly coupled that it is not possible to solve one without the other for real user notes. We tune and evaluate our approach on a large corpus of unscripted user files and reflect on the difficult recognition scenarios that we have encountered in practice.

How do you tell a computer from a human? The situation arises often on the Internet, when online polls are conducted, accounts are requested, undesired email is received, and chat-rooms are spammed. The approach we use is to create a visual challenge that is easy for humans but difficult for a computer. More specifically, our challenge is to recognize a string of random distorted characters. To pass the challenge, the subject must type in the correct corresponding ASCII string. From an OCR point of view, this problem is interesting because our goal is to use the vast amount of accumulated knowledge to defeat the state of the art OCR algorithms. This is a role reversal from traditional OCR research. Unlike many other systems, our algorithm is based on the assumption that segmentation is much more difficult than recognition. Our image challenges present hard segmentation problems that humans are particularly apt at solving. The technology is currently being used in MSN's Hotmail registration system, where it has significantly reduced daily registration rate with minimal Consumer Support impact.

Neural networks are a powerful technology forclassification of visual inputs arising from documents.However, there is a confusing plethora of different neuralnetwork methods that are used in the literature and inindustry. This paper describes a set of concrete bestpractices that document analysis researchers can use toget good results with neural networks. The mostimportant practice is getting a training set as large aspossible: we expand the training set by adding a newform of distorted data. The next most important practiceis that convolutional neural networks are better suited forvisual document tasks than fully connected networks. Wepropose that a simple do-it-yourself implementation ofconvolution with a flexible architecture is suitable formany visual document problems. This simpleconvolutional neural network does not require complexmethods, such as momentum, weight decay, structure-dependentlearning rates, averaging layers, tangent prop,or even finely-tuning the architecture. The end result is avery simple yet general architecture which can yieldstate-of-the-art performance for document analysis. Weillustrate our claims on the MNIST set of English digitimages.

Images typically contain smooth regions, which are easily compressed by linear transforms, and high activity regions (edges, textures), which are harder to compress. To compress the first kind, we use a "zero" encoder that has infinite context, very low capacity, and which adapts very quickly to the content. For the second, we use an "interpolation" encoder, based on neural networks, which has high capacity, a finite-size context, and is trained off-line. The two encoders can be used separately or in combination. The zero-encoder surpasses JPEG2000 by 3.5% in overall compression, even though it is less efficient in high activity regions. Thanks to off-line training, the interpolation-encoder predicts high activity regions well, so it also matches the performance of JPEG2000, even though it does not use an arithmetic encoder and is less efficient in low activity regions. In both cases it is surprising that we match the state-of-the-art in image compression without using adaptive arithmetic encoding.

On-line adaptation to nonstationary distributions is essential to good performance in image coding. Fixed-size contexts (with adaptive tables) are also widely used, in conjunction with arithmetic encoders, in state-of-the-art codecs. In contrast, we propose a simple two-dimensional filter that directly outputs the probability distribution function (PDF) estimate necessary to drive an adaptive arithmetic encoder. The filter is isotropic, in the sense that the impact of a previously encoded bit depends only on its value and distance to the bit to be coded. Surprisingly, this simple filter yields results comparable to or better than JPEG2000. It also brings an interesting distinction between on-line and off-line learning, and their relative importance in compression.

This paper presents an algorithm for the compression of images that have "don't care" regions within them. Such regions are specified by an additional binary image, the mask, which we assume is available at both the coder and the encoder (it is transmitted separately and without loss). Unlike previous approaches, which typically fill in the masked pixels with values geared toward good compression of the image, we use a special wavelet transform which is a function of the mask, but which can be computed efficiently. We compare our method with the previous approaches by measuring the compression for a given PSNR on the valid pixels. Our algorithm is both faster and yields compression improvements of up to 18% over the current state-of-the-art coders.

By representing images and image prototypes by linear subspaces spanned by "tangent vectors" (derivatives of an image with respect to translation, rotation, etc.), impressive invariance to known types of uniform distortion can be built into feedforward discriminators. We describe a new probability model that can jointly cluster data and learn mixtures of nonuniform, smooth deformation fields. Our fields are based on low-frequency wavelets, so they use very few parameters to model a wide range of smooth deformations (unlike, e.g., factor analysis, which uses a large number of parameters to model deformations). In spirit, our ideas are most similar to the idea of separating content from style published by Tenenbaum and Freeman. However, our models do not need labeled data for training, and thus allow for unsupervised separation of appearance from deformation. We give results on handwritten digit recognition and face recognition.

This paper compares the performance of several classifier algorithms on a standard database of handwritten digits. We consider not only raw accuracy, but also training time, recognition time, and memory requirements. When available, we report measurements of the fraction of patterns that must be rejected so that the remaining patterns have misclassification rates less than a given threshold.

Memory-based classification algorithms such as radial basis functions or K-nearest neighbors often rely on simple distances (Euclidean distance, Hamming distance, etc.), which are rarely meaningful on pattern vectors. More complex better suited distance measures are often expensive and rather ad-hoc. We propose a new distance measure which: 1) can be made locally invariant to any set of transformations of the input; and 2) can be computed efficiently. We tested the method on large handwritten character databases provided by the US Post Office and NIST. Using invariances with respect to translation, rotation, scaling, skewing and line thickness, the method outperformed all other systems on a small (less than 10,000 patterns) database and was competitive on our largest (60,000 patterns) database.

Simard, LeCun & Denker (1993) showed that the performance of nearest-neighbor classification schemes for handwritten character recognition can be improved by incorporating invariance to spe(cid:173) the so cific transformations in the underlying distance metric - called tangent distance. The resulting classifier, however, can be prohibitively slow and memory intensive due to the large amount of prototypes that need to be stored and used in the distance compar(cid:173) isons. In this paper we develop rich models for representing large subsets of the prototypes. These models are either used singly per class, or as basic building blocks in conjunction with the K-means clustering algorithm. *This work was performed while Trevor Hastie was a member of the Statistics and Data Analysis Research Group, AT&T Bell Laboratories, Murray Hill, NJ 07974.

Recurrent neural networks can be used to map input sequences to output sequences, such as for recognition, production or prediction problems. However, practical difficulties have been reported in training recurrent neural networks to perform tasks in which the temporal contingencies present in the input/output sequences span long intervals. We show why gradient based learning algorithms face an increasingly difficult problem as the duration of the dependencies to be captured increases. These results expose a trade-off between efficient learning by gradient descent and latching on information for long periods. Based on an understanding of this problem, alternatives to standard gradient descent are considered.

A boosting algorithm, based on the probably approximately correct (PAC) learning model is used to construct an ensemble of neural networks that significantly improves performance (compared to a single network) in optical character recognition (OCR) problems. The effect of boosting is reported on four handwritten image databases consisting of 12000 digits from segmented ZIP Codes from the United States Postal Service and the following from the National Institute of Standards and Technology: 220000 digits, 45000 upper case letters, and 45000 lower case letters. We use two performance measures: the raw error rate (no rejects) and the reject rate required to achieve a 1% error rate on the patterns not rejected. Boosting improved performance significantly, and, in some cases, dramatically.

In many machine learning applications, one has not only training data but also some high-level information about certain invariances that the system should exhibit. In character recognition, for example, the answer should be invariant with respect to small spatial distortions in the input images (translations, rotations, scale changes, etcetera). The authors have implemented a scheme that minimizes the derivative of the classifier outputs with respect to distortion operators. This not only produces tremendous speed advantages, but also provides a powerful language for specifying what generalizations the network can perform.>

The theory of image restoration by projection onto convex sets can also be applied to the restoration of vector fields. These can have properties that restrict them to lie in well-defined closed convex sets. One of the properties, divergence freedom, is considered, and the theory and numerical implementation of its projection operator are presented. The performance of the operator is illustrated by restoring, from partial information, two simulated divergence-free vector fields. This projection operator finds an important application in the restoration of velocity fields or optical flows computed from an image sequence when the real velocity field is known, a priori to be divergence-free.>