Definition: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
Input: We study a semi-supervised learning method based on the similarity graph and Regularized Laplacian. We give convenient optimization formulation of the Regularized Laplacian method and establish its various properties. In particular, we show that the kernel of the method can be interpreted in terms of discrete and continuous time random walks and possesses several important properties of proximity measures. Both optimization and linear algebra methods can be used for efficient computation of the classification functions. We demonstrate on numerical examples that the Regularized Laplacian method is competitive with respect to the other state of the art semi-supervised learning methods. Key-words: Semi-supervised learning, Graph-based learning, Regularized Laplacian, Proximity measure, Wikipedia article classification ∗ Corresponding author. K. Avrachenkov is with Inria Sophia Antipolis, 2004 Route des Lucioles, 06902, Sophia Antipolis, France k.avrachenkov@inria.fr † P. Chebotarev is with Trapeznikov Institute of Control Sciences of the Russian Academy of Sciences, 65 Profsoyuznaya Str., Moscow, 117997, Russia ‡ A. Mishenin is with St. Petersburg State University, Faculty of Applied Mathematics and Control Processes, Peterhof, 198504, Russia § This work was partially supported by Campus France, Alcatel-Lucent Inria Joint Lab, EU Project Congas FP7-ICT-2011-8-317672, and RFBR grant No. 13-07-00990. L’Apprentissage Semi-supervisé avec Laplacian Régularisé Résumé : Nous étudions une méthode d’apprentissage semi-supervisé, basé sur le graphe de similarité et Laplacian régularisé. Nous formalisons la méthode comme un problème d’optimisation convexe et quadratique et nous établissons ses diverses propriétés. En particulier, nous montrons que le noyau de la méthode peut être interprété en termes des marches aléatoires en temps discret et continu et possède plusieurs propriétés importantes des mesures de proximité. Les techniques d’optimisation ainsi que les techniques d’algébre linéaire peuvent être utilisé pour un calcul efficace des fonctions de classification. Nous démontrons sur des exemples numériques que la méthode de Laplacian régularisé est concurrentiel par rapport aux autres état de l’art méthodes d’apprentissage semi-supervisé. Mots-clés : Apprentissage Semi-supervisé, Apprentissage basé sur le graphe de similarité, Laplacian régularisé, mesure de proximité, classification des articles Wikipedia Semi-supervised Learning with Regularized Laplacian 3

Semi-supervised Learning with Regularized Laplacian