Course Web Pages

TIM250, Spring 2013, Section 01: Home

Warning message

Week one action items

  • (1) Please Register for the class 
  • (2) Please register for IPinYou competition at (http://contest.ipinyou.com/); 
    • download and unpack the data; 
    • calculate the click thru rates and the conversion rates for each of the ad campaigns.
    • how many unique combinations of feature values: what is the upper bound; what is the actual number if you have time

TIM 250: Stochastic Optimization in Information Systems and Technology with a special focus on Digital Online Advertising

 

TIM 250 in brief

TIM 250

Stochastic Optimization in Information Systems and Technology with a special focus on Digital Online Advertising

Dates

April 2, 2013 – May, 2013

Time

Tuesdays 6:00 pm -9:30 pm

Location

Main UCSC campus JB156  and Silicon Valley Campus (SVC) SVC 303 

The Silicon Valley Campus is located at 2505 Augustine Drive, Santa Clara, CA. You may find a map and directions at http://www.ucsc-extension.edu/directions

Webpage

https://courses.soe.ucsc.edu/courses/tim250/Spring13/01

Instructors

Dr James G. Shanahan

Independent Consultant

541 Duncan Street, San Francisco CA 94131
James.Shanahan_AT_gmail.com

 

 

Office Hours

Dr. James G. Shanahan: (by appointment)

Please send email:  James.Shanahan_AT_gmail.com

                               with subject TIM 250 Spring 2013

Recorded Lectures

https://webcast.ucsc.edu/

Grading

Task

Value

Homework and class participation

30%

Exams: midterm (20%) and Final exam

40%

Projects: IPinYou Real-time bidding contest ($160,000 prize)

30%

 

Focus

Want to win $160,000 for your project work while learning? If yes, read on!

Focus: TIM250 will focus on getting students familiar with core principles in Stochastic Optimization, grounding these principles in both (1) examples taken primarily form online advertising (a $65 Billion industry) and in (2) example projects and code in R and Matlab. Each class will be composed of theory, practice and problems, thereby informing and inspiring students on how to apply theory to practice.

The course is being taught a technical leader in the field of online advertising with over 25 years of research and development experience at world renowned research labs such as Xerox, AT&T and Clairvoyance. In addition, the instructor has broader experiences in web search, online advertising, information retrieval, statistical data mining and machine learning.

You will learn some of the following skills:

  • Analyze intelligent support systems for marketing decisions as well as develop mathematical models for optimizing sales, marketing, and pricing decisions in high tech
  • Learn the core subjects of optimization theory: gradient descent; classical programming; nonlinear programming; and linear programming. See how they are used every day in machine learning and in online advertising.
  • Learn basics of dynamic programming and Markov decision processes(MDP), including value and policy iteration  for finite and infinite horizon situations. Look at applications setting policies for online adverting to optimize various business objectives
  • Students will get to work on a real-world problem (with real data) in the area of Online advertising, that of predicting real-time bids on behalf of advertisers. Dr. Shanahan is a judge for this competition, which is organized by IPinYou. The competition has a grand prize of $160,000 (and lots of prestige).
  • Study online learning, whose core focus is learning in an explore-exploit mode, in a one example at a time; this is key to understanding, analyzing, and stimulating research in the field of learning in a non-stationary environment such as serving digital ads online; study multi-arm bandit approach to ad serving.
  • Stochastic Recommenders: review classical approaches to collaborative filtering while also looking at recent developments in the field of stochastic recommenders with applications to ecommerce and online advertising
  • Game Theory: auction mechanism design. Time permitting, we will cover game theory and study its application to online advertising auctions. This is an area that has and continues to revolutionize the economic models of online advertising

The course emphasis will be tuned to the class composition and interest.

Prerequisites: Students are expected to be mathematically mature, and to have had prior exposure to undergraduate linear algebra at the level of  MATH21 or  AMS10  and probability/statistics at the level of AMS 131 or MPE 107.

Course Outline

Course Outline on a week-by-week basis (assuming a one 3 hour lecture per week).

 Week

Core Subject

Application Subject

Week 1

Online advertising, Ad networks, real-time bidding(RTB), IPinYou data science competition ($160,000 prize)

Perceptron learning; linear regression; in R/Matlab code

Week 2

Gradient Descent, Lines, Tangents, Taylor Series, Slopes/Gradients, Roots of an equation, Newton-Rhapson

Perceptron learning; linear regression; in R/Matlab code

Week 3

Classical Programming, Equality Constraints, Convexity, concavity, constraint optimization, Lagrange Multipliers

Media Planning in online advertising

Week 4

Nonlinear Programming, first/second order conditions, efficient frontier

Keyword portfolio management

Week 5

Kuhn Tucker Conditions, primal from, dual form

Support Vector Machines 

Week 6

Linear Programming, Standard form, augmented form, Simple algorithm, Interior point method, slack variables

Forecasting and ad display scheduling

Week 7

Dynamic Programming; Markov Decision Processes

Optimal frequency capping policy for ads

Week 8

Online/sequential Learning; Gittins index, Regret, pacing algorithms, proportional control

Multi-arm bandit approach to ad optimization

Week 9

Stochastic Recommenders

Predicting Click thru rates

Week 10

Project presentations: Students present their findings

IPinYou data science competition

Week 11

Exam

 

 

 

Instructor biography:

Dr. James G. Shanahan, Independent Consultant, San Francisco

Jimi has spent the last 25 years developing and researching cutting-edge information management systems that harness machine learning, information retrieval, and linguistics. During the summer of 2007, he started a boutique consultancy (Church and Duncan Group Inc., in San Francisco) whose major goal is to help companies leverage their vast repositories of data using statistics, machine learning, optimisation theory and data mining for big data applications (billions of examples) in areas such as web search, local and mobile search, and digital advertising and marketing. Church and Duncan Group’s clients include Adobe, AT&T, Akamai, W3i, Digg.com, eBay, SearchMe.com, Ancestry.com, TapJoy, and SkyGrid.com. Along with architecting and developing large scale distributed statistical optimization systems for his clients, Jimi also leads and hires engineers and scientists, and provides business insights and strategic guidance to sales, analytics and business development groups within these organizations. In addition, Jimi has been affiliated with the University of California at Santa Cruz since 2009 where he teaches a sequence of graduate courses on big data analytics, machine learning, and stochastic optimization (TIM 206, ISM 209, ISM 250 and ISM251). He advises several high-tech startups (e.g., Quixey.com, W3i, InferSystems) and is executive VP of science and technology at Irish Innovation Center (IIC). He has served as a fact and expert witness.

Prior to founding Church and Duncan Group Inc., Jimi was Chief Scientist and executive team member at Turn Inc. (an online ad network that has recently morphed to a demand side platform).  Prior to joining Turn, Jimi was Principal Research Scientist at Clairvoyance Corporation where he led the “Knowledge Discovery from Text” Group. In the late 1990s he was a Research Scientist at Xerox Research Center Europe (XRCE) where he co-founded Document Souls, an anticipatory information system, where documents were given personalities of information services that foraged the web to stay informed and informative. In the early 90s, he worked on the AI Team within the Mitsubishi Group in Tokyo.

He has published six books, over 50 research publications, and 15 patents  in the areas of machine learning and information processing. Jimi chaired CIKM 2008 (Napa Valley), co-chaired International Conference in Weblog and Social Media (ICWSM) 2011 in Barcelona, and was PC co-chair of ICWSM 2012 (Dublin). He co-chaired the ISSDM Workshop on Knowledge Management: Analytics and Big Data at UC Santa Cruz.  He has organized several workshops in digital advertising as part of SIGIR, NIPS and SIGKDD. He is regularly invited to give talks at international conferences and universities around the world. Jimi received his Ph.D. in engineering mathematics from the University of Bristol, U. K. and holds a Bachelor of Science degree from the University of Limerick, Ireland. He is a Marie Curie fellow and member of IEEE and ACM. In 2011 he was selected as a member of the Silicon Valley 50 (Top 50 Irish Americans in Technology).

 

Reading Materials

Core Subject matter (Chapters from these books will be made available online as needed):

  • Mathematical Optimization and Economic Theory, Michael Intriligator, SIAM 2002
  • Nonlinear Programming, Theory and Algorithms, Mokhtar S. Bazaraa and C.M. Shetty, Wiley 1979
  • Dynamic Programming and Optimal Control, Dimitri P. Bertsekas, Athena Scientific 2000
  • Reinforcement Learning, Sutton and Barto, MIT Press, 1998
  • Linear and nonlinear Programming, David Luenberg, Yinyu Ye, 3rd edition, Springer
  • Artificial Intelligence: A Modern Approach (Third edition) by Stuart Russell and Peter Norvig.

·         Pattern Recognition and Machine Learning - Christopher M. Bishop, Springer

 

Online Advertising

  • Nelson, Philip, 1974. Advertising as Information, Journal of Political Economy, University of Chicago Press, vol. 82(4), pages 729-54.
  • R. Baeza-Yates,  A. Broder, P. Raghavan, WWW 2007,  Tutorial, Foundations and Challenges of Web Advertising
  • Y. Kohda and S. Endo. Ubiquitous advertising on the www: merging advertisement on the browser. Comput. Netw. ISDN Syst., 28(7-11):1493–1499, 1996.
  • The Google adwords. Google content-targeted advertising. http://adwords.google.com/select/ct_faq.html
  • David Maxwell Chickering , David Heckerman, Targeted advertising on the Web with inventory management, Interfaces, v.33 n.5, p.71-77, September 2003
  • Atsuyoshi Nakamura, Improvements in practical aspects of optimally scheduling web advertising, Proceedings of the eleventh international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA.
  •  Ribeiro-Neto, B., Cristo, M., Golgher, P. B., and Silva de Moura, E. 2005. Impedance coupling in content-targeted advertising. In Proceedings of the 28th Annual international ACM SIGIR Conference on Research and Development in information Retrieval (Salvador, Brazil, August 15 - 19, 2005). SIGIR '05, 496-503.
  •  Edelman, B., Ostrovsky, M., Schwarz, M. Internet advertising and the generalized second price auction: selling billions of dollars worth of keywords. NBER Working Paper No. W11765, 2005
  •  Broder, A., Ciaramita, M., Fontoura, M., Gabrilovich, E., Josifovski, V., Metzler, D., Murdock, V., and Plachouras, V. 2008. To swing or not to swing: learning when (not) to advertise. In Proceeding of the 17th ACM Conference on information and Knowledge Mining (Napa Valley, California, USA, October 26 - 30, 2008). CIKM '08. ACM, New York, NY, 1003-1012
  • Translating Relevance Scores to Probabilities for Contextual Advertising Deepak Agarwal; Evgeniy Gabrilovich; Rob Hall; Vanja Josifovski; Rajiv Khanna, The 18th ACM Conference on Information and Knowledge Management (CIKM), 2009
  • Explore/Exploit Schemes for Web Content Optimization (best paper award) Deepak Agarwal; Bee-Chung Chen; Pradheep Elango, IEEE International Conference on Data Mining, 2009 [view abstract]
  • Regression based Latent Factor Models Deepak Agarwal; Bee-Chung Chen, ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2009 [view abstract]
  •  Spatio-Temporal Models for Estimating Click-through Rate Deepak Agarwal; Bee-Chung Chen; Pradheep Elango, The 18th International World Wide Web Conference, 2009 [view abstract]
  •  Contextual Advertising by Combining Relevance with Click Feedback Deepayan Chakrabarti; Deepak Agarwal; Vanja Josifovski, WWW, 2008
  • Online Models for Content Optimization Deepak Agarwal; Bee-Chung Chen; Pradheep Elango; Raghu Ramakrishnan; Nitin Motgi; Scott Roy; Joe Zachariah, NIPS, 2008
  •  Statistical Challenges in Online Advertising Deepak Agarwal; Deepayan Chakrabarti, CIKM 2008, 2008
  • James G. Shanahan, Web Advertising: Business Models, Technologies and Issues in Information Retrieval, World Wide Web Conference, Lyon,  2012
  • James G. Shanahan, Web Advertising: Business Models, Technologies and Issues in Information Retrieval, Edited by Massimo Melucci and  Ricardo Baeza-Yates,  2010
  • Shanahan, J., G. and Van den Poel, D.: Determining optimal advertisement frequency capping policy via Markov Decision Processes to maximize click through rates. NIPS 2010 Workshop on Machine Learning for Online Advertising. (2010).
  • Pandey, S., Agarwal, D., Chakrabarti, D., Josifovski, V.: Bandits for taxonomies: A modelbased approach. In In Proc. of the SIAM International Conference on Data Mining. SDM (2007).
  • Agarwal, D., Chen, B., Elango, P.: Explore/Exploit Schemes for Web Content Optimization. ICDM. pp. 1-10 (2009).
  • Online advertising competition: real-time bidding(RTB) prediction (Starts April 1, 2013), IPinYou data science competition ($160,000 prize), http://contest.ipinyou.com/index.html

 

Instructors and Assistants