Data-driven Graph Transduction

Machine learning has been an emerging topic in recent two decades,which takes a critical place in today's research on artificial intelligence.Machine learning aims to design computer program to extract general knowledge from a set of known data,which can be used to process or analyze the future data.Machine learning is an interdisciplinary of computer science,statistics and cognitive science,etc,and has been widely applied to public security,national defense construction,biomedical research and so on.As an important approach of machine learning,graph transduction utilizes a weighted graph to assign unlabeled examples explicit class labels rather than builds a general decision function based on the available labeled examples.Besides,considering that the prior knowledge is often difficult to obtain,this thesis mainly studies how to develop prior knowledge free graph transduction algorithms that are directly based on the existing data.Specifically,this thesis develops a series of data-driven graph transduction methodologies via iterative or non-iterative way,which are summarized as follows:In Chapter 2,a non-iterative algorithm named “Label Prediction via Deformed Graph Laplacian”(LPDGL)is proposed.Different from the existing methods that usually employ a traditional graph Laplacian to achieve label smoothness among pairs of examples,LPDGL introduces a deformed graph Laplacian,which not only induces the existing pairwise smoothness term,but also leads to a novel local smoothness term.This local smoothness term detects the ambiguity of each example by exploring the associated degree,and assigns confident labels to the examples with large degree,as well as allocates “weak labels” to the uncertain examples with small degree.As a result,more robust transduction performance than some existing representative algorithms can be achieved by LPDGL.Although LPDGL is designed for transduction purpose,it can be easily extended to inductive settings.In Chapter 3,an iterative label propagation approach called “Fick's Law Assisted Propagation”(FLAP)is proposed for graph transduction.To be specific,this thesis regards label propagation on the graph as the practical fluid diffusion on a plane,and develops a novel label propagation algorithm by utilizing a well-known physical theory called Fick's Law of Diffusion.Different from existing machine learning models that are based on some heuristic principles,FLAP conducts label propagation in a “natural” way,namely when and how much label information is received or transferred by an example,or where these labels should be propagated to,are naturally governed.As a consequence,FLAP not only yields more robust propagation results,but also requires less computational time than the existing iterative methods.In Chapter 4,a propagation framework called “Teaching-to-Learn and Learning-to-Teach”(TLLT)is proposed.In TLLT,a “teacher”(i.e.a teaching algorithm that can guide the learning process)is introduced to guide the label propagation.Different from existing methods that equally treat all the unlabeled examples,TLLT assumes that different examples have different classification difficulties,and their propagations should follow a simple-to-difficult sequence.As such,the previously “leaned” simple examples can ease the learning for the subsequent more difficult examples,and thus these difficult examples can be correctly classified.In each iteration of propagation,the teacher will designate the simplest examples to the “learner”(i.e.a propagation algorithm).After“learning” these simplest examples,the learner will deliver a learning feedback to the teacher to assist it in choosing the next simplest examples.Due to the collaborate teaching and learning process,all the unlabeled examples are propagated in a well-organized sequence,which contributes to the improved performance over existing methods.In Chapter 5,the TLLT framework proposed in Chapter 4 is utilized to accomplish saliency detection,so that the saliency values of all the superpixels are decided from simple superpixels to more difficult ones.The difficulty of a superpixel is judged by its informativity,individuality,inhomogeneity,and connectivity.As a result,our saliency detector generates manifest saliency maps,and outperforms baseline methods on the typical public datasets.