Knowledge Matters: Importance of Prior Information for Optimization

Çağlar Gülçehre; Yoshua Bengio

Source-linked AI summary

Knowledge Matters: Importance of Prior Information for Optimization

Çağlar Gülçehre, Yoshua Bengio

arXiv:1301.4083v6Jan 17, 2013cs.LGcs.CVcs.NEstat.ML

TL;DR

The paper asks why a task that humans appear to learn easily defeats standard machine-learning methods. It uses a two-part MLP with intermediate supervision for sprite detection before final classification, and finds that guidance enables successful learning while unguided training can fail, supporting an optimization-based account with effective local minima.

Problem
The paper investigates why some tasks that seem easy for humans are difficult for generic machine-learning algorithms.
Method
A structured two-part MLP is trained by pre-training local components on intermediate sprite-category targets before predicting the final binary task.
Results
The same architecture learned the task with hint-based pre-training, whereas random initialization failed to generalize and SMLP-nohints reached 27.5% test error after 1046000 generated examples.
Takeaways & Limitations
The findings support guided learning and suggest that intermediate abstractions can help overcome optimization difficulty in composed nonlinear tasks.
Takeaways & Limitations
The paper leaves open whether unguided networks could eventually succeed with more training or alternate parameterizations, and whether results are task-specific.

Abstract

from arXiv · show

We explore the effect of introducing prior information into the intermediate level of neural networks for a learning task on which all the state-of-the-art machine learning algorithms tested failed to learn. We motivate our work from the hypothesis that humans learn such intermediate concepts from other individuals via a form of supervision or guidance using a curriculum. The experiments we have conducted provide positive evidence in favor of this hypothesis. In our experiments, a two-tiered MLP architecture is trained on a dataset with 64x64 binary inputs images, each image with three sprites. The final task is to decide whether all the sprites are the same or one of them is different. Sprites are pentomino tetris shapes and they are placed in an image with different locations using scaling and rotation transformations. The first part of the two-tiered MLP is pre-trained with intermediate-level targets being the presence of sprites at each location, while the second part takes the output of the first part as input and predicts the final task's target binary event. The two-tiered MLP architecture, with a few tens of thousand examples, was able to learn the task perfectly, whereas all other algorithms (include unsupervised pre-training, but also traditional algorithms like SVMs, decision trees and boosting) all perform no better than chance. We hypothesize that the optimization difficulty involved when the intermediate pre-training is not performed is due to the {\em composition} of two highly non-linear tasks. Our findings are also consistent with hypotheses on cultural learning inspired by the observations of optimization problems with deep learning, presumably because of effective local minima.

1. Introduction

The paper studies why some tasks that humans learn easily are difficult for generic machine-learning systems, and tests whether intermediate guidance can alleviate this difficulty. Its experiments support guided learning and optimization-based explanations involving composed nonlinear tasks and effective local minima.

Motivation: The paper asks whether tasks hard for a lone learner become easier when another agent provides intermediate concepts as learning cues.It also examines optimization difficulty, initialization, and whether failures reflect optimization or regularization problems.
Experimental motivation: Several tested algorithms failed to outperform random prediction on the binary Pentomino task, whereas intermediate hints enabled learning.The task uses binary 64×64 images containing three Pentomino sprites.
Contribution: The study is not intended to introduce a new algorithm or architecture, but to clarify training difficulties in composed tasks.It also provides empirical evidence related to guided learning and deeper, harder abstractions.
Optimization difficulty: The task combines object detection with a nonlinear logical operation, making it a composed learning problem.The paper frames this composition as a source of training difficulty for deep networks.
Optimization perspective: The experiments reinforce the view that targeted initialization can reach better effective local minima than random initialization.Related evidence also links unsupervised pre-training and initialization to different generalization outcomes.
Scope: Even large quantities of labeled data did not make the deep networks in these experiments successful.The paper therefore emphasizes that difficulty depends on the task, not only on dataset size.

2. Culture and Optimization Difficulty

The paper connects cultural or curriculum-like guidance with optimization difficulty in neural networks. It presents intermediate-task supervision as a way to prepare representations and parameters for harder composed tasks.

