One-vs-Rest Network-based Deep Probability Model for Open Set Recognition

We propose a model that combines a convolutional neural network (CNN) feature extractor and the following one-vs-rest sigmoid networks (see Fig. 8 in the supplementary section 6). For each target class, a one-vs-rest sigmoid network is trained to map latent representations of target class examples to one and map those of the other classes to zero. Additionally, the decision scores of one-vs-rest networks are transformed to a class membership probability by the EVT-based calibration method.

The SoftMax function $s(z_{y})=\frac{e^{z_{y}}}{\Sigma_{y\in\Upsilon}e^{z_{y}}}$, which is the de facto standard activation used for multiclass classification, is the normalized exponential function of the logit $z_{y}$ for target class $y$. A CNN with SoftMax output layer is trained to increase the relative quantity of $z_{y}$ to logits of the other classes, which causes the activations of nontarget classes to converge to zero by increasing the normalization term (the denominator), even though the logits of nontarget classes do not decrease substantially [10, 16]. The activations that converge to zero backpropagate very small gradients through the network and the network rarely learns hidden representations that can be useful for differentiating nonmatch samples. However, the sigmoid function $\rho(z_{y})=\frac{1}{1+e^{-z_{y}}}$ is not affected by the other output nodes. Match and nonmatch examples are equally considered in each sigmoid output node during training. Thus, each sigmoid node is trained to differentiate a dissimilar example from match examples. Naturally, a CNN with a sigmoid output node is more likely to reject unknown from known classes based on dissimilarity than is a CNN with a SoftMax output layer.

In a typical CNN architecture, where a single output layer follows the final hidden layer, only a very simple probability model can be constructed on the feature space. Specifically, if we assume probability estimating function is usually a monotonically increasing function of a sigmoid activation, the membership probability of class $y$ is a simple monotonically increasing function in the positive direction of vector $W_{y}^{fo}$ in the feature space, where $W_{y}^{fo}$ is the weight vector that maps the final hidden nodes to the output. This is because sigmoid is a monotonically increasing function of logit. If we set a probability threshold in this probability model, a linearly separated positively labeled area is given to a class. This result is not a problem for general classification tasks because the feature space can be trained to differentiate different known class samples linearly. However, the simple probability model is likely to generate redundant positively labeled space, in which positive samples do not exist. However, the simple probability model is likely to generate redundant positively labeled space, in which positive samples do not exist. However, one-vs-rest sigmoid networks can provide a more sophisticated probability model, because the one-vs-rest network can provide a flexible nonlinear features-to-score mapping for each target class. This flexible mapping can reduce the possibility of containing redundant space as a positive area. An illustrative example comparing simple and sophisticated probability models can be found in our supplementary. Additionally, ReLU activation can be used for the hidden layers to construct a probability model on the feature space, holding the properties of the CAP model in a subspacewise manner. Finally, the derived probability model minimizes and manages open space risk by controlling the size of the open space in the feature space.

The well-known definition of open space risk was provided by Scheirer et al. [11]. Let $f$ be a measurable recognition function, where $f_{y}(h)=1$ for recognition that a sample $h\in\mathcal{H}$ is included in a class $y$ and $f_{y}(h)=0$ otherwise, where $\mathcal{H}$ is the feature space. They defined open space risk $R_{\mathcal{O}}(f)$ for class $y$ as $R_{\mathcal{O}}(f)=\frac{\int_{\mathcal{O}}f_{y}(h)dh}{\int_{S_{o}}f_{y}(h)dh}$, where $\mathcal{O}$ is the open space and $S_{o}$ is a ball of radius $r_{o}$ that includes all the known positive training examples. In this definition, open space risk is considered to be the relative measure of positively labeled open space compared to the overall measure of positively labeled space. The definition of open space risk requires a definition of open space $\mathcal{O}$. Open space $\mathcal{O}=S_{o}-\cup_{i=1}^{N}B_{r}(h_{i})$ is defined as the space sufficiently far from any known positive training sample $h_{i}\in\mathcal{H},i=1,…,N$, where $B_{r}(h_{i})$ is a closed ball of radius $r$ centered on training sample $h_{i}$. In this paper, we call $B_{r}(h_{i})$ the plausible positive space around $h_{i}$.

