Learning Bounds for Open-Set Learning
Traditional supervised learning aims to train a classifier in the closed-set world, where training and test samples share the same label space. In this paper, we target a more challenging and realistic setting: open-set learning (OSL), where there exist test samples from the classes that are unseen during training. Although researchers have designed many methods from the algorithmic perspectives, there are few methods that provide generalization guarantees on their ability to achieve consistent performance on different training samples drawn from the same distribution. Motivated by the transfer learning and probably approximate correct (PAC) theory, we make a bold attempt to study OSL by proving its generalization error-given training samples with size n, the estimation error will get close to order O_p(1/\sqrt{n}). This is the first study to provide a generalization bound for OSL, which we do by theoretically investigating the risk of the target classifier on unknown classes. According to our theory, a novel algorithm, called auxiliary open-set risk (AOSR) is proposed to address the OSL problem. Experiments verify the efficacy of AOSR. The code is available at github.com/Anjin-Liu/Openset_Learning_AOSR.
Code (1)
Tasks
Learning TheoryOpen Set LearningTransfer LearningSimilar Papers 제목 키워드 기반
Quantifying Error in the Presence of Confounders for Causal Inference
Estimating average causal effect (ACE) is useful whenever we want to know the effect of an intervention on a given outcome. In the absence of a randomized experiment, many methods such as stratification and inverse prope…
Causal InferenceRepresentation LearningLocal Average and Marginal Treatment Effects with a Misclassified Treatment
This paper studies identification of the local average and marginal treatment effects (LATE and MTE) with a misclassified binary treatment variable. We derive bounds on the (generalized) LATE and exploit its relationship…
Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds
Strong worst-case performance bounds for episodic reinforcement learning exist but fortunately in practice RL algorithms perform much better than such bounds would predict. Algorithms and theory that provide strong probl…
Learning TheoryReinforcement LearningReinforcement Learning (RL)Bounds on the Expected Size of the Maximum Agreement Subtree
We prove polynomial upper and lower bounds on the expected size of the maximum agreement subtree of two random binary phylogenetic trees under both the uniform distribution and Yule-Harding distribution. This positively …
Make the Minority Great Again: First-Order Regret Bound for Contextual Bandits
Regret bounds in online learning compare the player's performance to $L^*$, the optimal performance in hindsight with a fixed strategy. Typically such bounds scale with the square root of the time horizon $T$. The more r…
Multi-Armed Bandits