---
abstract: 'Often, when dealing with real-world recognition problems, we do not need, and often cannot have, knowledge of the entire set of possible classes that might appear during operational testing. Moreover, sometimes some of these classes may be ill-sampled, not sampled at all or undefined. In such cases, we need to think of robust classification methods able to deal with the “unknown” and properly reject samples belonging to classes never seen during training. Notwithstanding, almost all existing classifiers to date were mostly developed for the closed-set scenario, i.e., the classification setup in which it is assumed that all test samples belong to one of the classes with which the classifier was trained. In the open-set scenario, however, a test sample can belong to none of the known classes and the classifier must properly reject it by classifying it as unknown. In this work, we extend upon the well-known Support Vector Machines (SVM) classifier and introduce the Specialized Support Vector Machines (SSVM), which is suitable for recognition in open-set setups. SSVM balances the empirical risk and the risk of the unknown and ensures that the region of the feature space in which a test sample would be classified as known (one of the known classes) is always bounded, ensuring a finite risk of the unknown. The same cannot be guaranteed by the traditional SVM formulation, even when using the Radial Basis Function (RBF) kernel. In this work, we also highlight the properties of the SVM classifier related to the open-set scenario, and provide necessary and sufficient conditions for an RBF SVM to have bounded open-space risk. An extensive set of experiments compares the proposed method with existing solutions in the literature for open-set recognition and the reported results show its effectiveness.'
author:
- |
    Pedro Ribeiro Mendes J[ú]{}nior pedrormjunior@gmail.com\
    RECOD Lab., Institute of Computing (IC)\
    University of Campinas (UNICAMP)\
    Av. Albert Einstein, 1251, Campinas, SP, 13083-852, Brazil Terrance E. Boult tboult@vast.uccs.edu\
    VAST Lab., Department of Computer Science, Engineering Building\
    University of Colorado Colorado Springs (UCCS)\
    1420 Austin Bluffs Parkway, Colorado Springs, CO 80918, USA Jacques Wainer wainer@ic.unicamp.br\
    Anderson Rocha anderson.rocha@ic.unicamp.br\
    RECOD Lab., Institute of Computing (IC)\
    University of Campinas (UNICAMP)\
    Av. Albert Einstein, 1251, Campinas, SP, 13083-852, Brazil
bibliography:
- 'mybib.bib'
title: |
    Specialized Support Vector Machines\
    for Open-set Recognition
---

open-set recognition, support vector machines, specialized support vector machines, bounded open-space risk, risk of the unknown