Optimization concepts: An effective local minimum is a training configuration where error stalls, whether because of a true local minimum or ill-conditioning.Its definition depends on both the objective and the limitations of the optimization algorithm.
Depth and difficulty: The difficulty associated with effective local minima appears to increase as neural networks become deeper.The paper leaves open whether this reflects more minima or greater difficulty reaching good ones.
Guided learning: Curriculum learning introduces simpler examples before more complex ones, while intermediate tasks can prepare the learner’s internal parameters.The paper relates this mechanism to continuation methods in global optimization.
Contribution: The paper’s contribution is to make the effective-local-minima issue explicit and identify problem types where it arises.It treats decomposition and prior information as established tools rather than proposing a new general algorithm.
Culture and learning: Cultural transmission is described as a way for groups to distribute knowledge and computation across individuals.The paper relates this division of processing to limitations of individual human brains.

3. Experimental Setup

The experimental setup targets a task that appears easy for humans but is difficult for generic machine-learning methods. The study tests whether hints about intermediate concepts make the task learnable.

Problem: The study focuses on a task that seems easy for humans but nearly impossible for current generic state-of-the-art machine-learning algorithms.The authors motivate this mismatch as a central research problem.
Guidance: The task becomes learnable when the learner receives hints about appropriate intermediate concepts.The same task is also reported as difficult for SVMs, boosting, and decision trees.
Evaluation: The experiments compare off-the-shelf black-box methods with popular deep-learning algorithms across varying dataset sizes.Algorithm details and hyperparameters are provided elsewhere in the paper.

3.1 Pentomino Dataset

The dataset contains simple binary 64×64 images with three transformed Pentomino sprites placed in separate grid blocks. The final label indicates whether the sprites share one shape class.

Task structure: The guided task first recognizes and locates each Pentomino object class, then performs final binary classification.The final decision asks whether all Pentominos belong to the same shape class.
Figures: Figure 1 contrasts an image containing different sprite types with one containing a single type under varied orientations and scales.Figure 2 displays the Pentomino shape classes used in the dataset.
Sprite classes: The dataset uses Pentomino classes including N, P, F, Y, J, Q, and mirror variants N2, F2, and Y2.These are the shape categories used to generate the images.
Image representation: Images are simple, texture-free binary scenes with foreground pixels coded as 1 and background pixels as 0.Training and test images are generated independently and identically distributed.
Transformations: Sprites undergo rotations by multiples of 90 degrees and scaling by factors 1 or 2 before placement.The transformations are sampled during the data-generation process.
Placement: Three sprites are placed in distinct blocks of an 8×8 grid within each 64×64 image, preventing overlap.Each sprite is centered in its block, so translation variation comes from block location.

3.2 Learning Algorithms Evaluated

The evaluated models use a structured two-part MLP, with patch-wise P1NN representations feeding a nonlinear P2NN. Intermediate hints and standardization were central to successful learning, while no-hint and unsupervised-pretraining variants failed on the task.

SMLP architecture: The SMLP applies one shared-weight P1NN to each non-overlapping 8×8 patch, then concatenates patch outputs for a fully connected P2NN.P1NN typically produces 11 outputs per patch, while P2NN performs the final nonlinear logical operation.
SMLP-hints: With hints, P1NN is trained patch-wise to classify empty patches or Pentomino categories before P2NN training.The 11-way target encodes rejection plus Pentomino shape classes at each of 64 patches.
Comparative results: The hinted model learned the Pentomino task with noisy-looking first-layer filters, whereas extensive attempts to match its performance without hints were unsuccessful.The reported hinted filters were trained on 40k examples; no-hint experiments used the same connectivity pattern but omitted intermediate targets.
Optimization: Standardization was crucial: without it, both hinted and non-hinted SMLPs achieved only chance performance and could not learn the training set.The procedure centers hidden-unit activations and divides by their minibatch standard deviation.
Unsupervised pre-training: Unsupervised pretraining with contractive and denoising auto-encoders did not learn the Pentomino task in any tested configuration.The experiments included greedy layerwise pretraining and several combinations of auto-encoder types.

