Selected Publications

• Michal Valko, Mohammad Ghavamzadeh, Alessandro Lazaric: Semi-supervised inverse reinforcement learning, in European Workshop on Reinforcement Learning (EWRL 2012)
• Michal Valko, Branislav Kveton, Hamed Valizadegan, Gregory F. Cooper, Milos Hauskrecht: Conditional Anomaly Detection with Soft Harmonic Functions, in International Conference on Data Mining (ICDM 2011) bibtex abstract

  Abstract:In this paper, we consider the problem of conditional anomaly detection that aims to identify data instances with an unusual response or a class label. We develop a new non-parametric approach for conditional anomaly detection based on the soft harmonic solution, with which we estimate the confidence of the label to detect anomalous mislabeling. We further regularize the solution to avoid the detection of isolated examples and examples on the boundary of the distribution support. We demonstrate the efficacy of the proposed method on several synthetic and UCI ML datasets in detecting unusual labels when compared to several baseline approaches. We also evaluate the performance of our method on a real-world electronic health record dataset where we seek to identify unusual patient-management decisions.

• Michal Valko: Adaptive Graph-Based Algorithms for Conditional Anomaly Detection and Semi-Supervised Learning, PhD thesis, University of Pittsburgh (PITT 2011) bibtex abstract

  Abstract:We develop graph-based methods for semi-supervised learning based on label propagation on a data similarity graph. When data is abundant or arrive in a stream, the problems of computation and data storage arise for any graph-based method. We propose a fast approximate online algorithm that solves for the harmonic solution on an approximate graph. We show, both empirically and theoretically, that good behavior can be achieved by collapsing nearby points into a set of local representative points that minimize distortion. Moreover, we regularize the harmonic solution to achieve better stability properties. We also present graph-based methods for detecting conditional anomalies and apply them to the identification of unusual clinical actions in hospitals. Our hypothesis is that patient-management actions that are unusual with respect to the past patients may be due to errors and that it is worthwhile to raise an alert if such a condition is encountered. Conditional anomaly detection extends standard unconditional anomaly framework but also faces new problems known as fringe and isolated points. We devise novel nonparametric graph-based methods to tackle these problems. Our methods rely on graph connectivity analysis and soft harmonic solution. Finally, we conduct an extensive human evaluation study of our conditional anomaly methods by 15 experts in critical care.

• Michal Valko, Branislav Kveton, Ling Huang, Daniel Ting: Online Semi-Supervised Learning on Quantized Graphs in Proceedings of the 26nd Annual Conference on Uncertainty in Artificial Intelligence (UAI 2010) bibtex abstract

  Abstract:In this paper, we tackle the problem of online semi-supervised learning (SSL). When data arrive in a stream, the dual problems of computation and data storage arise for any SSL method. We propose a fast approximate online SSL algorithm that solves for the harmonic solution on an approximate graph. We show, both empirically and theoretically, that good behavior can be achieved by collapsing nearby points into a set of local "representative points" that minimize distortion. Moreover, we regularize the harmonic solution to achieve better stability properties. We apply our algorithm to face recognition and optical character recognition applications to show that we can take advantage of the manifold structure to outperform the previous methods. Unlike previous heuristic approaches, we show that our method yields provable performance bounds.

  Video: Adaptation, Video: OfficeSpace, spotlight, poster
• Branislav Kveton, Michal Valko, Ali Rahimi, Ling Huang: Semi-Supervised Learning with Max-Margin Graph Cuts in Thirteenth International Conference on Artificial Intelligence and Statistics (AISTATS 2010) bibtex abstract

  Abstract:This paper proposes a novel algorithm for semisupervised learning. This algorithm learns graph cuts that maximize the margin with respect to the labels induced by the harmonic function solution. We motivate the approach, compare it to existing work, and prove a bound on its generalization error. The quality of our solutions is evaluated on a synthetic problem and three UCI ML repository datasets. In most cases, we outperform manifold regularization of support vector machines, which is a state-of-the-art approach to semi-supervised max-margin learning.