Introduction {#sec:introduction}
============

Machine learning literature is rich with works proposing classifiers for closed-set pattern recognition, with well-known examples including , Random Forests [@Breiman2001], , and . These classifiers were inherently designed to work in closed-set scenarios, i.e., scenarios in which all test samples must belong to a class used in training. What happens when the test sample belongs to a class not seen at training time? Consider a digital forensic scenario—e.g., source-camera attribution [@Costa2014], printer identification [@Ferreira2017]—in which law officials want verify that a particular artifact (e.g., a digital photo or a printed page) did originated from one of a few suspect devices. The suspected devices are the classes of interest, and a classifier can be trained on many examples of artifacts from these devices and from other non-suspected devices. But when assigning the source for the particular artifact in question the classifier must be aware that if the artifact is from an unknown region of the feature space—possibly far away from the training data—it cannot be assigned to one of the suspected devices, even if examples of those devices are the closest to the artifact. The classifier must be allowed to declare that the example does not belong to any of the classes it was trained on.

One possible way to address recognition in an open-set scenario is to use a closed-set classifier, obtain a similarity score—or simply the distance in the feature space—to the most likely class, apply a threshold on that similarity score aiming at classifying as unknown any test sample whose similarity score is below a specified threshold [@Dubuisson1993; @Muzzolini1998; @Moeini2017]. @MendesJunior2017 showed that when applying thresholds to the ratio of distances instead of distance themselves results in better performance in open-set scenarios.

Instead of using similarity-based algorithms, another alternative is to exploit kernel-based algorithms such as and one-class classifier [@Scholkopf1999]—applied to the entire training set as a rejection function [@Cortes2016]. This approach is sometimes called *classification with abstention*. The idea is to have an initial rejection phase that predicts if the input belongs to one of the training classes or not (known or unknown). In the former case, a second phase is performed with any sort of multiclass classifier aiming at choosing the correct class.

Another alternative method relies on having a binary rejection function for each of the known classes such that a test sample is classified as unknown when decisions are negative for every function. This is the case for any classifier based on the approach [@Rocha2014]. Some recent works have explored this idea [@Pritsos2013; @Costa2014; @Scheirer2014; @Jain2014] making efforts at minimizing the for every classifier that composes the one. In binary classification, refers to the that receives positive classification. is the region of the feature space outside the support of the training samples [@Scheirer2013]. In the multiclass level, a similar concept applies: , i.e., the region of the feature space outside the support of the training samples in which a test sample would be classified as one of the known classes. In this class of methods, the potential of binary methods can be highly explored to multiclass open-set scenarios. Furthermore, methods in this class can be adapted for multiple class recognition in open-set scenarios, as accomplished by @Heflin2012.

In this work, we propose the , that falls into the last class of methods and receives its name due to its ability to bound the for every classification in the binary level, consequently, bounding as well—when is applied. relies on the optimization of the bias term with kernel taking advantage of the following property we demonstrate in this work: with kernel bounds if and only if its bias term is negative.

Along with this work, we have evaluated multiple implementations of open-set methods for different . For all those methods, we have evaluated both traditional grid search and the open-set grid search formalized by @MendesJunior2017.

The remaining of this work is organized as follows. In Section \[sec:related-work\], we discuss some of the most important previous work in open-set recognition. In Section \[sec:ssvm\], we introduce the while, in Section \[sec:experiments\], we present the experiments that validate the proposed method. Finally, in Section \[sec:conclusion\], we present the conclusions and future work.

Related Work {#sec:related-work}
============

In this section, we review recent works that explicitly deal with open-set recognition in the literature, including some base works for them. We note that other insights presented in many existing works can be somehow extended to be used for the open-set scenario. Most of those works, however, did not perform the experiments with appropriate open-set recognition setup.

@Heflin2012 and @Pritsos2013 present a multiclass classifier based on the . For each of the training classes, they fit an . In the prediction phase, all $n$ classify the test sample, where $n$ is the number of for training. The test sample is classified as the class in which its classified as positive. When no classifies the test sample as positive, it is classified as unknown. @Heflin2012 extends the idea to multiple class classification, by allowing more than one to classify the example as positive; in this case, the example receives as labels, all classes whose corresponding classify it as positive. Differently, @Pritsos2013 choose the more confident classifier among the ones that classify as positive. In those works, is used with the kernel, which allows bounding the .

was proposed for data domain description, which means it is target to classify the input as belonging to the or not (known or unknown). In general, any one-class or binary classifier can be applied in such cascade approach to reject or accept the test sample as belonging to one of the known classes and further defining which class it is. It is similar to the framework proposed by @Cortes2016 in which a rejection function is trained along with a classifier, however, in open-set scenario the classifier should be multiclass. For the case in which the rejection function accepts a sample, any multiclass classifier can be applied to choose the correct class. In case of rejection, samples are classified as unknown.

In @Costa2012 [@Costa2014], the authors propose the , an extension of the classifier aiming at a more restrictive specialization on the positive class of the binary classifier. For this, they move the hyperplane a value $\epsilon$ towards the positive class (in rare cases backwards). The value $\epsilon$ is obtained by minimizing the . For multiclass classification, the approach can be used. uses the kernel.

@Scheirer2013 formalized the open-set recognition problem and proposed an extension upon the classifier called . Similar to the works of @Costa2012 [@Costa2014], they move the main hyperplane either direction depending on the . In addition, a second hyperplane, parallel to the main one, is created such that the positive class is between the two hyperplanes. This second hyperplane allows the samples “behind” the positive class to be classified as negative. Then a refinement step is performed on both hyperplanes to balance and . According to the authors, the method works better with the linear kernel, as the second plane does not provide much benefit for an kernel which has a naturally occurring upper bound. A approach is used to combine the binary classifiers for open-set multiclass classification.

@Scheirer2014 propose the . The authors proposed the model which decreases the probability of a test sample to be considered as belonging to one of the known classes when it is far away from the training samples. They use two stages for classification: a model based on a one-class classifier followed by a binary classifier with normalization based on . The binary classifier seeks to improve discrimination and its normalization has two steps. The first aims at obtaining the probability of a test sample to belong to a positive/known class and the second step estimates the probability of it not being from the negative classes. Product of both probabilities is the final probability of the test sample to belong to a positive/known class. uses the kernel and also the approach.

In @Jain2014, the authors propose the , also based on the . It is an algorithm for estimating the unnormalized posterior probability of class inclusion. For each known class, a Weibull distribution [@Coles2001] is estimated based on the smallest decision values of the positive training samples. The binary classifier for each class is an with kernel trained using the approach, i.e., the samples of all remaining classes are considered as negative samples. They introduce the idea of which is similar to the open-set [@MendesJunior2017] we apply in our work, which we shall discuss in details in Section \[sec:grid-search\]. For a test sample, chooses the class for which the decision value produces the maximum probability of inclusion. If that maximum is below a given threshold, the input is marked as unknown.

Applying in open-set recognition [@Scheirer2014; @Jain2014; @Zhang2017; @Scheirer2017] has been a recent research focus. @Scheirer2017 presents an overview of how have been recently applied to visual recognition, mainly on the context of open-set recognition. Notice these previous -based works are not capable of ensuring a bounded by solely relying on models. In the case of @Scheirer2014, they ensure bounded based on one-class models but not on models. For [@Jain2014], the authors did not prove their method is able to bound . In fact, can leave an unbounded when the value of the bias term of the model is in the range of scores used to fit the Weibull model.

Recently, @MendesJunior2017 have shown that thresholding ratio of distances in the feature space for a nearest neighbor classifiers is more accurate at prediction unknown samples in an open-set problem. The effectiveness of working with ratio of decision scores is confirmed by @Vareto2017, in which on of the best reject threshold on a face-recognition problem is established based on the ratio of the two highest scores obtained by a voting from a set of binary classifiers.

It is worth noticing that well-known machine learning areas have been investigated from the point of view of the open-set scenario, e.g., domain adaptation [@Busto2017], taking into account particularities from open-set recognition. Beyond those methods specifically proposed for open-set setups, many other solutions in literature can be investigated to be extended for open-set scenarios. In general, any binary classification method that aims at decreasing false positive rate [@Moraes2016] would potentially recognize unknown samples when composing such classifiers with approach.

In general, recent solutions for open-set recognition problems have focused on methods that use samples of all known classes for training models for individual classes. That is different from generative approaches that checks if the test sample is in the distribution of each of the known classes, as it tries to use data from all classes for generating the model for each class. It differs from [@Tax2008; @Bartlett2008] in the sense that we do not want just to postpone decision making. Moreover, open-set recognition differs from domain adaptation and from transfer learning in the sense that transferring knowledge from one domain to another does not ensure the ability of identifying samples belonging to unknown classes.

SSVM (SSVMs) {#sec:ssvm}
============

One cannot ensure that the positive class of the traditional has a bounded , even when the kernel is used. The main characteristic of the proposed is that a high enough regularization parameter ensures a bounded for every known class of interest, consequently, a bounded in multiclass level. The regularization parameter is a weight for optimizing the in relation to the . In Section \[sec:ssvm-bounding-open-space\], we present how to ensure a bounded using kernel. In Section \[sec:ssvm-choosing-bias-term\], we present the formulation of the optimization problem of the . In Section \[sec:grid-search\], we present the process of optimization of the parameters. To begin with, in Section \[sec:svm-basics\], we present some basic aspects of the classifier.

Basic aspects of Support Vector Machines {#sec:svm-basics}
----------------------------------------

is a binary classifier that, given a set $X$ of training samples $\mathbf{x}_i \in \mathbb{R}^d$ and the corresponding labels $y_i \in \{-1, 1\}$, $i = 1, \dots, m$, it finds a maximum-margin hyperplane that separates $\mathbf{x}_i$ for which $y_{i} = -1$ from $\mathbf{x}_i$ for which $y_{i} = 1$ [@Cortes1995]. We consider the soft margin case with parameter $C$.

The primal optimization problem is usually defined as $$      \min_{\mathbf{w},b,\xi} \frac{1}{2}||\mathbf{w}||^{2} + C\sum_{i=1}^{m}\xi_{i},$$ $$\begin{aligned}
      \label{eq:constraint-1}
      \mbox{s.t.}\ & y_i(\mathbf{w}^{T}\mathbf{x}_{i} + b) \ge 1 - \xi_{i}, \ \forall i,\\
      \label{eq:constraint-2}
                   & \xi_{i} \ge 0, \ \forall i.
    \end{aligned}$$

To solve this optimization problem, we use the Lagrangian method to create the dual optimization problem. In this case, the final Lagrangian is defined as $$\label{eq:lagrangian}
      \mathcal{L}(\mathbf{w}, b, \xi, \alpha, r) = \sum_{i=1}^{m}\alpha_{i} - \frac{1}{2}||\mathbf{w}||^{2},$$ in which $\alpha_{i} \in \mathbb{R}$, $r_{i} \in \mathbb{R}$, $i = 1, \dots, m$, are the Lagrangian multipliers. Then, the optimization problem now is defined as $$\begin{aligned}
      \label{eq:lagrangian-inv}
      \min_{\alpha}\ & W(\alpha) = -\mathcal{L}(\mathbf{w}, b, \xi, \alpha, r) = \frac{1}{2}||\mathbf{w}||^{2} - \sum_{i=1}^{m}\alpha_{i},\\
      \label{eq:slack-constraint}
      \mbox{s.t.}\ & 0 < \alpha_{i} < C, \ \forall i,\\
      \label{eq:sum_0_constraint}
                     & \sum_{i=1}^{m}\alpha_{i}y_{i} = 0.
    \end{aligned}$$

The decision function of a test sample $\mathbf{x}$ comes from the constraint in Equation and is defined as $$      f(\mathbf{x}) = \operatorname{sign}(\mathbf{w}^T \mathbf{x} + b) = \operatorname{sign}\left(\sum_{i=1}^{m} y_i \alpha_i \mathbf{x}_i^T \mathbf{x} + b\right).$$

In @Boser1992, the authors proposed a modification in for the cases in which the training data are not linearly separated in the feature space. Instead of linearly separating the samples in the original space $\mathcal{X}$ of the training samples in $X$, the samples are projected onto a higher dimensional space $\mathcal{Z}$ in which they are linearly separated. This projection is accomplished using the kernel trick. One advantage of this method is that in addition to separating non-linear data, the optimization problem of the remains almost the same: instead of calculating the inner product $\mathbf{x}^T\mathbf{x'}$, it uses a kernel $K(\mathbf{x}, \mathbf{x'})$ that is equivalent to the inner product $\phi(\mathbf{x})^T\phi(\mathbf{x'})$ in a higher dimensional space $\mathcal{Z}$, in which $\phi: \mathcal{X} \mapsto \mathcal{Z}$ is a projection function. When using the kernel trick, we do not need to know the $\mathcal{Z}$ space explicitly.

Using kernels, the decision function of a test sample $\mathbf{x}$ becomes $$\label{eq:decision-function-kernel}
      f(\mathbf{x}) = \operatorname{sign}\left(\sum_{i=1}^{m} y_i \alpha_i K(\mathbf{x}_i, \mathbf{x}) + b\right).$$

The most used kernel for is the kernel [@Scholkopf2001], defined as follows. $$\label{eq:kernel-rbf}
      K(\mathbf{x}, \mathbf{x'}) = e^{-\gamma ||\mathbf{x} - \mathbf{x'}||^2}.$$ It is proved that using this kernel, the projection space $\mathcal{Z}$ is an $\infty$-dimensional space.

Ensuring a bounded PLOS {#sec:ssvm-bounding-open-space}
-----------------------

By simply using the kernel we cannot ensure the is bounded.

\[thm:unbounded-positive\] with kernel has a bounded if and only if the bias term $b$ is negative.[^1]

We know that $$\label{eq:limit}
          \lim_{d \rightarrow \infty} K(\mathbf{x}, \mathbf{x'}) = 0,$$ in which $K(\mathbf{x}, \mathbf{x'})$ is the RBF kernel and $d = \|\mathbf{x} - \mathbf{x'}\|$. For the cases in which the test sample $\mathbf{x}$ is far away from every support vector $\mathbf{x}_i$, $$          \sum_{i=1}^{m} y_i \alpha_i K(\mathbf{x}_i, \mathbf{x})$$ also tends to 0. From Equation it follows that $$          f(\mathbf{x}) \rightarrow \operatorname{sign}\left(b\right)$$ when $\mathbf{x}$ is far away from the support vectors. Therefore, for negative values of $b$, $f(\mathbf{x})$ is always negative for far away $\mathbf{x}$ samples. That is, samples in an bounded region of the feature space will be classified as positive. For the only if direction, let $b$ be positive. Then there will exist a distance $d$ such that $\forall i: \|\mathbf{x}_{i}-\mathbf{x}\|>d \implies f(\mathbf{x}) = \operatorname{sign}(b) > 0$, i.e., positively classified samples will be in an unbounded region of the feature space.

Notice that Theorem \[thm:unbounded-positive\] can be applied not only to the kernel of Equation  but to any radial basis function [@Buhmann2003] kernel satisfying Equation , e.g., kernel, kernel, and kernel [@Souza2010], however, for the remaining part of this work, we focus on the kernel of Equation .

Figure \[fig:figPlottingkernel\] depicts the rationale behind Theorem \[thm:unbounded-positive\]. $z$ axis represents the decision values that possible test samples $(x, y)$ would have for different regions of the feature space. Training samples are normalized between 0 and 1. Note in the subfigures that for possible test samples far away from the training ones, e.g., $(2, 2)$, the decision value approaches the bias term $b$. Note in Figure \[fig:figPlottingkernel3d\_\_boat\_forboundaries\_\_cls03\_\_01\_\_gammaexp+04\] that an unbounded region of the feature space would have samples classified as positive. Consequently, all those samples would be classified as class 3 by the final multiclass-from-binary classifier. In general usage, both positive and negatives biases occur as $b$ depends on the training data.

In case of s without explicit bias term [@Vogt2002; @Kecman2005], $b=0$ is implicit.[^2] Consequently, the decision function is defined as $$      f(\mathbf{x}) = \operatorname{sign}\left(\sum_{i=1}^{m} y_i \alpha_i K(\mathbf{x}_i, \mathbf{x})\right).$$ For test samples far away from the support vectors, we have that $\sum_{i=1}^{m} y_i \alpha_i K(\mathbf{x}_i, \mathbf{x})$ converges to 0 from the bottom or from the above, depending on the training samples. Consequently, a bounded cannot be ensured in all cases.

[0.30]{} ![image]({\striplastbar{figsR2/}__}figBoundaries__boat_forboundaries__color.pdf){width="95.00000%"}

//in

/figPlottingkernel3d\_\_boat\_forboundaries\_\_cls01\_\_01\_\_gammaexp+04/

, /figPlottingkernel3d\_\_boat\_forboundaries\_\_cls02\_\_01\_\_gammaexp+04/

, /figPlottingkernel3d\_\_boat\_forboundaries\_\_cls03\_\_01\_\_gammaexp+04/

![image]({\striplastbar{figs/}__}\filename.pdf){width="95.00000%"} \[fig:\]

Theorem \[thm:unbounded-positive\] also provides a solution to the problem of unbounded . We can ensure a bounded by using an kernel and ensuring a negative $b$. In Section \[sec:ssvm-choosing-bias-term\], we present a new optimization objective that optimizes the margin while ensuring the bias term $b$ is negative.

Optimization to ensure negative bias term b {#sec:ssvm-choosing-bias-term}
-------------------------------------------

As we discussed in Section \[sec:ssvm-bounding-open-space\], we must ensure a negative $b$ to obtain a bounded . For this, we define the optimization problem as $$\label{eq:ssvm-primal-opt}
      \min_{\mathbf{w},b,\xi} \frac{1}{2}||\mathbf{w}||^{2} + C\sum_{i=1}^{m}\xi_{i} + \lambda b,$$ subject to the same constraints defined in Equations and , in which $\lambda$ is a regularization parameter that trades off between the and the .

From Equation , the dual formulation has the same Lagrangian defined in Equation . Consequently, we have to optimize the same function as defined in Equation with the constraint in Equation . However, the constraint in Equation is replaced by the constraint $$\label{eq:sum_lambda_constraint}
      \sum_{i=1}^{m}\alpha_{i}y_{i} = \lambda.$$

The same algorithm proposed by @Platt1998, with the proposed by @Fan2005, for optimizing ensuring the constraint in Equation can be applied to this optimization containing the constraint of the Equation . As the main idea of the algorithm is to ensure that $\sum\alpha_{i}y_{i}$ remains the same from one iteration to the other, before the optimization starts, we initialize $\alpha_{i}$ such that $\sum\alpha_{i}y_{i} = \lambda$. For this, we let $\alpha_{i} = \lambda/m_{p}$, $\forall i$ such that $y_{i} = 1$, in which $m_{p}$ is the number of positive training samples.

\[prop:maximum-lambda\] In the soft margin case, with parameter $C$, the maximum valid value for $\lambda$ is $C m_{p}$.

From Equation , $0\le\alpha_{i}\le C$. Maximum value $\lambda=\sum\alpha_{i}y_{i}$ is thus obtained by setting $\alpha_{i} = C$ for $i$ such that $y_{i} = 1$ and setting $\alpha_{i} = 0$ for $i$ such that $y_{i} = -1$. This yields $\lambda \le C m_{p}$

Thus during optimization, we must ensure , otherwise, for , the constraint in Equation would be broken for some $\alpha_{i}$.

Despite Proposition \[prop:maximum-lambda\] saying that it is allowed , when it happens, we have that $\alpha_{i} = C$ for $y_{i} = 1$ and $\alpha_{i} = 0$ for $y_{i} = -1$, and there will be no optimization. In this case, despite satisfying the constraints, there is no flexibility for changing the values of $\alpha_{i}$ because, for each pair $\alpha_{i}, \alpha_{j}$ selected by the algorithm [@Fan2005], we must update $\alpha_{i} = \alpha_{i} + \nabla_{\alpha}$, $\alpha_{j} = \alpha_{j} + \nabla_{\alpha}$ when $y_{i} \ne y_{j}$ and $\alpha_{i} = \alpha_{i} - \nabla_{\alpha}$, $\alpha_{j} = \alpha_{j} + \nabla_{\alpha}$ when $y_{i} = y_{j}$. For any $\nabla_{\alpha} \ne 0$, the constraint $0 < \alpha_{i} < C$ would break for either $\alpha_{i}$ or $\alpha_{j}$, for any selected pair. Then, in practice, we $\lambda$ in the interval $0 \le \lambda < C m_{p}$.

\[prop:negative-bias-term\] There exists some $\lambda$ such that we can obtain a bias term $b < 0$.

From the conditions, the bias term is defined as $$\begin{aligned}
          b &= y_{i} - \sum_{j=1}^{m}\alpha_{j}y_{j}K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right)\\
            &= y_{i} - \sum_{\substack{j=1:\\y_{j} = 1}}^{m}\alpha_{j}K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right) + \sum_{\substack{j=1:\\y_{j} = -1}}^{m}\alpha_{j}K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right),
        \end{aligned}$$ for any $i$ such that $0 < \alpha_{i} < C$. Now, let’s consider two possible cases: (1) $y_{i} = 1$ and (2) $y_{i} = -1$. For **Case (1)**, we have $$b = 1 - \alpha_{i} - \sum_{\substack{j=1:\\y_{j} = 1,\\j\ne i}}^{m}\alpha_{j}K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right) + \sum_{\substack{j=1:\\y_{j} = -1}}^{m}\alpha_{j}K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right),$$ as $K\left(\mathbf{x}_{i}, \mathbf{x}_{i}\right) = 1$. Note that $0 < K(\mathbf{x}, \mathbf{x}') \le 1$ for the kernel. To show that there exists a $\lambda$ such that $b < 0$, we analyze the worst case, i.e., when the kernel in the second summation—for negative training samples—is $1$. Then, we have $$          b = 1 - \alpha_{i} - \sum_{\substack{j=1:\\y_{j} = 1,\\j\ne i}}^{m}\alpha_{j}K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right) + \sum_{\substack{j=1:\\y_{j} = -1}}^{m}\alpha_{j}.$$ From Equation , we have $$\label{eq:sum_lambda_constraint_neg_equality}
          \sum_{\substack{j=1:\\y_{j} = -1}}^{m}\alpha_{j} = \sum_{\substack{j=1:\\y_{j} = 1}}^{m}\alpha_{j} - \lambda,$$ then $$b = 1 - \sum_{\substack{j=1:\\y_{j} = 1,\\j\ne i}}^{m}\alpha_{j}K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right) + \sum_{\substack{j=1:\\y_{j} = 1\\j\ne i}}^{m}\alpha_{j} - \lambda$$ Analyzing the worst case again, considering $\alpha_{j} = C$ for positive training samples, with $j \ne i$, we have $$\begin{aligned}
          b &= 1 - C\sum_{\substack{j=1:\\y_{j} = 1,\\j\ne i}}^{m}K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right) + C\left(m_{p} - 1\right) - \lambda\\
            &= 1 + C m_{p} - C - C\sum_{\substack{j=1:\\y_{j} = 1,\\j\ne i}}^{m}K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right) - \lambda.
        \end{aligned}$$ Given that, to ensure $b < 0$ it is sufficient to let $$          \lambda > 1 + C m_{p} - C\left(1 + \sum_{\substack{j=1:\\y_{j} = 1,\\j\ne i}}^{m}K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right)\right).$$ Given a $C \ge 1$ it is always possible to obtain a $\lambda$ such that $\lambda < C m_{p}$.

