PaperlayerView exact revision on arXiv

Source-linked AI summary

Open Set Domain Adaptation: Theoretical Bound and Algorithm

Zhen Fang, Jie Lu, Feng Liu, Junyu Xuan, Guangquan Zhang

arXiv:1907.08375v2cs.LGstat.ML

TL;DR

The paper addresses unsupervised adaptation when the unlabeled target contains classes absent from the labeled source, a setting not covered by existing closed-set theory. It derives an open-set learning bound centered on open set difference and uses it to design DAOD, which separates unknowns while aligning known classes. On 38 real-world tasks, DAOD outperformed competitive UOSDA baselines.

  • Problem

    UOSDA lacks theoretical treatment while target domains may contain unknown classes absent from the source label set.

  • Method

    The paper derives an open-set learning bound and designs DAOD by regularizing open set difference alongside distribution alignment.

  • Results

    DAOD achieved average Acc(OS) of 69.3% and Acc(OS∗) of 70.4% across 38 tasks, improving 3.4% and 3.6% over OSBP.

  • Takeaways & Limitations

    Open set difference provides the theoretical basis for recognizing unknown target samples while adapting known classes.

Abstract

from arXiv · show

The aim of unsupervised domain adaptation is to leverage the knowledge in a labeled (source) domain to improve a model's learning performance with an unlabeled (target) domain -- the basic strategy being to mitigate the effects of discrepancies between the two distributions. Most existing algorithms can only handle unsupervised closed set domain adaptation (UCSDA), i.e., where the source and target domains are assumed to share the same label set. In this paper, we target a more challenging but realistic setting: unsupervised open set domain adaptation (UOSDA), where the target domain has unknown classes that are not found in the source domain. This is the first study to provide a learning bound for open set domain adaptation, which we do by theoretically investigating the risk of the target classifier on unknown classes. The proposed learning bound has a special term, namely open set difference, which reflects the risk of the target classifier on unknown classes. Further, we present a novel and theoretically guided unsupervised algorithm for open set domain adaptation, called distribution alignment with ppen difference (DAOD), which is based on regularizing this open set difference bound. The experiments on several benchmark datasets show the superior performance of the proposed UOSDA method compared with the state-of-the-art methods in the literature.

I. INTRODUCTION

Unsupervised open set domain adaptation addresses target domains containing unknown classes absent from the labeled source domain. The paper develops a theoretical bound and the DAOD algorithm to identify unknowns while aligning known-class distributions.

  • Motivation: UDA transfers labeled source-domain knowledge to an unlabeled target domain despite discrepancies between their distributions.Existing approaches include feature matching and instance reweighting.
  • Motivation: Most UDA methods assume source and target domains share the same label set, defining the closed-set setting.This assumption is problematic when target labels are unavailable.
  • UOSDA Problem: UOSDA allows unknown target classes absent from the source label set, creating challenges in labeling unknowns and aligning distributions safely.Unknown samples can interfere with matching and cause negative transfer.
  • Theory: The paper derives a learning bound for UOSDA by relating target-classifier risk on unknown classes to an estimable open set difference.The bound extends prior closed-set theory beyond binary classification and closed settings.
  • Method: DAOD regularizes the open set difference while jointly optimizing structural risk, distribution alignment, and manifold regularization.It separates unknown target samples and aligns source and target domains for known classes.
  • Experiments: Across 38 real-world UOSDA tasks, DAOD outperformed ATI and OSBP, demonstrating the reported advantage of the proposed method.The evaluation included 20 face-recognition and 18 object-recognition tasks.

1) Notations for distributions:

The paper defines source and target distributions, risks, partial risks, and distribution distances used to analyze domain adaptation. It also introduces MMD and manifold regularization as tools for measuring and controlling domain discrepancy.

  • Distributions: Source and target conditional distributions describe class-specific feature distributions, while πt_C+1 denotes the target prior probability of unknown classes.
  • Risks: Source and target risks are expected losses under the respective labeled joint distributions.
  • Partial risks: Partial risks separately measure classifier behavior on known and unknown target classes.
  • Distribution distances: Discrepancy distance measures differences in loss behavior across two feature distributions and is symmetric, but need not be a true metric.
  • Distribution distances: MMD compares distributions through a function class, and with a universal kernel it is zero exactly when the distributions are equal.
  • Regularization: Projected MMD makes distribution discrepancy suitable as a regularization term, while manifold regularization captures geometric relationships among source and target samples.

