MetaDT: Meta Decision Tree for Interpretable Few-Shot Learning

Few-Shot Learning (FSL) aims to recognize novel classes with few labeled samples. Existing methods can be roughly grouped into two categories: meta-learning based approaches and representation learning-based approaches. The meta-learning based approaches focus on learning a task-agnostic meta-learner by constructing a large number of few-shot tasks from base classes, and then leverage the meta-learner to quickly learn/infer an FSL classifier for recognizing novel classes. The meta-learner can be a good initial model [13, 32], optimization algorithm [3, 53], embedding network [36, 21, 55], metric strategy [45, 56, 23], or label propagation strategy[37, 34, 50, 31], etc. The representation learning-based approaches aim to design a good feature extractor [52, 47] or training strategy [11, 38, 8, 25] to learn transferable representations from abundant base classes, so that the novel class samples can be recognized by a simple cosine classifier [9] or logistic regression classifier [30].

Recently, some studies attempt to introduce some external knowledge as auxiliary priors to further boost the performance [22, 46, 35, 27, 54] of existing FSL methods. For example, in [46, 22], the authors extend [36] by introducing the semantic information of class names as priors, to enhance class prototypes for FSL. In [27], they follow the representation learning-based approaches and introduce class hierarchies as priors to further boost cosine classifier [9] for FSL. Different from these methods, our MetaDT focuses on interpretable FSL and introduces the priors of class hierarchy to construct and infer a novel decision tree for interpretable FSL. Its advantage is that more superclasses can be exploited to improve knowledge transfer and detailed decision explanations can be provided for class prediction.

Zero-Shot Learning (ZSL) is a challenging machine learning task, which targets at recognizing novel classes without any labeled examples by resorting to some semantic knowledge summarized from human’s past experiences [42, 14]. The main idea is regarding class-level semantic knowledge as the auxiliary information, and then learning a map function between semantic knowledge and class representations for novel class prediction. The semantic knowledge can be class attributions [42], class names [46], class descriptions [12], or class hierarchies [17]. Our work differs from these models in two aspects: 1) our MetaDT focuses on interpretable FSL, where few labeled samples should be fully exploited; 2) resorting to the semantic knowledge of class hierarchy, we focus on learning an interpretable decision tree, i.e., learning a map from class hierarchy to decision trees instead of learning class representations.

Decision model interpretability is a very popular research topic in machine learning, which focuses on clearing model decision process to ensure decision reliability [7]. In earlier studies [33, 20], the decision tree is a very popular model on a wide variety of tasks, as its attractive interpretability. After that, considering the high accuracy of neural networks, some works [41, 18, 51, 19, 49] further combine neural network and decision tree to improve accuracy and interpretability jointly. Recently, several FSL studies also attempt to improve FSL interpretability [6, 48, 43]. For example, in [48], Xue et al. propose a region comparison network to highlight the region similarity between samples for the interpretable FSL. Wang et al. [43] propose an attention-based explainable FSL model by highlighting the discriminative patterns of each image. Almost all methods improve FSL interpretability from the perspective of heatmap visualization, which does not directly reveal why FSL models make such decision. Different from these existing methods, we focus on the interpretability of FSL decision process and propose a novel decision tree-based meta-learning framework (i.e., MetaDT), which directly reveals the reason for the classification decision of each sample.

The main details of the IDDTree $f_{\theta_{d}}()$ and the DTINet $f_{\theta_{g}}()$ will be introduced in Sections 4.2 and 4.3, respectively. Here, we mainly present the workflow depicted in Figure 2, including meta-training and meta-test phases.

Specifically, as shown in Figure 2, following the episodic training manner [40], we mimic the test setting and construct a number of $N$-way $K$-shot tasks (called episodes) from base classes. Then, we train our meta-learner $f_{\theta_{g}}()$ to quickly infer a task-specific IDDTree for each episode by minimizing the cross entropy loss on query set $\mathcal{Q}$. That is,

where $\mathbb{T}$ is the set of constructed episodes and $CE()$ denotes the cross entropy loss function. The above training process can be regarded as an outer-loop optimization for learning good initial parameters $\theta_{g}$. Next, we introduce how to calculate the class probability $P(k|x,\mathcal{S},\theta_{g})$ that each query sample $x\in\mathcal{Q}$ belongs to class $k$ in an inner-loop optimization manner, given initial parameters $\theta_{g}$ and support set $\mathcal{S}$. It includes the following three stages:

