Diagnosing Automatic Whitelisting For Dynamic Remarketing Ads Using .

Diagnosing Automatic Whitelisting for DynamicRemarketing Ads Using Hybrid ASPAlex Brik1 and Je rey B. Remmel2LPNMR 2015September 20151 Google2 UCIncSan DiegoAlex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using 2015Hybrid ASP1 / 30

Hybrid ASP (H-ASP) is an extension of ASP for combining ASP type rulesand numerical algorithms. Dynamic Remarketing Ads is Google’s platformfor showing customized ads based on past interactions with a user. Thepresentation will descibe the use of H-ASP in creating software thatdiagnoses possible reasons why an advertiser is not ready to show dynamicremarketing ads.Outline:1Automatic Whitelisting for Dynamic Remarketing Ads2The Branching Computational Pattern (BCP)3Hybrid ASP4H-ASP PL library5Example6Semantics of H-ASP PL7ConclusionAlex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using 2015Hybrid ASP2 / 30

Automatic Whitelisting for Dynamic Remarketing AdsIn order for Google to start showing dynamic remarketing ads for aparticular advertiser the readiness of that advertiser needs to beveri ed (advertiser needs to be whitelisted)Readiness is veri ed automaticallyThere are multiple ways for an advertiser to prepare for showingdynamic remarketing adsIn every case a set of constraints needs to be satis edSatisfaction of a constraint may depend on the contents of logs, adsdatabases and data from the previous constraint evaluationAlex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using 2015Hybrid ASP3 / 30

Automatic Whitelisting for Dynamic Remarketing AdsAn example of advertiser becoming ready to show dynamic remarketingads:An advertiser needs to install a JavaScript tag on their website(veri ed by searching advertiser related database), andA user visits advertiser’s website (veri ed by searching a user eventlog), andAn advertiser creates a dynamic remarketing ad (veri ed using afunction from a separate software library)Alex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using 2015Hybrid ASP4 / 30

Automatic Whitelisting for Dynamic Remarketing AdsA path from the root to a leaf with all constraints veri ed results inan advertiser being whiltelisted.A diagnosis contains an unsatis ed constraint for every caseAlex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using 2015Hybrid ASP5 / 30

Branching Computational Pattern (BCP)Diagnosing a failure of automatic whitelisting can be viewed as aninstance of the Branching Computational Pattern (BCP)BCP is a pattern of computation for generating a connected directedacyclic graph (cDAG) with the set of vertices consisting of pairs(A, p), where A is a set of atoms and p is a vector of parametervalues representable by a computer.At each cDAG vertex (A, p), the computation consists of the twosteps12use A and p to choose algorithms (that will possibly access externaldata repositories and/or perform computations) to produce the set ofnext parameter value vectors q1 , ., qk andfor each qi produced in step 1, derive sets of atoms Bi ,1 , Bi ,2 , ., Bi ,m i .The set of child states of (A, p) is f(B1,1 , q1 ),.,(B1,m 1 , q1 ) , (B2,1 , q2 ), .,(Bk ,m k , qk )g.The cDAG generated by a BCP with the sets of atoms restricted toAt and the set of vectors of parameters restricted to S is called acomputational cDAG over At and S.Alex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using 2015Hybrid ASP6 / 30

Branching Computational Pattern (BCP)Alex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using 2015Hybrid ASP7 / 30

Hybrid Answer Set Programming (H-ASP)H-ASP can be used to compute according to BCP.H-ASP is an extension of ASP for combining logical reasoning andnumerical processingA program P has a parameter space S and a set of atoms At.Elements of S (generalized positions) are of the formp (t, x1 , ., xm ), t is time and xi are parameter values, notation:t (p) t and xi (p) xi .The universe of P is At Sb fp 2 S : (9a 2 At ) ((a, p) 2 M )g - the set ofFor M At S, Mgeneralized positions used in MFor p 2 S, WM (p) fa 2 At : (a, p) 2 M g - the set of atomscorresponding to p in M. (WM (p) , p) is a hybrid state.A block B is of the form B a1 , ., an , not b1 , ., not bmM j (B, p)b and (ai , p) 2 M for i 2 f1, ., n g and (bj , p) 2if p 2 M/ M forj 2 f1, ., m g.Alex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using 2015Hybrid ASP8 / 30

Hybrid Answer Set Programming (H-ASP)The rule types are restricted to those relevant for computing with BCP.Two types of rules: Advancing rules (used to derive new generalizedpositions)aB : A, Owhere B is a block (of the form B a1 , ., an , not b1 , ., not bm ),O S, A is a set valued algorithm O ! 2S .The idea: for p 2 O if M j (B, p) then (a, q) should be in M for allbq 2 A (p) \ M.Stationary rules (used as constraints and to derive new atoms)aB1 ; B2 : H, O (or aB : H, O)where each Bi is a block, O S 2 (or O S), H is a boolean algorithm.The idea: for (p1 , p2 ) 2 O with t (p1 ) t (p2 ) (or p 2 O) ifM j (Bi , pi ) (M j (B, p)) and H (p1 , p2 ) (H (p)) is true then(a, p2 ) 2 M ((a, p) 2 M).Alex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using 2015Hybrid ASP9 / 30

