Graph Transduction Learning with Connectivity Constraints with Application to Multiple Foreground Cosegmentation
The proposed approach is based on standard graph transduction, semi-supervised learning (SSL) framework. Its key novelty is the integration of global connectivity constraints into this framework. Although connectivity leads to higher order constraints and their number is an exponential, finding the most violated connectivity constraint can be done efficiently in polynomial time. Moreover, each such constraint can be represented as a linear inequality. Based on this fact, we design a cutting-plane algorithm to solve the integrated problem. It iterates between solving a convex quadratic problem of label propagation with linear inequality constraints, and finding the most violated constraint. We demonstrate the benefits of the proposed approach on a realistic and very challenging problem of cosegmentation of multiple foreground objects in photo collections in which the foreground objects are not present in all photos. The obtained results not only demonstrate performance boost induced by the connectivity constraints, but also show a significant improvement over the state-of-the-art methods.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Learning on graphs using Orthonormal Representation is Statistically Consistent
Existing research \cite{reg} suggests that embedding graphs on a unit sphere can be beneficial in learning labels on the vertices of a graph. However the choice of optimal embedding remains an open issue. \emph{Orthonorm…
A Graph Transduction Game for Multi-target Tracking
Semi-supervised learning is a popular class of techniques to learn from labeled and unlabeled data. The paper proposes an application of a recently proposed approach of graph transduction that exploits game theoretic not…
Multiple People TrackingPosition Paper: Generalized grammar rules and structure-based generalization beyond classical equivariance for lexical tasks and transduction
Compositional generalization is one of the main properties which differentiates lexical learning in humans from state-of-art neural networks. We propose a general framework for building models that can generalize composi…
PositionRegular transductions with MCFG input syntax
We show that regular transductions for which the input part is generated by some multiple context-free grammar can be simulated by synchronous multiple context-free grammars. We prove that synchronous multiple context-fr…
Decentralized Global Connectivity Maintenance for Multi-Robot Navigation: A Reinforcement Learning Approach
The problem of multi-robot navigation of connectivity maintenance is challenging in multi-robot applications. This work investigates how to navigate a multi-robot team in unknown environments while maintaining connectivi…
Navigatereinforcement-learningReinforcement Learning (RL)Robot Navigation