How would one construct conjunctively local predicate of order k for checking if a shape is Convex?

Question

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

Answer 1

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

• Charlie Parker: 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?
• Discrete lizard: 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.