Stage 1. Class Hierarchy Construction. We first construct a tree-like class hierarchy as FSL priors. The class hierarchy reflects the semantic relations between classes, i.e., what kinds of superclasses these few-shot classes share. For example, the classes “pomeranian” and “bichon frise” share the same superclass “dog”. We note that such type of class hierarchy can be easily obtained from some external knowledge graphs, e.g., WordNet [26]. Then, we encode the tree-like class hierarchy by using an undirected graph $\mathcal{G}$, where its nodes denote all semantic classes (i.e., all few-shot classes and their superclasses) and its edges represent the hierarchy relations between all classes. Let $\mathcal{V}$ and $\mathcal{E}$ denote the set of nodes and edges respectively, i.e., $\mathcal{G}=(\mathcal{V},\mathcal{E})$. In the graph $\mathcal{G}$, each node is represented by a $d_{s}$-dimensional semantic vector $h_{i}$, i.e., the mean of all $d_{s}$-dimensional Glove-based word embeddings [28] of their class names, denoted by $\mathcal{H}=\{h_{i}\}_{i=0}^{F-1}$ where $F$ is the number of graph nodes. The edge set $\mathcal{E}$ is represented as a adjacency matrix $A\in\mathcal{R}^{F\times F}$ where $A_{i,j}=1$ if the node $i$ is associated with the node $j$, otherwise $A_{i,j}=0$.

Stage 2. Fast Adaptation. In this stage, we regard the class hierarchy $\mathcal{G}$ as inputs and the IDDTree $f_{\theta_{d}}()$ as predicted targets of our initial DTINet $f_{\theta_{g}}()$. Then, we evaluate the predicted IDDTree $f_{\theta_{d}}()$ on the support set $\mathcal{S}$ and leverage the evaluated classification loss $L_{\theta_{g}}(\mathcal{S})$ to quickly finetune the initial DTINet $f_{\theta_{g}}()$ with $M$-step gradient updates. As a result, a task-specific DTINet $f_{\theta^{\prime}_{g}}()$ with parameters $\theta^{\prime}_{g}$ can be obtained for each few-shot task. For example, when using one gradient updates (i.e., $M$=1), the process of such fast adaptation can be expressed as:

where $\alpha_{inner}$ is the learning rate of gradient updates. The above process can be regarded as an inner-loop optimization for learning good task-specific parameters $\theta^{\prime}_{g}$. Next, we elaborate on the calculation details for the classification loss $L_{\theta_{g}}(\mathcal{S})$ on the support set $\mathcal{S}$.

Speficifally, we first extract the features of each support sample $(x,y)\in\mathcal{S}$ via the feature extractor $f_{\theta_{f}}()$. Then, the class probability $P(k|x,\theta_{g})$ that each sample $(x,y)\in\mathcal{S}$ belongs to class $k$ can be calculated by using the IDDTree $f_{\theta_{d}}()$ infered by our meta-learner $f_{\theta_{g}}()$ (Please refers to Section 4.2 for its calculation details). That is,

Finally, we calculate the classification loss $L_{\theta_{g}}(f_{\theta_{g}},\mathcal{S})$ by using a cross entropy loss on support set $\mathcal{S}$:

Stage 3. Class Probability Prediction. Based on the above task-specific DTINet $f_{\theta_{g}^{{}^{\prime}}}()$, we can obtain a task-specific IDDTree $f_{\theta^{\prime}_{d}}()$. Then, the class probability $P(k|x,\mathcal{S},\theta_{g})$ that each query sample $x\in\mathcal{Q}$ belongs to class $k$ can be calculated in a sequential decision manner (Please refers to Section 4.2 for its details). That is,

In the subsection, we introduce the technical details of our IDDTree $f_{\theta_{d}}()$, including the following two parts.

