2
$\begingroup$

I am self-studying in the area of query learning and having a difficulty in understanding the definition of closed under projection for concept classes discussed in several papers (for example, here (page 2), here page 18 and here page 8) with regard to learning from membership queries in Query learning.

I have a set of elements X. Each concept is a subset of X and the concept class C is a set of concepts. For example the following is a concept class over $X=\{x_1,x_2,x_3,x_4,x_5\}$ with three concepts $f_1$,$f_2$ and $f_3$ represent respectively the sets $\{x_2,x_3,x_4\}$ $\{x_1,x_5\}$ and $\{x_1,x_2,x_4\}$.

      x1|x2|x3|x4|x5
  f1  0 |1 |1 |1 |0
  f2  1 |0 |0 |0 |1
  f3  1 |1 |0 |1 |0

The definition is different from restricting boolean functions to a specific range $A\subseteq X$ and can be stated as follows :

$C$ is a set of boolean functions $\{0,1\}^n\rightarrow\{0,1\}$. A partial assignment $p$ is $(p_1,p_2,\dots,p_n)$ where $p_i\in\{0,1,*\}$. $C$ is closed under projection if for every concept $f\in C$ and for every partial assignment $p$, $f(p)\in C$.

My issue is what's the shape of $f(p)$. What I understand from the definition, is that first I need to see the class as set of boolean functions:

      000|001|010|011|100|101|110|111
  f1  0  |1  |1  |1  |0  | 0 | 0 | 0
  f2  1  |0  |0  |0  |1  | 0 | 0 | 0
  f3  1  |1  |0  |1  |0  | 0 | 0 | 0

(as |X|=5, three new elements were added and mapped to 0).

Then for $x\in X$ the projection of $x$ to $p$, $p(x)=(d_1,d_2,\dots,d_n)$ such that $d_i=p_i$ for all $p_i\in \{0,1\}$ and the $ith$ value in $x$ if $p_i=*$. For example, $x=(0,1,1)$ and $p=(1,*,0)$ will result in $(1,1,0)$.

It is assumed that most of the classes in the literature are projecton-closed.

Consider the concept $f_3$ and $p=001$, the projection $f_p$ is a new concept such that $f_p(x)=f_3(p(x))$ for every $x\in X$. As $p$ projects every $x$ to $001$ and $f_3(001)=1$ we have $f_p=\{1,1,1,1,1,1,1,1\}$ . If my understanding is correct then any concept class where initially $|X|\neq 2^n$ will not be projection-closed. Is this true? I'm 99% sure I'm wrong but don't know where.

$\endgroup$

migrated from cs.stackexchange.com Dec 16 '15 at 17:29

This question came from our site for students, researchers and practitioners of computer science.

Your Answer

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

Browse other questions tagged or ask your own question.