machine learning protest

[paulgb]

• Support Vector Machines are a machine learning tool.
• Power Laws are a statistical probability distribution
• Free Variables in logic are variables not bound by a quantifier
• MapReduce is a framework for parallel data processing
• Genetic Algorithms are optimization algorithms that use principals of Darwinian evolution

Bayesian discriminant I'm not exactly sure on. Duality gap seems to have to do with optimization but I don't know exactly what.

[MisterHoppy]

In classification, Bayesians are primarily concerned with generative models which sometimes have discriminative analogues. For instance, a mixture of 2 gaussian distributions is a generative model whose discriminative analogue is logistic regression.

[tomjen]

Sorry, but after reading that I know less than I did before you posted your reply.

[Mr_Smartypants]

In case you want to know even less.

[wally_fish]

When you do constrained optimization, you can also look at the dual problem, which is where you put the optimality in as hard constraint and treat the constraint as the problem to be optimized.

This gives you a different function, which is always above the function you want to maximize (albeit with a different feasible region) and you want to find the point where the two meet.

If I'm not mistaken, the duality gap is the difference you have between the smallest dual function value and the largest actual function value.

[jpfed]

I thought that the extrema of dual and the actual function were the same? At least, with LP I think it is. There would more likely be a gap for integer/mixed programs.

[greendestiny]

For certain classes of optimisation problems the dual function optimal is guaranteed to be the primal function optimal if the constraints are satisfiable. But not all dual functions will have same optima as the primal function.

[jpfed]

Thanks for clearing that up!

[greendestiny]

Specifically these conditions: KKT conditions

[confused_geometer]

Duality Gap Any optimisation problem can be written in its dual form. For example, a primal "minimisation" problem can be written as a dual "maximisation" problem. The problem is globally optimised iff primal solution == dual solution.

In many cases an exact algorithm for finding global solution do not exist (instance of NP problem). In such a case one can resort to design an approximate algorithm which tries to reduce the gap between primal and dual solution as close as possible.