variational approximation to empirical likelihood ABC

Sanjay Chaudhuri and his colleagues from Singapore arXived last year a paper on a novel version of empirical likelihood ABC that I hadn’t yet found time to read. This proposal connects with our own, published with Kerrie Mengersen and Pierre Pudlo in 2013 in PNAS. It is presented as an attempt at approximating the posterior distribution based on a vector of (summary) statistics, the variational approximation (or information projection) appearing in the construction of the sampling distribution of the observed summary. (Along with a weird eyed-g symbol! I checked inside the original LaTeX file and it happens to be a mathbbmtt g, that is, the typewriter version of a blackboard computer modern g…) Which writes as an entropic correction of the true posterior distribution (in Theorem 1).

“First, the true log-joint density of the observed summary, the summaries of the i.i.d. replicates and the parameter have to be estimated. Second, we need to estimate the expectation of the above log-joint density with respect to the distribution of the data generating process. Finally, the differential entropy of the data generating density needs to be estimated from the m replicates…”

The density of the observed summary is estimated by empirical likelihood, but I do not understand the reasoning behind the moment condition used in this empirical likelihood. Indeed the moment made of the difference between the observed summaries and the observed ones is zero iff the true value of the parameter is used in the simulation. I also fail to understand the connection with our SAME procedure (Doucet, Godsill & X, 2002), in that the empirical likelihood is based on a sample made of pairs (observed,generated) where the observed part is repeated m times, indeed, but not with the intent of approximating a marginal likelihood estimator… The notion of using the actual data instead of the true expectation (i.e. as a unbiased estimator) at the true parameter value is appealing as it avoids specifying the exact (or analytical) value of this expectation (as in our approach), but I am missing the justification for the extension to any parameter value. Unless one uses an ancillary statistic, which does not sound pertinent… The differential entropy is estimated by a Kozachenko-Leonenko estimator implying k-nearest neighbours.

“The proposed empirical likelihood estimates weights by matching the moments of g(X¹), …, g(X⁹) with that of
g(X⁰), without requiring a direct relationship with the parameter. (…) the constraints used in the construction of the empirical likelihood are based on the identity in (7), which can only be satisfied when θ = θ⁰. “

Although I am feeling like missing one argument, the later part of the paper seems to comfort my impression, as quoted above. Meaning that the approximation will fare well only in the vicinity of the true parameter. Which makes it untrustworthy for model choice purposes, I believe. (The paper uses the g-and-k benchmark without exploiting Pierre Jacob’s package that allows for exact MCMC implementation.)

ABC in Kuala Lumpur [alas not!]

While attending an “ABC in…” conference in Malaysia would have been most exciting, barring the current difficulties with traveling, especially since I had not heard of it at an earlier stage and also had never visited Malaysia (except when considering that Singapore was was one of the 14 states of Malaysia from 1963 to 1965), the “International Conference on Approximate Bayesian Computation in Science and Engineering”, scheduled for Feb 2021 is alas not the right opportunity! As a fake conference run by WASET, the “World Academy of Science, Engineering and Technology”, which runs thousands of conferences every year, usually cramming several of them in the very same room at the very same time in a periphery motel..! As attendees, if any, are not expected to… attend. Judging from the current list of “selected papers”, none of them has any connection with ABC. It would be funny, were it not a swindle of sorts…