The rationale behind the closed-ball-shaped plausible positive space is that a probability model in which class membership probability abates as data points move from known data in all directions can be obtained. However, this assumption holds for only a few shallow machine learning models. To incorporate the concept of open space risk into DNNs, we redefine open space and open space risk based on the relationship between the hidden representation and the output of the network. Before presenting the definition, it is assumed that a well-trained neural network that uses ReLU hidden activation and sigmoid output activation follows the DNN feature extractor. In other words, for a class $y$, threshold $\delta$ can be set lower than all positive training samples in the sigmoid output space, while most negative training samples can be left below the threshold. Let $\rho$ be the sigmoid function and $g_{y}$ be the mapping function of the neural network that produces the logit of class $y$ by inputting $h\in\mathcal{H}$. We define comprehensive positive space $S_{p}$ as shown in (1), and open space risk $R_{\mathcal{O}}(f)$ is modified based on $S_{p}$ as shown in (2).

	$$\displaystyle S_{p}=\{h\mid\rho(g_{y}(h))>\delta,h\in\mathcal{H}\}.$$		(1)
	$$\displaystyle R_{\mathcal{O}}(f)=\frac{\int_{\mathcal{O}}f_{y}(h)dh}{\int_{S_{p}}f_{y}(h)dh}$$		(2)

In this paper, we consider open space as the set of points of which the activations are lower than those of any known training samples in positively labeled area, allowing a soft margin $r$. Thus, the formal definition of open space is provided in (3), where $\Delta_{r}(h_{i})=\{h\mid\rho(g_{y}(h))\geq\rho(g_{y}(h_{i}))-r,h\in\mathcal{H}\}$.

$$\displaystyle\mathcal{O}=S_{p}-\cup_{i=1}^{N}\Delta_{r}(h_{i}).$$

(3)

To construct a probability model that can explain increases and decreases in the probability score in the feature space, the probability model should be based on an abating function. An abating function $A(h)$ is a function that satisfies the property $\forall h,\exists h^{*}\mid 0<A(h)\leq\Psi(d(h,h^{*}))$, where $\Psi(d)$ is the upper bound of the abating function, which is a nonnegative finite square-integrable continuous decreasing function of distance measure $d$ [9]. That is, the abating function and bound monotonically decrease as the distance between the positive training sample $h^{*}$ and any point $h$ increases. Because an abating bound is nonnegative finite square-integrable, an abating function can be transformed into a probability function via calibration. We extend this abating function to the directional abating function $A_{W}(h)$, which abates in the direction of $W$. $A_{W}(h)$ satisfies the following inequality:

$$\displaystyle 0<A_{W}(h)\leq\Psi(W\cdot(h-h^{*}))\>\exists h^{*},\forall h\in U_{W}(h^{*}),$$

(4)

where $U_{W}(h^{*})=\{h\mid W\cdot(h-h^{*})>0\}$ and $\Psi(W\cdot(h-h^{*}))$ is the abating bound in the direction of $W$. From (4) and a property of the sigmoid function, we can derive the following.

Theorem 1 (The sigmoid activation is a directional abating function). Let $A_{-W}(h)=\rho(W\cdot h)$ for $h\in\mathcal{H}$; then, $A_{-W}(h)$ is a directional abating function in the direction of $-W$.

Proof. Let $h_{i}\in\mathcal{H},i=1,…,N$, be the feature vectors for the training dataset of class $y$, let $M$ be a sufficiently large number that satisfies $\forall i\mid M\|W\|^{2}\gg W\cdot h_{i}$, and let $h^{*}$ be a positive training feature vector. We define $\Psi(d(h,h^{*}))=\rho(-d(h,h^{*})+M\|W\|^{2})$, where $d(h,h^{*})=-W\cdot(h-h^{*})$ for$h\in U_{-W}(h^{*})$. Then, by definition,$\Psi(d(h,h^{*}))=\rho(W\cdot h+(M\|W\|^{2}-W\cdot h^{*}))$ is always larger than $\rho(W\cdot h)$. Moreover, because sigmoid $\rho$ is a monotonically increasing function with $\rho(z)>0$ for all $z\in\mathbb{R}$, $\Psi(d(h,h^{*}))$ is decreasing as the distance $d(h,h^{*})$ increases. Additionally, $\Psi(d(h,h^{*}))$ is a nonnegative finite square-integrable continuous decreasing function according to (5). Thus, (4) is always satisfied for $A_{-W}(h)$ and $\Psi(d(h,h^{*}))$.

