• 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
 
 
Disertación de Maestría
DOI
10.11606/D.3.2014.tde-24042015-113950
Documento
Autor
Nombre completo
Flávio Sales Truzzi
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2014
Director
Tribunal
Costa, Anna Helena Reali (Presidente)
Barros, Leliane Nunes de
Wainer, Jacques
Título en portugués
Modelagem e soluções para redes de anúncios.
Palabras clave en portugués
Aprendizado por reforço
Inteligência artificial
Processos de decisão Markov
Redes de anúncios
Resumen en 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 en inglés
Model and solutions for Ad Networks.
Palabras clave en inglés
Ad Networks
Artificial inteligence
Markov Decision Processes
Reinforcement learning
Resumen en 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.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
dissertacao.pdf (1.54 Mbytes)
Fecha de Publicación
2015-04-30
 
ADVERTENCIA: El material descrito abajo se refiere a los trabajos derivados de esta tesis o disertación. El contenido de estos documentos es responsabilidad del autor de la tesis o disertación.
  • 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 los derechos de la tesis/disertación pertenecen a los autores
Centro de Informática de São Carlos
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2021. Todos los derechos reservados.