IV. PROPOSED ALGORITHM

The paper defines open set difference as a key component of an open set domain adaptation bound and uses it to connect unknown-class risk with distribution discrepancy. The resulting theorem reduces to the closed-set case when the target has no unknown classes.

  • A. Main Theoretical Result and Open Set Difference: Open set difference is introduced to bound the classifier’s risk on unknown target classes.
  • A. Main Theoretical Result and Open Set Difference: Theorem 1 bounds open set adaptation using source risk, distribution discrepancy, open set difference, and a joint-error term under a mild hypothesis-space condition.
  • A. Main Theoretical Result and Open Set Difference: When the unknown-target prior is zero, the open set difference vanishes and Theorem 1 degenerates to a closed-set adaptation bound.
  • A. Main Theoretical Result and Open Set Difference: The open set difference contains positive and negative terms that respectively encourage unknown-target recognition and prevent source samples from being classified as unknown.
  • A. Main Theoretical Result and Open Set Difference: Both components of the open set difference can be estimated from unlabeled samples through empirical risk estimates.
  • A. Main Theoretical Result and Open Set Difference: DAOD is constructed by employing open set difference to guide distribution alignment.

B. Algorithm

DAOD optimizes source classification together with marginal and conditional distribution alignment, open set difference, manifold regularization, and hypothesis complexity control. Its formulation replaces discrepancy distance with projected MMD and uses pseudo target labels.

  • B. Algorithm: The optimization combines structural risk, joint distribution alignment, manifold regularization, and open set difference.
  • B. Algorithm: Conditional distribution alignment is added alongside marginal alignment using an adaptive factor to combine their contributions.
  • B. Algorithm: Projected MMD replaces discrepancy distance because discrepancy distance is difficult to estimate in the algorithmic objective.
  • B. Algorithm: The algorithm uses squared loss to obtain a theoretical bound based on MMD distance.
  • B. Algorithm: The representer theorem expresses the optimizer using source and target samples, kernel coefficients, and an MMD matrix.
  • B. Algorithm: Pseudo target labels support computation of conditional alignment terms for known and class-specific target samples.

2) Manifold Regularization: (

The training procedure builds sample affinities and manifold regularization, initializes pseudo labels with an open set classifier, and iteratively updates labels and classifier coefficients. A negative objective term is addressed by a uniqueness result for the optimizer.

  • 2) Manifold Regularization:: Manifold regularization uses pairwise sample affinities and a graph Laplacian to encode geometric structure across source and target samples.
  • C. Training: The matrix formulation encodes labels, source supervision, and unknown-target assignments in the loss and open set difference.
  • C. Training: Although the objective contains a negative term, the stated theorem guarantees a unique minimizer under a universal-kernel condition and a bounded open-set risk term.
  • C. Training: OSNNcv-t generates initial pseudo labels by comparing the two nearest neighbors and applying a distance-ratio threshold when their labels differ.
  • C. Training: Iterative refinement recomputes the MMD matrix, solves for β, and updates pseudo labels until the specified iteration count.

V. EXPERIMENTS AND EVALUATIONS

The experiments evaluate DAOD on three cross-domain recognition settings using real-world datasets, open-set protocols, and comparisons with no-transfer, closed-set, and open-set baselines. Parameter studies examine DAOD’s robustness and tuning behavior.

  • A. Real World Datasets: DAOD was evaluated on object-recognition tasks from Office-31 and Office-Home and face-recognition tasks from PIE.Office-31 has 6 tasks, Office-Home has 12, and the experiments use open-set protocols with designated known and unknown classes.
  • B. Baseline Algorithms: The comparison includes OSNN without transfer, TCA+OSNN as a closed-set method, and JDA+OSNN, JGSA+OSNN, ATI+OSNN, and OSBP as open-set methods.The baselines represent no-transfer, closed-set, and open-set approaches used to assess DAOD.
  • C. Parameter Tuning: DAOD’s hyper-parameters include the kernel function, adaptation parameters λ, σ, ρ, p, and µ, iteration count T, and threshold t.The paper discusses these parameters individually before reporting detailed evaluation results.
  • C. Parameter Tuning: DAOD uses a Gaussian kernel, estimates µ from domain and class-conditional A-distances, and recomputes this estimate at every iteration.The target samples predicted as known are used in the conditional-distribution estimate.
  • D. Evaluation Metrics: The evaluation reports Acc(OS) and Acc(OS*) as the two accuracy measures, with Acc(OS) identified as the main index for UOSDA performance.The metrics are based on predicted classifier outputs and class-specific counts.

