Greedy method, matroid and submodular function (refer)

Greedy, matroid, submodular function

CLRS The first 16 The chapter is devoted to greedy algorithm (Greedy Algorithm) The theoretical basis of is matroid (matroid) . Specific theories don't repeat nonsense . In fact, the more appropriate model is called Greedoid. Take a look at the relevant theories CLRS It's easy to understand . Be careful CLRS The so-called weighted matroid mentioned in the middle , In fact, it shows that the objective function is linear ( Function value F(A) It's equal to the set A The sum of the weights of each element in ). Edmonds 1970 As early as 70 In the s, a paper without abstract proved that the greedy algorithm for linear functions on the structure of matroids must be optimal . (http://portal.acm.org/citation.cfm?id=885912 )

real It is not linear in international application , It's a man named Yamo (submodular), See Wikipedia for specific details . (http://en.wikipedia.org/wiki/Supermodular ). The property of submodule is in popular words , As more elements are added to the set ,  F The less benefit the function value gets ( Diminishing marginal utility ). Obviously, the utility function of many problems in the world is of this nature . Such as the amount of information (Information Gain) And other utility functions . This function is in machine learning , It is widely used in economics and game theory . For example, the arrangement of sensors , Google Optimize the placement of advertising words , Optimal placement of Sensor Networks , Set coverage problem and so on . At the same time, submodular functions and matroids are closely related , Such as the rank of matroids (rank) The definition of , It must be a submodular function .

The most interesting result is , Unless P=NP, Otherwise, for submodular functions on matroids , Greedy algorithm is the best maximization algorithm that can be completed in polynomial time . This completely dispelled the enthusiasm of comrades to study new algorithms ： Use it directly , Anyway, there is nothing better . As for the minimization of modular functions , Another polynomial algorithm . Like linear programming , Ellipse method can solve . Other polynomial methods are not of high order .

Cam . MIT, UIUC Recently, submodular functions have been used to do WSN Or the article of graph partition . If you are interested, download it yourself . The gossip is , Google About AdWords Optimization auction paper , There is nothing about matroids and submodules , The same theoretical results are obtained , And spent a lot of effort to prove the conclusion that the above greedy algorithm is optimal in the bound estimation . Have to say , Learning mathematics is still a little good , At least don't spend a long time proving a theorem again . One of Cameron's team is more heroic , In the past, machine learning was all about the optimization of convex functions ( Such as SVM ), Next decade , Submodular functions will dominate the field of machine learning optimization .

Interested bosses, please enjoy the following articles .

An Introduction to Submodular Functions and Optimization. It belongs to the introduction
www.ima.umn.edu/optimization/seminar/queyranne.pdf

Card not in ICML do tutorial. Talked about the connection with machine learning
http://www.select.cs.cmu.edu/tutorials/submodularity-slides.pdf

Adwords Auctions with Decreasing Valuation Bids.  Google The paper of
www-static.cc.gatech.edu/grads/g/gagang/wine07_full.pdf

Revisiting the Greedy Approach to Submodular Set Function Maximization. MIT Sloan Thesis of the school of management
http://www.optimization-online.org/DB_FILE/2007/08/1740.pdf
Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical Studies. Cameron used to do a sensor placement .
http://www.select.cs.cmu.edu/publications/paperdir/jmlr2008-krause-singh-guestrin.pdf

It seems that I have to read the CLRS(introduction to Algorithms) carefully. There are lots of theory and algorithms that I have never know.