• Milos Hauskrecht, Michal Valko, Shyam Visweswaram, Iyad Batal, Gilles Clermont, Gregory Cooper: Conditional Outlier Detection for Clinical Alerting in Annual American Medical Informatics Association conference (AMIA 2010) bibtex abstract

  Abstract:We develop and evaluate a data-driven approach for detecting unusual (anomalous) patient-management actions using past patient cases stored in an electronic health record (EHR) system. Our hypothesis is that patient-management actions that are unusual with respect to past patients may be due to a potential error and that it is worthwhile to raise an alert if such a condition is encountered. We evaluate this hypothesis using data obtained from the electronic health records of 4,486 post-cardiac surgical patients. We base the evaluation on the opinions of a panel of experts. The results support that anomaly-based alerting can have reasonably low false alert rates and that stronger anomalies are correlated with higher alert rates.

  [Homer Warner Best Paper Award]
• Branislav Kveton, Michal Valko, Matthai Phillipose, Ling Huang: Online Semi-Supervised Perception: Real-Time Learning without Explicit Feedback in The Fourth IEEE Online Learning for Computer Vision Workshop in The 23rd IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2010 - OLCV) [best paper Google Award] bibtex abstract

  Abstract:This paper proposes an algorithm for real-time learning without explicit feedback. The algorithm combines the ideas of semi-supervised learning on graphs and online learning. In particular, it iteratively builds a graphical representation of its world and updates it with observed examples. Labeled examples constitute the initial bias of the algorithm and are provided offline, and a stream of unlabeled examples is collected online to update this bias. We motivate the algorithm, discuss how to implement it efficiently, prove a regret bound on the quality of its solutions, and apply it to the problem of real-time face recognition. Our recognizer runs in real time, and achieves superior precision and recall on 3 challenging video datasets.

Other Publications

• Thomas C. Hart, Patricia M. Corby, Milos Hauskrecht, Ok Hee Ryu, Richard Pelikan, Michal Valko, Maria B. Oliveira, Gerald T. Hoehn, and Walter A. Bretz: Identification of Microbial and Proteomic Biomarkers in Early Childhood Caries in International Journal of Dentistry (IJD 2011) bibtex abstract

  Abstract:The purpose of this study was to provide a univariate and multivariate analysis of genomic microbial data and salivary mass-spectrometry proteomic profiles for dental caries outcomes. In order to determine potential useful biomarkers for dental caries, a multivariate classification analysis was employed to build predictive models capable of classifying microbial and salivary sample profiles with generalization performance. We used high-throughput methodologies including multiplexed microbial arrays and SELDI-TOF-MS profiling to characterize the oral flora and salivary proteome in 204 children aged 1-8 years (n = 118 caries-free, n = 86 caries-active). The population received little dental care and was deemed at high risk for childhood caries. Findings of the study indicate that models incorporating both microbial and proteomic data are superior to models of only microbial or salivary data alone. Comparison of results for the combined and independent data suggests that the combination of proteomic and microbial sources is beneficial for the classification accuracy and that combined data lead to improved predictive models for caries-active and caries-free patients. The best predictive model had a 6\% test error, >92\% sensitivity, and >95\% specificity. These findings suggest that further characterization of the oral microflora and the salivary proteome associated with health and caries may provide clinically useful biomarkers to better predict future caries experience.

• Michal Valko, Hamed Valizadegan, Branislav Kveton, Gregory F. Cooper, Milos Hauskrecht: Conditional Anomaly Detection Using Soft Harmonic Functions: An Application to Clinical Alerting, Workshop on Machine Learning for Global Challenges in The 28th International Conference on Machine Learning (ICML 2011 - Global) bibtex abstract

  Abstract:Timely detection of concerning events is an important problem in clinical practice. In this paper, we consider the problem of conditional anomaly detection that aims to identify data instances with an unusual response, such as the omission of an important lab test. We develop a new non-parametric approach for conditional anomaly detection based on the soft harmonic solution, with which we estimate the confidence of the label to detect anomalous mislabeling. We further regularize the solution to avoid the detection of isolated examples and examples on the boundary of the distribution support. We demonstrate the efficacy of the proposed method in detecting unusual labels on a real-world electronic health record dataset and compare it to several baseline approaches.

  poster spotlight
• Michal Valko, Milos Hauskrecht: Feature importance analysis for patient management decisions in 13th International Congress on Medical Informatics (MEDINFO 2010) bibtex abstract

  Abstract:The objective of this paper is to understand what characteris-tics and features of clinical data influence physician.s deci-sion about ordering laboratory tests or prescribing medica-tions the most. We conduct our analysis on data and decisions extracted from electronic health records of 4486 post-surgical cardiac patients. The summary statistics for 335 different lab order decisions and 407 medication decisions are reported. We show that in many cases, physician.s lab-order and medication decisions are predicted well by simple patterns such as last value of a single test result, time since a certain lab test was ordered or time since certain procedure was executed.