3.3 Experiments with 1 of K representation

These experiments vary how patch information is represented to isolate task complexity. Simple one-hot inputs can be learned perfectly, while transformed or object-rich representations remain harder for standard MLPs.

Representations: The experiments compare four patch representations, from object-category one-hot inputs to disentangled and transformation-entangled binary encodings.The representations differ in whether object identity, rotation, and scaling are explicit or combined in the input.
Experiment 3: The 80-dimensional transformed one-hot representation encodes 10 object classes across 4 rotations and 2 scales, but leaves class identity spread across eight bits.A shape class can still be read out as an OR over the corresponding transformation-specific bits.
Experiment 1: 0 error on training and test sets was achieved for the one-hot representation without transformations using a single-hidden-layer MLP.This experiment served as a sanity check and required very few training epochs.
Results: The transformed and object-rich tasks produced intermediate results: learning occurred, but the task was not fully solved under the tested settings.Training and test curves were nearly identical, and comparable configuration counts produced similar MLP difficulty.

3.4 Does the Effect Persist with Larger Training Set Sizes?

Increasing training data did not reliably overcome the Pentomino task’s difficulty. The reported evidence favors an optimization problem over a simple regularization problem, although standardization improved the no-hints model.

Interpretation: The authors conclude that the Pentomino difficulty primarily reflects optimization rather than regularization.They examine both online minibatch training and fixed-dataset training while varying the number of examples.
No-hints optimization: 27.5% test error was obtained by SMLP-nohints with intermediate-layer standardization, versus near 0 error for SMLP-hints.This result used online minibatch SGD with Adadelta on 1,046,000 training examples.
No-hints optimization: 50.1% test error remained after training SMLP-nohints without intermediate-layer standardization on 1,580,000 examples.The model used 2,048 P1NN hidden units, 16 sigmoidal outputs per patch, and a 1,024-unit P2NN hidden layer.
Baseline performance: None of the tested state-of-the-art algorithms performed noticeably better than a random predictor without guiding hints.Decision trees and SVMs could overfit training data but failed to generalize, while large MLPs could approach zero training error without good test error.
Increased training size: Adding more examples did not reduce the fully connected MLP’s training or test errors, which stayed near 50%.The experiment used a three-hidden-layer MLP with 2,048 units per layer; Figure 14 reports no significant generalization improvement as examples increased.

3.5 Experiments on Effect of Initializing with Hints

The paper also tests whether hint-based pretraining helps by shaping initialization, and compares this with alternative no-hints configurations. Hint-based initialization is presented as a route toward better effective local minima.

Hint-based initialization: Hint-based pretraining is used to initialize the SMLP before continuing training without hints.The experiment targets the effect of initialization rather than proposing a new architecture.
No-hints comparison: With extensive hyperparameter optimization and standardization, SMLP-nohints reached 6.7% test error on an 80k-example Pentomino dataset.The corresponding training error was 5.3%, using softmax intermediate activations and rectifier hidden layers.
Optimization comparison: An MLP trained with LBFGS on 40k examples still performed at chance on the test dataset after training convergence.The model had two 1,024-unit rectifier hidden layers and used batches of 10,000 examples for gradient computation.
Intermediate activations: Linear intermediate units achieved 25% generalization error without standardization, while the tested nonlinear alternatives failed to generalize under the same conditions.The comparison concerns SMLP-nohints with the same number of training iterations and without hints.

4. Conclusion and Discussion

The task combines object detection with a nonlinear logical operation, making it difficult for standard black-box learners but nearly perfectly solvable when intermediate representations receive prior guidance. The results support guided-learning accounts while leaving questions about initialization, optimization, and task specificity open.

