*De Bie Tijl and Cristianini Nello*

- Published in print:
- 2006
- Published Online:
- August 2013
- ISBN:
- 9780262033589
- eISBN:
- 9780262255899
- Item type:
- chapter

- Publisher:
- The MIT Press
- DOI:
- 10.7551/mitpress/9780262033589.003.0007
- Subject:
- Computer Science, Machine Learning

This chapter discusses an alternative approach that is based on a convex relaxation of the optimization problem associated with support vector machine transduction. The result is a semi-definite ...
More

This chapter discusses an alternative approach that is based on a convex relaxation of the optimization problem associated with support vector machine transduction. The result is a semi-definite programming (SDP) problem which can be optimized in polynomial time, the solution of which is an approximation of the optimal labeling as well as a bound on the true optimum of the original transduction objective function. To further decrease the computational complexity, this chapter proposes an approximation that allows solving transduction problems of up to 1,000 unlabeled samples. Finally, the formulation is extended to more general settings of semi-supervised learning, where equivalence and inequivalence constraints are given on labels of some of the samples.Less

This chapter discusses an alternative approach that is based on a convex relaxation of the optimization problem associated with support vector machine transduction. The result is a semi-definite programming (SDP) problem which can be optimized in polynomial time, the solution of which is an approximation of the optimal labeling as well as a bound on the true optimum of the original transduction objective function. To further decrease the computational complexity, this chapter proposes an approximation that allows solving transduction problems of up to 1,000 unlabeled samples. Finally, the formulation is extended to more general settings of semi-supervised learning, where equivalence and inequivalence constraints are given on labels of some of the samples.

*Shin Hyunjung and Tsuda Koji*

- Published in print:
- 2006
- Published Online:
- August 2013
- ISBN:
- 9780262033589
- eISBN:
- 9780262255899
- Item type:
- chapter

- Publisher:
- The MIT Press
- DOI:
- 10.7551/mitpress/9780262033589.003.0020
- Subject:
- Computer Science, Machine Learning

This chapter describes an algorithm to assign weights to multiple graphs within graph-based semi-supervised learning. Both predicting class labels and searching for weights for combining multiple ...
More

This chapter describes an algorithm to assign weights to multiple graphs within graph-based semi-supervised learning. Both predicting class labels and searching for weights for combining multiple graphs are formulated into one convex optimization problem. The graph-combining method is applied to functional class prediction of yeast proteins. When compared with individual graphs, the combined graph with optimized weights performs significantly better than any single graph. When compared with the semi-definite programming-based support vector machine (SDP/SVM), it shows comparable accuracy in a remarkably short time. Compared with a combined graph with equal-valued weights, this method could select important graphs without loss of accuracy, which implies the desirable property of integration with selectivity.Less

This chapter describes an algorithm to assign weights to multiple graphs within graph-based semi-supervised learning. Both predicting class labels and searching for weights for combining multiple graphs are formulated into one convex optimization problem. The graph-combining method is applied to functional class prediction of yeast proteins. When compared with individual graphs, the combined graph with optimized weights performs significantly better than any single graph. When compared with the semi-definite programming-based support vector machine (SDP/SVM), it shows comparable accuracy in a remarkably short time. Compared with a combined graph with equal-valued weights, this method could select important graphs without loss of accuracy, which implies the desirable property of integration with selectivity.

*Valerio Scarani*

- Published in print:
- 2019
- Published Online:
- September 2019
- ISBN:
- 9780198788416
- eISBN:
- 9780191830327
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780198788416.003.0006
- Subject:
- Physics, Particle Physics / Astrophysics / Cosmology, Theoretical, Computational, and Statistical Physics

Part II is devoted to the applied side of nonlocality: device-independent certification of quantumness. After an introduction to this idea, the first chapter deals with the characterisation of the ...
More

Part II is devoted to the applied side of nonlocality: device-independent certification of quantumness. After an introduction to this idea, the first chapter deals with the characterisation of the set of quantum behaviors. Since this set is not easily parametrised, in practice one often works with outer approximations, membership of which can be cast as a semi-definite program.Less

Part II is devoted to the applied side of nonlocality: device-independent certification of quantumness. After an introduction to this idea, the first chapter deals with the characterisation of the set of quantum behaviors. Since this set is not easily parametrised, in practice one often works with outer approximations, membership of which can be cast as a semi-definite program.