• 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
 
 
Mémoire de Maîtrise
DOI
10.11606/D.3.2014.tde-24042015-113950
Document
Auteur
Nom complet
Flávio Sales Truzzi
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2014
Directeur
Jury
Costa, Anna Helena Reali (Président)
Barros, Leliane Nunes de
Wainer, Jacques
Titre en portugais
Modelagem e soluções para redes de anúncios.
Mots-clés en portugais
Aprendizado por reforço
Inteligência artificial
Processos de decisão Markov
Redes de anúncios
Resumé en portugais
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.
Titre en anglais
Model and solutions for Ad Networks.
Mots-clés en anglais
Ad Networks
Artificial inteligence
Markov Decision Processes
Reinforcement learning
Resumé en anglais
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.
 
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.
dissertacao.pdf (1.54 Mbytes)
Date de Publication
2015-04-30
 
AVERTISSEMENT: Le matériau se réfère à des documents provenant de cette thèse ou mémoire. Le contenu de ces documents est la responsabilité de l'auteur de la thèse ou mémoire.
  • 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.
Tous droits de la thèse/dissertation appartiennent aux auteurs
Centro de Informática de São Carlos
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2021. Tous droits réservés.