Talk:Parity function

Machine learning

Parity functions have received some interest in (theoretical) machine learning as well; see e.g. John Langford's blog, and recall that the inability of linear models to learn XOR (parity of two inputs) was a major point in the book Perceptrons back in 1969, or at least in the controversy surrounding the book. I'd love to write a bit more about this, but I'm not too familiar with the subject. QVVERTYVS (hm?) 01:38, 4 January 2014 (UTC)[reply]

equivalence classes of the infinite parity function?

I'm having trouble making sense of the following paragraph:

Assuming axiom of choice it can be easily proved that parity functions exist and there are

2^{\mathfrak {c}}

many of them - as many as the number of all functions from

\{0,1\}^{\omega }

to

\{0,1\}

. It is enough to take one representative per equivalence class of relation

\approx

defined as follows:

w\approx v

if

w

and

v

differ at finite number of coordinates. Having such representatives, we can map all of them to 0; the rest of

f

values are deducted unambiguously.

The first sentence is fine- we have lots of parity functions f. The second sentence introduces $E=\{0,1\}^{\omega }$ without naming it. But it has a name, its the Cantor space. The second sentence then seems to be saying that one should construct the quotient set $E=\{0,1\}^{\omega }/\approx$ with this cofinite string idea. That's fine, too. Intuitively, it is saying that $x\approx y$ where if x,y are the binary expansions of real numbers x,y with $x-y=(2m+1)/2^{n}$ for some integers m,n. OK, so far. It would be a lot cleaner to just say that $\mathbb {D}$ is the set of dyadic rationals, aka the set of all finite-length binary strings. Then define $E=\{0,1\}^{\omega }/\mathbb {D}$ as the quotient space. This cleans up four things: first, it avoids having to blather too much about the equivalence relation. Second, it allows one to make statements about the quotient topology. Third, Since the set $\mathbb {D}$ is the set of all finite-length binary strings, it allows the construction of the quotient space to resemble that of the construction of open sets in the Baire space (set theory): specifically, by identifying all of the open sets in Baire space. Or perhaps, better yet, the same construction, but on the Cantor space. Fourth, it cleans up the relationship between $w$ and $v$ differ at finite number of coordinates (aka the cylinder set for binary strings) and the tree basis topology for the same (which only uses prefixes of finite-length binary strings).

Anyway, there are still $2^{\omega }$ such equivalence classes; the cardinality of E is the continuum. Each equivalence class $e\in E$ contains only a countable number of representatives (because m and n are countable). Next, for each $e\in E$ pick one representative $x\in e$ , and set $p(x)=0$ . OK, so far. For all of the other $y\in e$ , the value of $p(y)$ is unambiguous (because x and y differ in only finitely many places, and there are only countably many different y grand total.) And this can be done for any other equivalence class $a\in E$ . Yes, I can see how this is horribly non-constructive. To build E, I need to somehow pick uncountably many real numbers, and do so in such a way that no two of them differ by a dyadic fraction. Ouch. Anyway, I think that this is what the above paragraph was trying to telegraph. It took me a while to figure this out. That paragraph should be expanded into something less concise, and easier to understand. A reference would be nice, too.

Oh, duhh! The collection of equivalence classes is just the Vitali set, or rather, it's homeomorphic to it. The homeomorphism is provided by the Minkowski question mark function, which provides a one-to-one and onto mapping between dyadic rationals $\mathbb {D}$ and rationals $\mathbb {Q}$ . This too should be mentioned in the article. Anyway, this is all "original research" on my part, but it seems obvious in retrospect, and surely there is some publication that actually spells all of this out in detail. 67.198.37.16 (talk) 08:51, 27 November 2023 (UTC)[reply]