MOTIVATION: There are many diseases with established genetic factors, such as Huntington's disease (HD), that are characterized by variable rates of progression. However, beyond the contribution of the known genetic factors - in this case the Huntingtin (HTT) gene - the impact of the full human genome on the natural progression of such diseases throughout a patient's life remains largely unknown. The increased availability of genome wide association (GWA) data in HD gene expansion carriers (HDGECs), combined with the clinical assessment scores on the same set of patients, has provided a perfect opportunity to assess the potentially broader genetic impact on the natural progression of HD. RESULTS: We present a genetics-driven, probabilistic disease progression model designed to identify and investigate the ways in which a range of genetic factors affect the natural progression of HD. When applied to a clinico-genomic HD dataset, our model identified several single nucleotide polymorphisms (SNPs) with previously unreported effects on disease progression that act at distinct stages and with varying magnitudes. This discovery may shed light on the potential mechanistic impact of previously unidentified genes on HD that may have implications for clinical management. As increasing amounts of GWA data become available more generally, we anticipate that this modeling framework will be broadly applicable to other diseases with strong genetic components. AVAILABILITY AND IMPLEMENTATION: The source code for IHDPM is available at https://github.com/BiomedSciAI/IHDPM.

Cloud Block Storage (CBS) systems underpin modern cloud infrastructures by decoupling storage from computation and enabling resource pooling for elasticity and cost efficiency. However, CBS faces two persistent challenges: load imbalance across storage nodes and network & storage amplification caused by redundancy mechanisms. While recent hybrid-redundancy block storage (HRBS) architectures combine replication caches with EC layers to reduce amplification, their static cache admission policies fail to adapt to dynamic cluster conditions, especially during node failures, leading to severe load imbalance and degraded throughput.

Nowadays, SSD cache plays an important role in cloud storage systems. The associated write policy, which enforces an admission control policy regarding filling data into the cache, has a significant impact on the performance of the cache system and the amount of write traffic to SSD caches. Based on our analysis on a typical cloud block storage system, approximately 47.09% writes are write-only, i.e., writes to the blocks which have not been read during a certain time window. Naively writing the write-only data to the SSD cache unnecessarily introduces a large number of harmful writes to the SSD cache without any contribution to cache performance. On the other hand, it is a challenging task to identify and filter out those write-only data in a real-time manner, especially in a cloud environment running changing and diverse workloads.In this paper, to alleviate the above cache problem, we propose an ML-WP, Machine Learning Based Write Policy, which reduces write traffic to SSDs by avoiding writing write-only data. The main challenge in this approach is to identify write-only data in a real-time manner. To realize ML-WP and achieve accurate write-only data identification, we use machine learning methods to classify data into two groups (i.e., write-only and normal data). Based on this classification, the write-only data is directly written to backend storage without being cached. Experimental results show that, compared with the industry widely deployed write-back policy, ML-WP decreases write traffic to SSD cache by 41.52%, while improving the hit ratio by 2.61% and reducing the average read latency by 37.52%.

Diabetes mellitus, commonly known as diabetes, is a chronic disease that often results in multiple complications. Risk prediction of diabetes complications is critical for healthcare professionals to design personalized treatment plans for patients in diabetes care for improved outcomes. In this paper, focusing on Type 2 diabetes mellitus (T2DM), we study the risk of developing complications after the initial T2DM diagnosis from longitudinal patient records. We propose a novel multi-task learning approach to simultaneously model multiple complications where each task corresponds to the risk modeling of one complication. Specifically, the proposed method strategically captures the relationships (1) between the risks of multiple T2DM complications, (2) between different risk factors, and (3) between the risk factor selection patterns, which assumes similar complications have similar contributing risk factors. The method uses coefficient shrinkage to identify an informative subset of risk factors from high-dimensional data, and uses a hierarchical Bayesian framework to allow domain knowledge to be incorporated as priors. The proposed method is favorable for healthcare applications because in addition to improved prediction performance, relationships among the different risks and among risk factors are also identified. Extensive experimental results on a large electronic medical claims database show that the proposed method outperforms state-of-the-art models by a significant margin. Furthermore, we show that the risk associations learned and the risk factors identified lead to meaningful clinical insights.

BACKGROUND: Adverse drug reactions (ADRs) are unintended and harmful reactions caused by normal uses of drugs. Predicting and preventing ADRs in the early stage of the drug development pipeline can help to enhance drug safety and reduce financial costs. METHODS: In this paper, we developed machine learning models including a deep learning framework which can simultaneously predict ADRs and identify the molecular substructures associated with those ADRs without defining the substructures a-priori. RESULTS: We evaluated the performance of our model with ten different state-of-the-art fingerprint models and found that neural fingerprints from the deep learning model outperformed all other methods in predicting ADRs. Via feature analysis on drug structures, we identified important molecular substructures that are associated with specific ADRs and assessed their associations via statistical analysis. CONCLUSIONS: The deep learning model with feature analysis, substructure identification, and statistical assessment provides a promising solution for identifying risky components within molecular structures and can potentially help to improve drug safety evaluation.

