World's most popular travel blog for travel bloggers.

[Solved]: What is a homogenous half-space?

, ,
Problem Detail:

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.

Answered By : FS12345

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.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50707

3.2K people like this