Hybrid Answer Set Programming (H-ASP)Stable ModelA Horn program does not contain any negated atoms in At.For a Horn program P, an initial condition I 2 S, and M At S,one-step provability operator TP ,I (M ) is M union all (a, J ) s.t12b [ fI g such9 a stationary rule C aB : H, O and p 2 O \ Mthat M j (B, p) and H (p) 1 and J p, or9 a stationary rule C aB1 ; B2 : H, O and2b(p1 , p2 ) 2 O \ M [ fI g such that Mi j (Bi , pi ) andH (p1 , p2 ) 1, and J p2 or3b [ fI g such9 an advancing rule C aB : A, O and p 2 O \ Mthat M j (B, p) and J 2 A (p)TP ,I ( ) " ω condition I . [TPk ,I ( ) is the least model of P with the initialk 0Alex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP10 / 30

Hybrid Answer Set Programming (H-ASP)Stable ModelAn advancing rule C aB : A, O is inconsistent with (M, I ) ifbfor all p 2 O \ M [ fI g either12M 6j (B , p)b A (p) \ MA stationary rule C aB1 , B2 : H, O is inconsistent with (M, I )b [ fI gif for all (p1 , p2 ) 2 O \ M122eitherM 6j B1 , p1 or M 6j B2 , p2 orH (p1 , p2 ) 0A stationary rule C aB : H, O is inconsistent with (M, I ) ifbfor all p 2 O \ M [ fI g either12M 6j (B , p) orH (p) 0Alex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP11 / 30

Hybrid Answer Set Programming (H-ASP)Stable ModelA Gelfond-Lifschitz reduct of P over M and I , P M ,I :1Eliminate all the inconsistent rules2If an advancing rule aB : A, O is not eliminated then it is replaced b [ fI g s.t.by aB : A , O where O is the set p 2 O \ Mb 6 and A (p) is de ned as A (p) \ MbM j (B , p) and A (p) \ M34If a stationary rule aB1 ; B2 : H, O is not eliminated then it isreplaced by aB1 ; B2 : H jO , O where O is the setb [ fI g(p1 , p2 )2O \ M2s.t. M j Bi , pi and H (p1 , p2 ) 1Similarly for a stationary rule aB : H, O that is not eliminated.M is a stable model of P with the initial condition I ifTP M ,I ,I ( ) " ω MAlex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP12 / 30

Hybrid Answer Set Programming (H-ASP)A H-ASP program of order 1 is a program that consists only of rules of theformaB : G, OTheorem(informally) Let At be a set of propositional atoms and let S be a set ofparameter values. Let hV , E i be a computational cDAG over At and S.Then there exists a H-ASP program P of order 1 and an initial condition Ifor P such that the set of stable models of P with the initial condition Iencode hV , E i.Alex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP13 / 30

H-ASP PL - H-ASP Python LibraryThe intuitionAlex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP14 / 30

H-ASP PL - H-ASP Python LibraryThe intuitionAlex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP15 / 30

H-ASP PL - H-ASP Python LibraryThe intuitionAlex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP16 / 30

H-ASP PL - H-ASP Python LibraryThe intuitionAlex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP17 / 30

H-ASP PL - H-ASP Python LibraryFeaturesSupport de nition of H-ASP rulesaa1 , a2 , not b1 ; a3 , not b2 : A, OintoDe neRule ("a", "a1, a2, not b1; a3 , not b2", A, O )where A and O are Python functionsParameters are named; each advancing algorithm outputs the valuesfor a speci ed subset of parameters, declared as a signature of theadvancing algorithm. The generalized positions are assembled byperforming cross products on the outputs of the algorithms.For an advancing algorithm A, if q 2 A (p) then t (q) t (p) 1For a stationary rule aB1 ; B2 : H, O, if the rule is applicable at(p1 , p2 ) then p2 is a successor of p1The restrictions can be implemented explicitly by H-ASP rules.Alex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP18 / 30

Example: Verifying Advertiser’s ReadinessConstraint C 1 requires data from D1, constraint C 3 requires datafrom D3constraint C 2 requires data used to check C 1 and data from D2Alex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP19 / 30

Example (The Local Algorithm)Two named parameters: DATA and EXPLANATION;Find stationary rules applicable at IAlex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP20 / 30

Example (The Local Algorithm)Find advancing rules applicable at ({BRANCH1}, I)Alex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP21 / 30

Example (The Local Algorithm)Find advancing rules applicable at ({BRANCH2}, I)Alex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP22 / 30

Example (The Local Algorithm)Find stationary rules applicable at ({CHECK C1}, (1, data1, null)}Alex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP23 / 30

Example (The Local Algorithm)Find advancing rules applicable at ({CHECK C1, C1 done}, (1, data1, null)}Alex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP24 / 30

The Local AlgorithmLet P be a valid H-ASP PL program and I be an initial condition1Use stationary rules applicable at I to derive sub-models at I2Repeat for every hybrid state (A, p):12Use advancing rules applicable at (A, p) to generate a set of nextcandidate states (D1 , q1 ), ., (Dn , qn )For every candidate state (Di , qi ) use stationary rules applicable at((A, p) , (Di , qi )) and stationary rules applicable at (Di , qi ) togenerate a set of next hybrid states (Di ,1 , qi ), ., Di ,m i , qiAlex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP25 / 30