# What does the notation $\{ \pm 1 \}^X$ in relation to functions and hypothesis classes means in the context of PAC learning over half spaces?

I was reading the following paper (on PAC learning over half-spaces) and encountered the following notation for a hypothesis class (on page 4):

$$\mathcal{H} \subset \{ \pm 1 \}^X$$

However, it was not clear to me what that notation means. Usually, when I see $\{0,1 \}^n$ in the context computer science, I usually assume its either the set of bit strings of size n with all the arrangements for 0 and 1 (or maybe the vectors of size n or sequences). However, $\{ \pm 1 \}^X$ seems a little odd. Does that mean the same thing but instead of 0's and 1's we have 1's and -1's?

Also a hypothesis (in the context of machine learning) is a function. Hence, its a little weird that:

$$\mathcal{H} \subset \{ \pm 1 \}^X$$

is called the hypothesis class.

Does anyone know why $\mathcal{H} \subset \{ \pm 1 \}^X$ is used to denote the hypothesis class in that paper? Isn't the hypothesis class a function? I understand that in the context of say, functional analysis, we can represent functions in vector spaces, but does that mean we can do that here? I am just confused about that.

After thinking about it a little bit, I think I know what it means. If you take $X$ to mean the instance space of the problem (i.e. the mathematical object that we are making predictions over, i.e. the input to the hypothesis function) then if the problem is in the context of classification (i.e. labels/co-domaine $\pm 1$), then if the hypothesis class is denoted by:

$$\mathcal{H} \subset \{ \pm 1 \}^X$$

the only thing that makes sense to me is, the set of functions that output single numbers 1 or -1, however, over the input space indicated by the instance space $X$. i.e.

$$h \in \mathcal{H} \subset \{ \pm 1 \}^X \iff h: X \rightarrow \{\pm1 \}$$

so $\mathcal{H} \subset \{ \pm 1 \}^X$ is a short hand notation for such functions (i.e. the hypothesis class). Thats what I think it means.

• $Y^X$ is a widely used notation for the set of functions from $X$ to $Y$, and $\{\pm 1\}$ must surely be intended to mean $\{-1, +1\}$, so I think you have probably correctly answered your own question (but I don't know anything about the subject matter of the paper). – Rob Arthan May 10 '15 at 15:11
• @RobArthan thanks Rob, I think it makes sense because of the context of the paper. I am surprised, I had never seen that notation before and I tend to enjoy some mathematical reading. Oh well, we learn new stuff every day! – Charlie Parker May 10 '15 at 15:15

It seems my suspicion was correct. For $\mathcal{H} \subset \{ \pm1\}^X$ means:
$$\{ \pm1\}^X \iff \{ h \mid h : X \rightarrow \{+1, -1\} \}$$
$$Y^X \iff \{ f \mid f : X \rightarrow Y \}$$