Lemma 20.4: on {±1}^k, ∧ᵢxᵢ = sign(1 − k + ∑ᵢxᵢ) and ∨ᵢxᵢ = sign(k − 1 + ∑ᵢxᵢ)
ProvedUnderstandingML.sign_and_orboolean-circuitshalfspacesneural-networks
Lemma 20.4. Suppose that a neuron , that implements the sign activation function, has incoming edges, connecting it to neurons whose outputs are in . Then, by adding one more edge, linking a "constant" neuron to , and by adjusting the weights on the edges to , the output of can implement the conjunction or the disjunction of its inputs.
Formally (the proof's formulas): for , iff all , and iff some .
Preamble
import Definitions.Def_UnderstandingML_NeuralNetworks open MeasureTheory
Formal statement
namespace UnderstandingML
/-- **Lemma 20.4** (p. 273). Suppose that a neuron `v`, that implements the sign activation
function, has `k` incoming edges, connecting it to neurons whose outputs are in `{±1}`. Then,
by adding one more edge, linking a "constant" neuron to `v`, and by adjusting the weights on
the edges to `v`, the output of `v` can implement the conjunction or the disjunction of its
inputs: `∧ᵢ xᵢ = sign(1 − k + ∑ᵢ xᵢ)` and `∨ᵢ xᵢ = sign(k − 1 + ∑ᵢ xᵢ)`. -/
theorem sign_and_or (k : ℕ) (x : Fin k → Bool) :
(0 < 1 - (k : ℝ) + ∑ i, (if x i then (1 : ℝ) else -1) ↔ ∀ i, x i = true) ∧
(0 < (k : ℝ) - 1 + ∑ i, (if x i then (1 : ℝ) else -1) ↔ ∃ i, x i = true) := by sorry
end UnderstandingML
Source
Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press 2014, doi:10.1017/CBO9781107298019, §20.3 p. 273, Lemma 20.4 with its proof
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.