• Michal Valko, Gregory Cooper, Amy Seybert, Shyam Visweswaran, Melissa Saul, Milos Hauskrecht: Conditional anomaly detection methods for patient-management alert systems, Workshop on Machine Learning in Health Care Applications in The 25th International Conference on Machine Learning (ICML-2008 - MLHealth) bibtex abstract

  Abstract:Anomaly detection methods can be very useful in identifying unusual or interesting patterns in data. A recently proposed conditional anomaly detection framework extends anomaly detection to the problem of identifying anomalous patterns on a subset of attributes in the data. The anomaly always depends (is conditioned) on the value of remaining attributes. The work presented in this paper focuses on instance-based methods for detecting conditional anomalies. The methods rely on the distance metric to identify examples in the dataset that are most critical for detecting the anomaly. We investigate various metrics and metric learning methods to optimize the performance of the instance-based anomaly detection methods. We show the benefits of the instance-based methods on two real-world detection problems: detection of unusual admission decisions for patients with the community-acquired pneumonia and detection of unusual orders of an HPF4 test that is used to confirm Heparin induced thrombocytopenia - a life-threatening condition caused by the Heparin therapy.

  talk
• Michal Valko, Milos Hauskrecht: Distance metric learning for conditional anomaly detection, Twenty-First International Florida AI Research Society Conference (FLAIRS 2008) bibtex abstract

  Abstract:Anomaly detection methods can be very useful in identifying unusual or interesting patterns in data. A recently proposed conditional anomaly detection framework extends anomaly detection to the problem of identifying anomalous patterns on a subset of attributes in the data. The anomaly always depends (is conditioned) on the value of remaining attributes. The work presented in this paper focuses on instance-based methods for detecting conditional anomalies. The methods depend heavily on the distance metric that lets us identify examples in the dataset that are most critical for detecting the anomaly. To optimize the performance of the anomaly detection methods we explore and study metric learning methods. We evaluate the quality of our methods on the Pneumonia PORT dataset by detecting unusual admission decisions for patients with the community-acquired pneumonia. The results of our metric learning methods show an improved detection performance over standard distance metrics, which is very promising for building automated anomaly detection systems for variety of intelligent monitoring applications.

• Michal Valko, Richard Pelikan, Milos Hauskrecht: Learning predictive models for combinations of heterogeneous proteomic data sources, AMIA Summit on Translational Bioinformatics (STB 2008) [outstanding paper award] bibtex abstract

  Abstract:Multiple technologies that measure expression levels of protein mixtures in the human body offer a potential for detection and understanding the disease. The recent increase of these technologies prompts researchers to evaluate the individual and combined utility of data generated by the technologies. In this work, we study two data sources to measure the expression of protein mixtures in the human body: whole-sample MS profiling and multiplexed protein arrays. We investigate the individual and combined utility of these technologies by learning and testing a variety of classification models on the data from a pancreatic cancer study. We show that for the combination of these two (heterogeneous) datasets, classification models that work well on one of them individually fail on the combination of the two datasets. We study and propose a class of model fusion methods that acknowledge the differences and try to reap most of the benefits from their combination.

  talk
• Milos Hauskrecht, Michal Valko, Branislav Kveton, Shyam Visweswaram, Gregory Cooper: Evidence-based Anomaly Detection in Clinical Domains in Annual American Medical Informatics Association conference (AMIA 2007). [nominated for the best paper award] bibtex abstract

  Abstract:Anomaly detection methods can be very useful in identifying interesting or concerning events. In this work, we develop and examine new probabilistic anomaly detection methods that let us evaluate management decisions for a specific patient and identify those decisions that are highly unusual with respect to patients with the same or similar condition. The statistics used in this detection are derived from probabilistic models such as Bayesian networks that are learned from a database of past patient cases. We evaluate our methods on the problem of detection of unusual hospitalization patterns for patients with community acquired pneumonia. The results show very encouraging detection performance with 0.5 precision at 0.53 recall and give us hope that these techniques may provide the basis of intelligent monitoring systems that alert clinicians to the occurrence of unusual events or decisions.

