On Linear Separability of the MNIST Handwritten Digits Dataset

Este artigo oferece uma investigação empírica abrangente para resolver a questão não resolvida sobre a separabilidade linear do conjunto de dados MNIST, analisando sistematicamente tanto a separação par a par quanto a de um contra todos em diferentes subconjuntos de treinamento e teste.

O essencial

Imagine que você tem uma caixa gigante cheia de desenhos de números feitos à mão (de 0 a 9). Esse é o famoso conjunto de dados MNIST, usado há décadas para ensinar computadores a "ler" números.

A pergunta que este artigo tenta responder é simples, mas profunda: Será que é possível desenhar uma única linha reta no espaço para separar perfeitamente dois desses números?

Para entender isso, vamos usar algumas analogias do dia a dia:

1. O Problema da "Linha Divisória" (Separabilidade Linear)

Imagine que você tem dois grupos de pessoas em uma sala: os que gostam de Pizza e os que gostam de Sushi.

• Separável: Se você conseguir colocar uma fita no chão e todos os fãs de Pizza ficarem de um lado e todos os fãs de Sushi do outro, sem ninguém cruzar a linha, o grupo é "linearmente separável".
• Não Separável: Se houver alguém que ama Pizza e Sushi ao mesmo tempo, ou se os fãs de Sushi estiverem espalhados em volta dos fãs de Pizza como um anel, nenhuma linha reta conseguirá separá-los perfeitamente. Você precisaria de uma linha curva ou de várias linhas.

O artigo investiga se os desenhos dos números no MNIST se comportam como os fãs de Pizza e Sushi (separáveis) ou como um caos misturado (não separáveis).

2. As Duas Formas de Testar

Os autores testaram de duas maneiras diferentes:

• Cenário A: Duelo de Um contra Um (Par a Par)
  Imagine uma briga de galo entre o número 2 e o número 3. Será que conseguimos traçar uma linha que separe todos os 2s dos todos os 3s?

  • O que descobriram: Em alguns duelos, sim! Por exemplo, separar o 0 do 1 é fácil (como separar um círculo de um traço). Mas separar o 2 do 3 é muito difícil, porque eles se parecem muito. O artigo descobriu que, no conjunto de treinamento (os dados que o computador estuda), alguns pares não conseguem ser separados por uma linha reta, mas outros conseguem.

• Cenário B: Um contra Todos (Um vs. Resto)
  Agora, imagine tentar separar apenas os 0s de todos os outros números juntos (1, 2, 3... 9).

  • O que descobriram: Isso é como tentar separar os fãs de Pizza de todos os outros sabores de comida do mundo. O resultado foi claro: Não é possível. Os 0s estão "escondidos" entre os outros números de formas que uma única linha reta não consegue capturar. O mesmo vale para o 1, o 6 e todos os outros.

3. A Surpresa: Treino vs. Teste

O artigo faz uma distinção importante entre o "Livro de Exercícios" (Treino) e a "Prova Final" (Teste):

• O Livro de Exercícios (Treino): Contém 60.000 desenhos. Aqui, a mistura é tão complexa que, se você tentar separar um número de todos os outros, falha. Não existe uma linha mágica que funcione para todos os casos.
• A Prova Final (Teste): Contém 10.000 desenhos que o computador nunca viu antes. Curiosamente, quando olhamos apenas para esses desenhos, todos os pares de números conseguem ser separados por uma linha reta.
  • Por que isso acontece? É como se, por sorte, na "prova final" não houvesse nenhum desenho de "2" que se parecesse tanto com um "3" a ponto de confundir a linha divisória. Mas isso é apenas uma coincidência estatística devido ao tamanho menor da amostra, não uma regra geral.

4. Como eles descobriram isso? (A Ferramenta Mágica)

Antes, as pessoas tentavam adivinhar ou usar métodos que podiam falhar. Os autores usaram uma ferramenta matemática chamada CVXPY.
Pense nela como um detetive super-rápido. Em vez de tentar desenhar a linha à mão, o detetive resolve um quebra-cabeça matemático: "Existe alguma linha que funcione?"

