Optimizing User Behavior in Viral Marketing Using Stochastic Control
Explore the world of viral marketing and user behavior optimization through stochastic optimal control in the realm of human-centered machine learning. Discover strategies to maximize user activity in social networks by steering behaviors and understanding endogenous and exogenous events. Dive into multidimensional Hawkes processes, steering endogenous actions, and solving optimization problems using Bellman's principle of optimality. Unravel the dynamics of jump SDEs and delve into the Hamilton-Jacobi-Bellman equation for optimal cost-to-go.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Viral marketing with Stochastic optimal control of TPP HUMAN-CENTERED MACHINE LEARNING http://courses.mpi-sws.org/hcml-ws18/
Maximizing activity in a social network Can we steer users behavior to maximize activity in a social network? 2
Endogenous and exogeneous events Exogenous activity Users actions due to drives external to the network Endogenous activity Users responses to other users actions in the network 3
Multidimensional Hawkes process For each user u, actions as a counting process Nu(t) Nu(t) Intensities or rates (Actions per time unit) Non-negative kernel (memory) User influence matrix Exogenous actions Endogenous actions 4
Steering endogenous actions Organic actions + Directly incentivized actions Directly incentivized actions Intensities of directly incentivized actions 5 [Zarezade et al., 2018]
Cost to go & Bellmans principle of optimality Loss Optimization problem Dynamics defined by Jump SDEs To solve the problem, we first define the corresponding optimal cost-to-go: 6 The cost-to-go, evaluated at t0, recovers the optimization problem! [Zarezade et al., 2018]
Cost to go & Bellmans principle of optimality Loss Optimization problem This is a stochastic optimal control problem for jump SDEs (we know how to solve this!) Dynamics defined by Jump SDEs To solve the problem, we first define the corresponding optimal cost-to-go: 7 The cost-to-go, evaluated at t0, recovers the optimization problem! [Zarezade et al., 2018]
Hamilton-Jacobi-Bellman (HJB) equation Lemma. The optimal cost-to-go satisfies Bellman s Principle of Optimality Partial differential equation in J (with respect to and t) [Zarezade et al., 2018] Hamilton-Jacobi-Bellman (HJB) equation 8
Solving the HJB equation Consider a quadratic loss Rewards organic actions Penalizes directly incentivizes actions We propose and then show that the optimal intensity is: Solution to a matrix Riccati differential equation Computed offline once! Closed form solution to a first order ODE 9 [Zarezade et al., 2018]
The Cheshire algorithm Intuition Steering actions means sampling action user & times from u*(t) More in detail Since the intensity function u*(t) is stochastic, we sample from it using: Superposition principle Standard thinning Easy to implement It only requires sampling from inhomog. Poisson! 10 10 10 [Zarezade et al., 2018]
Experiments on real data Five Twitter datasets (users) where actions are tweets and retweets 1. Fit model parameters exogeneous rate influence matrix 2. Simulate steering endogenous actions directly incentivized tweets chosen by each method [Zarezade et al., 2018] 11
Evaluation metrics & baselines Evaluation metrics Average number of not directly incentivized tweets Average time to reach 30,000 not directly incentivized tweets Baselines MSC [Farajtabar et al., NIPS 16] OPL [Farajtabar et al., NIPS 14] PRK (Pagerank) DEG (Out-degree) 12 [Zarezade et al., 2018]
Performance vs. time Series, M(tf) 5k Sports, M(tf) 5k Cheshire (in red) triggers 100%-400% more posts than the second best performer. 13 [Zarezade et al., 2018]
Performance vs. # of incentivized tweets Series, M(tf) 5k Sports, M(tf) 5k Cheshire (in red) reaches 30K tweets 20-50% faster than the second best performer 14 [Zarezade et al., 2018]
Why Cheshire? the Cheshire Cat has the ability to appear and disappear in any location Alice s Adventures in Wonderland, Lewis Carroll 15