For **Case (2)**, we have $$b = - 1 - \sum_{\substack{j=1:\\y_{j} = 1}}^{m}\alpha_{j}K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right) + \sum_{\substack{j=1:\\y_{j} = -1}}^{m}\alpha_{j}K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right).$$ Again, considering the worst case for the values of the kernel for negative samples and using the equality in Equation , we have $$b = -1 - \sum_{\substack{j=1:\\y_{j} = 1}}^{m}\alpha_{j}K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right) + \sum_{\substack{j=1:\\y_{j} = 1}}^{m}\alpha_{j} -  \lambda.$$ Again, considering the greatest possible value for $b$, by considering $\alpha_{j} = C$ for positive samples, we have $$b = -1 - C\sum_{\substack{j=1:\\y_{j} = 1}}^{m}K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right) + C m_{p} - \lambda.$$ In this case, to ensure $b < 0$ it is sufficient to let $$\lambda > C m_{p} - 1 - C\sum_{\substack{j=1:\\y_{j} = 1}}^{m}K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right),$$ which is possible to obtain for any value of $C$.

In Proposition \[prop:negative-bias-term\], we considered a very extreme case for the proof. For example, in Case (1)—for $i$ such that $y_{i} = 1$—we considered $K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right) = 1$ for $j$ such that $y_{j} = -1$ and $K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right) \approx 0$ for $j$ such that $y_{j} = 1$. It means that all the negative samples have the same feature vector of sample $\mathbf{x}_{i}$ under consideration and all positive samples are far away from sample $\mathbf{x}_{i}$. In practice, we do not have the $\lambda$ nearly as constrained as in the proof to ensure a negative bias term. More than this, in our experiments with the , we observed that most of the time the bias term is negative for a binary classifier trained with the approach, i.e., it is often the case that even with $\lambda=0$ the bias will be negative. More details about this behavior is shown in Section \[sec:remarks\].