• Se o detetive diz "Sim", ele desenha a linha.
• Se o detetive diz "Não" (Inviável), então é matematicamente impossível separar aqueles dados com uma linha reta.

Conclusão Simples

O artigo derruba mitos antigos:

1. Dizer que "o MNIST é separável" é falso se você olhar para o conjunto completo de dados e tentar separar um número de todos os outros.
2. Dizer que "o MNIST não é separável" é parcialmente falso, porque, em duelos específicos (par a par) e no conjunto de teste, a separação é possível.

A lição final: O mundo real (e os desenhos de números) é complexo. Às vezes, uma linha reta resolve o problema, mas na maioria das vezes, especialmente quando misturamos tudo, precisamos de ferramentas mais inteligentes (como redes neurais profundas, que podem desenhar linhas curvas e complexas) para entender os dados corretamente. O MNIST não é "fácil" como parece; ele esconde misturas que uma linha reta simples não consegue resolver.

Resumo técnico

Título: Sobre a Separabilidade Linear do Conjunto de Dados de Dígitos Manuscritos MNIST

Autor: Ákos Hajnal (SZTAKI / Óbuda University)
Data: Novembro de 2025

---

1. O Problema

O conjunto de dados MNIST, criado nos anos 90, é o benchmark fundamental para avaliação de modelos de reconhecimento de padrões e classificação de imagens. Embora sua simplicidade relativa (70.000 imagens em escala de cinza de 28x28 pixels) seja amplamente reconhecida, a questão de saber se o conjunto de dados é linearmente separável nunca foi totalmente resolvida de forma empírica e abrangente.

Existem alegações conflitantes na literatura científica e informal: algumas fontes afirmam que o MNIST é linearmente separável, enquanto outras (muitas vezes citando mal a literatura original) afirmam o contrário. O artigo visa esclarecer essa ambiguidade, distinguindo entre dois cenários de separação:

1. Par a Par (Pairwise): Separar um dígito específico de outro dígito específico (ex: 0 vs 1).
2. Um-contra-Todos (One-vs-Rest): Separar um dígito específico de todos os outros nove dígitos combinados.

O estudo analisa o conjunto de treinamento, o conjunto de teste e a combinação de ambos.

2. Metodologia

O autor utilizou uma abordagem baseada em Otimização Convexa para determinar a existência de um hiperplano separador, evitando métodos aproximados que não garantem a prova de não separabilidade.

• Formulação do Problema: O problema foi formulado como um Programa Linear (LP) de viabilidade. O objetivo é minimizar uma constante (0) sujeita às restrições de que um hiperplano $w^T x + b$ deve separar as classes com uma margem de pelo menos 1 (ou seja, $y_i(w^T x_i + b) \ge 1$).
  • Se o solucionador encontrar uma solução viável (Status: OPTIMAL), o conjunto é linearmente separável.
  • Se o solucionador determinar que não há solução (Status: INFEASIBLE), o conjunto não é linearmente separável.
• Ferramentas:
  • CVXPY (versão 1.6.7): Biblioteca Python de otimização convexa.
  • Solucionador CLARABEL: Selecionado automaticamente pelo CVXPY para resolver os problemas de viabilidade.
  • Ambiente: Google Colaboratory com GPU T4 e CPU Intel Xeon.
• Escopo dos Experimentos:
  • Testes de separabilidade par a par (45 combinações possíveis entre os 10 dígitos).
  • Testes de separabilidade um-contra-todos (10 dígitos).
  • Execução em três conjuntos de dados distintos: Treinamento (60k amostras), Teste (10k amostras) e Combinado (70k amostras).

3. Principais Resultados

A. Separabilidade Par a Par (Pairwise)