Adverse drug reaction (ADR) is a major burden for patients and healthcare industry. It usually causes preventable hospitalizations and deaths, while associated with a huge amount of cost. Traditional preclinical in vitro safety profiling and clinical safety trials are restricted in terms of small scale, long duration, huge financial costs and limited statistical signifi- cance. The availability of large amounts of drug and ADR data potentially allows ADR predictions during the drugs’ early preclinical stage with data analytics methods to inform more targeted clinical safety tests. Despite their initial success, existing methods have trade-offs among interpretability, predictive power and efficiency. This urges us to explore methods that could have all these strengths and provide practical solutions for real world ADR predictions. We cast the ADR-drug relation structure into a three-layer hierarchical Bayesian model. We interpret each ADR as a symbolic word and apply latent Dirichlet allocation (LDA) to learn topics that may represent certain biochemical mechanism that relates ADRs with drug structures. Based on LDA, we designed an equivalent regularization term to incorporate the hierarchical ADR domain knowledge. Finally, we developed a mixed input model leveraging a fast collapsed Gibbs sampling method that the complexity of each iteration of Gibbs sampling proportional only to the number of positive ADRs. Experiments on real world data show our models achieved higher prediction accuracy and shorter running time than the state-of-the-art alternatives.

Biological interpretation and understanding of machine learning based predictive models are highly desirable in healthcare analytics. Predicting Adverse Drug Reactions (ADRs) is extremely important for safe and precision medicine. There are various machine learning based approaches to predict adverse reactions for drugs. These models, though effective, lack biological interpretation and are treated as black-boxes. We propose DrugPathSeeker, a novel interactive user interface that integrates the machine learning model, database query API, statistical analysis, and visualization for exploring and understanding of the association between drugs and ADRs. The proposed UI can take a query drug, and provide a visual interface designed to support exploration of the predictions from the machine learning model for further understanding and interpretation. DrugPathSeeker uses a machine learning model, Small Molecular Risk Profiler, to make ADR predictions for a given drug. The visualization uses Sankey type flow diagrams for highlighting the relation between the drugs and ADRs. The main goal of Drug-PathSeeker is to mine the gene-pathways from public databases and analyze them in a visual manner to generate a biological hypothesis. DrugPathSeeker's effectiveness is demonstrated with two use cases: mechanisms of action for carbamazepine-induced dystonia, and fluorometholone-induced diabetes mellitus.

The proliferation of Electronic Health Records (EHRs) challenges data miners to discover potential and previously unknown patterns from a large collection of medical data. One of the tasks that we address in this paper is to reveal previously unknown effects of drugs on laboratory test results. We propose a method that leverages drug information to find a meaningful list of drugs that have an effect on the laboratory result. We formulate the problem as a convex non smooth function and develop a proximal gradient method to optimize it. The model has been evaluated on two important use cases: lowering low-density lipoproteins and glycated hemoglobin test results. The experimental results provide evidence that the proposed method is more accurate than the state-of-the-art method, rediscover drugs that are known to lower the levels of laboratory test results, and most importantly, discover additional potential drugs that may also lower these levels.

The recent years have witnessed a surge of interests in data analytics with patient Electronic Health Records (EHR). Data-driven healthcare, which aims at effective utilization of big medical data, representing the collective learning in treating hundreds of millions of patients, to provide the best and most personalized care, is believed to be one of the most promising directions for transforming healthcare. EHR is one of the major carriers for make this data-driven healthcare revolution successful. There are many challenges on working directly with EHR, such as temporality, sparsity, noisiness, bias, etc. Thus effective feature extraction, or phenotyping from patient EHRs is a key step before any further applications. In this paper, we propose a deep learning approach for phenotyping from patient EHRs. We first represent the EHRs for every patient as a temporal matrix with time on one dimension and event on the other dimension. Then we build a four-layer convolutional neural network model for extracting phenotypes and perform prediction. The first layer is composed of those EHR matrices. The second layer is a one-side convolution layer that can extract phenotypes from the first layer. The third layer is a max pooling layer introducing sparsity on the detected phenotypes, so that only those significant phenotypes will remain. The fourth layer is a fully connected softmax prediction layer. In order to incorporate the temporal smoothness of the patient EHR, we also investigated three different temporal fusion mechanisms in the model: early fusion, late fusion and slow fusion. Finally the proposed model is validated on a real world EHR data warehouse under the specific scenario of predictive modeling of chronic diseases.

The rapid growth in the development of healthcare information systems has led to an increased interest in utilizing the patient Electronic Health Records (EHR) for assisting disease diagnosis and phenotyping. The patient EHRs are generally longitudinal and naturally represented as medical event sequences, where the events include clinical notes, problems, medications, vital signs, laboratory reports, etc. The longitudinal and heterogeneous properties make EHR analysis an inherently difficult challenge. To address this challenge, in this paper, we develop a novel representation, namely the temporal graph, for such event sequences. The temporal graph is informative for a variety of challenging analytic tasks, such as predictive modeling, since it can capture temporal relationships of the medical events in each event sequence. By summarizing the longitudinal data, the temporal graphs are also robust and resistant to noisy and irregular observations. Based on the temporal graph representation, we further develop an approach for temporal phenotyping to identify the most significant and interpretable graph basis as phenotypes. This helps us better understand the disease evolving patterns. Moreover, by expressing the temporal graphs with the phenotypes, the expressing coefficients can be used for applications such as personalized medicine, disease diagnosis, and patient segmentation. Our temporal phenotyping framework is also flexible to incorporate semi-supervised/supervised information. Finally, we validate our framework on two real-world tasks. One is predicting the onset risk of heart failure. Another is predicting the risk of heart failure related hospitalization for patients with COPD pre-condition. Our results show that the diagnosis performance in both tasks can be improved significantly by the proposed approaches. Also, we illustrate some interesting phenotypes derived from the data.