D. Experimental Results

Across benchmark UOSDA tasks, DAOD generally outperforms the evaluated baselines, while its performance depends on balancing open-set parameters and distribution-alignment components. The sensitivity and convergence studies indicate robust behavior across broad parameter ranges and steady performance within fewer than ten iterations.

  • D. Experimental Results: Closed-set TCA performed poorly on most tasks, while open-set algorithms generally exceeded OSNN because source and known-target samples have different distributions.The results are interpreted as evidence of negative transfer for the closed-set method and the need to address distribution differences.
  • D. Experimental Results: 24 out of 38 tasks favored DAOD in Acc(OS), whose average Acc(OS) and Acc(OS*) were 69.3% and 70.4%, improving 3.4% and 3.6% over OSBP.DAOD achieved better Acc(OS) than six baseline algorithms on most tasks.
  • D. Experimental Results: DAOD’s negative open-set term helps separate source samples from unknown target samples, addressing a problem attributed to JDA, JGSA, and ATI.Those methods may mix unknown samples with known samples when constructing a latent space for distribution matching.
  • E. Open Set Parameters Analysis: Increasing δ increased unknown-class accuracy, but Acc(OS) decreased when δ exceeded 0.25 because more known samples were classified as unknown.The study found δ should be positive, with DAOD superior to the best baseline when δ was selected from [0.05, 0.2].
  • E. Open Set Parameters Analysis: The difference δ was more influential than α, and DAOD generally used α from [0.2, 0.4] and δ from [0.05, 0.25].Figures were similar across most α values from 0.4 to 1.2, while smaller α values performed slightly better than larger ones.
  • F. Parameter Sensitivity, Ablation Study and Convergence Analysis: DAOD was robust across broad parameter ranges, while the open-set difference and distribution-alignment terms were reported as important and necessary.The parameter studies covered λ, σ, ρ, p, t, α, γ, and T across Office-31, Office-Home, and PIE.
  • F. Parameter Sensitivity, Ablation Study and Convergence Analysis: Performance remained steady for ρ ∈ [0, 1] but dropped when ρ increased beyond 1, whereas threshold t remained stable from 0 to 0.9.Large ρ caused DAOD to focus mainly on geometric information and ignore other information; t was reported as insensitive in the iterative procedure.
  • F. Parameter Sensitivity, Ablation Study and Convergence Analysis: DAOD reached steady performance in fewer than 10 iterations.This convergence result was obtained in the analysis of iteration count T.

I. APPENDIX A: DEFINITION, NOTATIONS AND PROOF FOR THEOREM 1

Appendix A formalizes the source and target probability spaces, distributions, and risks, then proves supporting propositions used in Theorem 1. The proof separates target risk into source-label and unknown-class components and combines these bounds.

  • Definitions and notations: The source and target domains are defined as joint distributions over inputs and their respective label spaces.The associated random variables are measurable maps into X × Ys and X × Yt.
  • Definitions and notations: The appendix defines target distributions conditioned on source labels, an individual unknown class, and the source-label subset.These conditional distributions support separate risk calculations for known and unknown target classes.
  • Risk definitions: Source risk and target risk are defined by integrating the loss over the source and target joint distributions.The target risk is evaluated over the complete target label space, including the unknown class.
  • Proof for Theorem 1: Theorem 1’s proof proceeds in two steps: bounding the target risk on source labels and then controlling the unknown-class component.The two components are recombined to obtain the theorem’s result.

II. APPENDIX B: PROOF FOR THEOREM 2

Appendix B proves Theorem 2 by establishing properties of its objective function. The argument shows positive definiteness, existence of optimizers, and uniqueness of the solution.

  • Proof for Theorem 2: The proof uses positive semidefiniteness of projected MMD distance and manifold regularization to establish a lower-bound property of the objective.A universal kernel and γ < 1 imply that the relevant matrix is symmetric and positive definite.
  • Proof for Theorem 2: The matrix is analyzed through an orthogonal diagonalization, with the smallest diagonal entry of the diagonal matrix providing a positive constant.This supports the objective’s coercive behavior.
  • Proof for Theorem 2: The objective exceeds its value at zero outside a sufficiently large ball, so continuity and compactness guarantee the existence of optimizers.The optimizers lie inside the specified open ball.
  • Proof for Theorem 2: A minimizer satisfies the first-order condition, and uniqueness of the solution to that condition implies uniqueness of the minimizer.The proof concludes Theorem 2 after combining the three claims.