Conclusion: A task composed of object detection and a nonlinear XOR-like operation was almost impossible for standard black-box algorithms but nearly perfectly solvable with guided intermediate representations.The guidance encourages semantics for the intermediate level using prior knowledge.
Conclusion: The same network architecture generalized when pretrained with hints for one epoch but failed to generalize from random initialization.The comparison isolates the effect of initialization and intermediate supervision within the same architecture.
Optimization: Even 1,046,000 generated training examples left SMLP-nohints with 27.5% test error, suggesting the difficulty is not simply regularization.The authors associate this pattern with difficulty finding an effective local minimum of generalization error.
Optimization: Specific architectural constraints and domain knowledge may alleviate optimization difficulty in generic neural networks.The structured MLP can represent a good solution, but training can remain difficult without standardization.
Limitations: Increasing the training set eightfold did not reveal improved MLP test error, and 545,400 examples still left SMLP-nohints far from perfect generalization.The authors present this as a preliminary limitation on the possibility that more data alone resolves the optimization difficulty.
Implications and open questions: The findings support the Guided Learning and Deeper Harder hypotheses, while questions remain about alternate parametrizations, unsupervised learning, and task specificity.The paper identifies these issues as open questions rather than resolving them.

5.1 Binary-Binary RBMs on Pentomino Dataset

The RBM pretraining experiment tested whether unsupervised features could initialize SMLP-nohints for the Pentomino task. Although the RBM learned edge structure, the resulting network still reached zero training error while retaining chance-level test error.

RBM training: Binary-binary RBMs were trained on 8×8 Pentomino patches using PCD, weight decay, sparsity regularization, 256 hidden units, SGD, and momentum.Training used 120 epochs, approximately 50 million updates, with biases initialized to encourage sparse representations.
Network initialization: The pretrained RBM parameters initialized the first layer of an SMLP-nohints network with sigmoid P1NN and intermediate layers, 11 units per location, Adadelta, and intermediate standardization.The RBM served as unsupervised initialization rather than hint-based intermediate supervision.
Performance: Training error reached 0% at epoch 42, while test error remained at chance for the RBM-initialized SMLP-nohints network.The result demonstrates fitting without corresponding generalization.

5.2 Experimental Setup and Hyper-parameters

The experimental setup compared several standard classifiers and neural architectures under cross-validation, using 40,000 examples split into training and test sets. The section details the implementations and search procedures for these baselines.

Decision trees: The decision-tree baseline used CART with Gini impurity and grid-searched hyperparameters, selecting max depth = 300 and min split = 8.The best validation error was obtained with those settings.
SVM: The SVM baseline used scikit-learn’s Support Vector Classifier with cross-validation over C, γ, and kernel type.The implementation was based on libsvm and used kernel mappings with large-margin separation.
Neural and ensemble baselines: The remaining baselines included fully connected MLPs, Random Forests, k-NN, and convolutional networks with hyperparameters selected through random search, grid search, or cross-validation.The convolutional architecture used two convolution-pooling stages followed by an MLP.

5.2.7 Maxout Convolutional Neural Nets

This section describes maxout convolutional networks and stacked auto-encoder baselines used for the Pentomino task. The maxout model used two convolutional layers without pooling, while the auto-encoder variants supplied unsupervised pretraining before supervised fine-tuning.

Maxout convolutional network: The maxout convolutional network used two convolutional layers without pooling, a maxout nonlinearity in the final convolutional layer, and early stopping based on validation error.Hyperparameters were selected by random search over 48 configurations, including learning rates, channels, kernels, maxout units, and pieces.
Maxout hyperparameters: The selected maxout model used 16 channels per convolutional layer, 600 maxout hidden units, 6×6 second-layer kernels, and 5 or 4 maxout pieces.The learning rate decayed during training, and the final softmax used a norm constraint.
Maxout features: After 85 epochs on the 80,000-example training set, most first-layer maxout filters learned basic Pentomino edge structure.The filter visualization is reported in Figure 19.
Auto-encoder baselines: The DAE and CAE baselines used unsupervised feature learning followed by supervised MLP fine-tuning, with the CAE penalizing the Frobenius norm of hidden-unit input Jacobians.The CAE was described as producing more robust features, whereas the DAE emphasized robust reconstruction.
Stacked pretraining: The stacked auto-encoder variants included greedy CAE+DAE and DAE+DAE pretraining before supervised fine-tuning.The DAE+DAE architecture used two denoising auto-encoder layers, while the CAE+DAE stack combined sigmoid and rectifier nonlinearities.