Le Monde puzzle [#1081]

A “he said-she said” Le Monde mathematical puzzle (again in the spirit of the famous Singapore high-school birthdate problem):

Abigail and Corentin are both given a positive integer, a and b, such that a+b is either 19 or 20. They are asked one after the other and repeatedly if they are sure of the other’s number. What is the maximum number of times they are questioned?

If Abigail is given a 19, b=1 necessarily. Hence if Abigail does not reply, a<19. This implies that, if Corentin is given b=1 or b=19, he can reply a+b=19 or a+b=20, necessarily. Else, 1<b<19 implies that, if a=1 or a=18, b=18 or b=2. And so on…which leads to a maximum of 20 questions, 10 for Abigail and 10 for Corentin. Here is my R implementation

az=bz=cbind(20-(1:19),19-(1:19))
qwz=0;at=TRUE;bt=FALSE
while ((max(az)>0)&(max(bz)>0)){
 if (at){ 
  for (i in 1:19){ 
   if (sum(az[i,]>0)==2){
   for (j in az[i,az[i,]>0]){ 
     if (sum(bz[j,]==0)==2) az[i,]=rep(0,2)}}
   if (sum(az[i,]>0)<2){ 
    az[i,]=rep(0,2)}}} 
  if (bt){ 
   for (i in 1:19){ 
    if (sum(bz[i,bz[i,]>0]>0)==2){
     for (j in bz[i,bz[i,]>0]){ 
      if (sum(az[j,]==0)==2) bz[i,]=rep(0,2)}}
     if (sum(bz[i,]>0)<2){ bz[i,]=rep(0,2)}}}
  bt=!bt;at=!at;qwz=qwz+1}

Le Monde puzzle [#1071]

A “he said she said” Le Monde mathematical puzzle sixth competition problem that reminded me of the “Singapore birthday problem” (nothing to do with the original birthday problem!):

Arwen and Brandwein are privately and respectively given the day and month of Caradoc’s birthday [in the Gregorian calendar] with the information that the month number is at least the day number. Arwen starts by stating she knows Brandwein cannot deduce the birthday, followed by Brandwein who says the same about Arwen. If this “she says he says” goes on for the largest possible number of steps before Arwen says she knows, when is Caradoc’s birthday? Arwen and Brandwein are later given two numbers corresponding to Deirdre’s birthday with no indication of which one is the day and which one is the month. They know both numbers end up with the same digit and that the month number is strictly less than the day number. Arwen states she does not know the date and she knows Brandwein cannot know either. Then Brandwein says he indeed does not the date but he knows whether he got the day or the month. This prompts Arwen to conclude she knows, then Brandwein to do the same. When is Deirdre’s birthday?

Since this was a fairly easy puzzle (and since I had spent too much time debugging the previous R code!), I did not try coding this one but instead drew the possibilities and remove the impossibilities on a blackboard. The first question is quite simple actually since the day numbers stand between 1 and 12 and that each “I cannot know” excludes one of the remaining endpoints, removing first excludes 1 from both lists, then 12, then 2, then …. 8, ending up with 7. And 07/07 as Caradoc’s birthday. The second case sees 13,…,20,23,…,30 eliminated from Arwen’s numbers, then 3,…,10 as well, which eliminates the same numbers from Brandwein’s possibilities. That he knows whether it is a month or a day leaves only 1,2,21,22,31 as possible numbers. Then Arwen’s certainty reduces her numbers to be 2, 21, 22, or 31, and since Brandwein is also sure, the only possible cases are (2,22) and (22,2). Meaning Deirdre’s birthday is on 22/02. I dunno if this symmetry was to be expected! (And I cannot fathom why this puzzle is awarded so many points, when compared with the others.)

Le Monde puzzle [#1650]

A penultimate Le Monde mathematical puzzle  before the new competition starts [again!]

For a game opposing 40 players over 12 questions, anyone answering correctly a question gets as reward the number of people who failed to answer. Alice is the single winner: what is her minimal score? In another round, Bob is the only lowest grade: what is his maximum score?

For each player, the score S is the sum δ¹s¹+…+δ⁸s⁸, where the first term is an indicator for a correct answer and the second term is the sum over all other players of their complementary indicator, which can be replaced with the sum over all players since δ¹(1-δ¹)=0. Leading to the vector of scores

worz <- function(ansz){
  scor=apply(1-ansz,2,sum)
  return(apply(t(ansz)*scor,2,sum))}

Now, running by brute-force a massive number of simulations confirmed my intuition that the minimal winning score is 39, the number of players minus one [achieved by Alice giving a single good answer and the others none at all], while the maximum loosing score appeared to be 34, for which I had much less of an intuition!  I would have rather guessed something in the vicinity of 80 (being half of the answers replied correctly by half of the players)… Indeed, while in SIngapore, I however ran in the wee hours a quick simulated annealing code from this solution and moved to 77.

And the 2018 version of Le Monde maths puzzle competition starts today!, for a total of eight double questions, starting with an optimisation problem where the adjacent X table is filled with zeros and ones, trying to optimise (max and min) the number of positive entries [out of 45] for which an even number of neighbours is equal to one. On the represented configuration, green stands for one (16 ones) and P for the positive entries (31 of them). This should be amenable to a R resolution [R solution], by, once again!, simulated annealing. Deadline for the reply on the competition website is next Tuesday, midnight [UTC+1]