Step 1. For each non-leaf node $i$ (i.e., superclasses), we need to make decisions for its all child nodes denoted by $\mathcal{C}_{child}^{i}$, i.e., evaluating the conditional probability $P(j|i,x,\theta_{d})$ that the sample $x$ belongs to child class $j\in\mathcal{C}_{child}^{i}$. We evaluate the conditional probability $P(j|i,x,\theta_{d})$ by computing the cosine similarity between the sample $x$ and the weights $\theta^{j}_{d}$ of child class $j\in\mathcal{C}_{child}^{i}$. That is,

where $<\cdot>$ denotes the cosine similarity of two vectors and $\gamma$ is a scale parameter. Following [8], $\gamma=10$ is used.

Step 2. For each leaf node (i.e., few-shot class $k$), given its traversal path $\tau_{k}$ from the root and the conditional probability $P(j|i,x,\theta_{d})$ of each node $i\in\tau_{k}$ traversing its child node $j$ in the path $\tau_{k}$, i.e., $j\in\tau_{k}\cap\mathcal{C}_{child}^{i}$, the class probability $P(k|x,\theta_{d})$ that each support/query sample $x$ belongs to the class $k$ can be calculated in a cumulative product manner along the traversal path $\tau_{k}$. That is,

For clarity, we give an example to show the above calculation process. As shown in Figure 4, given a sample $x$, 1) we compute all conditional probability of non-leaf nodes in Eq. 7, e.g., $P(5|6,x,\theta_{d})=0.7$; and then 2) the class probability is obtained by using Eq. 8, e.g., $P(3|x,\theta_{d})=P(6|x,\theta_{d})P(5|6,x,\theta_{d})P(3|5,x,\theta_{d})=1\cdot 0.7\cdot 0.6=0.42$.

In the IDDTree $f_{\theta_{d}}()$, its key challenge is how to quickly infer its parameters $\theta_{d}=\{\theta^{i}_{d}\}_{i=0}^{F-1}$ when only few labeled samples are available. To address the challenge, we regard the class hierarchy $\mathcal{G}$ as inputs and then design a graph convolution-based inference network $f_{\theta_{g}}()$ to learn the map from class hierarchy $\mathcal{G}$ to the parameters $\theta_{d}$. The intuition behind this design is fully leveraging human’s prior knowledge to enable fast adaptation of decision trees.

The overall structure is shown in Figure 4, which consists of an input layer, a hidden layer, and an output layer. The input and hidden layers aim to obtain a good representation for each graph node by exploiting abundant semantic information and hierarchy relations between classes. Then, the parameters $\theta_{d}$ of IDDTree $f_{\theta_{d}}()$ are predicted by the final output layer. The overall process can be defined as:

where $W^{(0)}$, $W^{(1)}$, and $W^{(2)}$ denote a trainable weight matrix for input, hidden and output layers, respectively, i.e., $\theta_{g}=\{W^{(0)},W^{(1)},W^{(2)}\}$; $\hat{A}$ is the normalized $A$, i.e., $\hat{A}=D^{-\frac{1}{2}}AD^{\frac{1}{2}}$; $D$ is the degree matrix, i.e., $D_{ii}=\sum_{j}A_{ij}$; and $\delta()$ denotes the ReLU activation function.

As for the FSL methods using knowledge, they also explore the semantic knowledge as priors for improving FSL but mainly use the nearest neighbor classifier. Different from these methods, our MetaDT leverages the priors of class hierarchy to quickly infer a task-specific decision tree for interpretable FSL. The results demonstrate the effectiveness of our MetaDT. Note that our MetaDT exceeds FSLKT around 6% $\sim$ 10%, which also utilizes the priors of class hierarchy. Different from FSLKT, our MetaDT regards the class hierarchy as a decision tree, so that more superclasses can be exploited for novel class prediction. The results show the superiority of our MetaDT to leverage class hierarchy.

To illustrate this point, we calculate the percentage of seen and unseen superclasses on miniImagenet, CIFAR-FS, and tieredImagenet, in Table 3. From the results, we indeed find that the percentage of unseen superclasses of tieredImagenet is much larger than the one of miniImagenet and CIFAR-FS. This means the meta knowledge learned from the base classes is difficult to transfer to the novel classes. For the issue, we will leave it to future work.

We conduct various experiments on miniImagenet to investigate the impacts of different components.