News: An article accepted to International Journal of Dentistry.
News: ICDM 2011 paper accepted.
News: I received PhD in Machine Learning from University of Pittsburgh.
News: I submitted the final version of my dissertation on August 18th, 2011.
News: I defended my dissertation on August 1st, 2011.
News: I will be giving talk at Microsoft Research on July 6th, 10:30am in Research Room A
News: I will be at ICML from June 24th till July 2nd.

Michal is a postdoctoral researcher in SequeL team at INRIA Lille - Nord Europe, France working with Remi Munos, Mohammad Ghavamzadeh, Alessandro Lazaric, and Daniil Ryabko. He is funded from the CompLACS project. Michal's primary research interests are in machine learning with emphasis on semi-supervised learning and conditional anomaly detection. The common thread of his work has been adaptive graph-based learning and its application to the real world applications such as medical error detection and face recognition. He graduated in August 2011 from University of Pittsburgh. Miloš Hauskrecht was his advisor. Michal's 1-page resume and long CV .

• 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 [3+2 citations]
• 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.

  [3+3 citations]
• 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] [3+2 citations]
• 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.

  [3 + 2 citations]

Contact:

• Inria Lille - Nord Europe, equipe SequeL (bureau: 009)
• Parc Scientifique de la Haute-Bornee
• 40 avenue Halley
• 59650 Villeneuve d'Ascq, France
• phone: +1 (412) 499-3474