Comprehensive risk assessment lies in the core of enabling proactive healthcare delivery systems. In recent years, data-driven predictive modeling approaches have been increasingly recognized as promising techniques to help enhance healthcare quality and reduce cost. In this paper, we propose a data-driven comprehensive risk prediction method, named LINKAGE, which can be used to jointly assess a set of associated risks in support of holistic care management. Our method can not only perform prediction but also discover the relationships among those risks. The advantages of the proposed model include: 1) It can leverage the relationship between risks and domains and achieve better risk prediction performance; 2) It provides a data-driven approach to understand relationship between risks; 3) It leverages the information between risk prediction and risk association learning to regulate the improvement on both parts; 4) It provides flexibility to incorporate domain knowledge in learning risk associations. We validate the effectiveness of the proposed model on synthetic data and a real-world healthcare survey data set.

Patient Electronic Health Records (EHR) are systematic collection of electronic patient health information including demographics, diagnosis, medication, procedure, lab tests, etc. Because of the rapid development of hardware and storage technologies, more and more EHRs become available and they are now serving as the basis for a lot of medical informatics applications, such as predictive modeling, patient risk stratification and care pathway analysis. One major challenge or working with EHR is sparsity. This is because patients will only have EHR recorded when they paid visits to clinical facilities. However, the patients typically will not pay frequent visits to those clinical sites unless they are severely sick and need intensive monitoring. In this paper, we propose Density Transfer, a data driven approach for imputing the sparse patient EHRs. As its name suggests, the idea is to transfer knowledge from patients with denser EHRs to their similar patients with sparse EHRs. We formulate Density Transfer as an optimization problem and propose an efficient block coordinate descent based approach to solve it.

Accurate assessment of patients' risk against a certain disease is pivotal to healthcare management and personalized medicine. Although a variety of risk prediction models have been proposed in the literature, these models are mostly single-task, i.e. they only predict the risk of one disease at a time. However, in practice, the risks of multiple related diseases are often studied together. By separately applying single-task model to these diseases, the relation between them, such as the common risk factors, will likely be lost. To address this problem, in this work we propose a multi-task framework that can jointly predict the risk of multiple related diseases. We characterize the disease relatedness by assuming that the co morbidities underlying these diseases have overlap. We develop an optimization-based formulation that can simultaneously predict the risk for all diseases and learn the shared comorbidities. To validate our model, we apply it to a real Electronic Health Record database with patients at risk of Congestive Heart Failure and Chronic Obstructive Pulmonary Disease. We demonstrate that our model not only achieves good prediction accuracy but more importantly identifies a meaningful set of shared comorbidities that leads to deeper understanding of the association between the two diseases.

Inferring phenotypic patterns from population-scale clinical data is a core computational task in the development of personalized medicine. One important source of data on which to conduct this type of research is patient Electronic Medical Records (EMR). However, the patient EMRs are typically sparse and noisy, which creates significant challenges if we use them directly to represent patient phenotypes. In this paper, we propose a data driven phenotyping framework called Pacifier (PAtient reCord densIFIER), where we interpret the longitudinal EMR data of each patient as a sparse matrix with a feature dimension and a time dimension, and derive more robust patient phenotypes by exploring the latent structure of those matrices. Specifically, we assume that each derived phenotype is composed of a subset of the medical features contained in original patient EMR, whose value evolves smoothly over time. We propose two formulations to achieve such goal. One is Individual Basis Approach (IBA), which assumes the phenotypes are different for every patient. The other is Shared Basis Approach (SBA), which assumes the patient population shares a common set of phenotypes. We develop an efficient optimization algorithm that is capable of resolving both problems efficiently. Finally we validate Pacifier on two real world EMR cohorts for the tasks of early prediction of Congestive Heart Failure (CHF) and End Stage Renal Disease (ESRD). Our results show that the predictive performance in both tasks can be improved significantly by the proposed algorithms (average AUC score improved from 0.689 to 0.816 on CHF, and from 0.756 to 0.838 on ESRD respectively, on diagnosis group granularity). We also illustrate some interesting phenotypes derived from our data.

Patient risk stratification, which aims to stratify a patient cohort into a set of homogeneous groups according to some risk evaluation criteria, is an important task in modern medical informatics. Good risk stratification is the key to good personalized care plan design and delivery. The typical procedure for risk stratification is to first identify a set of risk-relevant medical features (also called risk factors), and then construct a predictive model to estimate the risk scores for individual patients. However, due to the heterogeneity of patients' clinical conditions, the risk factors and their importance vary across different patient groups. Therefore a better approach is to first segment the patient cohort into a set of homogeneous groups with consistent clinical conditions, namely risk groups, and then develop group-specific risk prediction models. In this paper, we propose RISGAL (RISk Group Analysis), a novel semi-supervised learning framework for patient risk group exploration. Our method segments a patient similarity graph into a set of risk groups such that some risk groups are in alignment with (incomplete) prior knowledge from the domain experts while the remaining groups reveal new knowledge from the data. Our method is validated on public benchmark datasets as well as a real electronic medical record database to identify risk groups from a set of potential Congestive Heart Failure (CHF) patients.

