2
$\begingroup$

I am currently studying the paper Learning and Evaluating Classifiers under Sample Selection Bias by Bianca Zadrozny. In section 3.4. Support vector machines, the author says the following:

3.4. Support vector machines
In its basic form, the support vector machine (SVM) algorithm (Joachims, 2000a) learns the parameters $a$ and $b$ describing a linear decision rule $$h(x) = \text{sign}(a \cdot x + b),$$ whose sign determines the label of an example, so that the smallest distance between each training example and the decision boundary, i.e. the margin, is maximized. Given a sample of examples $(x_i, y_i)$, where $y_i \in \{ -1, 1 \}$, it accomplishes margin maximization by solving the following optimization problem: $$\text{minimize:} \ V(a, b) = \dfrac{1}{2} a \cdot a \\ \text{subject to:} \ \forall i : \ y_i[a \cdot x_i + b] \ge 1$$ The constraint requires that all examples in the training set are classified correctly. Thus, sample selection bias will not systematically affect the output of this optimization, assuming that the selection probability $P(s = 1 \mid x)$ is greater than zero for all $x$.

How does the constraint that all examples in the training set are classified correctly imply that sample selection bias will not systematically affect the output of the optimisation? Furthermore, why is it necessary to assume that the selection probability is greater than zero for all $x$? These are not clear to me.

$\endgroup$
3
+50
$\begingroup$

I seriously doubt the correctness of Zadrozny's conclusion. Her argument is not supported by any formal deliberations and only by one artificial example. So I can only try to interpret her logic.

To answer your questions:

How does the constraint that all examples in the training set are classified correctly imply that sample selection bias will not systematically affect the output of the optimisation?

It does not, by itself. Zadrozny seems to consider it in combination with the maximum margin property of the SVMs, which implies that only the points on the margin determine the boundary. The logic is apparently that the selection bias in the vicinity of the class boundary is more-or-less constant, equally affecting both classes, and thus doesn't affect the boundary (much). In my opinion, this is a bold statement that calls for a formal proof.

Furthermore, why is it necessary to assume that the selection probability is greater than zero for all $x$?

It is not necessary, but, following Zadrozny's logic, should be sufficient: If all points have a non-zero probability to be selected, then the margin points also have a chance of being selected. On the other hand, if the selection probability is zero for $x$ around the true boundary, those points cannot be selected and the estimated class boundary will differ significantly from the true one.

Again, I am not convinced and would prefer seeing a formal proof.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer. What do you mean by "true boundary"? $\endgroup$ Dec 27 '20 at 19:08
  • 1
    $\begingroup$ You're right, "true" is misleading. I meant "the boundary that would be estimated if all points were available (without selection bias)". $\endgroup$
    – Igor F.
    Dec 27 '20 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.