• Conjunto de Treinamento:
  • Não Separável: 7 pares de dígitos foram encontrados como não linearmente separáveis: (2-3), (2-8), (3-5), (3-8), (4-9), (5-8) e (7-9).
  • Separável: Os dígitos 0, 1 e 6 provaram ser linearmente separáveis de todos os outros dígitos individualmente.
  • O dígito 8 foi identificado como o mais problemático, entrando em conflito com três outros dígitos (2, 3 e 5).
• Conjunto Combinado (Treino + Teste):
  • Os resultados foram idênticos aos do conjunto de treinamento. A adição dos dados de teste não alterou a separabilidade dos pares, indicando que, se um hiperplano existe para o treino, ele também separa perfeitamente o teste (nesse contexto específico).
• Conjunto de Teste:
  • Todos os pares foram encontrados como linearmente separáveis. Isso é atribuído ao tamanho menor da amostra (10.000 imagens), que reduz a probabilidade de sobreposição de classes complexas em comparação ao conjunto de treino.

B. Separabilidade Um-contra-Todos (One-vs-Rest)

• Conjunto de Treinamento e Combinado:
  • Nenhum dos 10 dígitos pôde ser linearmente separado de todos os outros dígitos simultaneamente. Todos os casos resultaram em INFEASIBLE (não separável).
  • Isso confirma que, no cenário realista de classificação multiclasse (onde o modelo deve distinguir um dígito de todos os outros), o MNIST não é linearmente separável.
• Conjunto de Teste:
  • Alguns dígitos (0, 1, 2, 3, 4, 6, 7) pareceram separáveis, mas o autor ressalta que, devido ao pequeno tamanho da amostra e aos resultados do conjunto de treinamento, esses achados não são conclusivos para a generalidade do problema.

C. Desempenho Computacional

• O uso do CVXPY demonstrou alta eficiência.
• Os tempos de execução variaram de segundos para pares (ex: 12s para pares separáveis no treino, ~24s para não separáveis) a cerca de 2 minutos para testes um-contra-todos no conjunto de treinamento (209s no pior caso).
• Houve uma aceleração de 4x a 8x em comparação com métodos anteriores citados na literatura (como o de Zhong et al.).

4. Contribuições Chave

1. Resolução de uma Questão Aberta: O artigo fornece a primeira análise empírica abrangente e definitiva sobre a separabilidade linear do MNIST, desmistificando alegações contraditórias.
2. Distinção de Cenários: Demonstra que a resposta à pergunta "O MNIST é linearmente separável?" depende inteiramente do contexto:
   • Sim (parcialmente): Para pares específicos no conjunto de teste e para os dígitos 0, 1 e 6 contra qualquer outro dígito individual no treino.
   • Não: Para a tarefa de classificação multiclasse real (um-contra-todos) no conjunto de treinamento e combinado.
3. Validação de Métricas: Confirma empiricamente que dígitos visualmente complexos ou semelhantes (como 2, 3, 5, 8, 9) geram sobreposições no espaço de características que impedem a separação linear perfeita.
4. Reprodutibilidade: Disponibiliza o código fonte em um repositório GitHub e detalha o ambiente experimental para futuras comparações.

5. Significado e Conclusão

O estudo conclui que alegações simplistas como "o MNIST é linearmente separável" ou "o MNIST não é linearmente separável" são imprecisas. A realidade é matizada:

• O conjunto de dados não é linearmente separável na configuração de classificação multiclasse (um-contra-todos) no conjunto de treinamento, o que justifica a necessidade de modelos não lineares (como Redes Neurais Convolucionais) para atingir a precisão máxima (>99%).
• No entanto, a separabilidade linear existe para subconjuntos específicos (pares de dígitos ou dígitos isolados vs. um único outro dígito), o que pode ser útil para entender a topologia dos dados e a dificuldade relativa de distinguir certos dígitos.

Este trabalho serve como uma referência técnica sólida para pesquisadores que estudam as propriedades geométricas de conjuntos de dados de aprendizado de máquina e estabelece uma linha de base de desempenho para testes de viabilidade linear.