patternMinor
Explanation of proof of why connectedness is not conjunctively local of any order $k$
Viewed 0 times
conjunctivelywhylocalorderconnectednessanynotproofexplanation
Problem
I was reading Minsky's and Papert's book on perceptrons and I was reading theorem 0.6.1 and I was having a hard time understanding it. The theorem was about proving that the property "connected" was not a local property i.e. that you somehow had to see the whole picture to know if something was connected or not. In particular their prove shows that "connected" is not a conjunctively local property of any order (for definition of conjunctively local see appendix at the end of this question).
In particular goes as follows:
Suppose that $\psi_{CONNECTED}$ has order K. Then to distinguish between these two $k+1$-wide figures:
there must be some $\varphi_0$ such that $\varphi_0(X_0) = 0$, because $X_0$ is not connected. All $\varphi$'s have value 1 on $X_1$, which is connected. Now $ \varphi_0$ can depend on at most $k$ points, so there must be at least one middle square, say $S_j$, that does not contain one of these points.
This last sentence is the one that does not make sense to me. Why does there must be at least one middle square that does not contain one of these points? I don't understand this. When it says "these points" what does that mean? Why are we talking about the middle points? Why does that matter? Also, the sentence as a whole doesn't make sense to me nor its purpose.
Like the first two properties make sense:
In particular goes as follows:
Suppose that $\psi_{CONNECTED}$ has order K. Then to distinguish between these two $k+1$-wide figures:
there must be some $\varphi_0$ such that $\varphi_0(X_0) = 0$, because $X_0$ is not connected. All $\varphi$'s have value 1 on $X_1$, which is connected. Now $ \varphi_0$ can depend on at most $k$ points, so there must be at least one middle square, say $S_j$, that does not contain one of these points.
This last sentence is the one that does not make sense to me. Why does there must be at least one middle square that does not contain one of these points? I don't understand this. When it says "these points" what does that mean? Why are we talking about the middle points? Why does that matter? Also, the sentence as a whole doesn't make sense to me nor its purpose.
Like the first two properties make sense:
- of course there must exist a $\varphi_0$ that rejects $X_0$, since $\psi_{CONNECTED}$ can only work properly if all of its predicates say YES if and only if the shape is connected. Since $X_0$ is not connected then some predicate must reject it. That is clear.
- For a similar reason its obvious that all the predicates say YES on $X_1$ since its connected. More precisely, that is the definition of connected according to $\psi_{CONNECTED}$, that all its predicates say YES. Since $X_1$ is connected then all its predicates must say YES.
- Last part that does make sense before my brain gets confused is that of course $\varphi_0$ can depend on
Solution
The predicate $\varphi_0$ depends on at most $k$ points. There are $k+1$ middle squares. So $\varphi_0$ cannot depend on all of them. That is, there is a middle square that $\varphi_0$ does not depend on. Therefore, if we add that square, the value of $\varphi_0$ doesn't change, and so $\psi$ is still 0, even though the figure is now connected.
Context
StackExchange Computer Science Q#70838, answer score: 5
Revisions (0)
No revisions yet.