In Appendix \[appendix:sec:ssvm-formulation\] we present the complete formulation of the optimization problem for the classifier.[^3]

#### Choosing the $\lambda$ parameter for the 

Proposition \[prop:negative-bias-term\] states that we can find a $\lambda$ parameter that ensures a bounded for the optimization problem presented above. To ensure this, models with a non-negative bias term receive accuracy of $-\infty$ on the validation set, during the . Nevertheless, we cannot ignore that, in special circumstances, certain $\lambda$ values allow a negative bias term during the but not for training in the whole set of training samples. In this case, once the parameters are obtained by , if the obtained $\lambda$ does not ensure a negative bias term for training set, one would need to retrain the classifier with an increased value for $\lambda$, until a negative bias term is obtained for the final model. However, for grid search, we assume the distribution of the validation set, a subset of the training set, represents the distribution of the training set; that is one possible explanation as for why in our experiments we did not need to retrain the classifier with a value of $\lambda$ larger than the one obtained during grid search, as all values of $\lambda$ obtained during were able to ensure a negative bias term for all binary classifiers.

grid search in an open-set setup {#sec:grid-search}
--------------------------------

Two different approaches for grid searching the parameters in classifiers have been considered in the literature thus far [@Chang2011]: (1) the external approach and (2) the internal one. These forms were originally defined for a closed-set setting [@Chang2011], and properly extended to open-set scenarios [@MendesJunior2017]. In the external approach, on the parameters happens in the multiclass level so that all binary classifiers that compose the multiclass classifiers share the same set of parameters. On the other hand, in the internal approach, each binary classifier performs its own .

To perform a on the training set $X$, a subset $F \subset X$ is used to fit an classifier while performing the . Subset $V=X-F$ then forms the validation set. This can be done for both external and internal approaches.

There are two forms of dividing the training set $X$ into the fitting set $F$ and the validation set $V$ while performing the : the closed-set (traditional) and the open-set forms [@MendesJunior2017]. Both forms can be applied to both external and internal approaches. In open-set , the set of classes in $F$ is a proper subset of the classes in $X$. Open-set simulates the real scenario: the set of classes in $X$ is a proper subset of the classes that can appear at system usage—or in the [^4].

#### External closed-set 

As an example of the external closed-set , for the multiclass classifier, $80\%$ of the samples in $X$ are randomly selected for $F$ and $20\%$ for $V$. $F$ can have representative samples of all $n$ . Then, the multiclass classifier is trained with $F$ and evaluated with $V$, testing possible parameters. This is the traditional form of the external : we do not mind when the negative samples in $F$ represent the $n$ classes available for training.

#### External open-set 

In the external open-set , for the multiclass classifier, $\left\lfloor n/2 \right\rfloor$ of the $n$ for training are taken for $V$. Among the samples of the remaining $\left\lceil n/2 \right\rceil$ classes, $80\%$ are randomly selected for $F$ and $20\%$ for $V$. Then, the multiclass classifier is trained with $F$ and evaluated with $V$, testing possible parameters.

#### Internal closed-set 

In the internal closed-set , for a binary classifier, $80\%$ of the samples in $X$ are randomly selected for $F$ and $20\%$ for $V$. We ensure a random partitioning such that both $F$ and $V$ have representative samples of the positive and negative classes. In this case, the negative samples in $V$ can have representative samples of all $n-1$ negative classes, as the partitioning between $F$ and $V$ is random. That is, when using $V$ to obtain the accuracy during the , all classes in $V$ can be known a priori by the classifier trained with $F$. Then, the binary classifier is trained with $F$ and evaluated with $V$, testing possible parameters. This is the traditional form of the internal : we do not mind when the negative samples in $F$ represent the $n-1$ negative classes of the training.

#### Internal open-set 

In the internal open-set , for a binary classifier, $\left\lfloor (n-1)/2 \right\rfloor$ of the $n-1$ negative classes are taken for $V$. Among the samples of the remaining $\left\lceil (n-1)/2 \right\rceil + 1$ classes (considering the positive class), $80\%$ are randomly selected for $F$ and $20\%$ for $V$. Also, a random partitioning such that both $F$ and $V$ have representative samples of the positive and negative classes must be guaranteed. Then, the binary classifier is trained with $F$ and evaluated with $V$, testing possible parameters.

Figure \[fig:figGridSearch\] depicts how the set $X$ of training samples is partitioned for the closed- and open-set .

//in

/figGridSearchC/

, /figGridSearchO/

![ Difference between closed- and open-set . Each colored box represents a known class during training. Blue color represents the amount of samples used to train a classifier during the grid-search procedure (fitting set). Red part represents the validation set used to evaluate the classifier. Parameters with the best accuracy on the validation set are selected for training the classifier. For the open-set depicted in (), some of the known classes are considered as unknown during the grid-search procedure. For both external and internal , the closed- and open-set variations are split the same way, however ensuring, for the case of the internal , the positive class have representative samples in fitting set. []{data-label="fig:figGridSearch"}]({\striplastbar{figs/}__}\filename.pdf "fig:"){width="95.00000%"} \[fig:\]

Experiments {#sec:experiments}
===========

In this section, we present the experiments and details for comparing the proposed method with the existing ones in the literature, discussed in Section \[sec:related-work\]. In Section \[sec:experiments-baselines-summary\], we summarize the baselines. In Section \[sec:evaluation-measures\], we describe the evaluation measures used in our experiments. In Section \[sec:datasets\], we describe the and features. In Section \[sec:results-decision-boundaries\], we present initial results regarding the behavior of the methods in feature space. Finally, we present the results with statistical tests in Section \[sec:results\], finishing this section with some remarks in Section \[sec:remarks\].

Baselines {#sec:experiments-baselines-summary}
---------

For a fair comparison, we have implemented both the closed- and open-set approaches for the existing methods in the literature. We denote a given classifier using the closed- and open-set as and , respectively. All compared methods are -based. We use approach in the multiclass level except for the methods specified with subscript OVO.

In this work, we employ the one-class–based method of @Pritsos2013 for comparison, hereinafter referred to as . Although @Pritsos2013 uses a as the method to define a rejection function for each class, one could also use a , since it is also a form of one-class classifier. We also implemented this alternative to and refer to it as .

For the types of methods that train a rejection method and a multiclass classifier, we use implementations based on and as well: , , , and . indicates methods, i.e., methods that implements one rejection function at first and a multiclass classification method for the case the rejection function accepts the test sample as known.

Despite dealing with a multiclass problem, @Costa2012 [@Costa2014] evaluated their method in the binary fashion by obtaining the accuracy of individual binary classifiers. They did not present the multiclass version of the classifier directly. Therefore, in this work, we consider their method with the approach in the experiments. The test sample is classified as unknown when no binary classifier classifies it as positive. Complementarily, it is classified as the most confident class when one or more classifiers tags it as positive.

Besides those methods, we have employed [@Chang2011], [@Scheirer2013], [@Scheirer2014], [@Jain2014] as baselines for our experiments. Despite using an model, also makes use of for bounding and . We summarize the methods in Table \[tab:baselines-summary\].

For , , and , we perform external because we use the multiclass implementation made available by the authors [@Scheirer2013; @Scheirer2014; @Jain2014]. and internally make use of the multiclass implementation available in , so we perform external grid search for them as well. We have included and in the experiments to better evaluate the effectiveness of the reject function, as the with approach is closed-set and cannot classify as unknown once the reject function accepts the test sample. All other methods perform approach for both closed- and open-set procedures.

Except for —for which @Scheirer2013 have observed linear kernel performs better all other methods use kernel. Among all those methods, only one-class–based methods and are able to ensure a bounded .

As for open-set recognition is a growing research area, we highlight that one advantage of our proposed method, compared to -based ones, relies on its simplicity. The proposed method is defined purely as a convex optimization problem, as it is for . -based methods require post-processing after model is trained. At testing phase, our proposed method requires just the prediction from the obtained model, while -based methods require extra predictions from models for each binary classifier that composes the multiclass one.

Evaluation measures {#sec:evaluation-measures}
-------------------

Most of the proposed evaluation performance measures in the literature are focused on binary classification, e.g., traditional classification accuracy, , etc. [@Sokolova2009]. Even the ones proposed for multiclass scenarios—e.g., average accuracy, multiclass , etc. [@Sokolova2009]—usually consider only the closed-set scenario. Recently, @MendesJunior2017 have proposed and for multiclass open-set recognition problems. In this work, we apply such measures and further extend the to , based on the harmonic mean [@Mitchell2004].

$$\glssymbol{hna} =
      \begin{cases}
        0, \text{if } \glssymbol{aks} = 0 \text{ or } \glssymbol{aus} = 0,\\
        \frac{2}{\left(\frac{1}{\scriptsize\glssymbol{aks}} + \frac{1}{\scriptsize\glssymbol{aus}}\right)}, \text{otherwise}.
      \end{cases}$$

In this case, is the and is the . is the accuracy obtained on the testing samples that belong to one of the classes with which the classifier was trained. is the accuracy on the testing samples whose classes have no representative samples in the training set.

One advantage of over is that when a classifier performs poorly on or , drops toward 0. One biased classifier that blindly classifies every sample as unknown, would receive of 0.5 while would be 0. However, notice that 0.5 is not the worst possible accuracy for , as some methods—trying to correctly predict test labels—can have its smaller than 0.5. The worst case for —when it is 0—would be when all known samples are classified as unknown and all unknown samples classified as belonging to one of the known classes. On the other hand, the worst case for would be when at least one of such cases happens.

For experiments in this work, we have considered , , , and . For a fair comparison with previous methods in the literature [@Scheirer2013; @Scheirer2014; @Jain2014]—which only showed performance figures using the traditional we also present results regarding the traditional multiclass [@Sokolova2009] considering both and .

data set {#sec:datasets}
--------

For validating the proposed method and comparing it with existing methods, we consider . In the (with 15 classes), the images are represented by a bag-of-visual-word vector created with soft assignment [@Gemert2010] and max pooling [@Boureau2010], based on a codebook of 1000 Scale Invariant Feature Transform (SIFT) codewords [@Lowe2004]. (with 26 classes) represents the letters of the English alphabet (black-and-white rectangular pixel displays). In the (with 95 classes), the data was acquired using two Fifth Dimension Technologies (5DT) gloves hardware and two Ascension Flock-of-Birds magnetic position trackers. In the (with 256 classes), the feature vectors consider a bag-of-visual-words characterization approach, with features acquired with dense sampling, SIFT descriptor for the points of interest, hard assignment [@Gemert2010], and average pooling [@Boureau2010]. Finally, for the (with 1000 classes), the features were extracted with the Border/Interior (BIC) descriptor [@Stehling2002]. These or other could be used with different characterizations, however, in this work, we focus on the learning part of the problem rather than on the feature characterization one.

In Table \[tab:datasets\], we summarize the main features of the considered in terms of number of samples, number of classes, dimensionality, and approximate number of samples per class.[^5]

[crrrr]{} **** & **\# samples** & **\# classes** & **\# features** & **\# samples/class**\
**** & & & &\
**** & & & &\
**** & & & &\
**** & & & &\
**** & & & &\

Decision regions {#sec:results-decision-boundaries}
----------------

We start presenting results on artificial so that the of each classifier can be visualized. For these cases, we show the region of the feature space in which a possible test sample would be classified as one of the known classes or unknown. We also show how each classifier handles the . Figure \[fig:cone-torus\] depicts the images of for the . In Figure \[subfig:cone-torus\_\_mcossvm\_ova\_gsic\], as expected, we see that the gracefully bounds the ; any sample that would appear in the white region would be classified as unknown. We present images of for other in Appendix \[appendix:sec:more-results\].

/in [ /, \_\_mcsvm\_ova\_gsic\_highGamma\_fixedC/, \_\_mcsvmdbc\_ova\_gsic/, \_\_svm1vsll\_ovx\_gsec/, \_\_mcocsvm\_ova\_gsic/, \_\_mcocbbsvm\_ova\_gsic/, \_\_mcocbbsvm\_ovo\_gsec/, \_\_mcsvdd\_ova\_gsic/, \_\_mcsvddbb\_ova\_gsic/, \_\_mcsvddbb\_ovo\_gsec/, \_\_wsvm\_ovx\_gsec/, \_\_pisvm\_ovx\_gseo/, \_\_mcossvm\_ova\_gsic/ ]{}

[0.24]{} ![ for the . Non-white regions represent the region in which a test sample would be classified as belonging to the same class of the samples with the same color. All samples in the white regions would be classified as unknown. []{data-label="fig:cone-torus"}]({\striplastbar{figsR2/}__}figBoundaries__cone-torus_forboundaries\filename__color.png "fig:"){width="\textwidth"} \[subfig:cone-torus\]

Results {#sec:results}
-------

We performed a series of experiments simulating an open-set scenario in which 3, 6, 9, and 12 classes are available for training the classifiers. Remaining classes of each are unknown at training phase and only appear on testing stage. Since different have a different number of known classes, the fraction of unknown classes, or the openness [in the sense of @Scheirer2013], varies per . For each , method, and number $n$ of , we ran 10 experiments by choosing $n$ random classes for training, among the classes of the . Selected sets of classes are used across each experiment with different classifiers. In addition, the same samples used for training one classifier $C_i$ is used when training another classifier $C_j$ (a similar setup is adopted for the testing and validation sets), which is referred to as a paired experiment.

Figures \[fig:graphs\_ossvm\_R2\_normal\_open/na/na\]–\[fig:graphs\_ossvm\_R2\_normal\_open/mafm/osfmM\] show the results considering , , and , respectively, for all . In those figures, we compare only methods implemented with open-set grid search and thus we have excluded methods from them. We see that, in general, maintains a good accuracy among the , while the other methods have good accuracy for one or two but do not maintain a similar accuracy for the others. We present additional results considering other measures—, , and —and methods in Appendix \[appendix:sec:more-results\].

![image]({\striplastbar{graphs_ossvm_R2_normal_open/}__}figGraphs_legend.pdf){width="0.75\linewidth"}

/in [na/na]{}

/in [ 15scenes\_bow\_soft\_max\_1000/15-scenes, aloi\_bic/aloi, auslan/auslan, caltech256\_bow\_dense\_hard\_average\_1000/caltech-256, letter/letter ]{}

[0.495]{} ![image]({\striplastbar{graphs_ossvm_R2_normal_open/}__}figGraphs__\dataset__\measure__color__withoutlegend.pdf){width="0.9\linewidth"}

![image]({\striplastbar{graphs_ossvm_R2_normal_open/}__}figGraphs_legend.pdf){width="0.75\linewidth"}

/in [harmonicNA/hna]{}

/in [ 15scenes\_bow\_soft\_max\_1000/15-scenes, aloi\_bic/aloi, auslan/auslan, caltech256\_bow\_dense\_hard\_average\_1000/caltech-256, letter/letter ]{}

[0.495]{} ![image]({\striplastbar{graphs_ossvm_R2_normal_open/}__}figGraphs__\dataset__\measure__color__withoutlegend.pdf){width="0.9\linewidth"}

![image]({\striplastbar{graphs_ossvm_R2_normal_open/}__}figGraphs_legend.pdf){width="0.75\linewidth"}

/in [mafm/osfmM]{}

/in [ 15scenes\_bow\_soft\_max\_1000/15-scenes, aloi\_bic/aloi, auslan/auslan, caltech256\_bow\_dense\_hard\_average\_1000/caltech-256, letter/letter ]{}

[0.495]{} ![image]({\striplastbar{graphs_ossvm_R2_normal_open/}__}figGraphs__\dataset__\measure__color__withoutlegend.pdf){width="0.9\linewidth"}

Superiority of is confirmed by the Wilcoxon test using the Holm method to adjust each of the paired p-values to account for multiple comparisons [@Demsar2006]. For the Wilcoxon test, we used the mean of the 10 experiments for each pair of and method. In Table \[tab:wilcoxon-open\], we present the comparison among the methods using the open-set . Once again, in virtually all cases, the outperformed (with statistical significance) all the baselines. Except when comparing with : in this case there is no statistical significance for most of the measures. When comparing with , performs better with statistical significance for all measures. It is worth noticing that @Jain2014 proposed with the scheme, which has the same principle of the open-set later formalized by @MendesJunior2017.

The Wilcoxon statistical test verifies if the difference in performance measure is significant. Aiming at evaluating if the frequency wins is statistically significant, we have performed an additional test with Binomial test, presented in Appendix \[appendix:sec:more-results\]. According to Binomial tests, performs better than with statistical significance in most of the cases.

We have compared with separately to better organize the results. In Table \[tab:wilcoxon-ocbb\], we present Wilcoxon statistical test comparing with methods. We can see in Table \[tab:wilcoxon-ocbb\] that performs better in all cases; in most of them with statistical significance.

Finally, we also investigate the efficacy of the open-set by comparing the open- and closed-set grid search versions of each classifier. We present this comparison, with Wilcoxon test, in Table \[tab:wilcoxon-open-vs-closed\]. For some methods—, , , and implementations with open-set grid search perform consistently better than closed-set counterparts. For the specific case of , it seems that usually the closed-set form is preferable, however, and point better performance with statistical difference towards open-set version. For , , and , in general the measures point towards open-set , however, it is not a consistent result.[^6]

Remarks {#sec:remarks}
-------

Note that even the traditional obtained better results than some of the methods in the literature specially tailored for the open-set scenario. We observed that the higher the $\gamma$ parameter, the better the ’s performance for the open-set scenario. When grid-searching the $\gamma$ parameter, the implementation used in this work chooses the higher $\gamma$ value in case of tie in the validation set. In many cases, there is statistical difference between this implementation and the implementation that chooses the smallest $\gamma$ in case of ties. Therefore, the used herein is an optimized version for the open-set scenario and it is expected to outperform the traditional implementation.

Another remark is about the frequency of negative bias terms in the binary classifiers that compose the . Most of the binary classifiers for the approach already have the correct negative bias term, as shown in Table \[tab:correct-bias-term-frequency\]. To better understand the reason, we also obtained the frequency of binary classifiers with negative bias term using the approach, also shown in Table \[tab:correct-bias-term-frequency\]. In this case, only about half of the binary classifiers have negative bias term.

An informal explanation for this behavior is that in the approach, we have more negative than positive samples—and more than one class in the negative set. Then, it is more likely to have the negative samples “surround” the positive ones helping the to create a bounded for the positive class. This intuition is confirmed by Figure \[fig:figPlottingkernel\]. For both class 1 and class 2, the creates a bounded (negative bias term) because class 3 is negative for those binary classifiers and is “surround” the positive class in both cases. Considering class 3 as positive, we have no negative samples surround the positive class. That is why, in this case, the is unbounded (non-negative bias term).

The high frequency of negative bias term for the explains why some authors in the literature have been reporting good accuracy for detection problems using s with kernels. For a detection problem, we have one class of interest and multiple others that we consider as negative for what we have access to train with. As the number of negative samples is usually larger, it is more likely to have a classifier with bounded for detection problems.

  ---------- -------- -------- -------- -------- --------
   Approach                                      
              99.00    97.67    99.00    98.00    99.67 
  ---------- -------- -------- -------- -------- --------

  : Percentage of binary classifiers with negative bias term for and approaches.[]{data-label="tab:correct-bias-term-frequency"}

Despite most of the cases the obtains the correct bias term for the approach, the optimization problem presented in Section \[sec:ssvm\] also optimizes the . That is, it optimizes for recognition in open-set scenario.

Conclusions and future work {#sec:conclusion}
===========================

In this work, we gave sufficient and necessary condition for the with kernel to have finite . We then showed that by reformulating the optimization policy to simultaneously optimize margin and ensure a negative bias term, the is bounded and it provides a formal open-set recognition algorithm.

Proposed extends upon the traditional ’s optimization problem. Objective function is changed in the primal problem, but the Lagrangian for the dual problem remains the same. In the dual problem for the , only a single constraint differs from the ’s dual problem. The same algorithm [@Platt1998] can be used to ensure the new constraint is satisfied between iterations. Also, the same algorithm [@Fan2005] can be applied. Consequently, it makes the method easy to extend from a implementation.

A limitation of the proposed method is that it can be applied to specific kinds of kernel: only the ones that are monotonically decreasing when the samples get far apart from each other. Among the well-known kernels, only has this property. Another limitation of this work is the lack of a proof that ensures the parameters selected during grid search phase can always generate a model on the training phase which has a negative bias term for bounding .

As future work, one can investigate alternative forms for ensuring a bounded for specific implementations of s that do not rely on the bias term—as the ones in @Vogt2002 and @Kecman2005. As shown in Section \[sec:ssvm-bounding-open-space\], the without the bias term cannot ensure a bounded , as it depends on the shape of the training data. However, a simple solution can be obtained by training the without bias term and establishing an artificial negative bias term in the decision function. In this case, research can be done on how to obtain this artificial bias term.

Another future work is to investigate the properties of the with the approach. In a binary , at least one of the two classes will always have infinite —if one is bounded, the other must include all the remaining space and so it must be infinite. We observed experimentally that, according to the way the probability is calculated for each binary classifier [@Platt2000; @Lin2007] and according to the way the probability estimates are combined in the level [@Wu2004], depending on the threshold established, a bounded can occur but cannot be ensured. Future work relies on investigating mechanisms to always ensure a bounded and, consequently, a limited . This is worth investigating because some works in the literature have presented better results with the than approach for closed-set problems [@Galar2011]. We already performed some initial experiments using the proposed herein as a binary classifier for the approach—rather than the ’s configuration—and we checked that by ensuring a bounded for every binary classifier does not ensure a bounded in this new configuration. We then hypothesize that, for approach, this investigation should be accomplished in the probability estimation or/and probability combination.

Finally, with the recent trend on deep neural networks for a range of problems, employing deep features with open-set classification methods is worth investigating in a future work. In Appendix \[appendix:sec:imagenet-results\], we present preliminary results in this direction with and some baselines.

Complete SSVM formulation {#appendix:sec:ssvm-formulation}
=========================

The optimization problem for the classifier is defined as $$\begin{aligned}
        \min_{\mathbf{w},b,\xi}\ & \frac{1}{2}||\mathbf{w}||^{2} + C\sum_{i=1}^{m}\xi_{i} + \lambda b,\\
        \mbox{s.t.}\ & y_{i}\left(\mathbf{w}^{T}\mathbf{x}_{i} + b\right) - 1 + \xi_{i} \ge 0,\\
                                 & \xi_{i} \ge 0.
  \end{aligned}$$

Using the Lagrangian method, we have the Lagrangian defined as $$\begin{aligned}
    \label{appendix:eq:lagrangian-initial}
    \mathcal{L}(\mathbf{w}, b, \xi, \alpha, r) &= \frac{1}{2}||w||^{2} + C\sum_{i=1}^{m}\xi_{i} + \lambda b - \sum_{i=1}^{m}r_{i}\xi_{i} \nonumber \\
                                               &- \sum_{i=1}^{m}\alpha_{i}\left[y_{i}\left(\mathbf{w}^{T}\mathbf{x}_{i} + b\right) - 1 + \xi_{i}\right],
  \end{aligned}$$ in which $\alpha_{i} \in \mathbb{R}$ and $r_{i} \in \mathbb{R}$, $i = 1, \dots, m$, are the Lagrangian multipliers

First we want to minimize with respect to $\mathbf{w}$, $b$, and $\xi_{i}$, then we must ensure $$\nabla_{\mathbf{w}} = \frac{\partial}{\partial b}\mathcal{L} = \frac{\partial}{\partial\xi_{i}}\mathcal{L} = 0.$$

Consequently, we have $$\begin{aligned}
    \label{appendix:eq:gradient-w}
    w - \sum_{i=1}^{m}\alpha_{i}y_{i}\mathbf{x}_{i} = 0 \implies w = \sum_{i=1}^{m}\alpha_{i}y_{i}\mathbf{x}_{i},\\
    \label{appendix:eq:derivative-b}
    \lambda - \sum_{i=1}^{m}\alpha_{i}y_{i} = 0 \implies \sum_{i=1}^{m}\alpha_{i}y_{i} = \lambda,\\
    \label{appendix:eq:derivative-xi}
    C - \alpha_{i} - r_{i} = 0 \implies r_{i} = C - \alpha_{i}.
  \end{aligned}$$

As the Lagrangian multipliers $\alpha_{i}, r_{i}$ must be greater than 0, from Equation we have the constraint $0 \le \alpha_{i} \le C$ as a consequence, in the dual problem, of the soft margin formulation. This is the same constraint we have in the traditional formulation of the classifier.

Using Equations – to simplify the Lagrangian in Equation , we have $$    \mathcal{L}(\mathbf{w}, b, \xi, \alpha, r) = \sum_{i=1}^{m}\alpha_{i} - \frac{1}{2}||\mathbf{w}||^{2},$$ i.e., the same Lagrangian of the traditional optimization problem. The optimization of the bias term $b$ relies on the constraint in Equation .

Therefore, the dual optimization problem is defined as $$\begin{aligned}
        \min_{\alpha}\ & W(\alpha) = - \mathcal{L}(\mathbf{w}, b, \xi, \alpha, r) = \frac{1}{2}||\mathbf{w}||^{2} - \sum_{i=1}^{m}\alpha_{i},\\
        \mbox{s.t.}\ & 0 < \alpha_{i} < C, \ \forall i,\\
                       & \sum_{i=1}^{m}\alpha_{i}y_{i} = \lambda.
  \end{aligned}$$

Additional examples, results and discussion {#appendix:sec:more-results}
===========================================

In this section, we present additional results to the ones presented in Sections \[sec:results-decision-boundaries\] and \[sec:results\]. In Figures \[fig:boat\]–\[fig:regular\], we present more examples of of different classifiers for data sets, complementary to those presented in Section \[sec:results-decision-boundaries\].

In those figures, we see that depending on the shape of the , is not able to bound the , as in Figure \[subfig:boat\_\_mcsvm\_ova\_gsic\_highGamma\_fixedC\] for the blue class, while for other , e.g., in Figures \[subfig:four-gauss\_\_mcsvm\_ova\_gsic\_highGamma\_fixedC\] and \[subfig:regular\_\_mcsvm\_ova\_gsic\_highGamma\_fixedC\], we observe that is able to bound the for each know class. In Figures \[subfig:boat\_\_mcsvmdbc\_ova\_gsic\] and \[subfig:four-gauss\_\_mcsvmdbc\_ova\_gsic\], we notice that the behavior of the is similar to the ’s one, as it simply moves the hyperplane towards the positive class. As the translation of the hyperplane is based on the , measured on the training data for each binary classifier, we can see in Figure \[subfig:regular\_\_mcsvmdbc\_ova\_gsic\] that some binary classifiers dominate over others when combining them for the extension. As expected, in Figures \[subfig:boat\_\_svm1vsll\_ovx\_gsec\]–\[subfig:regular\_\_svm1vsll\_ovx\_gsec\], leaves an unbounded . However, the confusion showed in Figure \[subfig:regular\_\_svm1vsll\_ovx\_gsec\] is because the is only . In Figures \[subfig:boat\_\_mcocsvm\_ova\_gsic\]–\[subfig:regular\_\_mcocsvm\_ova\_gsic\], we can observe the highly-specialized behavior of the for both applied with approach (Figures \[subfig:boat\_\_mcocsvm\_ova\_gsic\]–\[subfig:regular\_\_mcocsvm\_ova\_gsic\]) and for classification (Figures \[subfig:boat\_\_mcocbbsvm\_ova\_gsic\]–\[subfig:regular\_\_mcocbbsvm\_ova\_gsic\]). In Figures \[subfig:boat\_\_mcsvdd\_ova\_gsic\]–\[subfig:regular\_\_mcsvdd\_ova\_gsic\], -based methods has a similar behavior to -based ones, however, with better generalization ability. In Figures \[subfig:boat\_\_wsvm\_ovx\_gsec\]–\[subfig:regular\_\_wsvm\_ovx\_gsec\], we can notice the prevalence of the one-class model of the , however not as specialized as the , due to the parameters adjustment performed by . We also note in Figures \[subfig:boat\_\_wsvm\_ovx\_gsec\] and \[subfig:four-gauss\_\_wsvm\_ovx\_gsec\] that the binary model of the is able to better separate among the known classes, compared to (Figures \[subfig:boat\_\_mcocsvm\_ova\_gsic\] and \[subfig:four-gauss\_\_mcocsvm\_ova\_gsic\]) and (Figures \[subfig:boat\_\_mcsvdd\_ova\_gsic\] and \[subfig:four-gauss\_\_mcsvdd\_ova\_gsic\]). In Figures \[subfig:four-gauss\_\_pisvm\_ovx\_gseo\] and \[subfig:regular\_\_pisvm\_ovx\_gseo\], we can see that is able the bound the for every class, however, as seen in Figure \[subfig:boat\_\_pisvm\_ovx\_gseo\], that is not always the case. Authors of proposed the method to optimize according to the , however they did not prove a bounded for the method. Finally, in Figures \[subfig:boat\_\_mcossvm\_ova\_gsic\]–\[subfig:regular\_\_mcossvm\_ova\_gsic\], we observe the behavior of the proposed and how it gracefully bounds the .

/in [ /, \_\_mcsvm\_ova\_gsic\_highGamma\_fixedC/, \_\_mcsvmdbc\_ova\_gsic/, \_\_svm1vsll\_ovx\_gsec/, \_\_mcocsvm\_ova\_gsic/, \_\_mcocbbsvm\_ova\_gsic/, \_\_mcocbbsvm\_ovo\_gsec/, \_\_mcsvdd\_ova\_gsic/, \_\_mcsvddbb\_ova\_gsic/, \_\_mcsvddbb\_ovo\_gsec/, \_\_wsvm\_ovx\_gsec/, \_\_pisvm\_ovx\_gseo/, \_\_mcossvm\_ova\_gsic/ ]{}

[0.24]{} ![ for the . Non-white regions represent the region in which a test sample would be classified as belonging to the same class of the samples with the same color. All samples in the white regions would be classified as unknown. []{data-label="fig:boat"}]({\striplastbar{figsR2/}__}figBoundaries__boat_forboundaries\filename__color.png "fig:"){width="\textwidth"} \[subfig:boat\]

/in [ /, \_\_mcsvm\_ova\_gsic\_highGamma\_fixedC/, \_\_mcsvmdbc\_ova\_gsic/, \_\_svm1vsll\_ovx\_gsec/, \_\_mcocsvm\_ova\_gsic/, \_\_mcocbbsvm\_ova\_gsic/, \_\_mcocbbsvm\_ovo\_gsec/, \_\_mcsvdd\_ova\_gsic/, \_\_mcsvddbb\_ova\_gsic/, \_\_mcsvddbb\_ovo\_gsec/, \_\_wsvm\_ovx\_gsec/, \_\_pisvm\_ovx\_gseo/, \_\_mcossvm\_ova\_gsic/ ]{}

[0.24]{} ![ for the . Non-white regions represent the region in which a test sample would be classified as belonging to the same class of the samples with the same color. All samples in the white regions would be classified as unknown. []{data-label="fig:four-gauss"}]({\striplastbar{figsR2/}__}figBoundaries__four-gauss_forboundaries\filename__color.png "fig:"){width="\textwidth"} \[subfig:four-gauss\]

/in [ /, \_\_mcsvm\_ova\_gsic\_highGamma\_fixedC/, \_\_mcsvmdbc\_ova\_gsic/, \_\_svm1vsll\_ovx\_gsec/, \_\_mcocsvm\_ova\_gsic/, \_\_mcocbbsvm\_ova\_gsic/, \_\_mcocbbsvm\_ovo\_gsec/, \_\_mcsvdd\_ova\_gsic/, \_\_mcsvddbb\_ova\_gsic/, \_\_mcsvddbb\_ovo\_gsec/, \_\_wsvm\_ovx\_gsec/, \_\_pisvm\_ovx\_gseo/, \_\_mcossvm\_ova\_gsic/ ]{}

[0.24]{} ![ for the . Non-white regions represent the region in which a test sample would be classified as belonging to the same class of the samples with the same color. All samples in the white regions would be classified as unknown. []{data-label="fig:regular"}]({\striplastbar{figsR2/}__}figBoundaries__regular_forboundaries\filename__color.png "fig:"){width="\textwidth"} \[subfig:regular\]

In Section \[sec:results\], we presented the results for , , and . In Figures \[fig:graphs\_ossvm\_R2\_normal\_open/mifm/osfmm\]–\[fig:graphs\_ossvm\_R2\_normal\_open/aus/aus\], we present complementary results for methods with open-set regarding other measures: , , , , and , respectively. In Figures \[fig:graphs\_ossvm\_R2\_normal\_open/mifm/osfmm\]–\[fig:graphs\_ossvm\_R2\_normal\_open/bbmifm/fmm\], for the results regarding , , and , we see that does not obtain the best behavior in all cases but it consistently appears in the top positions for all the , while the other methods have better results for one or two and lower performance for the others. Overall, the has better performance with statistical difference for those measures, as shown in Tables \[tab:wilcoxon-open\] (Wilcoxon test) and \[tab:binomial-open\] (Binomial test). In Figures \[fig:graphs\_ossvm\_R2\_normal\_open/aks/aks\] and \[fig:graphs\_ossvm\_R2\_normal\_open/aus/aus\] are the results regarding the measures that compose both and : and , respectively. We observe in those figures that is able to keep a reasonable accuracy for both and .

![image]({\striplastbar{graphs_ossvm_R2_normal_open/}__}figGraphs_legend.pdf){width="0.75\linewidth"}

/in [mifm/osfmm]{}

/in [ 15scenes\_bow\_soft\_max\_1000/15-scenes, aloi\_bic/aloi, auslan/auslan, caltech256\_bow\_dense\_hard\_average\_1000/caltech-256, letter/letter ]{}

[0.495]{} ![image]({\striplastbar{graphs_ossvm_R2_normal_open/}__}figGraphs__\dataset__\measure__color__withoutlegend.pdf){width="0.9\linewidth"}

![image]({\striplastbar{graphs_ossvm_R2_normal_open/}__}figGraphs_legend.pdf){width="0.75\linewidth"}

/in [bbmafm/fmM]{}

/in [ 15scenes\_bow\_soft\_max\_1000/15-scenes, aloi\_bic/aloi, auslan/auslan, caltech256\_bow\_dense\_hard\_average\_1000/caltech-256, letter/letter ]{}

[0.495]{} ![image]({\striplastbar{graphs_ossvm_R2_normal_open/}__}figGraphs__\dataset__\measure__color__withoutlegend.pdf){width="0.9\linewidth"}

![image]({\striplastbar{graphs_ossvm_R2_normal_open/}__}figGraphs_legend.pdf){width="0.75\linewidth"}

/in [bbmifm/fmm]{}

/in [ 15scenes\_bow\_soft\_max\_1000/15-scenes, aloi\_bic/aloi, auslan/auslan, caltech256\_bow\_dense\_hard\_average\_1000/caltech-256, letter/letter ]{}

[0.495]{} ![image]({\striplastbar{graphs_ossvm_R2_normal_open/}__}figGraphs__\dataset__\measure__color__withoutlegend.pdf){width="0.9\linewidth"}

![image]({\striplastbar{graphs_ossvm_R2_normal_open/}__}figGraphs_legend.pdf){width="0.75\linewidth"}

/in [aks/aks]{}

/in [ 15scenes\_bow\_soft\_max\_1000/15-scenes, aloi\_bic/aloi, auslan/auslan, caltech256\_bow\_dense\_hard\_average\_1000/caltech-256, letter/letter ]{}

[0.495]{} ![image]({\striplastbar{graphs_ossvm_R2_normal_open/}__}figGraphs__\dataset__\measure__color__withoutlegend.pdf){width="0.9\linewidth"}

![image]({\striplastbar{graphs_ossvm_R2_normal_open/}__}figGraphs_legend.pdf){width="0.75\linewidth"}

/in [aus/aus]{}

/in [ 15scenes\_bow\_soft\_max\_1000/15-scenes, aloi\_bic/aloi, auslan/auslan, caltech256\_bow\_dense\_hard\_average\_1000/caltech-256, letter/letter ]{}

[0.495]{} ![image]({\striplastbar{graphs_ossvm_R2_normal_open/}__}figGraphs__\dataset__\measure__color__withoutlegend.pdf){width="0.9\linewidth"}

Regarding methods, in Section \[sec:results\], we have presented only the Wilcoxon statistical tests (Table \[tab:wilcoxon-ocbb\]). Complementing those results, in Figures \[fig:graphs\_ossvm\_R2\_normal\_ocbb/na/na\]–\[fig:graphs\_ossvm\_R2\_normal\_ocbb/mafm/osfmM\], we present accuracies , , and , respectively, for methods compared to . We complement the analysis with Binomial statistical tests in Table \[tab:binomial-ocbb\], where we can see that performs better than any method.

![image]({\striplastbar{graphs_ossvm_R2_normal_ocbb/}__}figGraphs_legend.pdf){width="0.75\linewidth"}

/in [na/na]{}

/in [ 15scenes\_bow\_soft\_max\_1000/15-scenes, aloi\_bic/aloi, auslan/auslan, caltech256\_bow\_dense\_hard\_average\_1000/caltech-256, letter/letter ]{}

[0.495]{} ![image]({\striplastbar{graphs_ossvm_R2_normal_ocbb/}__}figGraphs__\dataset__\measure__color__withoutlegend.pdf){width="0.9\linewidth"}

![image]({\striplastbar{graphs_ossvm_R2_normal_ocbb/}__}figGraphs_legend.pdf){width="0.75\linewidth"}

/in [harmonicNA/hna]{}

/in [ 15scenes\_bow\_soft\_max\_1000/15-scenes, aloi\_bic/aloi, auslan/auslan, caltech256\_bow\_dense\_hard\_average\_1000/caltech-256, letter/letter ]{}

[0.495]{} ![image]({\striplastbar{graphs_ossvm_R2_normal_ocbb/}__}figGraphs__\dataset__\measure__color__withoutlegend.pdf){width="0.9\linewidth"}

![image]({\striplastbar{graphs_ossvm_R2_normal_ocbb/}__}figGraphs_legend.pdf){width="0.75\linewidth"}

/in [mafm/osfmM]{}

/in [ 15scenes\_bow\_soft\_max\_1000/15-scenes, aloi\_bic/aloi, auslan/auslan, caltech256\_bow\_dense\_hard\_average\_1000/caltech-256, letter/letter ]{}

[0.495]{} ![image]({\striplastbar{graphs_ossvm_R2_normal_ocbb/}__}figGraphs__\dataset__\measure__color__withoutlegend.pdf){width="0.9\linewidth"}

Extra experiments with deep features {#appendix:sec:imagenet-results}
====================================

With recent advances in deep learning [@LeCun2015; @Russakovsky2015], the machine learning literature has received plenty of works based on those neural networks. Deep features have been explored together with other methods—e.g., linear —for final classification. Although it is not the focus of our work, we have performed an initial experiment on based on deep features. However, results we obtained are not conclusive, as using deep features for open-set experiments raises much details that should be studied in future research. In this section, we describe some of such details for future investigation and preliminary results.

We performed experiments on 360 classes of that has no overlap with the 1000 classes in . Those images were made available by @Bendale2016. The network used for feature extraction on those 360 classes was trained on . We used a different for training the network aiming at avoiding considering as unknown the classes that could be known from the point view of the network, i.e., classes for which the network learns how to represent. We trained a network and extracted the features from its last pooling layer. We applied to reduce from 1024 features to 100. Out of those 360 classes, we performed experiments with the same setup presented in Section \[sec:results\]: we considered 3, 6, 9, and 12 for training the methods by selecting 10 random classes per number of available classes—40 experiments in total.

An ideal experiment should consider training one individual network per experiment—out of those 40 experiments—because this way we could ensure the network only knows what is known from the point of view of the experiment we are about to perform. As this is not the focus of the current work, we simply trained the network on a separated . We did avoid training the network on itself because the classes we would consider as unknown in our experiments would not be really unknown from the point of view of the network. Open-set scenario combined with deep features introduces particularities that should be investigated in future work.

Preliminary results are presented in Figure \[fig:graphs\_ossvm\_R2\_onlyImageNet/na/na,harmonicNA/harmonicNA,mafm/osfmM\]. As expected, in general, methods with open-set performs better than closet-set variants. Among them, , , , , and performs better. Those methods obtained and close to 100% for 3, 6, 9, and 12 , as can be inferred from Figures \[fig:graphs\_ossvm\_R2\_onlyImageNet/na\] and \[fig:graphs\_ossvm\_R2\_onlyImageNet/harmonicNA\]. In general, performed better, with more winning cases. was not the main competing method with throughout our experiments (Section \[sec:results\]), however, for this dataset, Wilcoxon statistical tests in Table \[tab:wilcoxon-open-imagenet\] indicates performs better with statistical significance.

![image]({\striplastbar{graphs_ossvm_R2_onlyImageNet/}__}figGraphs_legend.pdf){width="0.75\linewidth"}

/in [na/na,harmonicNA/harmonicNA,mafm/osfmM]{}

in [ ImageNet\_googlenet\_openset\_images\_07102017 ]{}

[0.945]{} ![image]({\striplastbar{graphs_ossvm_R2_onlyImageNet/}__}figGraphs__\dataset__\measure__color__withoutlegend.pdf){width="0.9\linewidth"}

We highlight that those results are preliminary, as further details should be investigated to setup an open-set experiment based on deep features. Future research must be accomplished regarding the relation to what is known from the point of view of the network and what is known for the open-set classification algorithm. In practical cases, that should probably be the same classes for both the network and classification method, however, transfer learning prior from extracting features should not be neglected [@Yosinski2014].

0.2in

[^1]: Note in some implementations, including the library [@Chang2011], the decision function is defined as $f(\mathbf{x}) = \operatorname{sign}(\mathbf{w}^T \mathbf{x} - \rho)$. In that case, instead of ensuring a negative bias term $b$, one must ensure a positive bias term $\rho$ to bound the .

[^2]: The main difference from the without bias term to the traditional is that the constraint in Equation does not exist in the dual formulation.

[^3]: Source code, extended upon the implementation [@Chang2011], will be available upon acceptance of this manuscript.

[^4]: For both the closed-set and the open-set approaches, we consider open-set scenarios in the testing phase of our experiments in Section \[sec:experiments\].

[^5]: Feature vectors for the used in this work will be available upon acceptance of this manuscript.

[^6]: Raw results obtained in our experiments as well as the script to perform the statistical analysis are available at <https://github.com/pedrormjunior/ssvm-results>.