The patient risk prediction model aims at assessing the risk of a patient in developing a target disease based on his/her health profile. As electronic health records (EHRs) become more prevalent, a large number of features can be constructed in order to characterize patient profiles. This wealth of data provides unprecedented opportunities for data mining researchers to address important biomedical questions. Practical data mining challenges include: How to correctly select and rank those features based on their prediction power? What predictive model performs the best in predicting a target disease using those features? In this paper, we propose top-k stability selection, which generalizes a powerful sparse learning method for feature selection by overcoming its limitation on parameter selection. In particular, our proposed top-k stability selection includes the original stability selection method as a special case given k = 1. Moreover, we show that the top-k stability selection is more robust by utilizing more information from selection probabilities than the original stability selection, and provides stronger theoretical properties. In a large set of real clinical prediction datasets, the top-k stability selection methods outperform many existing feature selection methods including the original stability selection. We also compare three competitive classification methods (SVM, logistic regression and random forest) to demonstrate the effectiveness of selected features by our proposed method in the context of clinical prediction applications. Finally, through several clinical applications on predicting heart failure related symptoms, we show that top-k stability selection can successfully identify important features that are clinically meaningful.

This paper proposes a novel temporal knowledge representation and learning framework to perform large-scale temporal signature mining of longitudinal heterogeneous event data. The framework enables the representation, extraction, and mining of high-order latent event structure and relationships within single and multiple event sequences. The proposed knowledge representation maps the heterogeneous event sequences to a geometric image by encoding events as a structured spatial-temporal shape process. We present a doubly constrained convolutional sparse coding framework that learns interpretable and shift-invariant latent temporal event signatures. We show how to cope with the sparsity in the data as well as in the latent factor model by inducing a double sparsity constraint on the β-divergence to learn an overcomplete sparse latent factor model. A novel stochastic optimization scheme performs large-scale incremental learning of group-specific temporal event signatures. We validate the framework on synthetic data and on an electronic health record dataset.

Large collections of electronic clinical records today provide us with a vast source of information on medical practice. However, the utilization of those data for exploratory analysis to support clinical decisions is still limited. Extracting useful patterns from such data is particularly challenging because it is longitudinal, sparse and heterogeneous. In this paper, we propose a Nonnegative Matrix Factorization (NMF) based framework using a convolutional approach for open-ended temporal pattern discovery over large collections of clinical records. We call the method One-Sided Convolutional NMF (OSC-NMF). Our framework can mine common as well as individual shift-invariant temporal patterns from heterogeneous events over different patient groups, and handle sparsity as well as scalability problems well. Furthermore, we use an event matrix based representation that can encode quantitatively all key temporal concepts including order, concurrency and synchronicity. We derive efficient multiplicative update rules for OSC-NMF, and also prove theoretically its convergence. Finally, the experimental results on both synthetic and real world electronic patient data are presented to demonstrate the effectiveness of the proposed method.

As more clinical information with increasing diversity become available for analysis, a large number of features can be constructed and leveraged for predictive modeling. Feature selection is a classic analytic component that faces new challenges due to the new applications: How to handle a diverse set of high dimensional features? How to select features with high predictive power, but low redundant information? How to design methods that can select globally optimal features with theoretical guarantee? How to incorporate and extend existing knowledge driven approach? In this paper, we present Scalable Orthogonal Regression (SOR), an optimization-based feature selection method with the following novelties: 1) Scalability: SOR achieves nearly linear scale-up with respect to the number of input features and the number of samples; 2) Optimality: SOR is formulated as an alternative convex optimization problem with theoretical convergence and global optimality guarantee; 3) Low-redundancy: thanks to the orthogonality objective, SOR is designed specifically to select less redundant features without sacrificing quality; 4) Extendability: SOR can enhance an existing set of preselected features by adding additional features that complement the existing feature set but still with strong predictive power. We present evaluation results showing that SOR consistently outperforms state of the art feature selection methods in a range of quality metrics on several real world data sets. We demonstrate a case study of a large-scale clinical application for predicting early onset of Heart Failure (HF) using real Electronic Health Records (EHRs) data of over 10K patients for over 7 years. Leveraging SOR, we are able to construct accurate and robust predictive models and derive potential clinical insights.

Sparse Coding (SC), which models the data vectors as sparse linear combinations over basis vectors (i.e., dictionary), has been widely applied in machine learning, signal processing and neuroscience. Recently, one specific SC technique, Group Sparse Coding (GSC), has been proposed to learn a common dictionary over multiple different groups of data, where the data groups are assumed to be pre-defined. In practice, this may not always be the case. In this paper, we propose Automatic Group Sparse Coding (AutoGSC), which can (1) discover the hidden data groups; (2) learn a common dictionary over different data groups; and (3) learn an individual dictionary for each data group. Finally, we conduct experiments on both synthetic and real world data sets to demonstrate the effectiveness of AutoGSC, and compare it with traditional sparse coding and Nonnegative Matrix Factorization (NMF) methods.

