3
$\begingroup$

I can't think of any definition for half-space that would involve some sort of quantity not being homogenous.

This term is used in the paper Robust Concepts and Random Projection in the following paragraphs:

The next problem we consider is learning an intersection of t half-spaces in Rn, i.e., the positive examples all lie in the intersection of t half-spaces and the negative examples lie outside that region. It is not known how to solve the problem for an arbitrary distribution. However efficient algorithms have been developed for reasonably general distributions assuming that the number of half-spaces is relatively small [8, 44]. Here, we derive efficient learning algorithms for robust concepts in this class.

We assume that all the half-spaces are homogenous. Let the concept class of intersections of half-spaces be denoted by H(t,n). A single concept in this class is specified by a set of t half-spaces P = {h1, . . . , ht}, and the positive examples are precisely those that satisfy hi · x ≥ 0 for i = 1 . . . t. Let (P, D) be a concept-distribution pair such that P is -robust with respect to the distribution D. We assume that the support D is a subset of the unit sphere (and remind the reader that this as well as homogeneity are not really restrictive, as they can be achieved by scaling and adding an extra dimension, respectively; see e.g. [44]).

It's not clear to me from context, not defined in the paper and I haven't been able to find a clear definition from searching for it.

$\endgroup$
  • $\begingroup$ Is this related? $\endgroup$ – G. Bach Dec 14 '15 at 10:10
5
$\begingroup$

A half-space is said to be homogeneous if the hyperplane that defines it contains the origin.

(Source: S. Vempala, A Random Sampling based Algorithm for Learning Intersections of Half-spaces. Journal of the ACM 57(6) article 32, 2010. PDF.)

$\endgroup$

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.