$$\displaystyle\int\limits_{0}^{\infty}\Psi(d(h,h^{*}))^{2}dd(h,h^{*})<\int\limits_{0}^{\infty}\Psi(d(h,h^{*}))dd(h,h^{*})=\int\limits_{-\infty}^{M\|W\|^{2}}\rho(z)dz=ln(1+e^{M\|W\|^{2}})$$

(5)

Neural networks that use ReLU hidden activation layers decompose the input space into multiple polyhedra, and on each polyhedron, the output logit and features have a linear relationship [17]. Without loss of generality, Theorem 1 holds for any polyhedron in the feature space. Let $\mathcal{H}=\cup_{j=1}^{K}\Omega_{j}$ , where $\Omega_{j}$ is a polyhedral subspace decomposed by the following neural network that applies ReLU hidden activation and $K$ is the number of subspaces. Then, the subspacewise directional abating function $A_{-W_{\Omega_{j}}}(h\mid h\in\Omega_{j})=\rho(W_{\Omega_{j}}\cdot h)$ is defined for each subspace $\Omega_{j}$, where $W_{\Omega_{j}}$ is the weight vector that produces the logit for $h\in\Omega_{j}$.

Sigmoid activation has been used to estimate the probability of class membership in machine learning models [28, 29]. However, because a DNN with a sigmoid output layer, unlike a DNN with a SoftMax output layer, is highly likely to overfit training examples, calibration is needed to estimate the probabilities of both known and unknown examples. Thus, we define the probability model $P$ that calibrates the sigmoid output of the DNN for class $y$ as follows:

$$\displaystyle P(y\mid h\in\Omega_{j})=C(\rho(g_{y}(h))),$$

(6)

where $C$ is a monotonically increasing calibration function. We provide the EVT-based calibration function in Section 3.4. The probability model defined in (6) is converted to the following conditional probability model:

$$\displaystyle P(y\mid h\in\Omega_{j})=C(A_{-W_{\Omega_{j}}}(h))\>\forall j\in\{1,2,...,K\}.$$

(7)

This conditional probability model is based on the subspacewise directional abating function; thus, we call the model the subspacewise directional abating probability model.

The subspacewise directional abating probability model can provide a low probability for points in the open space of the subspace. However, there is still the risk that unknown examples are recognized as belonging to a known class because the model can have nonzero probability over open space $\mathcal{O}$. To address this problem, we define a subspacewise directional CAP model with a sigmoid activation threshold $\tau$, and the model $P_{\tau}$ satisfies the following property:

$$\displaystyle\rho(W_{\Omega_{j}}\cdot h)<\tau\Rightarrow P_{\tau}(y\mid h\in\Omega_{j})=0\>\forall j\in\{1,2,...,K\}.$$

(8)

From the definition of the subspacewise directional CAP model, we can derive the following core theorem. Thus, the proposed one-vs-rest networks can be used as the base model to yield the class membership probability by managing open space risk.

Theorem 2 (A subspacewise directional CAP model can minimize and manage open space risk). Let $P_{\tau}(y\mid h\in\Omega_{j}),\>j=1,…,K$ be subspacewise directional CAP models and $f_{y}(h)$ be a measurable function of $h\in\mathcal{H}$ that determines the class membership based on $P_{\tau}(y\mid h\in\Omega_{j})$. Let $R_{\mathcal{O}}(f)$ be the open space risk and $\mathcal{O}$ be open space, defined as in (2) and (3), respectively. If $\tau$ in (8) satisfies $\max_{j}\rho(W_{\Omega_{j}}\cdot h_{\Omega_{j^{*}}})-r<\tau$, where $h_{\Omega_{j^{*}}}=\arg\!\min_{h_{i}\in\Omega_{j}}\rho(W_{\Omega_{j}}\cdot h_{i})$ and $h_{i}\in\mathcal{H},i=1,…,N$, are the feature vectors for the training dataset of a class $y$, then $R_{\mathcal{O}}(f)=0$. That is, the open space risk of subspacewise directional CAP models can be zero. From this and the property of the CAP defined in (8), we derive that open space risk can be managed by adjusting $\tau$.