Chronic diseases constitute the leading cause of mortality in the western world, have a major impact on the patients' quality of life, and comprise the bulk of healthcare costs. Nowadays, healthcare data management systems integrate large amounts of medical information on patients, including diagnoses, medical procedures, lab test results, and more. Sophisticated analysis methods are needed for utilizing these data to assist in patient management and to enhance treatment quality at reduced costs. In this study, we take a first step towards better disease management of diabetic patients by applying state-of-the art methods to anticipate the patient's future health condition and to identify patients at high risk. Two relevant outcome measures are explored: the need for emergency care services and the probability of the treatment producing a sub-optimal result, as defined by domain experts. By identifying the high-risk patients our prediction system can be used by healthcare providers to prepare both financially and logistically for the patient needs. To demonstrate a potential downstream application for the identified high-risk patients, we explore the association between the physician treating these patients and the treatment outcome, and propose a system that can assist healthcare providers in optimizing the match between a patient and a physician.

Patient similarity assessment aims at providing a clinically meaningful distance measure for case retrieval in the context of clinical decision intelligence. Two of the key challenges are how to incorporate physician feedback with regard to the retrieval results and how to interactively update the underlying similarity measure based on the feedback. In this paper, we present the interactive Metric learning (iMet) method that can incrementally adjust the underlying distance metric based on latest supervision information. iMet is designed to scale linearly with the data set size based on matrix perturbation theory which allows the derivation of sound theoretical guarantees. We show empirical results demonstrating that iMet outperforms the baseline by three orders of magnitude in speed while obtaining comparable accuracy on several benchmark datasets. We also describe the application of the algorithm in a real world physician decision support system.

Consider a typical recommendation problem. A company has historical records of products sold to a large customer base. These records may be compactly represented as a sparse customer-times-product ``who-bought-what" binary matrix. Given this matrix, the goal is to build a model that provides recommendations for which products should be sold next to the existing customer base. Such problems may naturally be formulated as collaborative filtering tasks. However, this is a {\it one-class} setting, that is, the only known entries in the matrix are one-valued. If a customer has not bought a product yet, it does not imply that the customer has a low propensity to {\it potentially} be interested in that product. In the absence of entries explicitly labeled as negative examples, one may resort to considering unobserved customer-product pairs as either missing data or as surrogate negative instances. In this paper, we propose an approach to explicitly deal with this kind of ambiguity by instead treating the unobserved entries as optimization variables. These variables are optimized in conjunction with learning a weighted, low-rank non-negative matrix factorization (NMF) of the customer-product matrix, similar to how Transductive SVMs implement the low-density separation principle for semi-supervised learning. Experimental results show that our approach gives significantly better recommendations in comparison to various competing alternatives on one-class collaborative filtering tasks.

We present a mining system that can predict the future health status of the patient using the temporal trajectories of health status of a set of similar patients. The main novelties of this system are its use of stream processing technology for handling the incoming physiological time series data and incorporating domain knowledge in learning the similarity metric between patients represented by their temporal data. The proposed approach and system were tested using the MIMIC II database, which consists of physiological waveforms, and accompanying clinical data obtained for ICU patients. The study was carried out on 1500 patients from this database. In the experiments we report the efficiency and throughput of the stream processing unit for feature extraction, the effectiveness of the supervised similarity measure both in the context of classification and retrieval tasks compared to unsupervised approaches, and the accuracy of the temporal projections of the patient data.

Effective patient similarity assessment is important for clinical decision support. It enables the capture of past experience as manifested in the collective longitudinal medical records of patients to help clinicians assess the likely outcomes resulting from their decisions and actions. However, it is challenging to devise a patient similarity metric that is clinically relevant and semantically sound. Patient similarity is highly context sensitive: it depends on factors such as the disease, the particular stage of the disease, and co-morbidities. One way to discern the semantics in a particular context is to take advantage of physicians' expert knowledge as reflected in labels assigned to some patients. In this paper we present a method that leverages localized supervised metric learning to effectively incorporate such expert knowledge to arrive at semantically sound patient similarity measures. Experiments using data obtained from the MIMIC II database demonstrate the effectiveness of this approach.

This paper presents a new semi-supervised clustering framework to the recognition of heavily degraded characters in historical typewritten documents, where off-the-shelf OCR typically fails. The constraints are generated using typographical (collection-independent) domain knowledge and are used to guide both sample (glyph set) partitioning and metric learning. Experimental results using simple features provide encouraging evidence that this approach can lead to significantly improved clustering results compared to simple K-means clustering, as well as to clustering using a state-of-the art OCR engine.

We present algorithms for improved Viterbi decoding for the case of hidden semi-Markov models. By carefully constructing directed acyclic graphs, we pose the decoding problem as that of finding the longest path between specific pairs of nodes. We consider fully connected models as well as restrictive topologies and state duration conditions, and show that performance improves by a significant factor in all cases. Detailed algorithms as well as theoretical results related to their run times are provided.

Many applications require matching objects to a predefined, yet highly dynamic set of categories accompanied by category descriptions. We present a novel approach to solving this class of categorization problems by formulating it in a semi-supervised clustering framework. Text-based matching is performed to generate ldquosoftrdquo seeds, which are then used to guide clustering in the basic feature space. We introduce a new variation of the k-means algorithm, called Soft Seeded k-means, which can effectively incorporate seeds that are of varying degrees of confidence, while allowing for incomplete coverage of the pre-defined categories. The algorithm is applied to real-world data from a business analytics application, and we demonstrate that it leads to superior performance compared to previous approaches.

