Mémoire de Maîtrise
DOI
https://doi.org/10.11606/D.45.2018.tde-04012018-162035
Document
Auteur
Nom complet
Luiz Gustavo de Moura dos Santos
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2017
Directeur
Jury
Birgin, Ernesto Julian Goldberg (Président)
Bueno, Luis Felipe Cesar da Rocha
Mascarenhas, Walter Figueiredo
Titre en portugais
Métodos de busca em coordenada
Mots-clés en portugais
Busca em coordenada
Busca em coordenada aleatória
Máquina de suporte vetorial
Otimização convexa
Pagerank
Resumé en portugais
Problemas reais em áreas como aprendizado de máquina têm chamado atenção pela enorme quantidade de variáveis (> 10^6) e volume de dados. Em problemas dessa escala o custo para se obter e trabalhar com informações de segunda ordem são proibitivos. Tais problemas apresentam caracterÃsticas que podem ser aproveitadas por métodos de busca em coordenada. Essa classe de métodos é caracterizada pela alteração de apenas uma ou poucas variáveis a cada iteração. A variante do método comumente descrita na literatura é a minimização cÃclica de variáveis. Porém, resultados recentes sugerem que variantes aleatórias do método possuem melhores garantias de convergência. Nessa variante, a cada iteração, a variável a ser alterada é sorteada com uma probabilidade preestabelecida não necessariamente uniforme. Neste trabalho estudamos algumas variações do método de busca em coordenada. São apresentados aspectos teóricos desses métodos, porém focamos nos aspectos práticos de implementação e na comparação experimental entre variações do método de busca em coordenada aplicados a diferentes problemas com aplicações reais.
Titre en anglais
Coordinate descent methods
Mots-clés en anglais
Convex optimization
Coordinate minimization
Pagerank
Random coordinate descent
Support vector machine
Resumé en anglais
Real world problemas in areas such as machine learning are known for the huge number of decision variables (> 10^6) and data volume. For such problems working with second order derivatives is prohibitive. These problems have properties that benefits the application of coordinate descent/minimization methods. These kind of methods are defined by the change of a single, or small number of, decision variable at each iteration. In the literature, the commonly found description of this type of method is based on the cyclic change of variables. Recent papers have shown that randomized versions of this method have better convergence properties. This version is based on the change of a single variable chosen randomly at each iteration, based on a fixed, but not necessarily uniform, distribution. In this work we present some theoretical aspects of such methods, but we focus on practical aspects.
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2018-02-19
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées
cliquant ici.