Proof. Let $\mathcal{O}^{\prime}=S_{o}-\cup_{i=1}^{N}\Delta_{\Omega(h_{i}),r}(h_{i})$, which satisfies $\mathcal{O}\subseteq\mathcal{O}^{\prime}$, where $\Omega(h_{i})$ is the polyhedral subspace containing $h_{i}$ and $\Delta_{\Omega(h_{i}),r}(h_{i})=\{h\mid\rho(W_{\Omega(h_{i})}\cdot h)\geq\rho(W_{\Omega(h_{i})}\cdot h_{i})-r,h\in\Omega(h_{i})\}$. $\mathcal{O}^{\prime}$ can be reformulated as $\mathcal{O}^{\prime}=S_{p}-\cup_{j=1}^{K}\Delta_{\Omega_{j},r}(h_{\Omega_{j}^{*}})$. According to this definition and the definition of $S_{p}$ in (1), $\mathcal{O}^{\prime}$ is reformulated as:

$$\displaystyle\mathcal{O}^{\prime}=\cup_{j=1}^{K}\{h\mid\delta\leq\rho(W_{\Omega_{j}}\cdot h)<\rho(W_{\Omega_{j}}\cdot h_{\Omega_{j}^{*}})-r,\>h\in\Omega_{j}\}.$$

(9)

Since $\forall j\mid\rho(W_{\Omega_{j}}\cdot h_{\Omega_{j}^{*}})-r<\tau$ and $P_{\tau}(y\mid h\in\Omega_{j})=0$ for $\rho(W_{\Omega_{j}}\cdot h)<\tau$, we have $\int_{\mathcal{O}^{\prime}}f_{y}(h)dh=0$. From $\mathcal{O}\subseteq\mathcal{O}^{\prime}$, $\int_{\mathcal{O}}f_{y}(h)dh=0$ is satisfied, which yields $R_{\mathcal{O}}(f)=0$.

The remaining issue that to address to complete the deep probability model is estimating class membership probability by applying a calibration method, as shown in (7). Because there are no unknown examples during training, nonmatch examples are used as substitutes for unknown examples. The main hurdle of open set recognition is in differentiating similar match and nonmatch examples. In other words, when constructing an open set recognition system, the extreme examples are more informative than the examples with scores in the center area of a particular class score distribution [19]. Additionally, the extreme values of score distribution produced by a well-trained recognition model can be modeled by an EVT distribution, which provides probability estimates for match and nonmatch samples [11, 13, 15, 23]. Therefore, we applied the EVT-based calibration technique to the sigmoid outputs. According to the statistical EVT, the extreme values of a score distribution follow a Weibull distribution if the scores are bounded below and follow a reverse Weibull distribution if bounded above [21, 30]. We construct two probability functions that estimate the probability of “being a positive” and the probability of “not being a negative”. Before modeling, we first separate training examples into match examples and nonmatch examples for class y. Let us assume that $s_{i}^{y}=F_{y}(x_{i})$ is the score of example $x_{i}$ for class $y$, where $F_{y}$ is the mapping function of the proposed model that produces sigmoid output for class $y$. Then, we can collect the scores of matches $S_{y+}$ and the scores of nonmatches $S_{y-}$ separately. Let $E_{y+}$ be the lower extremes of the matches $S_{y+}$ and $E_{y-}$ be the upper extremes of the nonmatches $S_{y-}$. The relative quantity of extremes of matches and nonmatches is represented by the ratio parameter $\alpha$. Because $E_{y+}$ follows a Weibull distribution, we use the Weibull CDF to estimate the probability of being a positive, as shown in (10). Furthermore, the reverse Weibull CDF is used to estimate the probability of not being a negative, as shown in (11). The Weibull and reverse Weibull distributions have three parameters: location $\nu$, scale $\lambda$, and shape $\kappa$. We estimate $\nu_{y+}$, $\lambda_{y+}$, and $\kappa_{y+}$ that best fit $E_{y+}$ and $\nu_{y-}$, $\lambda_{y-}$, and $\kappa_{y-}$ that best fit negative values of $E_{y-}$ by applying the maximum likelihood method provided by the SciPy library of Python [31].

	$$\displaystyle P_{+}(y\mid F_{y}(x_{i}))=1-e^{-(\frac{F_{y}(x_{i})-\nu_{y+}}{\lambda_{y+}})^{\kappa_{y+}}}.$$		(10)
	$$\displaystyle P_{-}(y\mid F_{y}(x_{i}))=e^{-(\frac{-F_{y}(x_{i})-\nu_{y-}}{\lambda_{y-}})^{\kappa_{y-}}}.$$		(11)

