Առաջադրություն 4

Թող \(X\)-ը լինի վերջավոր բազմություն՝ որոշ վերջավոր չափով \(k\)։ Թող \(A\)-ն լինի սովորող (learner), որը նմուշի վրա \(S=((x_1, y_1), \ldots, (x_m, y_m)) \in (X \times \{0,1\})^m\) արտաբերում է մի ֆունկցիա \(A(S)\) այնպես, որ՝

Եթե \(x=x_i\) որոշ \(i \in \{1, \ldots, m\}\)-ի համար, ապա \(A(S)(x)= y_i\),

Եթե \(x \notin \{x_1, \ldots, x_m\}\), ապա \(A(S)(x)\)-ը ընտրվում է պատահականորեն հավանականություն \(1/2\)-ով յուրաքանչյուր պիտակի համար \(\{0,1\}\)-ում։

Տրված լինի \(f: X \to \{0,1\}\) ֆունկցիան, սահմանեք հավանականության բաշխում \((U,f)\) բազմության վրա \(X \times \{0,1\}\)՝ վերագրելով հավանականություն \(1/k\) ցանկացած զույգի \((x, f(x))\) և հավանականություն 0 ցանկացած \((x,y)\)-ի, որը չի պատկանում \(\{(x, f(x)): x \in X\}\)-ին։

Ցույց տվեք, որ յուրաքանչյուր \(f: X \to \{0,1\}\) և \(S=((x_1, f(x_1)), \ldots, (x_m, f(x_m)))\)-ի համար

\[L_{(U,f)}(A(S)) -L_S(A(S)) \geq \frac{(k-m)}{2k}.\]

[Ընդամենը 7 միավոր]