1y ago

35 Views

2 Downloads

1.87 MB

30 Pages

Transcription

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

Semantics of H-ASP PLEvery valid H-ASP PL program P has an underlying H-ASP programTr (Tr [PL] (P ))For every valid H-ASP PL program P, Tr (Tr [PL] (P )) has a uniquemaximal stable modelA stable model of a valid H-ASP PL program P is de ned as atransform of the unique maximal stable model of Tr (Tr [PL] (P ))Theorem(informal) Every computer representable computational cDAG can begenerated by a suitably constructed H-ASP PL programTheoremFor a valid H-ASP PL program P and an initial condition I of Tr [PL] (P ),the result of applying the Local Algorithm to P produces the uniquemaximal stable model of Tr (Tr [PL] (P )) with the (suitably transformed)initial condition J (I )Alex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP26 / 30

Generating a diagnosisH-ASP PL program W that encodes all the possible ways toautomatically whitelist an advertiser (applicable to any advertiser)For a speci c advertiser c the initial condition I (c ) contains theinformation about the advertiserLocal Algorithm generates a maximal stable model of W with theinitial condition I (c )The maximal stable model encodes the computational cDAG, withthe leaf nodes corresponding to hybrid states containing atom ENDA diagnosis exists if all the hybrid states with atom END also containatom EXPLAINEDDiagnosis is created by examining EXPLANATION parameter of allthe hybrid states containing atoms END and EXPLAINED.Alex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP27 / 30

ConclusionUse of ASP like program allowed rapid update the diagnostic logic:criteria for whitelisting changed many timesThe program was used to diagnose the failures for many advertisersover a time interval of several monthsReduced the time to diagnose a single failure from 30-60 mins(manual debugging per advertiser) to 1-3 minsAlex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP28 / 30

Related WorkSolving diagnostic problems based on the theory of action languageAL (by Balduccini and Gelfond)(Balduccini and Gelfond) a mathematical model of the dynamic domainInteresting future work; not attempted due to project’s time constraintsExtensions of ASP allowing external data searches: DLV DB , VIprograms, GRINGO grounder, HEX programsRedl in the PhD thesis notes that HEX programs generalize the aboveHEX programs (Eiter et al.) are an extension of ASP that allowaccessing external data sources via external atoms.The main di erences with H-ASP PL:For H-ASP PL, information processed by algorithm is kept as aseparate class of information from logical atomsH-ASP PL has built-in support for producing computational cDAGsH-ASP PL stable models are the unique maximal stable modelsAlex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP29 / 30

Thank youAlex Brik and Je rey B. Remmel (LPNMR 2015)Diagnosing Automatic Whitelisting for Dynamic RemarketingSeptemberAds Using2015Hybrid ASP30 / 30

Dynamic Remarketing Ads is Google s platform for showing customized ads based on past interactions with a user. The presentation will descibe the use of H-ASP in creating software that diagnoses possible reasons why an advertiser is not ready to show dynamic remarketing ads. Outline: 1 Automatic Whitelisting for Dynamic Remarketing Ads

Related Documents: