Retângulos paralelos do eixo de aprendizado PAC

Eu estou tentando entender a prova de que os retângulos paralelos do eixo podem ser aprendidos no caso realizável. Isso significa que, dado com dados suficientes, podemos encontrar uma função tal que \ mathbb {P} \ left [\ text {error}> \ epsilon \ right] \ leq \ delta Aqui, o erro pode ser visto como o probabilidade de cometer um erro com a função escolhida h .$\epsilon, \delta$$h$

Agora, para retângulos paralelos ao eixo (na classificação binária), o argumento usual é o seguinte: seja $R$ o retângulo verdadeiro e $R'$ seja o menor retângulo que contém os exemplos positivos, claramente $R' \subseteq R$ , consideramos as quatro faixas retangulares entre $R'$ e $R$ . Claramente, se todos eles têm probabilidade $\leq \epsilon/4$ , a probabilidade de cometer um erro é menor que $\epsilon$ , portanto, podemos assumir que pelo menos um tenha probabilidade de cometer um erro $\geq \epsilon/4$ .

Para uma faixa desse tipo, a probabilidade de classificar corretamente todos os $m$ exemplos de treinamento é no máximo $(1 - \epsilon/4)^m$ , e, assim, vincular uma união a todas as faixas, obtemos que a probabilidade de classificar tudo corretamente é menor que $4(1-\epsilon/4)^m \leq 4e^{-m/4}$ e, com um pouco de álgebra, resulta que a complexidade da amostra é $m \geq (4/\epsilon)\ln(4/\delta)$ .

Aqui está um pdf que explica um pouco mais detalhadamente, com algumas fotos, eu apenas tive que condensar o argumento o máximo possível para encaixá-lo aqui.

Minha pergunta é: por que temos que considerar as quatro faixas retangulares separadamente, por que não podemos simplesmente dizer que a probabilidade da região entre $R'$ e $R$ deve ser maior que $\epsilon$ (porque, caso contrário, terminamos), e assim, usando o mesmo argumento, chegaríamos ao melhor limite $m \geq (1/\epsilon)\ln(1/\delta)$ ?

Desculpe pela longa pergunta e agradeço antecipadamente.

A pergunta é um pouco vaga, mas parece que o que você quer argumentar é o seguinte: Seja o conceito de aprender e considere qualquer retângulo que cubra um -fraction de . Então, com alguma probabilidade, conterá .$R$$R^*\subset R$$(1-\epsilon)$$R$$R'$$R^*$

O problema disso é que a probabilidade específica depende da escolha específica de . Acho que o que você está confuso é que deseja que o um bom desempenho em exemplos invisíveis . Por construção, classificará corretamente todos os dados de treinamento. O evento ruim é, na verdade, que todos os dados de treinamento estão concentrados em um retângulo muito pequeno; isso acontece com probabilidade, no máximo, no caso de uma das tiras não ser observada em todos os exemplos de treinamento.$R^*$$R'$$R'$

hmm ... bem, na prova que você mencionou, extraímos pontos (x, y) de alguma distribuição D e verificamos se realmente caem em um quadrado. Ou seja, escolhemos o mesmo para cada limite (max x, min x, max y, min y). Agora, se você tinha um círculo, não pode simplesmente fazer isso - você precisa escolher um delta para um raio, e o raio é uma função das coordenadas. Isso tornará a prova mais complicada.$\delta$

Se você optar por polígonos não côncavos - deve ficar muito mais difícil.