III. APPENDIX C: LEARNING BOUND BASED ON MMD

Appendix C develops an MMD-based learning bound for open set domain adaptation under squared loss. It extends a scalar-function bound to vector-valued scoring functions and incorporates an open set difference term.

  • Learning bound based on MMD: The bound addresses OSDA under squared loss and shows how MMD controls generalization performance.The setting uses an RKHS with a universal kernel.
  • Learning bound based on MMD: The appendix identifies that an existing bound handles scalar-valued functions, whereas OSDA uses vector-valued scoring functions.A new bound is therefore proposed for the scoring-function setting.
  • Learning bound based on MMD: Lemma 3 bounds the discrepancy between two input distributions for the hypothesis class using a constant vector-valued function and MMD.The coefficient is L = max{4Mm(C + 1), (C + 1)Mm + M}.
  • Learning bound based on MMD: Theorem 4 assumes a universal-kernel RKHS, squared loss, bounded function parameters, measurability, and a hypothesis class augmented with an unknown-class constant vector.Its proof combines triangle inequalities, Proposition 2, Fubini’s theorem, and discrepancy-distance bounds.
  • Learning bound based on MMD: The resulting bound includes the target risk on unknown classes and the open set difference Δo alongside source and conditional-target discrepancy terms.The proof obtains the result by combining the intermediate inequalities.

IV. APPENDIX D: LEARNING BOUND BASED ON EMPIRICAL VERSION

Appendix D derives empirical versions of the learning bounds using Rademacher complexity and Natarajan dimension. The resulting high-probability bounds apply to labeled source and unlabeled target samples.

  • Empirical learning bound: The random-variable bounds are difficult to evaluate directly, motivating empirical bounds based on Rademacher complexity and Natarajan dimension.These quantities measure the richness of real-valued and multiclass hypothesis classes, respectively.
  • Empirical learning bound: The empirical proof separately controls source risk, unknown-class target risk, and target risk associated with treating unlabeled samples as unknown.The three controls are combined with Theorem 1.
  • Empirical learning bound: The Natarajan dimension generalizes VC dimension from binary to multiclass predictors.When there are exactly two classes, the two dimensions are equal.
  • Empirical learning bound: Corollary 1.1 gives a bound with probability at least 1 − 3δ for hypotheses satisfying the constant unknown-class function condition and having Natarajan dimension d.The samples comprise labeled source observations and unlabeled target observations drawn independently.
  • Empirical learning bound: Theorem 5 provides an empirical version under a universal-kernel RKHS, squared loss, bounded hypotheses, and labeled-source plus unlabeled-target samples.Its proof applies concentration and Rademacher-complexity arguments to the three risk components.

A. More experiments

The experiments evaluate DAOD across benchmark datasets, openness levels, manifold-regularization ablations, and running time. DAOD remains robust across openness values, benefits from manifold regularization, and has comparable running time to leading baselines.

  • Datasets and settings: The experiments covered 12 Office-Home and 12 ImageCLEF-DA transfer tasks using multiple deep-framework features.Office-Home used VGG16, VGG19, and ResNet-50 features; ImageCLEF-DA used ResNet-50, VGG16, and VGG19 features.
  • Manifold regularization: 55 out of 60 tasks showed higher Acc(OS) for DAOD with manifold regularization than without it.The comparison used ablation studies on ImageCLEF-DA and Office-31 datasets.
  • Manifold regularization: 75.3% average Acc(OS) across 60 tasks represented a 1.04% improvement from adding manifold regularization.ImageCLEF-DA and Office-31 averages improved by 1.07% and 1.00%, respectively.
  • Openness robustness: DAOD achieved the best performance for almost all tested openness values while using the same parameters throughout.Office-Home experiments varied openness from 0.10 to nearly 0.85 and compared DAOD with OSBP.
  • Running time: DAOD had comparable running time to ATI and JGSA while achieving superior classification accuracy.The timing comparison used the same input features and fixed iteration counts for the algorithms.
Loading 1907.08375v2…