We present a new L1-distance-based k-means clustering algorithm to address the challenge of clustering high-dimensional proportional vectors. The new algorithm explicitly incorporates proportionality constraints in the computation of the cluster centroids, resulting in reduced L1 error rates. We compare the new method to two competing methods, an approximate L1-distance k-means algorithm, where the centroid is estimated using cluster means, and a median L1 k-means algorithm, where the centroid is estimated using cluster medians, with proportionality constraints imposed by normalization in a second step. Application to clustering of projects based on distribution of labor hours by skill illustrates the advantages of the new algorithm.

By attempting to simultaneously partition both the rows (examples) and columns (features) of a data matrix, Co-clustering algorithms often demonstrate surpris- ingly impressive performance improvements over traditional one-sided (row) clustering techniques. A good clustering of features may be seen as a combinatorial transformation of the data matrix, effectively enforcing a form of regularization that may lead to a better clustering of examples (and vice-versa). In many applications, partial supervision in the form of a few row labels as well as column labels may be available to potentially assist co-clustering. In this paper, we develop two novel semi-supervised multi-class classification algorithms motivated respectively by spectral bipartite graph partitioning and matrix approximation (e.g., non-negative matrix factorization) formulations for co-clustering. These algorithms (i) support dual supervision in the form of labels for both examples and/or features, (ii) provide principled predictive capability on out-of-sample test data, and (iii) arise naturally from the classical Representer theorem applied to regularization problems posed on a collection of Reproducing Kernel Hilbert Spaces. Empirical results demonstrate the effectiveness and utility of our algorithms.

Despite the wide use of data mining techniques in client segmentation and market analysis applications, so far there have been no algorithms that allow for the discovery of strategically important combinations of products (or offerings) – the ones that have the highest impact on the performance of the company. We present a novel algorithm for analyzing a multiproduct environment and identifying strategically important combinations of offerings with respect to a predefined criterion, such as revenue impact, profit impact, inventory turnover etc. In contrast to the traditional association rule and frequent item mining techniques, the goal of the new algorithm is to find segments of data, defined through combinations of products (rules), which satisfy certain conditions as a group. We present a novel algorithm to derive specialized partition threes, called High Yield Partition Trees, which lead to such segments, and investigate different splitting strategies. The algorithm has been tested on real-world data, and achieved very good performance.

In this paper we describe a new approach to dynamic signature verification using the discriminative training framework. The authentic and forgery samples are represented by two separate Gaussian Mixture models and discriminative training is used to achieve optimal separation between the two models. An enrollment sample clustering and screening procedure is described which improves the robustness of the system. We also introduce a method to estimate and apply subject norms representing the "typical" variation of the subject's signatures. The subject norm functions are parameterized, and the parameters are trained as an integral part of the discriminative training. The system was evaluated using 480 authentic signature samples and 260 skilled forgery samples from 44 accounts and achieved an equal error rate of 2.25%.

The World Wide Web provides an increasingly powerfuland popular publication mechanism. Web documents oftencontain a large number of images serving various differentpurposes. This paper focuses on images that are associatedwith a story or preview to a story. Such images often accompanythe key content on a web page, thus their identificationis important for applications such as web page summarizationand mobile access. We present a novel algorithmfor automatic identification of story/preview images whichcombines features extracted from both the image itself andthe surrounding text. The effectiveness of this algorithm isdemonstrated by experimental results on over 1500 imagescollected from 25 news web sites.

Table is a commonly used presentation scheme, especially for describing relational information. However, table understanding remains an open problem. In this paper, we consider the problem of table detection in web documents. Its potential applications include web mining, knowledge management, and web content summarization and delivery to narrow-bandwidth devices. We describe a machine learning based approach to classify each given table entity as either genuine or non-genuine. Various features reflecting the layout as well as content characteristics of tables are studied.In order to facilitate the training and evaluation of our table classifier, we designed a novel web document table ground truthing protocol and used it to build a large table ground truth database. The database consists of 1,393 HTML files collected from hundreds of different web sites and contains 11,477 leaf TABLE elements, out of which 1,740 are genuine tables. Experiments were conducted using the cross validation method and an F-measure of 95.89% was achieved.

Color descriptors are among the most important features used in image analysis and retrieval. Due to its compact representation and low complexity, direct histogram comparison is a commonly used technique for measuring the color similarity. However, it has many serious drawbacks, including a high degree of dependency on color codebook design, sensitivity to quantization boundaries, and inefficiency in representing images with few dominant colors. In this paper, we present a new algorithm for color matching that models behavior of the human visual system in capturing color appearance of an image. We first develop a new method for color codebook design in the Lab space. The method is well suited for creating small fixed color codebooks; for image analysis, matching, and retrieval. Then we introduce a statistical technique to extract perceptually relevant colors. We also propose a new color distance measure that is based on the optimal mapping between two sets of color components representing two images. Experiments comparing the new algorithm to some existing techniques show that these novel elements lead to better match to human perception in judging image similarity in terms of color composition.

The principle that for every document analysis task there exists a mechanism for creating well-defined ground-truth is a widely held tenet. Past experience with standard datasets providing ground-truth for character recognition and page segmentation tasks supports this belief. In the process of attempting to evaluate several table recognition algorithms we have been developing, however, we have uncovered a number of serious hurdles connected with the ground-truthing of tables. This problem may, in fact, be much more difficult than it appears. We present a detailed analysis of why table ground-truthing is so hard, including the notions that there may exist more than one acceptable "truth" and/or incomplete or partial "truths".