• Wendy W. Chapman, John N. Dowling, Gregory F. Cooper, Milos Hauskrecht and Michal Valko: A Comparison of Chief Complaints and Emergency Department Reports for Identifying Patients with Acute Lower Respiratory Syndrome in Proceedings of the National Syndromic Surveillance Conference (ISDS 2006) bibtex abstract

  Abstract:Automated syndromic surveillance systems often classify patients into syndromic categories based on free-text chief complaints. Chief complaints (CC) demonstrate low to moderate sensitivity in identify-ing syndromic cases. Emergency Department (ED) reports promise more detailed clinical information that may increase sensitivity of detection.

• Miloš Hauskrecht, Richard Pelikan, Michal Valko, James Lyons-Weiler: Feature Selection and Dimensionality Reduction in Genomics and Proteomics. Fundamentals of Data Mining in Genomics and Proteomics, eds. Berrar, Dubitzky, Granzow. Springer (2006) bibtex abstract

  Abstract:Finding reliable, meaningful patterns in data with high numbers of attributes can be extremely difficult. Feature selection helps us to decide what attributes or combination of attributes are most important for finding these patterns. In this chapter, we study feature selection methods for building classification models from high-throughput genomic (microarray) and proteomic (mass spectrometry) data sets. Thousands of feature candidates must be analyzed, compared and combined in such data sets. We describe the basics of four different approaches used for feature selection and illustrate their effects on an MS cancer proteomic data set. The closing discussion provides assistance in performing an analysis in high-dimensional genomic and proteomic data.

• Michal Valko, Nuno C. Marques, Marco Castelani: Evolutionary Feature Selection for Spiking Neural Network Pattern Classifiers in Proceedings of Portuguese Conference on Artificial Intelligence (EPIA 2005), eds. Bento et al., IEEE, pages 24-32. bibtex abstract

  Abstract:This paper presents an application of the biologically realistic JASTAP neural network model to classification tasks. The JASTAP neural network model is presented as an alternative to the basic multi-layer perceptron model. An evolutionary procedure previously applied to the simultaneous solution of feature selection and neural network training on standard multi-layer perceptrons is extended with JASTAP model. Preliminary results on IRIS standard data set give evidence that this extension allows the use of smaller neural networks that can handle noisier data without any degradation in classification accuracy.

• Michal Valko Evolving Neural Networks for Statistical Decision Theory, Comenius University, Bratislava, 2005 (master thesis) (2005) Advisor: Radoslav Harman thesis@sk bibtex abstract

  Abstract:Real biological networks are able to make decisions. We will show that this behavior can be observed even in some simple architectures of biologically plausible neural models. The great interest of this thesis is also to contribute to methods of statistical decision theory by giving a lead how to evolve the neural networks to solve miscellaneous decision tasks.

  talk

Invited talks

• Michal Valko: Adaptive Graph-Based Algorithms, Presented on July 6th, 2011 at Microsoft Research Redmond (MSR 2011) video
• Michal Valko: Online Semi-Supervised Learning, Presented at MPI Tuebingen, Germany
• Michal Valko: Semi-supervised Learning with Random Walks on Graphs, Presented at 6th Comenius University Alumni conference (TAM 2009) talk

Presentations

• Michal Valko: Graph-Based Anomaly Detection with Soft Harmonic Functions: Presented at CS Department Research Competition (Research 2011) [#1st place] talk also at (Grad Expo 2011) and (CS DAY 2011) poster
• Branislav Kveton, Michal Valko:, Matthai Philiposse: Real-Time Adaptive Face Recognition, Presented at 23rd Neural Information Processing Systems conference (NIPS 2009), Video: Adaptation, Video: OfficeSpace, poster #1, poster #2
• Michal Valko:, Branislav Kveton, Matthai Philiposse: Robust Face Recognition Using Online Learning, Presented at 9th University of Pittsburgh Science conference (SCIENCE 2009) Live Demonstration (Grad Expo 2010) talk and (CS Day 2010) poster
• Michal Valko: Conditional anomaly detection with adaptive similarity metric: Presented at CS Department Research Competition (Research 2008) [#1st place] talk
• Michal Valko, Milos Hauskrecht, G. Cooper, S. Visweswaran, M. Saul, A. Seybert, J. Harrison, A. Post: Conditional Anomaly Detection, Presented at (CS Day 2008) [#1st by people, #2nd by faculty] also at University of Pittsburgh, Arts & Sciences (Grad Expo 2008) poster

References

• miki.bib - bibtex file with references I often use