walexi/fellowshipai

Edge-labeling Graph Neural Network for one-shot learning (WIP)

This is a challenge submission for fellowship.ai cohort 15.

The challenge is to perform 1-shot learning on the Omniglot dataset.

Omniglot Dataset

• The Omniglot data set is designed for developing more human-like learning algorithms.
• It contains 1623 different handwritten characters from 50 different alphabets.
• Each of the 1623 characters was drawn online via Amazon's Mechanical Turk by 20 different people.
• Each image is paired with stroke data, a sequences of [x,y,t] coordinates with time (t) in milliseconds.

Challenge Goal/Objective/Approach

• Use background set of 30 alphabets for training and evaluate on set of 20 alphabets.
• Report one-shot classification (20-way) results using a meta learning approach like MAML.
• Some basic exploration, 1-NN experiment and demo run from dataset authors using a distance metric are in

One-shot Learning and Meta-learning

• One-shot learning is the task of learning information about object categories from a single training example.
• Each classification task T contains a support set S, a labeled set of input-label pairs, and a query set Q, an unlabeled set on which the learned classifier is evaluated.
• For a 20-way 1-shot cassification, the support set S contains K=1 labeled sample for each of N=20 unique classes
• Earlier work on one-shot learning is largely based on hand-engineered features
• With meta-learning (also known as learn to learn), we hope to learn a common feature representation for all tasks in an end-to-end fashion

Existing solutions and current benchmarks

• Lake et. al use Bayesian Program learning to achieve an error rate < 5% on the 20-way one-shot classification task. This method makes use of the stroke information. For a Siamese ConvNet they report an error of < 10%.
• Jake Snell et. al use Prototypical networks (which map examples to a pdimensional vector space such that examples of a given output class are close together) to learn a metric space in which classification can be performed by computing distances to prototype representations of each class. They report an accuracy rate of 96.0% on the 20-way one-shot classification task on the Omniglot dataset
• Vinyals et al use a differentiable nearest neighbours classifier (non-parametric approach). Accuracy of 93.8% and 93.2% were reported on the 20-way one-shot classification task on the Omniglot dataset respectively
• Alex Nichol et al use First-Order Meta-Learning Algorithms (an approximation to MAML obtained by ignoring second-order derivatives). Accuracy of 89.4%, and 89.43% were reported on the 20-way one-shot classification task on the Omniglot dataset using First-order MAML (using Transduction) and a new algorithm Reptile (using Transduction) respectively

Solution

• Edge-Labeling Graph Neural Network for Few-shot Learning
• It consists of a number of layers where each layer consists of a node-update block and an edge-update block
• The parameters of the network (for each layer) are learned by episodic training
• Updates edge labels as it utilizes both intra-cluster similarity and inter-cluster dissimilarity
• It can be easily extended to perform a transductive inference

Possible improvements

• Use another loss such as the cycle loss.

Reference Papers

• Edge-Labeling Graph Neural Network for Few-shot Learning Bryan Perozzi et al