Coarse-refinement dilemma: on generalization bounds for data clustering (2020)
- Authors:
- Autor USP: VAZ, YULE - ICMC
- Unidade: ICMC
- Sigla do Departamento: SCC
- Subjects: APRENDIZADO COMPUTACIONAL; ESPAÇOS MÉTRICOS; ESPAÇOS TOPOLÓGICOS; ESTABILIDADE; HOMOLOGIA
- Keywords: Agrupamento de dados; Agrupamento hierarquico; Algorithmic stability; Data clustering; Estabilidade algorítmica; Hierarchical clustering; Homologia persistente; Mudança de conceito topológico; Persistent homology; Topological concept drift
- Language: Inglês
- Abstract: O Aprendizado de Máquina é tipicamente organizado em dois principais paradigmas: (i) o Aprendizado de Máquina Supervisionado (do inglês Supervised Machine Learning SML) que identifica padrões de dados pré-rotulados, empregando uma função de perda para adaptar o modelo estatístico correspondente; e, (ii) o Aprendizado de Máquina Não-supervisionado (do inglês Unsupervised Machine Learning UML) que organiza dados não rotulados por meio de relações de similaridade. O SML é suportado por arcabouços teóricos bem consolidados tais como a Teoria do Aprendizado Estatístico e a Estabilidade Algorítmica as quais definem suas principais suposições, propriedades e garantias de convergência, permitindo a comparação de diferentes métodos de SML e, consequentemente, seus aperfeiçoamentos. Complementarmente, UML conta com investigações sobre Agrupamento de Dados (do inglês Data Clustering DC) e Agrupamento Hierárquico de Dados (do inglês Hierarchical Clustering HC) definindo propriedades e caracterizando DC e HC de maneira mais adequada. Especificamente, Kleinberg estabeleceu riqueza, invariância à escala e consistência de partição como propriedades necessárias para a definição do problema de DC, provando a impossibilidade de satisfazê-las simultaneamente. Ackerman, Ben-David e Loker exploraram outras propriedades tais como a localidade, e Carlsson e Mémoli relataram resultados sobre a estabilidade e consistência para HC baseando-se na distância entre espaços métricos. A fim decomplementar tais trabalhos, considera-se nesta tese de doutorado espaços topológicos para desenvolver um arcabouço teórico mais geral dado que: (i) a invariância de espaços topológicos, isomorfismos de grupos homológicos mais precisamente, garante as propriedades de invariância à escala, consistência de partição e localidade; e (ii) essa mesma invariância é herdada ao longo de espaços menos gerais, tal como o métrico, permitindo uma representação mais abstrata de agrupamento. Nesse contexto, foi demonstrado que topologias sobre-refinadas adotadas por modelos de DC e HC levam à não-consistência dos grupos homológicos associados. Por outro lado, topologias muito grosseiras levam à consistência, porém produzem grupos homológicos sem representatividade; nomeamos tal dilema como Coarse-Refinement Dilemma (CRD). Os problemas de DC e HC foram então formulados empregando a homologia persistente bidimensional de Carlsson e Zomorodian, sendo a primeira dimensão correspondente às hierarquias do HC e a segunda às inclusões de novos dados, o que permitiu o estudo probabilístico por meio de processos de martingales e subsequente formalização de um limite de generalização para DC e HC. Por meio desse resultado, complementamos os trabalhos relacionados: (i) definindo limitantes inferiores e superiores para a consistência métrica de Carlsson e Mémoli; (ii) mostrando que o axioma da riqueza de Kleinberg deve ser relaxado, caso contrário agrupamentos sobre-refinados e sobre-grosseiros serãoobtidos; e, finalmente, (iii) definindo mudanças inesperadas em topologias consistentes como Mudanças Topológicas de Conceito (do inglês Topological Concept Drifts TCD). Um extenso conjunto de experimentos foi executado para analisar o CRD e o TCD, incluindo um breve estudo de um cenário real envolvendo documentos textuais. Resultados corroboraram com a empregabilidade de espaços topológicos para a representação de problemas de DC e HC, sendo possível detectar mudanças topológicas e a existência do CRD.
- Imprenta:
- Publisher place: São Carlos
- Date published: 2020
- Data da defesa: 01.10.2020
-
ABNT
VAZ, Yule. Coarse-refinement dilemma: on generalization bounds for data clustering. 2020. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2020. Disponível em: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-18112020-130229/. Acesso em: 03 dez. 2025. -
APA
Vaz, Y. (2020). Coarse-refinement dilemma: on generalization bounds for data clustering (Tese (Doutorado). Universidade de São Paulo, São Carlos. Recuperado de https://www.teses.usp.br/teses/disponiveis/55/55134/tde-18112020-130229/ -
NLM
Vaz Y. Coarse-refinement dilemma: on generalization bounds for data clustering [Internet]. 2020 ;[citado 2025 dez. 03 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-18112020-130229/ -
Vancouver
Vaz Y. Coarse-refinement dilemma: on generalization bounds for data clustering [Internet]. 2020 ;[citado 2025 dez. 03 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-18112020-130229/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
