Source-linked AI summary
Shift-Invariance Sparse Coding for Audio Classification
Roger Grosse, Rajat Raina, Helen Kwong, Andrew Y. Ng
TL;DR
Audio classification needs useful representations from limited labeled data, while ordinary sparse coding handles temporal occurrences inefficiently. The paper develops an efficient SISC algorithm and reports useful speech and music classification features, with performance comparable to or better than MFCCs under some conditions.
Problem
Ordinary sparse coding treats each acoustic pattern at each time offset as a separate basis, while exact SISC solutions were difficult to compute because existing methods used heuristics.
Method
The paper learns shift-invariant sparse-coding representations by efficiently solving alternating coefficient and basis optimization problems for self-taught audio learning.
Results
SISC features achieved the highest accuracy in musical genre classification and provided useful features for speech and music classification.
Takeaways & Limitations
Automatically learned SISC features can provide comparable or superior performance to carefully engineered MFCC features in the reported audio classification settings.
Takeaways & Limitations
For long signals, the number of nonzero optimal coefficients grows roughly linearly with signal length, making each least-squares problem less efficient.
Abstract
from arXiv · showhide
Sparse coding is an unsupervised learning algorithm that learns a succinct high-level representation of the inputs given only unlabeled data; it represents each input as a sparse linear combination of a set of basis functions. Originally applied to modeling the human visual cortex, sparse coding has also been shown to be useful for self-taught learning, in which the goal is to solve a supervised classification task given access to additional unlabeled data drawn from different classes than that in the supervised learning problem. Shift-invariant sparse coding (SISC) is an extension of sparse coding which reconstructs a (usually time-series) input using all of the basis functions in all possible shifts. In this paper, we present an efficient algorithm for learning SISC bases. Our method is based on iteratively solving two large convex optimization problems: The first, which computes the linear coefficients, is an L1-regularized linear least squares problem with potentially hundreds of thousands of variables. Existing methods typically use a heuristic to select a small subset of the variables to optimize, but we present a way to efficiently compute the exact solution. The second, which solves for bases, is a constrained linear least squares problem. By optimizing over complex-valued variables in the Fourier domain, we reduce the coupling between the different variables, allowing the problem to be solved efficiently. We show that SISC's learned high-level representations of speech and music provide useful features for classification tasks within those domains. When applied to classification, under certain conditions the learned features outperform state of the art spectral and cepstral features.
1 Introduction
The paper motivates self-taught learning as a way to use abundant unlabeled data from outside the target classes, and applies shift-invariant sparse coding to audio classification.
- Labeled data is difficult and expensive to obtain, motivating methods that exploit additional data.
- Self-taught learning uses unlabeled data that need not share the target labels or generative distribution.
- Shift-invariant sparse coding reuses basis functions at different time offsets, as illustrated for spectrogram inputs.
- Audio clips from radio broadcasts or the internet can provide easily obtainable unlabeled data for learning.
- The paper presents a self-taught learning algorithm based on shift-invariant sparse coding and applies it to audio classification.
2 Overview
The overview defines SISC as sparse coding with reusable basis functions across time shifts, addressing the difficulty of exact optimization in audio representations. It formulates the model probabilistically and alternates convex updates for coefficients and bases.
- 2 Overview: Sparse coding learns a dictionary whose input signals are approximated by sparse combinations of basis functions.The resulting active bases provide a concise representation of each signal.
- 2 Overview: Exact SISC solutions were previously difficult because shifted coefficients are tightly coupled, making heuristic subset selection unreliable.A naive tied-parameter reformulation also ignores special structure and is computationally infeasible for moderate problem sizes.
- 2.1 Preliminaries and notation: SISC optimization is not jointly convex, but it is convex in either coefficients or bases, enabling alternating convex optimization.The coefficient step is L1-regularized least squares, while the basis step is an L2-constrained convex problem.
- 2 Overview: SISC allows each basis function to appear at all possible time offsets within an input signal.Convolution represents these shifted uses compactly, and basis functions may be shorter than the input.
- 2.1 Preliminaries and notation: For a 500ms speech signal sampled at 16kHz, a basis may be 100ms long, giving a 1600-dimensional basis for an 8000-dimensional input.
- 2.1 Preliminaries and notation: The SISC coefficients are vectors whose entries correspond to temporal offsets of each basis within each input.
3 Efficient SISC Algorithm
The efficient SISC algorithm alternates between coefficient optimization and basis optimization, using exact or convergent methods for the coupled problems. It handles coefficient coupling with feature-sign methods and simplifies basis optimization through Fourier-domain transformations.
- Alternating optimization: SISC alternates between solving for coefficients with fixed bases and solving for bases with fixed coefficients.Each subproblem is convex when the other variable set is held fixed.
- Solving for coefficients: Highly coupled coefficient variables make heuristic subset selection prone to suboptimal solutions.Adjacent shifted coefficients can explain the same signal similarly, making selection difficult.
- Solving for coefficients: Feature-sign search reduces the L1-regularized problem to quadratic optimization over nonzero coefficients and provably converges to the optimum.The method searches over nonzero coefficients and their signs.
- Solving for coefficients: Sliding-window feature-sign optimization solves smaller problems over roughly 2q coefficients and is guaranteed to converge because the objective is convex.The method is called FS-WINDOW, while plain feature-sign search is FS-EXACT.
- Solving for coefficients: After two passes, the sliding-window objective was only a tiny fraction of a percent worse than the optimal value in experiments on images, speech, and music.This empirical result concerns convergence speed rather than classification accuracy.
- Solving for bases: For basis optimization, the Fourier transform preserves L2 structure and converts convolution into elementwise multiplication, reducing variable coupling.The transformed problem is equivalent because Parseval’s theorem preserves the norm up to a known constant.
4 Constructing features using unlabeled data
The method uses SISC on unlabeled data to learn shift-invariant bases, then represents labeled inputs with sparse features for classification. These features capture higher-level patterns and remain aligned under input shifts.
- Self-taught learning uses unlabeled examples that may not share the classification task’s labels.
- The learned features can capture higher-level patterns than raw inputs and often improve generalization with standard classifiers.
- SISC learns shift-invariant basis functions from unlabeled data and uses them to construct features for labeled classification inputs.
- SISC features shift with an input signal without changing their relative values, providing robustness to translations.
- The paper proposes MultiExp because SISC features are sparse, long-tailed, and poorly modeled by a multivariate Gaussian.
5 Experiments
Experiments evaluate exact coefficient learning, Fourier-domain basis updates, and SISC features on speech and music classification. The proposed methods converge faster in optimization tests, while SISC features achieve strong classification performance against engineered baselines.
- 5.1 Algorithms: After 8 seconds, FS-EXACT is 10^-2-suboptimal, while the best other algorithm needs 40 seconds to reach that level.
- 5.1 Algorithms: Both heuristic coefficient-learning methods converge to suboptimal solutions.
- 5.1 Algorithms: DUAL computes optimal bases for fixed coefficients at each iteration, contributing to faster overall basis-learning convergence than GD-BASIS.
- 5.2 Classification: The classification experiments test speaker identification and musical genre recognition using small labeled sets and unlabeled data from different speakers, dialects, or genres.
- 5.2 Classification: SISC features achieve the highest musical genre classification accuracy and are comparable or superior to carefully engineered MFCC features.
- 5.2 Classification: Speaker-identification experiments compare SISC with raw spectrogram and MFCC features under noiseless, shared-noise, random-noise, and mismatched-noise conditions.
6 Discussion
The paper presents an efficient SISC algorithm and demonstrates its effectiveness for self-taught audio classification using unlabeled data from other classes.
- The algorithm efficiently solves SISC by searching over coefficient signs and decomposing Fourier-domain basis optimization into smaller, weakly coupled problems.This addresses both coefficient and basis optimization challenges in the SISC procedure.
- The method performs well in self-taught learning, where classification exploits unlabeled data drawn from classes other than those of interest.
- SISC therefore provides an efficient route to learning audio representations for supervised classification with additional unlabeled data.