We propose a set of baseline heuristics for identifying genuinely tabular information and news links in HTML documents. A prototype implementation of these heuristics is described for delivering content from news providers' home pages to a narrow-bandwidth device such as a portable digital assistant or cellular phone display. Its evaluation on 75 Web sites is provided, along with a discussion of topics for future research.

Video summarization is receiving increasing attention due to the large amount of video content made available on the Internet. In this paper we present a novel idea to track video from multiple sources for video summarization. An algorithm that takes advantage of both video and close caption text information for video scene clustering is described. Experimental results are given followed by discussion on future directions.

A video sequence is first mapped to a sequence of points in a semi-metric space that forms a polyline. We require only that a semi-distance between pairs of points be defined that need not satisfy the triangle inequality. By simplifying the polyline, we obtain a small set of the most relevant key frames that is representative of the whole video sequence. The degree of the simplification is either determined automatically or selected by the user. Using our technique, a viewer can browse a video at the level of summarization that suits his patience level. Applications include the creation of a smart fast-forward function for digital VCRs, and the automatic creation of short summaries or trailers that can be used as previews before videos are downloaded from the Web.

We present a color matching algorithm that models the behavior of the human visual system in capturing color appearance of an image. We first develop a new method for color codebook design. The method is well suited for creating small color codebooks used in image analysis and retrieval. We then introduce a statistical technique to extract perceptually relevant colors. We also propose a new color metric that guarantees optimality in matching different color components of two images. Experiments comparing the new algorithm to several existing ones show that it provides a better match to human perception of color similarity.

Color features are among the most important features used in image database retrieval, especially in cases where no additional semantic information is available. Due to its compact representation and low complexity, direct histogram comparison is the most commonly used technique in comparing color similarity of images. However, it has many serious drawbacks, including a high degree of dependency on color codebook design, sensitivity to quantization boundaries, and inefficiency in representing images with few dominant colors. We present an algorithm for color matching. We describe a statistical technique to extract perceptually relevant colors. We propose a new color distance measure that guarantees optimality in matching different color components of two images. Finally, experimental results are presented comparing this new algorithm to some existing techniques.

We propose a perceptually based system for pattern retrieval and matching. The central idea is that similarity judgment has to be modeled along perceptual dimensions. Hence, we detect basic visual categories that people use in their judgment of similarity, and design a computational model that accepts patterns as input and, depending on the query, produces a set of choices that follow human behavior in pattern matching. There are two major research aspects to our work. The first one addresses the issue of how humans perceive and measure similarity within the domain of color patterns. To understand and describe this mechanism, we performed a subjective experiment which yielded five perceptual criteria used in comparison between color patterns (vocabulary), as well as a set of rules governing the use of these criteria in similarity judgment (grammar). The second research aspect is the implementation of the perceptual criteria and rules in an image retrieval system. Following the processing typical for human vision, we design a system to: (1) extract perceptual features from the vocabulary and (2) perform the comparison between the patterns according to the grammar rules. The modeling of human perception of color patterns is new--starting with a new color codebook design, compact color representation, and texture description through multi-scale edge distribution along different directions. Moreover, we propose new color and texture distance functions that correlate with human performance. The performance of the system is illustrated with numerous examples from image databases from different application domains.

The paper describes features and methods for document image comparison and classification at the spatial layout level. The methods are useful for visual similarity based document retrieval as well as fast algorithms for initial document type classification without OCR. A novel feature set called interval encoding is introduced to capture elements of spatial layout. This feature set encodes region layout information in fixed-length vectors which can be used for fast page layout comparison. The paper describes experiments and results to rank-order a set of document pages in terms of their layout similarity to a test document. We also demonstrate the usefulness of the features derived from interval encoding in a hidden Markov model based page layout classification system that is trainable and extendible.

We propose a perceptually-based system for pattern retrieval and matching. The central idea of the work is that similarity judgment has to be modeled along perceptual dimensions. Hence, we detect basic visual categories that people use in judgment of similarity, and design a computational model which accepts patterns as input, and depending on the query, produces a set of choices that follow human behavior in pattern matching. To understand how humans perceive color patterns we performed a subjective experiment The experiment yielded five perceptual criteria used in comparison between color patterns (vocabulary), as well as a set of rules governing the use of these criteria in similarity judgment (grammar). This paper describes the actual implementation of the perceptual criteria and rules in the image retrieval system. Following the processing typical for human vision, we designed a system to: (a) extract perceptual features from the vocabulary and (b) perform the comparison between the patterns according to the grammar rules. We propose new color and texture features, as well as new distance functions that correlate with human performance. The performance of the system is illustrated with numerous examples from image databases from different application domains.

The signature block is a common structured component found in email messages. Accurate identification and analysis of signature blocks is important in many multimedia messaging and information retrieval applications such as email text-to-speech rendering, automatic construction of personal address databases, and interactive message retrieval. It is also a very challenging task, because signature blocks often appear in complex two-dimensional layouts which are guided only by loose conventions. Traditional text analysis methods designed to deal with sequential text cannot handle two-dimensional structures, while the highly unconstrained nature of signature blocks makes the application of two-dimensional grammars very difficult. In this article, we describe an algorithm for signature block analysis which combines two-dimensional structural segmentation with one-dimensional grammatical constraints. The information obtained from both layout and linguistic analysis is integrated in the form of weighted finite-state transducers. The algorithm is currently implemented as a component in a preprocessing system for email text-to-speech rendering.

