Similarity-Based Pattern Recognition: Second International Workshop, SIMBAD 2013, York, UK, July 3-5, 2013, Proceedings (Image Processing, Computer Vision, Pattern Recognition, and Graphics)

✍ Scribed by Edwin Hancock (editor), Marcello Pelillo (editor)

• Publisher: Springer
• Year: 2013
• Tongue: English
• Leaves: 307
• Edition: 2013
• Category: Library

✦ Synopsis

This book constitutes the proceedings of the Second International Workshop on Similarity Based Pattern Analysis and Recognition, SIMBAD 2013, which was held in York, UK, in July 2013. The 18 papers presented were carefully reviewed and selected from 33 submissions. They cover a wide range of problems and perspectives, from supervised to unsupervised learning, from generative to discriminative models, from theoretical issues to real-world practical applications, and offer a timely picture of the state of the art in the field.

✦ Table of Contents

Preface
Organization
Table of Contents
Pattern Learning and Recognition on Statistical Manifolds: An Information-Geometric Review
1 Introduction
1.1 Learning Statistical Patterns and the Cram´er-Rao Lower Bound
1.2 Unsupervised Pattern Recognition
1.3 Supervised Pattern Recognition
1.4 Core Geometric Structures and Algorithmic Toolboxes
1.5 Outline of the Paper
2 Statistical Distances and Divergences
2.1 The Fundamental Kullback-Leibler Divergence
2.2 Genesis of Statistical Distances
2.3 Novel Quasi-Arithmetic α-Divergences and Chernoff
Information
3 Divergence, Invariance and Geometry
4 Rao Statistical Manifolds: A Riemannian Approach
4.1 Riemannian Construction of Rao Manifolds
4.2 Rao Riemannian Geodesic Metric Distance
4.3 Geometric Computing on Rao Statistical Manifolds
5 Amari-Chentsov Statistical Manifolds
5.1 Construction of Dually Flat Statistical Manifolds
5.2 Dual Geodesics: Exponential and Mixture Geodesics
5.3 Learning Statistical Patterns
5.4 Statistical Voronoi Diagrams
6 Conclusion and Perspectives
References
Dimension Reduction Methods for Image Pattern Recognition
1 Introduction
2 Related Works
3 Dimension Reduction Methods
3.1 Gaussian-Based Pyramid Transform
3.2 Random Projection
3.3 Two-Dimensional Random Projection
3.4 Two-Dimensional Discrete Cosine Transform
4 Classification Methods
4.1 Subspace Method
4.2 Mutual Subspace Method
4.3 Constraint Mutual Subspace Method
4.4 Two-Dimensional Tensorial Subspace Method
5 Experiments
6 Conclusions
References
Efficient Regression in Metric Spaces via Approximate Lipschitz Extension
1 Introduction
2 Bounds on Uniform Deviation via Fat Shattering
2.1 Preliminaries
2.2 Basic Generalization Bounds
2.3 Simultaneous Bounds for Multiple Lipschitz Constants
3 Structural Risk Minimization
3.1 Motivation and Construction
3.2 Solving the Linear Program
3.3 Solving the Quadratic Program
4 Approximate Lipschitz Extension
References
Data Analysis of (Non-)Metric Proximities at Linear Costs
1 Introduction
2 Transformation Techniques for Dissimilarity Data
2.1 Analyzing Dissimilarities by Means of Similarities for Small N
2.2 Analyzing Dissimilarities by Dedicated Methods for Small N
3 Nystr¨om Approximation
3.1 Nystr¨om Approximation for Similarities
3.2 Nystr¨om Approximation for Dissimilarity Data
4 Transformations of (Dis-)Similarities with Linear Costs
4.1 Transformation of Dissimilarities to Similarities
4.2 Non-metric (Dis-)Similarities
5 Experiments
6 Outlook and Conclusions
References
On the Informativeness of Asymmetric Dissimilarities
1 Introduction
2 Asymmetric Dissimilarities
2.1 Shapes and Images
2.2 Multiple Instance Learning
3 Dissimilarity Space
3.1 Prototype Selection
4 Combining the Asymmetry Information
5 Extended Asymmetric Dissimilarity Space
6 Experiments
6.1 Datasets
6.2 Experimental Setup
6.3 Results and Discussion
7 Conclusions
References
Information-Theoretic Dissimilarities for Graphs
1 Introduction
2 Divergences between Embeddings
2.1 Symmetrized Normalized Entropy Square Variation
2.2 Leonenko et al. Entropy Estimator
2.3 Henze-Penrose Divergence
2.4 Total Variation k-dP Divergence
2.5 Retrieval from GatorBait
3 Tensor-Based Divergences
3.1 Tensor-Based Graph Representations
3.2 Bregman and Total Bregman Divergences
4 Conclusions
References
Information Theoretic Pairwise Clustering
1 Introduction
2 Similarity Graphs and Random Walks
3 Clustering the States of a Markov Chain
4 The Clustering Algorithm
5 Related Work
6 Experimental Results
7 Conclusion
References
Correlation Clustering with Stochastic Labellings
1 Introduction
2 Correlation Clustering
2.1 Clustering with Noisy Correlation Graphs
3 Relaxed Formulations with Stochastic Labellings
4 Optimization Using the Baum-Eagon Inequality
4.1 Algorithms for Correlation Clustering with Stochastic
5 Ensemble of Random Functions Sampled from Kernel Space
6 Experiments
7 Conclusions
References
Break and Conquer: Efficient Correlation Clustering for Image Segmentation
1 Introduction
2 Correlation Clustering for Image Segmentation
3 Efficiently Finding the Optimal Segmentation
4 Experimental Results
4.1 Extracting Superpixels and Local Weights
4.2 Segmentations Results on Weizmann Two-Objects Dataset
4.3 Segmentations Results on BSDS500
4.4 Efficiency Analysis of the ILP Algorithm
4.5 Cutting Plane Intermediate Segmentation Results
References
Multi-task Averaging via Task Clustering
1 Introduction
2 Background
3 MTA in High Dimensional Spaces
4 k-MTA: Multi-task Averaging via Information Theoretic Clustering
4.1 Information Theoretic Tasks’ Similarity Measure
4.2 Spectral Clustering
4.3 Proposed Algorithm
5 Experimental Results
5.1 Artificial Dataset
5.2 School Dataset
6 Conclusions and Future Work
References
Modeling and Detecting Community Hierarchies
1 Introduction
2 Hierarchical Community Model
3 Hierarchical Community Detection Algorithm
4 Experiments
4.1 Evaluation on Real-World Networks
4.2 Evaluation on Synthetic Networks
5 Conclusion
References
Graph Characterization Using Gaussian Wave Packet Signature
1 Introduction
2 Graphs
3 Edge-Based Eigensystem
3.1 Vertex Supported Edge-Based Eigenfunctions
3.2 Edge-Interior Eigenfunctions
3.3 Normalization of Eigenfunctions
4 Solution of the Wave Equation
4.1 Initial Conditions
4.2 Gaussian Wave Packet
4.3 Complete Reconstruction
5 WavePacketSignatures
6 Experiments
6.1 Synthetic Dataset
6.2 Real-World Dataset
7 Conclusion and Future Work
References
Analysis of the Schrödinger Operator in the Context of Graph Characterization
1 Introduction
2 Heat Flow
3 Heat Kernel vs. Schrödinger Operator
3.1 Analysis of the Schrödinger Operator
3.2 The Quantum Energy Flow
3.3 Frequency Domain Analysis of the Schrödinger Operator
4 Experimental Results
4.1 Noise Sensitivity
4.2 Characterization of Synthetic Data
4.3 Characterization of Real-World Data
4.4 Network Dynamics Analysis
5 Conclusions and Future Work
References
Attributed Graph Similarity from the Quantum Jensen-Shannon Divergence
1 Introduction
2 Quantum Mechanical Background
2.1 Quantum Jensen-Shannon Divergence
3 A Similarity Measure for Attributed Graphs
3.1 A QJSD Kernel for Attributed Graphs
3.2 Kernel Computation
4 Experimental Results
4.1 Synthetic Data
4.2 Delaunay Graphs
4.3 Shock Graphs
5 Conclusions and Future Work
References
Entropy and Heterogeneity Measures for Directed Graphs
1 Introduction
1.1 Related Literature
1.2 Paper Outline
2 Von Neumann Entropy of Directed Graphs
2.1 Laplacian of Directed Graphs
2.2 Von Neumann Entropy of Undirected Graphs
2.3 Von Neumann Entropy of Directed Graphs
3 Heterogeneity Index and Commute Time
3.1 Heterogeneity Index of Directed Graphs
3.2 Commute Time of Directed Graphs
3.3 Relationship between Heterogeneity Index and Commute Time
4 Experiments and Evaluations
4.1 The Datasets
4.2 Entropy for Weakly and Strongly Directed Graphs
4.3 Heterogeneity Index and Commute Time
5 Conclusion
References
Fast Learning of Gamma Mixture Models with with k-MLE
1 Introduction and Prior Work
2 Exponential Families and Their Parametrizations
2.1 Definition
2.2 Bregman Divergences
2.3 Bijection between Exponential Families and Bregman Divergences
2.4 Gamma Family Is an Exponential Family
3 Learning Mixtures of Exponential Families
3.1 Bregman Soft Clustering
3.2 k-Maximum Likelihood Estimator
4 k-MLE for Gamma
4.1 Gamma with Fixed Rate Parameter
4.2 Maximum Likelihood Estimator
4.3 Learning Mixtures
4.4 Convergence to a Local Maximum
5 Expectation-Maximization for Gamma Mixtures
6 Experiments
6.1 On Synthetic Data
6.2 On a Real Dataset
7 Conclusion
References
Exploiting Geometry in Counting Grids
1 Introduction
2 Background: Counting Grid Model
3 (Dis-)Similarity Measure for CG
4 Experimental Evaluation
4.1 Microarray Classfication
4.2 Brain Classification
4.3 Experimental Details
4.4 Results
5 Conclusions
References
On the Dissimilarity Representation and Prototype Selection for Signature-Based
Bio-cryptographic Systems
1 Introduction
2 Background
3 Proposed Dissimilarity Representation and Prototype Selection Method
3.1 Design of the Encoding Messages and the Dissimilarity Measure
3.2 Prototype Selection and Dissimilarity Threshold Optimization
4 Experimental Methodology
4.1 Database
4.2 Feature Extraction
4.3 Design of Encoding Messages and Dissimilarity Measure
4.4 Prototype Selection and Dissimilarity Threshold Optimization
4.5 Performance Measures
5 Experimental Results
6 Conclusions and Future Work
References
A Repeated Local Search Algorithm for BiClustering of Gene Expression Data
1 Introduction
2 Related Work
3 The Biclustering Problem
4 A Repeated Local Search Algorithm for Biclustering
5 Experiments
6 Conclusion
References
Author Index