Finally, we propose a recognition rule to assign a sample to a known class or to reject it. We use the product $P_{+}(y\mid F_{y}(x_{i}))\times P_{-}(y\mid F_{y}(x_{i}))$ as $P(y\mid F_{y}(x_{i}))$, the probability of belonging to class y. That is, if an example has a high probability of being from the matches and not from nonmatches, then the example is highly likely to belong to the positive class. However, we reject an example if it cannot be considered to belong to any of the known classes. Thus, the multiclass open set recognition rule is defined as follows:

$$\displaystyle y^{*}=\begin{cases}\arg\!\max_{y\in\Upsilon}P(y\mid F_{y}(x_{i}))&\text{if $P(y\mid F_{y}(x_{i}))\geq\theta$}\\ \text{unknown}&\text{otherwise},\end{cases}.$$

(12)

where $\theta$ is the lower limit to be assigned to one of the known classes $y\in\Upsilon$, which is the calibrated value of $\tau$ in (8). We select the optimal $\theta$ and $\alpha$, the ratio of extremes, that maximize the open set recognition performance via cross-class validation [24], which measures the performance for the validation set while leaving out a randomly selected subset of known classes as “unknown”.

To measure and compare the KL divergences, we follow the settings described in the supplementary section 6. When the feature space is discretized into 10, 30, 50 and 70 areas, the KL divergences for 370 known and unknown class pairs are distributed as shown in Fig. 1. The results show that the finer the discretized feature space is, the greater the difference between the probability distributions of the known and unknown classes. Additionally, the KL divergence distribution of the one-vs-rest networks is always significantly higher than that of the SoftMax layer. The p-values of the paired $t$ test were less than $10^{-4}$ for all cases

The proposed method and the four benchmarks were compared under various openness values. To vary the openness, we increased the number of known classes from 5 to 30 in intervals of 5 and randomly selected known classes. The remaining classes were assigned as unknown classes and were not used in training. More details on experimental settings are given in our supplementary. Fig. 3 shows the evaluation results according to openness and reveals that the proposed method outperformed the other methods as openness increased. Additionally, sigmoid CNN-based methods (the proposed method and DOC) outperformed the SoftMax CNN-based methods in all cases. The performance gap between sigmoid CNN-based methods and SoftMax CNN-based methods increased as the openness increased. This result demonstrates that sigmoid activation can provide a better explanation of unknown examples compared to SoftMax activation. Also, introducing one-vs-rest networks and EVT-based calibration is effective because the F-measure gap between the proposed method and DOC is explained mainly by the output layer structure and the method of estimating class membership probabilities.

We additionally observed the performance differences according to the number of nodes in the hidden layer of the one-vs-rest network and the number of unknown classes, and the results are presented in Fig. 3. For the cases in which the number of hidden nodes was larger than five, there was no substantial difference in the F-measure for the same number of unknown classes. However, as the number of hidden nodes decreased from five, the performance abruptly decreased substantially. Thus, the proposed method should be based on probability estimation through one-vs-rest networks with a sufficiently high level of complexity.