The signature block is a common structured component found in e-mail messages. Accurate identification and analysis of signature blocks are important in many multimedia messaging and information retrieval applications such as e-mail text-to-speech rendering. Traditional text analysis methods designed to deal with sequential text cannot handle 2D structures, while the highly unconstrained nature of signature blocks makes the application of 2D grammars very difficult. In this paper we describe an algorithm for signature block analysis which combines 2D structural segmentation with 1D grammatical constraints. The information obtained from both geometrical and linguistic analysis are integrated in a form of weighted finite state transducers, and the final solution is the optimal interpretation under both constraints.

E-mail reading is one of the most important commercial applications of text-to-speech synthesis (TTS). Yet e-mail is one of the most difficult types of text to deal with, since it is both highly structured -frequently containing elements such as tables, signatures, "artwork" and quotations from previous messages; and at the same time often lacks any reliable unambiguous indicators for such structure. This paper describes Emu, an e-mail mark-up and rendering program that preprocesses e-mail for TTS. We discuss algorithms for detecting regions of interest in the input text; for "normalizing" the input; and for actually rendering the input through the Bell Labs TTS system.

We introduce a new method for size and orientation normalization of unconstrained handwritten words based on the Hough transform. A modified Hough transform is applied to extremum points along the y coordinate to extract parallel lines corresponding to the boundary lines separating different vertical zones of the handwritten word. One dimensional Gaussian smoothing with variable variance is applied in the Hough space to alleviate the problems caused by the large variation in natural handwriting and the sparseness of extremum points. The method has been tested with and incorporated into an HMM based writer-independent, unconstrained on-line handwriting recognition system and a 25% error rate reduction has been achieved.

A method for the automatic verification of on-line handwritten signatures using both global and local features as described. The global and local features capture various aspects of signature shape and dynamics of signature production. The authors demonstrate that with the addition to the global features of a local feature based on the signature likelihood obtained from hidden Markov models (HMM) the performance of signature verification improves significantly. The current version of the program, has 2.5% equal error rate. At the 1% false rejection (FR) point, the addition of the local information to the algorithm with only global features reduced the false acceptance (FA) rate from 13% to 5%.

This paper discusses some technical aspects of multimedia messaging systems. By 'messages', we mean non-real-time communications containing various media (text, speech, FAXed document images, video, electronic ink, etc.), passing between users over enterprise-wide telephony and data networks, and collecting in 'multimedia mailboxes'. Messaging, like 'digital libraries', is an application domain for indexing, retrieval, searching, etc.-but it offers some significantly different challenges and opportunities. We discuss some technical implications of the expected contents of messages, waiting time in mailboxes, and the particular needs of messaging users.

It is well known that N-best decoding for speech recognition coupled with post-processing can provide significant accuracy advantages. We have implemented and experimented with N-best decoding for handwriting recognition, using an N-best decoding algorithm that employs a synchronous forward pass and an asynchronous backward pass. One novel aspect of our algorithm is the use of pruning in the backward pass to constrain the search to candidates whose likelihood score is within a threshold specified using the likelihood score of the best candidate. We show that this algorithm is more efficient than traditional N-best decoding algorithms. A two-stage method is introduced in which the language model changes from a relaxed model during the N-best search to a more constrained model for rescoring in a second pass. This method reduces the computation needed for more detailed pattern matching by preselecting the N-best most likely candidates.

It is well known that language models are effective for increasing accuracy of speech and handwriting recognizers, but large language models are often required to achieve low model perplexity (or entropy) and still have adequate language coverage.We study three efficient methods for stochastic language modeling in the context of the stochastic pattern recognition problem and give results of a comparative performance analysis.In addition we show that a method which combines two of these language modeling techniques yields even better performance than the best of the single techniques tested.

Hidden Markov model (HMM) based recognition of handwriting is now quite common, but the incorporation of HMM's into a complex stochastic language model for handwriting recognition is still in its infancy. We have taken advantage of developments in the speech processing field to build a more sophisticated handwriting recognition system. The pattern elements of the handwriting model are subcharacter stroke types modeled by HMMs. These HMMs are concatenated to form letter models, which are further embedded in a stochastic language model. In addition to better language modeling, we introduce new handwriting recognition features of various kinds. Some of these features have invariance properties, and some are segmental, covering a larger region of the input pattern. We have achieved a writer independent recognition rate of 94.5% on 3,823 unconstrained handwritten word samples from 18 writers covering a 32 word vocabulary.

Fully automatic road recognition remains an elusive goal in spite of many years of research. Most practical systems today use tedious manual tracing for the entry of data from satellite and aerial images to geographical data bases. The paper presents a semi-automatic method for the entry of such data. First ribbons of high contrast are found by analyzing gray scale surface principal curvatures. Then, pixels belonging to such ribbons are fitted by conic splines, and then a graph is constructed whose nodes are end points of the arcs fitted by the splines. The key new idea is to assign edges between all nodes and label them with a cost function based on physical constraints on roads. Once a pair of end points is chosen, a shortest path algorithm is used to determine the road between them. Thus a global optimization is performed over all possible candidates.>