• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
10.11606/D.3.2014.tde-24042015-113950
Documento
Autor
Nome completo
Flávio Sales Truzzi
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2014
Orientador
Banca examinadora
Costa, Anna Helena Reali (Presidente)
Barros, Leliane Nunes de
Wainer, Jacques
Título em português
Modelagem e soluções para redes de anúncios.
Palavras-chave em português
Aprendizado por reforço
Inteligência artificial
Processos de decisão Markov
Redes de anúncios
Resumo em português
Redes de Anúncios (Ad Networks) são redes que promovem a distribuição de anúncios pela internet, de forma a maximizar o lucro total gerado pela exibição dos anúncios nos websites. Estas redes tipicamente operam através do modelo de negócios chamado CPC (Custo por Clique), em que o anunciante paga um determinado valor somente se algum usuário clicar em seu anúncio. A escolha de como o intermediador planeja a distribuição dos anúncios aos websites é de extrema importância, já que a taxa de cliques nos anúncios é extremamente baixa. Atualmente a alocação dos anúncios tem sido feita através de uma solução aproximada baseada na alocação ótima definida com dados de um período anterior, a qual é calculada através de programação linear aliada à utilização de heurísticas. Entretanto, este sistema claramente é um processo de decisão sequencial em que diversas restrições são aplicáveis, como por exemplo: o orçamento dos anunciantes, limites mínimos do número de exibições de cada anúncio, categorias dos anúncios, entre outras. Neste trabalho argumenta-se que MDPs (Markov Decision Processes) fornecem uma melhor modelagem para o problema, já que conseguem levar em conta a dinâmica do sistema, considerando, por exemplo, que um anúncio que tem poucas chances de ser clicado consiga ser alocado de forma eficiente em relação ao retorno de longo prazo, mesmo quando outros anúncios proveriam um lucro maior a curto prazo. No entanto, devido ao grande número de estados, utilizar uma solução ótima através de MDPs é impraticável. Portanto analisa-se o desempenho relativo entre o estado da arte e a modelagem ótima, obtendo garantias de que a solução aproximada baseada em programação linear não está longe da solução ótima, e que em problemas grandes (similares aos encontrados na prática) essa diferença pode ser ignorada. Por fim, propõe-se uma modelagem baseada em aprendizado por reforço para a solução deste problema, utilizando duas abordagens, uma desconsiderando informações de contexto e outra considerando informações de contexto. Aqui argumenta-se que o uso de aprendizado por reforço é mais apropriado para a solução do problema de alocação de anúncios, já que ele é capaz de adaptar sua política de alocação em função das mudanças que ocorrem como, por exemplo, no perfil do usuário.
Título em inglês
Model and solutions for Ad Networks.
Palavras-chave em inglês
Ad Networks
Artificial inteligence
Markov Decision Processes
Reinforcement learning
Resumo em inglês
Ad Networks promote the distribution of ads in the internet, so as to maximize the revenue generated by their display of ads in websites. These networks typically operate using the CPC (Cost per Click) business model, where the advertiser pays a monetary value when a user clicks in its advertisement. The choice of how the Ad Network distributes ads to websites is of utmost importance, since the rate of clicks on ads is extremely low. The allocation of ads has been done by an approximate solution based on data from an early period of time, which is calculated using linear programming combined with heuristics. However, this problem is clearly a sequential decision process in which multiple sequential restrictions apply, such as: the budget of the advertisers, minimum limits on the number of views for each campaign, categories of advertisements. In this dissertation we argue that MDPs (Markov Decision Processes) provide a better model for the problem, since they can automatically take into account the dynamics of the system, considering, for example, an ad with little chance of being clicked can be allocated in an efficient way, even when other ads would provide a higher profit in the short term. However, due to the large number of states, an optimal solution through MDPs is impractical; therefore we analyze here the relative performance between the linear programming and the MDP approaches, deriving guarantees that the approximate solution based on linear programming is not far from the MDP optimal solution, and in large problems (similar to those found in practice) this difference can be disregarded. Finally, we propose a model based on reinforcement learning using two different approaches, one disregarding the contextual information, and the other using contextual information. We argue that the use of reinforcement learning is more suitable for solving the problem of allocation of ads, since it is able to adapt its allocation policy to reflect changes that occur, e.g., in the user profile.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
dissertacao.pdf (1.54 Mbytes)
Data de Publicação
2015-04-30
 
AVISO: O material descrito abaixo refere-se a trabalhos decorrentes desta tese ou dissertação. O conteúdo desses trabalhos é de inteira responsabilidade do autor da tese ou dissertação.
  • TRUZZI, F. S., et al. Markov Decision Processes for Ad Network Optimization. In IX Encontro Nacional de Inteligência Artificial (ENIA 2012), Curitiba, 2012. IX Encontro Nacional de Inteligência Artificial, Brazilian Conference on Intelligent Systems.Porto Alegre : SBC, 2012.
  • TRUZZI, F. S., et al. Robust image segmentation applied to bee s fore wings. In X Encontro sobre Abelhas, Ribeirão Preto, 2012. Anais do X Encontro sobre Abelhas., 2012. Abstract.
  • TRUZZI, F. S., WERNECK, N. L., e COSTA, Anna Helena Reali. Rastreamento de pessoas em sequências de imagens capturadas por uma câmera estática. In VI Workshop de Visão Computacional, Presidente Prudente, 2010. Anais do VI WVC.Presidente Prudente : FCT Unesp, 2010. Dispon?vel em: http://iris.sel.eesc.usp.br/wvc/anais_WVC2010.
  • WERNECK, N. L., TRUZZI, F. S., e COSTA, Anna Helena Reali. Medição de distância e altura de bordas horizontais com visão monocular linear para robôs móveis. In WVC'2009 - V Workshop de Visão Computacional, São Paulo, 2009. Anais do V Workshop de Visão Computacional.São Paulo : Universidade Presbiteriana Mackenzie, 2009.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2018. Todos os direitos reservados.