To evaluate the proposed and comparison methods on the LFW face dataset, we followed the data setting protocol introduced in [13]. More details on experimental settings are given in our supplementary. We used the training dataset of the known classes and ten largest unknown class datasets to estimate KL divergence distributions. Since the $10^{th}$ unknown class included only 37 images, the feature space was discretized into four to ten areas in intervals of two. As a result, the CNN with one-vs-rest networks always provided larger KL divergences than the SoftMax CNN, yielding p-values less than 0.01 in all cases. The KL divergence distributions according to the number of discretized areas can be seen in supplementary materials.

We varied openness from $26\%$ to $59\%$ by taking 10 to 60 unknown classes to evaluate the classification performance. Fig. 5 shows the performance evaluation results. The results are the same as those for EMNIST in that the proposed method and DOC outperformed the SoftMax-based methods. Additionally, DOC slightly outperformed the proposed method when the openness exceeded $50\%$. However, the proposed method provided a much higher F-measure at lower openness. Considering that an openness greater than $50\%$ means there are at least three times more unknown than known classes, which is uncommon in the real world, providing better performance at moderate openness using the proposed method is realistic and acceptable.

Fig. 5 shows the performance of the proposed method according to $\theta$ and $\alpha$. For the LFW dataset, $\theta$ had a greater impact on performance than $\alpha$, and performance was more affected by $\theta$ when openness was large. In regard to $\alpha$, it did not have a substantial impact on performance in the case of low openness but had a considerable impact in the case of high openness. Specifically, a small tail size can deteriorate performance in the case of high openness, because seven of the known classes had fewer than one hundred samples and the quantity of data was insufficient to fit the Weibull distribution well when a low ratio of extremes was applied. The poorly fit Weibull distribution could not provide accurate probability estimates.

We randomly selected 40 classes from a total of 100 classes as known classes, and the remaining classes were considered unknown. Cifar-100 contains 500 training images and 100 testing images for each class [39]. For one-vs-rest networks, a single hidden layer of ten nodes is applied. We used the training images to attain KL divergence distributions. The feature space was discretized into 5 to 30 areas in intervals of 5. For all cases, the paired t test revealed that the one-vs-rest networks provided a significantly larger difference in the distributions of known class samples and unknown class samples in the feature space, with a p-value less than $10^{-25}$. The KL divergence distributions according to the number of discretized areas can be seen in supplementary materials.

We varied openness from $6\%$ to $37\%$ by taking 5 to 60 unknown classes to compare the performances of the open recognition methods. We applied cross-class validation, leaving ten training classes as unknown classes to find the optimal $\theta$ and $\alpha$. The comparison results are summarized in Fig. 6. When openness was $5.7\%$ and $10.6\%$, the SoftMax-based methods outperformed the proposed method, but the performance gap was small. However, as openness increased, the proposed method significantly outperformed the other methods. These results can be explained by the observation that the proposed one-vs-rest networks provide more informative latent features for unknown examples.

We set various $\theta$ and $\alpha$ and observed the performance differences according to the parameter combinations, as shown in Fig. 7. Overall, performance determined mostly by the score threshold. However, there is no substantial difference in the F-measure when $\theta$ is less than 0.2. Notably, when the score threshold is lower than 0.2, the minimum ratio of extremes yields the best F-measure. This explains why a small quantity of extremes should be used to calibrate decision scores when the quantity of data is sufficient.

The proposed model consists of a CNN feature extractor and the following one-vs-rest sigmoid networks. The one-vs-rest sigmoid networks, which use rectified linear unit (ReLU) activation for hidden layers, consist of a simple feedforward neural network that produces a sigmoid decision score for each target class, as shown in Fig. 8.

To observe the difference in probability mapping between single sigmoid output layer and one-vs-rest sigmoid networks, we designed an illustrative example. We assumed that there is the feature space, where three class examples are well separated linearly. The examples were used to train both mapping models, and the derived probability mappings are shown in Fig. 9. Each one-vs-rest network had one hidden layer that consists of five ReLU hidden nodes and both models were trained to minimize cross-entropy loss, with final losses of $7\times 10^{-4}$ and $9\times 10^{-4}$ for the sigmoid layer and the one-vs-rest sigmoid networks. We applied the probability estimation technique proposed in Section 3.