2
$\begingroup$

I was reading Minsky's and Papert's book on perceptrons and it had the definition of conjunctively local as follow (look at the last images if its still unclear):

A predicate $\psi$ is conjunctively local of order k if it can be computed by independently computing a set of functions $\varphi_1(X)$...$\varphi_n(X)$ and then combined by the results of another function $\Omega$ of n argument by a set $\Phi $ of predicates $\varphi$ such that each $\varphi$ depends no more than $k$ points on a 2D Euclidean plane $R$ and: $$ \psi(X) = \begin{cases} 1 \text{ if } \varphi(X) = 1 \text{ for every } \varphi \text{ in } \Phi \\ 0 \text{ otherwise. } \end{cases} $$

Then in the book they claim that testing if a figure $X$ drawn on a 2D Euclidean pixel plan $R$ is conjunctively local of order 3. First recall how one would text for convexity on $R$. Essentially one woul look at three points/pixels and draw a line segment joining the points and if the third chose point between them is not in the drawn figure $X$, then it would not be convex.

My question is given this knowledge, how does one show that $\Psi_{convex}(X)$ is conjuctively local of order 3? The order 3 seems sort of clear to me because each $\varphi$ only needs look at 3 points to test convexity. However, it remains unclear to me how one would construct a general $\Psi(X)$ such that it always test correctly for any drawn geometric shape if its convex or not. I guess maybe part of my quesiton is that the definition of conjuctively local is not clear to me. Is it correct to think of $\Psi$ as a function only on the given geometric shape or is it also a funciton fo the whole plane $R$? It seems clear how to construct $\Psi$ if we know the shape in advance but otherwise it doesn't seem we can fix one single architecture and be able to text for convexity.


enter image description here

enter image description here

$\endgroup$
3
$\begingroup$

One way to construct $\Psi_{\mathrm {CONVEX }}$ is as follows: define $\phi_{i,j,k}(X) := \begin{cases} 1 & \text{if $(x_i,x_j \in X \Rightarrow x_k\in X)$ } \\ 0 & \text{otherwise}\\\end{cases}$.

Now, we define the set $\Phi$ by picking all pairs of $x_i,x_j\in R$ and all $x_k$ that lie on the line segment between them, i.e. $\phi_{i,j,k}\in \Phi$ for all $x_i,x_j\in R$ and all $x_k\in \{x\in R\mid \exists\lambda\in [0,1]: x=\lambda x_i + (1-\lambda)x_j\}$.

Note that each $\phi_{i,j,k}$ depends on only three values of $R$ and that the shape $X$ is convex if and only if all $\phi_{i,j,k} \in \Phi$ have value $1$. So, according to your definition, $\Psi_{\mathrm {CONVEX }}$ is conjuctively local of order $3$.

This does not seem like a very practical approach to determine the convexity of a shape, in particular when $R = \mathbb{R}^2$, since that means $\Phi$ is of infinite size.

So the basic idea is that for given indices $i,j,k$, the $\phi_{i,j,k}$ are functions of $X$ and exactly three points of $R$: $x_i,x_j$ and $x_k$. The selection of their indices (i.e. the set $\Phi$) is independent of $X$, but does depend on $R$.

$\endgroup$
  • $\begingroup$ I guess right now I'm still a bit confused on whether things are functions of R or only X. Do you mind clarifying that? Are the smaller predicates $\phi(\cdot)$ functions of the form $\varphi:X \to \{0,1\}$ or $\varphi:R \to \{0,1\}$? From your discussion, it seems that $\Phi_{i,j,k}$ has to process things not in X to ever discover its not convex. So the notation of the book seems confusing. Its a function of R, always and we are testing figures X, but we observe also things not in X, right? $\endgroup$ – Pinocchio Feb 26 '17 at 2:03
  • $\begingroup$ Well, for given indices $i,j,k$, $\phi_{i,j,k}$ depends on only three points of $R$, independent of $X$, and on $X$ (this is given in the definition). The choice of indices, which is essentially means which functions we pick, does depend on $R$, but not on $X$. That it depends on $R$ is unavoidable, since we need to find a point not in $X$ to show non-convexity. That the choice of the indices may not depend on $X$ seems to be mentioned in the lower part of your image, as we would get a very trivial function of order 0 otherwise. $\endgroup$ – Discrete lizard Feb 26 '17 at 9:08

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.