text:
# Multiscale inference with transport maps

This notebook uses the latest version of MUQ to illustrate concepts from A multiscale strategy for Bayesian inference using transport maps by Matthew Parno, Tarek Moselhy, and Youssef Marzouk.

### The general multiscale setting

The idea is to take advantage of multiscale structure to decompose the usual Bayesian inference problem into two components: a coarse problem and a fine problem. To illustrate this mathematically, let $\theta$ be a random variable taking values in $\mathbb{R}^{d_\theta}$ and let $y$ be an observable random variable (e.g., the data) taking values in $\mathbb{R}^{d_y}$. Our goal is then to generate samples of the Bayesian posterior

$$\pi(\theta | y) \propto \pi(y|\theta)\pi(\theta).$$

However, as [Parno et al.] outlines, additional structure can be exploited when the relationship between $\theta$ and $y$ exhibits multiscale behavior. Let $\gamma$ be a intermediate coarse random variable taking values in $\mathbb{R}^{d_\gamma}$ and assume that $\theta$ and $y$ are conditionally independent given $\gamma$. That is,

$$\pi(\theta,y|\gamma) = \pi(\theta|\gamma)\pi(y|\gamma).$$

Using this fact for the joint posterior $\pi(\theta,\gamma | y)$, yields

\begin{eqnarray*} \pi(\theta,\gamma | y) &\propto& \pi(y | \theta,\gamma)\pi(\theta,\gamma)\\ &=& \pi(y|\gamma)\pi(\gamma)\pi(\theta|\gamma) \end{eqnarray*}

Looking at this expression closer, we can see that $\pi(\theta,\gamma | y)$ contains a coarse posterior $\pi(y|\gamma)\pi(\gamma)$ and a coarse-to-fine distribution $\pi(\theta|\gamma)$. Following [Parno et al.] we will use MCMC to sample the coarse posterior and then "prolongate" those coarse samples back to the fine scale using $\pi(\theta | y)$.

### A solution strategy

There are two challenges in performing multiscale inference as described above: first, we need to know the coarsescale prior so that we can sample $\pi(\gamma|y) \propto \pi(y|\gamma)\pi(\gamma)$, and second, we need to be able to sample
$\pi(\theta|\gamma)$. Both of these challenges can be addressed with an appropriately constructed transport map.

Consider the map

$$S(\gamma,\theta) = \left[\begin{array}{l} S_c(\gamma) \\ S_f(\gamma,\theta)\end{array}\right] = \left[\begin{array}{c}r_c\\r_f\end{array}\right],$$

and its inverse

$$T(r_c,r_f) = \left[\begin{array}{l} T_c(r_c) \\ T_f(r_c,r_f)\end{array}\right] = \left[\begin{array}{c}\gamma\\\theta\end{array}\right],$$

where $r_c$ and $r_f$ are IID standard normal random variables with the same dimensions as $\gamma$ and $\theta$, respectively. Using $T_c$, we can sample the posterior $\pi(r_c|y)$ (instead of $\pi(\gamma|y)$) and then use the coarse map $T_f(r_c,r_f)$ to generate samples of $\pi(\theta | r_c)$. See [Parno et al.] for more details of this approach.

### A specific example

In this notebook, we are concerned with a specific example of multiscale, which was first used for illustration in [Parno et al.]. In this example, $\theta$ is two-dimensional, $\gamma$ is one-dimensional, and they are deterministically related through

$$\gamma = log\left(\frac{1.0}{\exp(-x_1) + \exp(-x_2)}\right)$$

Also, $\theta$ has a multivariate Gaussian prior defined by

$$\theta \sim N\left(\left[\begin{array}{c}0 \\ 0\end{array}\right],\left[\begin{array}{cc}2.0 & 0.6 \\ 0.6 & 2.0\end{array}\right]\right)$$

The data, $y$, is related to to $\gamma$ by

$$y = \exp(3\gamma) - 2 + \eta$$

where $\eta\sim N(0,0.1)$ is a scalar Gaussian random variable. Notice that $y$ does not explicitly depend on $\theta$; if $\gamma$ is known, $\theta$ is not needed to calculate $y$. Thus, this problem satisfies the conditional independence assumption needed in the derivation of $\pi(\theta,\gamma | y)$ above.

### Setting up the problem in MUQ

There are three main components of MUQ that are needed to sample the posterior $\pi(\theta|y)$ using this multiscale approach. First is the modeling module, which we use to define ModPieces and ModGraphs describing the relationships between $\theta$, $\gamma$, and $y$. Second is the use of transport maps, which are needed to set up the coarse scale inference problem and also to generate finescale samples from coarsescale samples. And third, is the MCMC model for coarse scale sampling.

Below, we will:

1. Define children of the ModPiece class describing the relationships between $\theta$, $\gamma$, and $y$.
2. Sample the prior to generate samples of the joint distribution $\pi(\gamma,\theta)$.
3. Construct a transport map from $(\gamma,\theta)$ to $(r_c,r_f)$ and use regression to approximate its inverse. This will create the maps $S(\gamma,\theta)$ and $T(r_c,r_f)$.
4. Set up the coarse reference posterior $\pi(r_c|y)$ and sample it using a MALA MCMC approach. The result will be a set of coarse posterior samples $\{r_c^{(1)},r_c^{(2)},...,r_c^{(K)}\}$.
5. Evaluate the fine map $\theta^{(i)}=T_f(r_c^{(i)},r_f)$ at each posterior sample with a random $r_f$ to generate a set of finescale samples $\{\theta^{(1)},\theta^{(2)},...,\theta^{(K)}\}$.

## Include the necessary header files

// std library includes
#include <fstream>
#include <iostream>

// boost includes
#include <Eigen/Core>
#include <Eigen/Sparse>

// muq utilities includes
#include "MUQ/Utilities/HDF5File.h"
#include "MUQ/Utilities/RandomGenerator.h"
#include "MUQ/Utilities/MultiIndex/MultiIndexFactory.h"

// muq inference includes
#include "MUQ/Inference/MCMC/MCMCBase.h"
#include "MUQ/Inference/ProblemClasses/InferenceProblem.h"
#include "MUQ/Inference/MAP/MAPbase.h"
#include "MUQ/Inference/TransportMaps/MapFactory.h"

// muq modelling includes
#include "MUQ/Modelling/ModPieceTemplates.h"
#include "MUQ/Modelling/ModGraphPiece.h"
#include "MUQ/Modelling/GaussianPair.h"
#include "MUQ/Modelling/DensityProduct.h"
#include "MUQ/Modelling/EmpiricalRandVar.h"
#include "MUQ/Modelling/VectorPassthroughModel.h"

// namespaces
using namespace std;
using namespace muq::Modelling;
using namespace muq::Utilities;
using namespace muq::Inference;

## Define a fine-to-coarse model

Here we define the fine-to-coarse model by creating a child of the ModPiece class. Notice that there is only one input $\theta$, and one output $\gamma$, so we used the template class OneInputNoDerivModPiece.

class Fine2Coarse : public OneInputNoDerivModPiece {
public:

Fine2Coarse() : OneInputNoDerivModPiece(2, 1) {}

virtual Eigen::VectorXd EvaluateImpl(const Eigen::VectorXd& x) override
{
Eigen::VectorXd y(1);

y(0) = log(1.0 / (exp(-1.0 * x(0)) + exp(-1.0 * x(1))));
return y;
}
};

## Define a coarse-to-data model

The following cell creates a child of ModPiece describing the deterministic relationship between the coarse variable $\gamma$ and the data $y$. The additive error $\eta$ will come into play later on in the likelihood definition.

class Coarse2Data : public OneInputNoDerivModPiece {
public:

Coarse2Data(double bIn = 1.0) : OneInputNoDerivModPiece(1, 1), b(bIn) {}

virtual Eigen::VectorXd EvaluateImpl(const Eigen::VectorXd& x) override
{
Eigen::VectorXd y(1);

y(0) = pow(exp(x(0)), 3) - b;
return y;
}

private:

double b;
};

## A function to generate fine and coarse samples

Eigen::MatrixXd GenerateSamples(int numSamps, shared_ptr<RandVar> priorRv, shared_ptr<ModPiece> f2c)
{

Eigen::MatrixXd allSamples(3,numSamps);

// first generate the prior samples
allSamples.bottomRows(2) = priorRv->Sample(numSamps);

// now generate the coarse samples
allSamples.topRows(1) = f2c->EvaluateMulti(allSamples.bottomRows(2));

return allSamples;
}

## A function to construct the transport maps

A total order multiindex set is used here to construct the transport map. Notice that the multiindex set returned by CreateTriTotalOrder guarantees that the map is lower triangular, thus allowing us to split it into $T_c$ and $T_f$. The CreateTriHyperbolic function is another alternative, which produces more parsimonious multiindex sets.

To construct $T$ from $S$, we use regression. In this cell, we first build $S$ with a call to BuildToNormal. Then we evaluate $S$ at all the prior samples with the EvaluateMulti member function. Finally, the RegressSampsToSamps function uses the inputs and outputs of the $S$ in a regression framework to approximate $T$.

shared_ptr<TransportMap> BuildMap(int maxOrder, Eigen::MatrixXd const& allSamples)
{

auto multis = MultiIndexFactory::CreateTriTotalOrder(allSamples.rows(),maxOrder);
auto invmap = MapFactory::BuildToNormal(allSamples, multis);

Eigen::MatrixXd refSamps = invmap->EvaluateMulti(allSamples);

return MapFactory::RegressSampsToSamps(refSamps, allSamples, multis);
}

## Function to perform coarse MCMC

The following function sets of the coarse inference problem and then samples it using MCMC.

### Step 1: Create a ModGraph to describe the posterior.

Notice that the coarse map $T_c$ is separated from the entire map $T$ using the head function. Like the Eigen::VectorXd class, the TransportMap class has functions like head, tail, and segment. All of these slices are performed on the map output.

Eigen::MatrixXd RunCoarseMCMC(Eigen::VectorXd const& data, shared_ptr<TransportMap> jointMap)
{
auto graph = make_shared<ModGraph>();

double dataVar = 0.1;

Eigen::VectorXd priorMu = Eigen::VectorXd::Ones(1);

### Step 2: Create an inference problem

Here the ModGraph is translated into an InferenceProblem, which the MCMC algorithms know how to work with.

auto problem = make_shared<InferenceProblem>(graph);

### Step 3: Define the MCMC parameters

See our list of parameters for a more comprehensive list of options. Note that these options can also be conveniently stored in an XML or JSON file and read with boost's xml parser or json parser

// define the properties and tuning parameters for preconditioned MALA
boost::property_tree::ptree params;
params.put("MCMC.Method", "SingleChainMCMC");
params.put("MCMC.Kernel", "MHKernel");
params.put("MCMC.Proposal", "PreMALA");
params.put("MCMC.Steps", 20000);
params.put("MCMC.BurnIn", 5000);
params.put("MCMC.MH.PropSize", 0.01);
params.put("Verbose", 3);

### Step 4: Construct the MCMC sampler

Use the options defined in the params ptree to construct an MCMC sampler.

// construct a MCMC sampling task from the parameters and the inference problem.
auto mcmcSampler = MCMCBase::ConstructMCMC(problem, params);

### Step 5: Sample the coarse posterior

Here is where all the work actually happens. From an initial starting point of $r_c=0.5$, this cell runs the MCMC chain and returns and Eigen::MatrixXd with the samples. Each column of the matrix is a sample.

Eigen::VectorXd startingPoint(1);
startingPoint << 0.5;

auto mcmcChain = mcmcSampler->Sample(startingPoint);

return mcmcChain->GetAllSamples();
}

## A function to generate finescale samples

After running the coarsescale MCMC, this function will generate realizations of the finescale posterior $\pi(\theta|y)$ using $T_f$.

Eigen::MatrixXd SampleFinescale(Eigen::MatrixXd const& coarseSamples, shared_ptr<TransportMap> jointMap)
{
int numSamps = coarseSamples.cols();
Eigen::MatrixXd refSamps(3,numSamps);

// set r_c to come from the MCMC samples
refSamps.row(0) = coarseSamples;

// generate independent samples of r_f
refSamps.bottomRows(2) = RandomGenerator::GetNormalRandomMatrix(2,numSamps);

return jointMap->EvaluateMulti(refSamps);
}

## Put all the functions together

Here is where the rubber meets the road! First we define the prior $\pi(\theta)$. Then we use the classes and functions above to generate samples of $\pi(\theta|y)$.

int main(){

// Define the prior
Eigen::VectorXd mu = Eigen::VectorXd::Zero(2);
Eigen::MatrixXd cov(2,2);
cov << 2.0, 0.6,
0.6, 2.0;
auto priorRv = make_shared<GaussianRV>(mu,cov);

auto f2c = make_shared<Fine2Coarse>();

int numSamps = 5e4;
Eigen::MatrixXd allSamps = GenerateSamples(numSamps, priorRv, f2c);

int maxOrder = 7;
auto map = BuildMap(maxOrder, allSamps);

Eigen::VectorXd data(1);
data << -1.8;
Eigen::MatrixXd coarsePostSamps = RunCoarseMCMC(data, map);

Eigen::MatrixXd finePostSamps = SampleFinescale(coarsePostSamps, map);

### Save the samples

The following cell uses an instance of the HDF5File class to store the samples. Note that older version of MUQ only had the HDF5Wrapper class, which creates a persistent interface to a single global HDF5 file. The HDF5File, on the other hand, allows opening and closing several HDF5 files simultaneously within a single scope.

HDF5File fout("MultiscaleResults.h5");
fout.WriteMatrix("/Training/Samples",allSamps);
fout.WriteScalarAttribute("/Training", "Number of Samples", numSamps);
fout.WriteScalarAttribute("/Training", "Maximum Polynomial Order", maxOrder);

fout.WriteMatrix("/Posterior/CoarseSamples", coarsePostSamps);
fout.WriteMatrix("/Posterior/FineSamples",finePostSamps);

fout.CloseFile();
return 0;
}

## If you build it, the samples will come...

See the cmake file for more details.

cd build; cmake ..; make; cd ../

-- Configuring done
-- Generating done
-- Build files have been written to: /Users/mparno/Documents/Repositories/MUQ/MUQ/MUQ/examples/Inference/TransportMaps/MultiscaleInference/build
Scanning dependencies of target SmallMultiscale
[100%] Building CXX object CMakeFiles/SmallMultiscale.dir/SmallMultiscale.cpp.o
[100%] Built target SmallMultiscale

## Run the code

build/SmallMultiscale

10% Complete
MH: Acceptance rate =  47.9%
20.0% Complete
MH: Acceptance rate =  48.5%
30.0% Complete
MH: Acceptance rate =  48.1%
40.0% Complete
MH: Acceptance rate =  50.9%
50.0% Complete
MH: Acceptance rate =  51.7%
60.0% Complete
MH: Acceptance rate =  53.1%
70.0% Complete
MH: Acceptance rate =  54.2%
80.0% Complete
MH: Acceptance rate =  54.7%
90.0% Complete
MH: Acceptance rate =  54.8%
100.0% Complete
MH: Acceptance rate =  55.0%

# Analyze the results

Now we switch over to Python to plot the results. The finescale samples are read from the HDF5 file created in c++ and matplotlib is used for plotting.

import h5py
import matplotlib.pyplot as plt

f = h5py.File('MultiscaleResults.h5')
postSamps = f['/Posterior/FineSamples']

plt.plot(postSamps[1,0:15000:2],postSamps[2,0:15000:2],'.')
plt.xlim([-2,2])
plt.ylim([-2,2])
plt.show()

## Completed code:

### Python

import h5py
import matplotlib.pyplot as plt

f = h5py.File('MultiscaleResults.h5')
postSamps = f['/Posterior/FineSamples']

plt.plot(postSamps[1,0:15000:2],postSamps[2,0:15000:2],'.')
plt.xlim([-2,2])
plt.ylim([-2,2])
plt.show()

### SmallMultiscale.cpp

// std library includes
#include <fstream>
#include <iostream>

// boost includes
#include <Eigen/Core>
#include <Eigen/Sparse>

// muq utilities includes
#include "MUQ/Utilities/HDF5File.h"
#include "MUQ/Utilities/RandomGenerator.h"
#include "MUQ/Utilities/MultiIndex/MultiIndexFactory.h"

// muq inference includes
#include "MUQ/Inference/MCMC/MCMCBase.h"
#include "MUQ/Inference/ProblemClasses/InferenceProblem.h"
#include "MUQ/Inference/MAP/MAPbase.h"
#include "MUQ/Inference/TransportMaps/MapFactory.h"

// muq modelling includes
#include "MUQ/Modelling/ModPieceTemplates.h"
#include "MUQ/Modelling/ModGraphPiece.h"
#include "MUQ/Modelling/GaussianPair.h"
#include "MUQ/Modelling/DensityProduct.h"
#include "MUQ/Modelling/EmpiricalRandVar.h"
#include "MUQ/Modelling/VectorPassthroughModel.h"

// namespaces
using namespace std;
using namespace muq::Modelling;
using namespace muq::Utilities;
using namespace muq::Inference;

class Fine2Coarse : public OneInputNoDerivModPiece {
public:

Fine2Coarse() : OneInputNoDerivModPiece(2, 1) {}

virtual Eigen::VectorXd EvaluateImpl(const Eigen::VectorXd& x) override
{
Eigen::VectorXd y(1);

y(0) = log(1.0 / (exp(-1.0 * x(0)) + exp(-1.0 * x(1))));
return y;
}
};

class Coarse2Data : public OneInputNoDerivModPiece {
public:

Coarse2Data(double bIn = 1.0) : OneInputNoDerivModPiece(1, 1), b(bIn) {}

virtual Eigen::VectorXd EvaluateImpl(const Eigen::VectorXd& x) override
{
Eigen::VectorXd y(1);

y(0) = pow(exp(x(0)), 3) - b;
return y;
}

private:

double b;
};

Eigen::MatrixXd GenerateSamples(int numSamps, shared_ptr<RandVar> priorRv, shared_ptr<ModPiece> f2c)
{

Eigen::MatrixXd allSamples(3,numSamps);

// first generate the prior samples
allSamples.bottomRows(2) = priorRv->Sample(numSamps);

// now generate the coarse samples
allSamples.topRows(1) = f2c->EvaluateMulti(allSamples.bottomRows(2));

return allSamples;
}

shared_ptr<TransportMap> BuildMap(int maxOrder, Eigen::MatrixXd const& allSamples)
{

auto multis = MultiIndexFactory::CreateTriTotalOrder(allSamples.rows(),maxOrder);
auto invmap = MapFactory::BuildToNormal(allSamples, multis);

Eigen::MatrixXd refSamps = invmap->EvaluateMulti(allSamples);

return MapFactory::RegressSampsToSamps(refSamps, allSamples, multis);
}

Eigen::MatrixXd RunCoarseMCMC(Eigen::VectorXd const& data, shared_ptr<TransportMap> jointMap)
{
auto graph = make_shared<ModGraph>();

double dataVar = 0.1;

Eigen::VectorXd priorMu = Eigen::VectorXd::Ones(1);

auto problem = make_shared<InferenceProblem>(graph);

// define the properties and tuning parameters for preconditioned MALA
boost::property_tree::ptree params;
params.put("MCMC.Method", "SingleChainMCMC");
params.put("MCMC.Kernel", "MHKernel");
params.put("MCMC.Proposal", "PreMALA");
params.put("MCMC.Steps", 20000);
params.put("MCMC.BurnIn", 5000);
params.put("MCMC.MH.PropSize", 0.01);
params.put("Verbose", 3);

// construct a MCMC sampling task from the parameters and the inference problem.
auto mcmcSampler = MCMCBase::ConstructMCMC(problem, params);

Eigen::VectorXd startingPoint(1);
startingPoint << 0.5;

auto mcmcChain = mcmcSampler->Sample(startingPoint);

return mcmcChain->GetAllSamples();
}

Eigen::MatrixXd SampleFinescale(Eigen::MatrixXd const& coarseSamples, shared_ptr<TransportMap> jointMap)
{
int numSamps = coarseSamples.cols();
Eigen::MatrixXd refSamps(3,numSamps);

// set r_c to come from the MCMC samples
refSamps.row(0) = coarseSamples;

// generate independent samples of r_f
refSamps.bottomRows(2) = RandomGenerator::GetNormalRandomMatrix(2,numSamps);

return jointMap->EvaluateMulti(refSamps);
}

int main(){

// Define the prior
Eigen::VectorXd mu = Eigen::VectorXd::Zero(2);
Eigen::MatrixXd cov(2,2);
cov << 2.0, 0.6,
0.6, 2.0;
auto priorRv = make_shared<GaussianRV>(mu,cov);

auto f2c = make_shared<Fine2Coarse>();

int numSamps = 5e4;
Eigen::MatrixXd allSamps = GenerateSamples(numSamps, priorRv, f2c);

int maxOrder = 7;
auto map = BuildMap(maxOrder, allSamps);

Eigen::VectorXd data(1);
data << -1.8;
Eigen::MatrixXd coarsePostSamps = RunCoarseMCMC(data, map);

Eigen::MatrixXd finePostSamps = SampleFinescale(coarsePostSamps, map);

HDF5File fout("MultiscaleResults.h5");
fout.WriteMatrix("/Training/Samples",allSamps);
fout.WriteScalarAttribute("/Training", "Number of Samples", numSamps);
fout.WriteScalarAttribute("/Training", "Maximum Polynomial Order", maxOrder);

fout.WriteMatrix("/Posterior/CoarseSamples", coarsePostSamps);
fout.WriteMatrix("/Posterior/FineSamples",finePostSamps);

fout.CloseFile();
return 0;
}

Test Status
• ##### Develop Branch
OS Compiler
OSX Clang
Ubuntu Clang
Ubuntu g++ 4.7
Ubuntu g++ 4.8
Ubuntu g++ 4.9
Acknowledgments
This material is based upon work supported by the National Science Foundation under Grant No. 1550487.

This work was supported by the DOE Office of Science through the QUEST SciDAC Institute.

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.


text:
## SRN – Racing Thompson by Zhou et al.

While browsing the accepted papers list of ICML 2018, I discovered this paper ‘Racing Thompson: an Efficient Algorithm for Thompson Sampling with Non-conjugate Priors‘ by Zhou, Zhu, and Zhuo. Thompson sampling is a popular algorithm for exploration-exploitation tradeoff problems and is also known as Bayesian bandits. I decided to write my Sunday Reading Notes post on this paper because have been interested in the exploration-exploitation tradeoff for a while and explored this topic through Bayesian optimization and my WSDM’19 paper on sequential A/B testing.

Suppose we want to identify the best arm among $K$ arms and we have some prior knowledge about their rewards $\mu \sim \pi.$ Thompson sampling (TS) balances exploring unexplored arms getting rewards from arms already yielding high rewards by choosing the $k$th arm according to its the posterior probability of being the optimal arm $P_{it} = \pi\left( \mu_i = \max_j \mu_j \right).$ The computational challenge is to compute the probabilities $P_{it}$. Because TS is often used as an online algorithm, efficient calculation of the posterior probabilities is very important. In the conjugate prior case, this calculation is done in $O(K)$. With non-conjugate priors, I have seen in the literature that people using Markov Chain Monte Carlo (MCMC) and sequential Monte Carlo (SMC). The authors recognize this probability as an expectation and propose to use an Importance Sampling (IS) step combined with Gumbel-Max trick, which transforms the sampling problem to an optimization problem, to sample $k$ at time $k$ according to probabilities $\pi\left( \mu_i = \max_j \mu_j \right) = \mathbb{E}_{\mu\sim \pi(\cdot|X(1:t))}\left[\mathbb{I}[\mu_k = \max_j {\mu_j}] \right] = \mathbb{E}_{\mu\sim B_t}\left[\mathbb{I}[\mu_k = \max_j {\mu_j}] \frac{\pi(\mu|X(1:t)}{B_t(\mu}\right].$

The benefits of this IS step comes from flexibility to choose $B_t$ at each time step and also the authors leveraged the stopping rule of racing algorithms to deterime the number of IS samples needed to approximate the expectation.

The resulting algorithm, which combines benefits from Importance Sampling, Gumble-Max trick, and the racing algorithm, is proved to be $(\delta,\sigma)-$PAC, which is asymptotic good in the sense the total variance distance between the true value $P_{it}$ and its estimate converges to zero.

What I find very interesting from the regret analysis section is the fact that the racing TS in this paper can provide much lower regret compared to Thompson sampling and prior-swapping (PS) even though it uses much few particles than SMC and PS. It is not intuitive to me why this should happen. But upon a little further investigation, I found that the priors used for TS and PS & Racing are different in both plots. For ease of implementation, the authors have chosen a conjugate prior for TS. This leaves me wondering what the results would be if we were to use MCMC or SMC with more particles as the baseline for the regret analysis.

References:

• Zhou, Y., Zhu, J. & Zhuo, J.. (2018). Racing Thompson: an Efficient Algorithm for Thompson Sampling with Non-conjugate Priors. Proceedings of the 35th International Conference on Machine Learning, in PMLR 80:6000-6008

## SRN – Scalable Bayesian Inference for Excitatory Point Process Networks by Linderman and Adams

The topic of this week’s SRN is latent network discovery. The paper ‘Scalable bayesian inference for excitatory point process networks‘ by Scott Linderman and Ryan Adams is suggested to me by Gonzalo Mena.

In a multivariate Hawkes process, there are $K$ individual point processes and events on one constituent process are more likely to happen right after an event from a neighboring process. To put it in other words, events are ‘induce’ subsequent events according to a network describing their interactions. If we imagine a network of neurons, if neuron A and B are connected and when neuron A fires it can excite neuron B and neuron B has a higher chance of firing. When we want to infer connectivity, if neuron B consistently after neuron A fires, we might  infer that there is likely an excitatory connection between them.

In the work by Linderman and Adams, they extend previous works on continuous time Hawkes process and study the discrete time network Hawkes model. This discretization is motivated by computational concerns. In Simma and Jordan (2010), the authors invoke auxiliary variable $z_{k,n}$ that which denotes the origin of the $n$-th event on process $k$. So the number of auxiliary variables needed is large for highly active networks, which could be a computational bottleneck. But working in the discrete model assuming a time scale $\Delta t$, we can ‘bin’ events and ignore interactions within the same bin. This reduction in number of auxiliary variables improves the run time of inference algorithms such as Gibbs sampler.

Besides Gibbs sampler, Linderman and Adams also derived stochastic variational inference algorithm for the discrete time network Hawkes model. This work focuses on scaling to long duration $T$ and the problem of scaling with size of network $K$ remains open.

References:

• Linderman, S. W., & Adams, R. P. (2015). Scalable bayesian inference for excitatory point process networks. arXiv preprint arXiv:1507.03228.
• Linderman, S., & Adams, R. (2014, January). Discovering latent network structure in point process data. In International Conference on Machine Learning (pp. 1413-1421).
• Simma, A., & Jordan, M. I. (2012). Modeling events with cascades of Poisson processes. arXiv preprint arXiv:1203.3516.
• Steven Morse (2017, June). Python class for Hawkes Process. [Blog post] https://stmorse.github.io/journal/Hawkes-python.html.

## SRN – Bayesian Calibration of Microsimulation Models by Rutter et al.

The Sunday Reading Notes paper for this week is ‘Bayesian Calibration of Microsimulation Models’ by Carolyn Rutter, Diana Miglioretti and James Savarino. This is a 2009 JASA Applications and Case Studies paper.

According to a 2012 Review paper by Rutter et al,

Microsimulation models (MSMs) for health outcomes simulate individual event histories associated with key components of a disease process; these simulated life histories can be aggregated to estimate population-level effects of treatment on disease outcomes and the comparative effectiveness of treatments. Although MSMs are used to address a wide range of research questions, methodological improvements in MSM approaches have been slowed by the lack of communication among modelers. In addition, there are few resources to guide individuals who may wish to use MSM projections to inform decisions.

In this paper, the authors propose a Bayesian method to calibrate microsimulations models, using Markov Chain Monte Carlo. The case study in this paper is the history of colorectal cancer (CRC). In this paper, the authors assume all CRCs arise from an adenoma and the history of CRC consists of four components: 1) adenoma risk, 2) adenoma growth, 3) transition from adenoma to preclinical cancer and 4) transition from preclinical cancel to clinical cancer. These four components are not observed directly and the calibration data consists of prevalence of adenomas and preclinical cancers and the size and/or number of adenomas from many (independent) studies from different years and about different subpopulations and using different colonoscopy methods.

The authors use $\theta$ to denote MSM parameters and these parameters can be separated from $K$ components with independent priors: $\pi(\theta) = \prod_{i=1}^k \pi_i(\theta_i).$ The calibration data come from $N$ independent sources and each follows some distribution  $y_j|\theta \sim f_j(g_j(\theta))$ parametrized by some unknown functions of the MSM parameters. The likelihood is therefore $f(Y | \theta) = f(Y|g(\theta) )= \prod_{j=1}^n f_j(y_j|g_j(\theta))$.

What makes the calibration problem hard is the unknown function $g(\theta)$. Suppose we want to simulate from the posterior distribution of $\theta|Y$ using a Metropolis-Hastings(MH) algorithm, we need to know $r(\theta,\theta^*) = \frac{\pi(\theta)f(y|g(\theta)}{\pi(\theta^*)f(y|g(\theta^*)}$. But because $g$ is unknown, the MH step cannot be performed.

So the authors propose an approximate MH algorithm that includes a step to estimate $g(\theta)$ for both the current value $\theta$ and the proposed value $\theta^*$. To me this feels like an ‘EM’ step: simulate $m$ copies of $\tilde{y}_{ji}$ from $f_j(y_j| g_j(\theta))$ and calculate the MLE $\hat{g}_j(\theta).$ With this approximation, the resulting transition probability function $\hat{\alpha}(\theta,\theta^*)$for the Metropolis-within-Gibbs step on $\theta_i$ is based on $\frac{\pi(\theta_i)}{\pi(\theta_i^*)}\cdot \frac{\prod_{j=1}^N f_j(y_j|\hat{g}_j(\theta^*_i, \theta_{(-i)})}{\prod_{j=1}^n f_j(y_j|\hat{g}_j(\theta))}.$ In the Appendix, the authors prove that this approximation satisfies the detailed-balanced condition in the limit of $m$ goes to infinity.

I think this paper provides an interesting example of how to incorporate data from multiple sources. As the authors point out,

how closely the model should calibrate to observed data is unclear, especially when calibration data are variable and many provide conflicting interest. […] It depends on how modelers trade-off concerns about possibly overparameterizing and overfitting calibration data relative to the importance of exactly replicating observed or expected results.

References:

• Rutter, C. M., Miglioretti, D. L., & Savarino, J. E. (2009). Bayesian calibration of microsimulation models. Journal of the American Statistical Association104(488), 1338-1350.
• Rutter, C. M., Zaslavsky, A. M., & Feuer, E. J. (2011). Dynamic microsimulation models for health outcomes: a review. Medical Decision Making31(1), 10-18.

## SRN – A Geometric Interpretation of the Metropolis-Hastings Algorithm by Billera and Diaconis

Coming back to the Sunday Reading Notes, this week I discuss the paper ‘A Geometric Interpretation of the Metropolis-Hastings Algorithm’ by Louis J. Billera and Persi Diaconis from Statistical Science. This paper is suggested to me by Joe Blitzstein.

In Section 4 of ‘Informed proposals for local MCMC in discrete spaces’ by Giacomo Zanella (see my SRN Part I and II), Zanella mentions that the Metropolis-Hasting acceptance probability function(APF) $\min\left(1,\frac{\pi(y)p(x,y)}{\pi(x)p(y,x)}\right)$ is not the only APF that makes the resulting kernel $\pi$-reversible as long as detailed-balance is satisfied. This comes first as a ‘surprise’ to me as I have never seen another APF in practice. But very quickly I realize that this fact was mentioned in both Stat 213 & Stat 220 at Harvard and I have read about it from Section 5.3 – ‘Why Does the Metropolis Algorithm Work?‘ of ‘Monte Carlo Strategies in Scientific Computing‘ by Jun S. Liu. Unfortunately, I did not pay enough attention. Joe suggested this article to me after I posted on Facebook about being upset with not knowing such a basic fact.

In this Billera and Diaconis paper, the authors focus on the finite state space case $X$ and considers the MH kernel as the projection of stochastic matrices (row sums are all 1 and all entries are non-negative, denoted by$\mathcal{s}(X)$) onto the set of $\pi$-reversible Markov chains (stochastic matrices that satisfy detailed balance $\pi(x)M(x,y) = \pi(y)M(y,x)$, denoted by $R(\pi)).$ If we introduce a metric on the stochastic matrices: $d(K,K') = \sum_{x} \sum_{x\not=y} \pi(x) |K(x,y)-K'(x,y)|$.

The key result in this paper is Theorem 1. The authors prove that the Metropolis maps $M := M(K)(x,y) = \min\left( K(x,y), \frac{\pi(y}{\pi(x)}K(y,x)\right)$ minimizes the distance $d$ from the proposal kernel $K$ to $R(\pi).$ This means that $M(K)$ is the unique closest element in $R(\pi)$ that is coordinate-wise smaller than $K$ on its off-diagonal entries. So $M$ is in a sense the closest reversible kernel to the original kernel $K$.

I think this geometric interpretation offers great intuition about how the MH algorithm works: we start with a kernel $K$ and change it to another kernel with stationary distribution $\pi$. And the change must occur as follows:

from $x$, choose $y$ from $K(x,y)$ and decide to accept $x$ or stay at $y$; this last choice may be stochastic with acceptance probabilty $F(x,y) \in [0,1]$. This gives the new chain with transition probabilities: $K(x,y) F(x,y)$, x \not =y$. The diagonal entries are changed so that each row sums to 1. Indeed the above procedure describes how the MH algorithm works. If we insist on $\pi$-reversibility, we must have $0 \leq 0 \leq \min(1,R(x,y)$ where $R(x,y) = \frac{\pi(y)K(y,x)}{\pi(x)K(x,y)}.$ So the MH choice of APF is one that maximizes the chance of moving from $x$ to $y$. The resulting MH kernel $M$ has the largest spectral gap (1 – second largest eigenvalue) and by Peksun’s theorem must have the minimum asymptotic variance estimating additive functionals. In Remark 3.2, the authors point out if we consider only APF that are functions of $R(x,y)$, then the function must satisfy $g(x) = x g(1/x)$ which is the characteristic of balancing functions in Zanella’s ‘informed proposals’ paper. This paper allows me to study Metropolis-Hastings algorithm from another angle and review facts I have neglected in my coursework. References: • Billera, L. J., & Diaconis, P. (2001). A geometric interpretation of the Metropolis-Hastings algorithm. Statistical Science, 335-339. • Zanella, G. (2017). Informed proposals for local MCMC in discrete spaces. arXiv preprint arXiv:1711.07424. • Liu, J. S. (2008). Monte Carlo strategies in scientific computing. Springer Science & Business Media. ## SRN – Informed proposals for local MCMC in discrete spaces by Zanella (Part II) This is a super delayed Sunday Reading Notes post and today I come back to finish discussing the informed proposals paper by Giacomo Zanella. In Part I of my discussions, I reviewed point-wise informed proposals and locally-informed criterion. In Part II, I hope to focus on asymptotical optimality of locally informed proposals and their simulation studies. The author uses Peskun ordering to compare efficiency of MH schemes. He deduces that ‘locally-balanced proposals are asymptotically optimal in terms of Peskun ordering’ as dimensionality of the underlying state space increases. Conditions for asymptotic optimality are indeed mild (Proposition 1) for the three illustrative examples: 1) independent binary components, 2) weighted permutation and 3) Ising model. In Section 4, Zanella points out a connection between the balancing function and acceptance probability function (APF) for MH algorithms, which I find very interesting. He also shows that the optimal proposal for independent binary variables is Barker choice $g(t) = \frac{t}{1+t}.$ The proof goes by finding the limiting continuous-time process of the MH chain and finding the optimal $g$ for the limiting process. The simulation studies use the illustrative examples: weighted permutations and Ising models. The comparisons are in terms of 1) acceptance rate, 2) number of successful flips per computation time and 3) mixing of some summary statistics. The second criterion concerns the trade-off between computational cost (of calculating the informed proposal) and statistical accuracy (by producing efficient moves). For simple target distributions (such as Uniform), using locally-balanced proposals does not bring much benefits but it achieves a much higher number of flips per unit time for more complicated and ‘rough’ targets. See second row of Figure 1 of the paper. I find it interesting that globally-balanced proposals (aka ‘naively-informed’ or $g(t) = t$) are extremely sensitive to initialization. Looking at the effective sample size (ESS) per time, the chains from GB has much more stable behavior if initialized from stationarity. See GB v.s. GB( station.) in Figure 2. But in Figure 5, this phenomenon does not show up for Ising models: initializing from stationarity does not yield ESS performance comparable to that of LBs. In the simulation studies section, the author emphasizes the cost-vs-efficiency trade-off, which I find very important. I feel I have ignored this aspect of designing MCMC algorithms and should think more about it in my future studies. The author indicates that ‘computations required to sample from locally-balanced proposals are trivially parallelizable’. This is also something very interesting to me and I hope to learn more about multi-core computations during my PhD. In his discussions, the author makes reference to Multiple-Try Metropolis. The connection between LB proposals and MT proposals is not entirely obvious to me, but I intuitively agree with the author’s comment that the weight function in MT serves a very similar purpose as the balancing function term $g\left(\frac{\pi(y)}{\pi(x)}\right)$ in LB. Side note: From my downloaded version of the paper, the transition kernel of the first equation on Page 1 is wrong, because the $Q(x,dy)$ terms needs to be multiplied by its acceptance probability $a(x,y).$ References: • Zanella, G. (2017). Informed proposals for local MCMC in discrete spaces. arXiv preprint arXiv:1711.07424. • Liu, J. S., Liang, F., & Wong, W. H. (2000). The multiple-try method and local optimization in Metropolis sampling. Journal of the American Statistical Association95(449), 121-134. ## SRN – Informed proposals for local MCMC in discrete spaces by Zanella (Part I) This week I am reading ‘Informed proposals for local MCMC in discrete spaces‘ by Giacomo Zanella. This paper is about designing MCMC algorithms for discrete-values high-dimensional parameters, and the goal is similar to the papers discussed in previous posts (Hamming ball sampler & auxiliary-variable HMC). I decide to split the Sunday Reading Notes on this paper into two parts, because I find many interesting ideas in this paper. In this paper, Zanella come up with locally-balanced proposals. Suppose $\pi(x)$ is the target density and $K_{\sigma}(x,dy)$ is an uninformed proposal. We assume that as $\sigma \to 0$ the kernel $K_{\sigma}(x,dy)$ converges to the delta measure. Zanella seeks to modify this uninformed proposal so that it incorporates information about the target $\pi$ and is biased towards areas with higher density. An example of locally-balanced proposals is $Q_{\sqrt{\pi}} (x,dy) = \frac{\sqrt{\pi(y) }K_{\sigma}(x,dy)}{(\sqrt{\pi} * K_{\sigma})(x)}$. This kernel is reversible with respect to $\sqrt{\pi(x)}(\sqrt{\pi} * K_{\sigma})(x)$, which converges to $\pi(x)dx$ as $x \to 0.$ [Note the normalizing constatn is the convolution $\sqrt{\pi(x)}* K_{\sigma} = \int \sqrt{\pi(y)} K_{\sigma}(x,dy)].$] More generally, Zanella considers a class of pointwise informed proposals that has the structure $Q_{g,\sigma} = \frac{1}{Z_{g}}\cdot g\left(\frac{\pi(y)}{\pi(x)}\right) K_{\sigma}(x,dy).$ It is suggested that the function $g$ satisfy $g(t) = t g(1/t).$ I will save the discussion on locally-balanced proposals and Peskun optimality to Part II. In this part, I want to discuss Section 5: Connection to MALA and gradient-based MCMC. In continuous space, the point-wise informed proposal $Q_{g,\sigma}$ would be infeasible to sample from because of the term $g\left(\frac{\pi(y)}{\pi(x)}\right) .$ If we take a first-order Taylor expansion, we would have $Q_{g,\sigma}^{(1)} \propto g \left( \exp ( \nabla \log \pi(x) (y-x)) \right) K_{\sigma}(x,dy).$ If we choose $g(t) = \sqrt{t}$ and $K_{\sigma}(x,\cdot) =N(x,\sigma^2)$, this is the MALA proposal. I find this connection very interesting, although I do not have a good intuition about where this connection comes from. One way to explain it is that gradient-based MCMC in continuous space is using local information to design informed proposals. In the conclusions, the author mentions that this connection should improve robustness of gradient-based MCMC schemes and help with parameter tuning. References:(x) • Zanella, G. (2017). Informed proposals for local MCMC in discrete spaces. arXiv preprint arXiv:1711.07424. ## SRN – Auxiliary-variable Exact HMC samplers for Binary Distributions by Pakman and Paninski It’s time for Sunday Reading Notes again! This week I am discussing another computational statistics paper: ‘Auxiliary-variable Exact Hamiltonian Monte Carlo Samplers for Binary Distributions’ by Ari Pakman and Liam Paninski from Columbia University. This paper is published at NIPS 2013. In the previous Hamming Ball sampler SRN post, the algorithm uses data augmentation to sample from discrete distributions. In this week’s paper, the goal is to sample from generic binary distributions with data augmentation into continuous variables. Let’s say we want to sample from the distribution $p(s)$ defined over $s \in \{\pm 1 \}^d$ given an un-normalized density $f(s).$ The authors propose augmenting with a continuous variable $y \in \mathbb{R}^d$ with joint density $p(s,y) = p(s)p(y|s)$ where $p(y|s)$ is a density we can design but it must satisfy $s_i = \mathrm{sgn}(y_i)$ for all $i = 1,\cdots,d.$ The marginal distribution of$y$is$p(y) = p(s)p(y|s)$as a result of this constraint. It turns out that at this point we transformed a d-dimentional binary problem on $s$ into a d-dimensional continuous problem on $y$. To sample from $y$, the authors suggest using Hamiltonian Monte Carlo, the potential energy is $U(y) = - \log p(y) = -\log p(y|s) - log f(s)$ and the kinetic energy terms is $K(q) = /2.$ The HMC sampler involves simulating a trajectory of $y$ that preserves the Hamiltonian $H(y,q) = U(y) + K(q)$ and typically leap-frog simulation is used. With the constraint in $p(y|s)$, the potential function is defined only piece-wise and we need to be careful when the trajectory crosses regions. o this end, the authors insist we choose $p(y|s)$ such that $\log p(y|s)$ is quadratic, so that the trajectory is deterministic and approximations methods are not necessary. Because $U(y)$ has a jump at $y_i = 0$, the value of momentum $q_i$ should change when we cross boundaries. This is, in my opinion, the most interesting part of the paper. Suppose at time $t_j$ we have $y_j = 0$, then a change in trajectory must happen and let’s say the momentum just before and after $y_j = 0$ are $q_j(t_j^-)$ and $q_j(t_j^+).$ Conservation of energy says we must have $q_j^2(t_j^+)/2+ U(y_j = 0, s_j = -1) = q_j^2(t_j^-)/ 2+ U(y_j = 0, s_j = +1)$ if $y_j <0$ before the $y_j = 0.$ From this equation, if $q_j^2(t_j^+)>0$ then we continue the trajectory with $q_j(t_j^+) =q_j(t_j^-)$; however, if $q_j^2(t_j^+)<0$ then the particle is reflected from a wall at $y_j = 0$ and the trajectory gets reflected with $q_j(t_j^+) = - q_j(t_j^-).$ The two augmentations mentioned in this paper are Gaussian augmentation and exponential augmentation. Both results in quadratic log likelihood. The Gaussian augmentation is very interesting because there is a fixed order that each coordinate $y_j$ reaches zero and the successive hits occur at $t_j + n \pi.$ The authors makes an observation that: Interestingly, the rate at which wall $y_j = 0$ is crossed coincides with the acceptance rate in a Metropolis algorithm that samples uniformly a value for $i$ and makes a proposal of flipping the binary variable $s_i.$ To me this is a sanity check rather than a surprise because each coordinate hits the boundary the same number of times and making a decision to continue or to bounce back in $y_j$ is the same as deciding whether we should flip the sign of $s_i.$ But I think the authors give a very help comment pointing out that although the acceptance probability is the same, the method proposed is still different from Metropolis because in HMC the order in which the walls are hit is fixed given the initial velocity, and the values of $q_i^2$ at successive hits of $y_i = 0$ within the same iteration are not independent. What’s interesting for the exponential augmentation method is that particles moves away faster from areas of lower probability. This is certainly a nice feature to have so that the sample mixes well. In the simulation examples, the authors compared Gaussian HMC and Metropolis on 1d and 2d ising models and showed that: 1. ‘the HMC sampler explores faster the samples space once chain has reached equilibrium distribution.’ 2. ‘the HMC sampler is faster in reaching the equilibrium distribution.’ I think the take away from this paper is the continuous data augmentation to sample discrete variables and their dealing with piece-wise defined potential function. Reference: • Pakman, A., & Paninski, L. (2013). Auxiliary-variable exact Hamiltonian Monte Carlo samplers for binary distributions. In Advances in neural information processing systems (pp. 2490-2498). • Neal, R. M. (2011). MCMC using Hamiltonian dynamics. Handbook of Markov Chain Monte Carlo2(11), 2. ## SRN – The Bayesian Lasso by Park and Casella ‘The Bayesian Lasso’ paper by Park and Casella has been on my desk for a while. Thanks to the Sunday Reading Notes (SRN) series, I finally sit down to read and think about this paper. Lasso (Least absolute shrinkage and selection operator) is a regression method where comparing to ordinary least squares some estimators shrinks to zero while others are set to zero. Lasso is able to do both variable selection (done with step-wise regression before Lasso) and shrinkage to avoid overfitting (for example with ridge regression) at the same time. The objective function for Lasso is $\min_{\beta} (y-X\beta)^T(y-X\beta) + \lambda \sum_{j=1}^p |\beta_j|.$ In the 1996 paper, Tibshirani points out that Lasso estimates can be interpreted as posterior mode estimates (MAP) when we put i.i.d. Lapalace priors ($\pi(\beta) \propto \prod_{j=1}^p \exp(-\lambda |\beta_j|).$ When I took the Bayesian Data Analysis class (STAT 220 at Harvard), our textbook BDA3 contains an exercise on Lasso regularization and it claims that ‘a fully Bayesian lasso is the same model as lasso but assigning a hyperprior to $\lambda.$‘ But ‘The Bayesian Lasso’ paper sets up the hierarchy with a different route: The full conditional distributions on $\beta, \sigma^2$ and $\vec{\tau^2}$ have closed-form solutions and are provided in Section 2 of the paper. In Section 3, the authors discuss ways of choosing the Lasso parameter: 1) Empirical Bayes by marginal maximum likelihood: iteratively update $\lambda^{(k)} = \sqrt{\frac{2p}{\sum_{j=1}^p \mathbb{E}_{\lambda^{(k-1)}} [\tau_j^2|y] }}$; 2) hyper-priors on $\lambda^2$. The examples in this paper come from the diabetes dataset from the Tibshirani 1996 paper and can be found in the ‘lars‘ R package. On this dataset the results from a Bayesian lasso are very similar to a regular Lasso, as seen in Figure 1 & 2 from the paper or the plot below where I borrowed code from the Rdocumentation of the ‘monomvn‘ R package. In the plot above, we can see the shrinkage effect and the variable selection happening. Compared to ordinary least squares (green), the both the lasso estimates and samples from Bayesian lasso shrink towards zero (except for b.3) and the lasso estimate fixes some parameters (b.1,2,5,6,8,10) at zero. Comparing to Lasso where we do not have uncertainty estimates unless with bootstrap, the Bayesian lasso is providing these uncertainty estimates. References: Hastie, T., & Efron, B. (2013). lars: Least angle regression, lasso and forward stagewise, 2013. Gramacy, R. B., & Gramacy, M. R. B. (2013). Package ‘monomvn’. Park, T., & Casella, G. (2008). The bayesian lasso. Journal of the American Statistical Association103(482), 681-686. Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society. Series B (Methodological), 267-288. ## SRN – The Hamming Ball Sampler by Titsias and Yau My Sunday Reading Notes (SRN) this semester will mostly be about Bayesian Computations. This week’s post is on The Hamming Ball Sampler proposed by Titsias and Yau.The hamming ball sampler is a MCMC algorithm for high-dimensional discrete-valued vectors or matrices. While reading this paper, I also found a blog post about it from Xi’an’s OG, which provided some high-level intuitions and background knowledge. The paper considers a state space model with discrete hidden space $X$ with parameters $\theta$ and observations $y.$ Factorial Hidden Markov Model (fHMM) is an example of such a model. In state space models, the complete data likelihood can be factorized with $p(y,X,\theta) = p(X,\theta) \prod_{i=1}^N p(y_i|X,\theta).$ Given some prior, we want to sample from the posterior distribution $X,\theta | y.$ When the dimension of $X$ is large, we would suffer from ‘the curse of dimensionality’. Using a Gibbs sampler, we can iteratively sample $\theta \sim \cdot | X,y$ and$\theta X \sim \cdot | \theta,y$. Because the dimension of$X\$ is high, we should also consider blocked Gibbs sampling on $X$ by for example updating one row (or column) of $X$ at a time. While this is conceptually straightforward and potentially also easy to implement, as the authors pointed out:

Conditional sampling may lead to an inability to escape from local modes in the posterior distribution particularly if the elements of $X$ exhibit strong correlations with each other and together with $\theta$.

The Hamming Ball Sampler (HBS) introduces an auxiliary variable $U$ that has the same dimension as the latent space $X$. The augmented joint probability can be factorized with as $p(y,X,\theta,U) = p(U|X) p(y,X,\theta).$ The conditional distribution $p(U|X)$ is chosen to be uniform over a neighborhood set $\mathcal{H}_m(X).$ This set $\mathcal{H}_m(X)$ is a Hamming Ball and it basically says that if $U,X$ are $K \times N$ matrices, then $U$ and $X$ can be different on at most $m$ positions among the $K$ rows. With the auxiliary variable $U$, the Hamming Ball Sampler alternate between the steps $U \gets p(U|X)$ and $(\theta, X) \gets p(\theta,X|U,y).$

The Hamming Ball Sampler is like slice-sampling in discrete spaces, and each Hamming Ball $\mathcal{H}_m(X)$ is a slice. Introducing the slice introduces random exploration, and makes it easier to escape from local modes. For the simplest example where $X$ is a $K \times N$ matrix and the hamming distance is defined the the number of different elements each column, if we set $m = K/2$ then we can potentially change all elements of $X$ in one update. But when $m$ is large, the algorithm complexity also increases.

In this paper the authors provided several numerical examples comparing the Hamming Ball Sampler with block Gibbs Samplers. In the fHMM examples (Figure 4 in the paper) we can see that HBS with $m = 2$ or $3$ achieves having joint posterior density much faster than the block Gibbs Samplers. They also conclude that HB-2 is best balances computational time and sampling efficiency.

Reference:

Titsias, M. K., & Yau, C. (2017). The Hamming ball sampler. Journal of the American Statistical Association112(520), 1598-1611.

Ghahramani, Z., & Jordan, M. I. (1996). Factorial hidden Markov models. In Advances in Neural Information Processing Systems (pp. 472-478).

## SRN – Should I follow the crowd? by Canamares and Castells from SIGIR’18

It’s time for Sunday Reading Notes again. This past week I have been reading the paper ‘Should I Follow the Crowd? A Probabilistic Analysis of the Effectiveness of Popularity in Recommender Systems‘ by Rocio Canamares and Pablo Castells. It won the best paper award at SIGIR 2018!

Current state of the art recommender systems tend to recommend popular items to their users. As the paper points out in its abstract:

The fundamental questions remains open though whether popularity is really a bias we should avoid or not, whether it could be a useful and reliable signal in recommendation, or it may be unfairly rewarded by the experimentation biases.

This paper is concerned with un-personalized recommendations evaluated in off-line experiments. The dataset consists of rated items only and is randomly split into training and test. The ratings takes binary values (positive rating / negative rating). For every item, popularity is defined in terms of number of positive ratings, which is different from average rating. In order to make recommendations, we want to measure ‘relevance‘, which is a binary random variable and $res(i) = 1$ if the user likes item $i.$ From this set-up, we have $pop(i) \sim p(rel,rate|i)$ and $avg(i) \sim p(rel|rate,i).$ But we cannot directly measure $p(rel|i).$

The author uses the metric ‘expected precision’ as the metric for recommendations and emphasizes that true precision (cannot be measured from offline experiments) is different from observed precision (measured with rating from the test set). The authors find the optimal ranking function for both true precision and observed precision. Using relevance optimizes the true precision : $f(i) = p(rel|i)\frac{1-\rho p(rated|rel,i)}{1-\rho p(rated|i)}$ is the optimal ranking function for $\mathbb{E}[P@1|f]$, and as a result of experimental design the expected observed precision $\mathbb{E}[\hat{p}@1|f]$ is optimized by $\hat{f}(i) \sim p(rel|i)\frac{p(rated|rel,i)}{1-\rho p(rated|i)}.$ As we can see, popularity has advantage in optimizing the expected observed precision.

Because customers have a tendency to rate items that they like, the rating information is not missing at random. To understand rated given relevance and item, the authors gives two simple conditions: conditional item independence and conditional relevance independence. Under both conditions, using $pop(i)$ optimizes the expected observed precision and using $avg(i)$ optimized the expected true precision.

Because we can only measure the expected observed precision with offline experiments and because popularity has advantage optimizing $\mathbb{E}(\hat{P}@1)$, the current recommender systems that are based on offline evaluations favors popularity. Although not all recommender systems are designed the same way as described in this paper, I believe this elegant framework provides intuitions because the ‘popularity of popularity’.

Acknowledging that a user can rate an item only if he or she has bought the item, the authors further consider ‘discovery bias’, because rating depends on all of relevance, discovery and item. This dependencies are characterized in Figure 2 from the paper.

In a realistic senario, our data should fall into category 4 – ‘no assumption’. In this case the expected precision can be approximated with Monte Carlo integration.

The key results and experiment are summaries in Table 1 and Figure 5 in the paper.

Besides the probability based framework, what I really like about this paper is that the authors designed and collected a crowdsourced dataset that makes real data experiments of relevance-independent discovery and item-independent discovery possible. After reading going through the math and the experiments, I feel quite convinced that

average rating may be in fact a better, safer, more robust signal than the number of positive ratings in terms of true achieved accuracy in most general situations.

Although the metric $\mathbb{E}(P@1|R)$ seems too simple because essentially it is like we can only recommend one item to a user, it is a good and tractable measure to start with. The authors suggest that it empirically consistently generalize other metric such as nDCG@k. However I am not sure how much I would agree with this point, because nDCG@k cares much beyond the top ranked item.

Overall I really like this paper and I think it touches many fundamental problems in popularity bias and provides enough mathematical clairty. I wonder if this paper suggests we should do more online experiments for recommender systems because true accuracy cannot be measured with offline experiments. I am also eager to see what the author has to say about temporal data splitting. Lastly I hope the authors talk about what we should do with the very common ‘5-star’ rating system.

Reference:

1. Rocío Cañamares and Pablo Castells. 2018. Should I Follow the Crowd? A Prob- abilistic Analysis of the Effectiveness of Popularity in Recommender Systems. In Proceedings of ACM SIGIR ’18, July 8–12, 2018, Ann Arbor, MI, USA.
ACM, NY, NY, USA, 10 pages. https://doi.org/10.1145/3209978.3210014

format: plain


text:
# Area bounded by the curve

Question:

Area bounded by the curve $y=x^{3}$, the $x$-axis and the ordinates $x=-2$ and $x=1$ is

A. $-9$

B. $-\frac{15}{4}$

C. $\frac{15}{4}$

D. $\frac{17}{4}$

Solution:

Required Area $=\left|\int_{-2}^{0} y d x\right|+\int_{0}^{1} y d x$

$=\left|\int_{-2}^{0} x^{3} d x\right|+\int_{0}^{1} x^{3} d x$

$=\left|\left[\frac{x^{4}}{4}\right]_{-2}^{0}\right|+\left[\frac{x^{4}}{4}\right]_{0}^{1}$

$=\left|\left[0-\frac{16}{4}\right]\right|+\left[\frac{1}{4}-0\right]$

$=|-4|+\frac{1}{4}$

$=4+\frac{1}{4}$

$=\frac{17}{4}$ sq. units

Thus, the correct answer is D.


text:
• July 12th 2010, 01:04 PM
jess0517
Heyy Forum
Im having difficulty figuring out this question soo any help would be greatly appriciated
Thanks so much (Happy)

Attachment 18180
• July 12th 2010, 02:05 PM
roninpro
Did you try working out the product for different values of $n$?
• July 12th 2010, 02:07 PM
jess0517
Quote:

Originally Posted by roninpro
Did you try working out the product for different values of $n$?

Yes i did but i still couldnt seem to figure it out
• July 12th 2010, 02:08 PM
roninpro
I computed the values for $2\leq n\leq 20$:

$\frac{3}{4},\frac{2}{3},\frac{5}{8},\frac{3}{5},\f rac{7}{12},\frac{4}{7},\frac{9}{16},\frac{5}{9},\f rac{11}{20},\frac{6}{11},\frac{13}{24},\frac{7}{13 },\frac{15}{28},\frac{8}{15},\frac{17}{32},\frac{9 }{17},\frac{19}{36},\frac{10}{19},\frac{21}{40}$

Do you see a pattern, at least in the denominators?
• July 12th 2010, 02:10 PM
tonio
Quote:

Originally Posted by jess0517
Heyy Forum
Im having difficulty figuring out this question soo any help would be greatly appriciated
Thanks so much (Happy)

Attachment 18180

Do some particular cases: $n=2\Longrightarrow 1-\frac{1}{4}=\frac{3}{4}\,,\,\,n=3\Longrightarrow \frac{3}{4}\cdot\frac{8}{9}=\frac{2}{3}$ , $n=4\Longrightarrow \frac{2}{3}\cdot \frac{15}{16}=\frac{5}{8}$ ,

etc., and now separate in odd and even n's...can you see a pretty clear patern for each case?

Tonio
• July 12th 2010, 03:57 PM
Soroban
Hello, jess0517!

Quote:

Find a prove a formula for: . $\displaystyle{\prod ^n_{i=2}\left(1 - \frac{1}{i^2}\right) }$

I cranked out the first few partial products:

. . $\begin{array}{cccc}
n & P(n) \\ \hline \\[-4mm]
2 & \frac{3}{4} \\ \\[-4mm]
3 & \frac{4}{6}\\ \\ [-4mm]
4 & \frac{5}{8}\\ \\[-4mm]
5 & \frac{6}{10}\\ \\[-4mm]
6 & \frac{7}{12} \\ \\[-4mm]
7 & \frac{8}{14} \\
\vdots & \vdots \end{array}$

It appears that: . $P(n) \:=\:\dfrac{n+1}{2n}$

I'll let you supply the proof.

• July 12th 2010, 04:12 PM
melese
Direct computation.
I assume "find and prove" means that induction is involved.

But anyway you could find the value of $\prod_{i=2}^{n}(1-\frac{1}{i^2})$ by direct manipulation of the terms of the product $(1-\frac{1}{2^2})(1-\frac{1}{3^2})...(1-\frac{1}{n^2})$.
• July 13th 2010, 01:21 AM
Opalg
Notice that $1-\dfrac1{i^2} = \dfrac{i^2-1}{i^2} = \dfrac{(i-1)(i+1)}{i^2}$. Therefore

$\left(1-\dfrac{1}{2^2}\right)\left(1-\dfrac{1}{3^2}\right)\ldots\left(1-\dfrac{1}{n^2}\right) = \dfrac{1\cdot3}{2^2} \cdot \dfrac{2\cdot4}{3^2} \cdot \dfrac{3\cdot5}{4^2} \cdots\dfrac{(n-1)(n+1)}{n^2}.$

Now start cancelling: each of the two factors in the numerators cancels with a factor in a neighbouring denominator. The only terms left uncancelled are $\frac12$ at the start and $\frac{n+1}n$ at the end.
• July 13th 2010, 11:03 AM
jess0517
Quote:

Originally Posted by Soroban
Hello, jess0517!

I cranked out the first few partial products:

. . $\begin{array}{cccc}
n & P(n) \\ \hline \\[-4mm]
2 & \frac{3}{4} \\ \\[-4mm]
3 & \frac{4}{6}\\ \\ [-4mm]
4 & \frac{5}{8}\\ \\[-4mm]
5 & \frac{6}{10}\\ \\[-4mm]
6 & \frac{7}{12} \\ \\[-4mm]
7 & \frac{8}{14} \\
\vdots & \vdots \end{array}$

It appears that: . $P(n) \:=\:\dfrac{n+1}{2n}$

I'll let you supply the proof.

So using induction would this be correct?.. im not to sure how to write it out formaly on this site but this is how i did it:

[(k+1)+1]/2k =[k+2]/2k = 1/2+1/k = [k+2]/2k ?
Obviously adding a formal base step, induction hypothesis and induction step
• July 14th 2010, 03:26 AM
mr fantastic
Thread closed due to this member deleting questions after getting help.


text:
# Transactions

Each Ergo transaction is an atomic state transition operation.

• It destroys a box from the state and creates new ones.
• If the transaction is spending boxes protected by some non-trivial scripts, its inputs should also contain proof of spending correctness - context extension (user-defined key-value map) and data inputs (links to existing boxes in the state) that may be used during script reduction to crypto, signatures that satisfies the remaining cryptographic protection of the script.
• Transactions are not encrypted, so it is possible to browse and view every transaction ever collected into a block.

Each transaction executed on Ergo consists of these three things.

• One or more Input boxes (source of funds).
• These boxes must already exist and will be destroyed.
• The guard script in each of these boxes will be evaluated and must return true for the transaction to be considered valid,
• One or more Output boxes (destination of funds).
• These boxes will be created.
• Zero or more Data-Inputs boxes.
• These are additional boxes whose data can be referenced and used by smart contracts of the inputs.
• The guard script in these boxes will not be evaluated.

Data inputs are unique to Ergo and not yet present in other extended-UTXO systems. Multiple transactions can share a data-input box, and it will store only a single reference to the box in the block.

We can also spend a data-input box in the same transaction as long as it existed before the transaction was applied. As an example, the box with id

d2b9b6536287b242f436436ce5a1e4a117d7b4843a13ce3abe3168bff99924a1

was used as both an input and a data input in this transaction.

While the use of data-inputs may not be immediately apparent, they play a major role in making Ergo more friendly to DeFi applications where we want to refer to a box without needing (or having the ability) to spend it, such as in decentralized order-books (DEX).

For instance, the above transaction used a "timestamping service" to timestamp a box provided as data input.

A script in Ergo can refer to other boxes in the transaction. For instance, the code snippet INPUTS(0).value > 10000 && OUTPUTS(1).value > 20000 in any of the inputs boxes would enforce that the first input and the second output boxes must have a value greater than 10000 and 20000, respectively.

For a comparison between the logic used in eUTXO and account-based models, please see Off Chain Logic & eUTXO and a model transaction

### Box Format

A box is made of registers (and nothing but registers!), we allow every box in the system to have up to 10 registers. We denote the registers as R_0,R_1,...,R_9. From these registers, four are filled with mandatory values: R_0 contains monetary value of a box, R_1 contains serialized guard script, R_2 contains tokens, R_3 contains declared creation height, unique identifier of transaction which created the coin and also an index of the box in the transaction.

Each register is an expression in sigma language. Thus the registers are typed: every register contains a value of some type. Types are defined in TODO. The value should be evaluated (i.e. it should be a concrete constant value, not a function of a known output type).

We introduce extract({}) function, which is reading contents of a register, for example, extract({c, R_0}) extracts monetary value from the box c.

Box bytes used to obtain the box identifier, build authenticated tree for the state, and build a transaction, are to be formed as follows:

• monetary value. We use VLQ-encoded unsigned long value to store monetary value of the box
• bytes of a script. To see how the script is serialized, see (TODO). The script is to be represented as register R1 by wrapping its bytes are constant array of constant bytes.
• creation height VLQ-encoded unsigned integer value
• number of tokens which box is carrying. Represented as a one-byte unsigned integer.
• tokens. A box can carry multiple tokens. A single record in this field is represented as a tuple token\_identifier -> amount, where identifier is of 32 bytes and amount is VLQ-encoded integer.
• number of additional registers. Extra registers should come in order (R4, ..., etc), so this number, represented as 1-byte unsigned value, defines how much non-empty registers are coming after mandatory ones. If the number is zero, next field is missed.
• additional registers. Extra registers are serialized without any delimiters. Each register is serialized as a sigmaexpression.
• transaction identifier. 32-bytes long identifier of a transaction which created the box
• index of a transaction output. VLQ-encoded index of the box in the transaction outputs.

### Box candidate

Here we describe difference between a box and a box candidate. A box has a unique identifier to be defined deterministically from its contents. Thus we need to have different identifiers for boxs of the same meaning, even if they are created by the same transaction. We also require a box to have an identifier which is derived solely from box contents, thus we can not use (transaction_id, output_id) pair as Bitcoin Core implementation is doing.

To solve the issue we split concepts of a box and a box candidate. A box candidate is defining semantics of the corresponding box i.e. has the same values for all the registers except of the register R_3 which is set to be (creation\_height, transaction\_id || output\_index) for a box and (creation\_height, 0^{34*8}) (so instead of real transaction id and output index, a zero-bit string of 34 bytes is used) for a box candidate.

### Transaction Format

Ergo transaction consists of 3 parts:

• inputs - links to boxs that will be removed from the state during the transaction application. Every inputs consists of box id, proof for final sigma proposition of this box protecting script and a context extension to be used during script evaluation.
• data inputs - links to boxs that won't be removed from the state, but will be available in context of regular inputs scripts.
• outputs - new boxs that will be included into the state during the transaction application.

Transaction bytes are to be formed as follows:

• inputs number - VLQ-encoded number of inputs.
• inputs - every input is represented as 32-byte id of a box to be spent, VLQ-encoded length of signature, signature itself, VLQ-encoded number of key-value pairs of context extension, and context extension pairs, that are 1-byte key and values serialized as a sigmaexpression
• number of data inputs - VLQ-encoded number of data inputs.
• data inputs - 32-byte length ids of data boxes
• distinct tokens number - number of distinct tokens in the transaction, represented as 1 byte unsigned integer.
• token ids - 32-byte length ids of tokens in the transaction
• outputs number - VLQ-encoded number of transaction outputs
• boxcandidates - every coin candidates are serialized in the same way, as box bytes from 4.1 section, but transaction identifier and index of a transaction output are missed, and also tokens are represented as pairs index -> amount, where index is 1-byte index of token in token ids section

Inputs signatures should sign a bytesToSign(tx) message, that is calculated as transaction bytes, as if all it's signatures are empty (and thus VLQ-encoded length of signature equals to 0). Transaction id is calculated as a Blake2b256 hash from message to sign.

### Transaction Merkle Tree

Like a miner in the Bitcoin protocol is building a Merkle tree of block transactions, as well as a Merkle tree of transaction witnesses (after the Segwit upgrade), in Ergo, a miner should build a Merkle tree (and include a correct root hash of the tree into a block header), which is in case of Ergo combines both transactions and their respective spending proofs.

This tree is to be constructed as follows. A data block under a leaf of the tree could be empty or 64 bytes in length. Data of 64 bytes contains identifier of the transaction (256-bits digest of transaction bytes without spending proofs) and 256 bits of a digest of all the spending proofs for the transaction combined. Data for i-th transaction in the block (starting from 0) is authenticated by the i-th leaf. A leaf is hash(0 || pos || data), if the data is not empty  (we do add prefix for domain separation), or null otherwise. Here, pos is a position of the transaction in the block. For internal nodes, a node is hash(1 || left\_child || right\_child), if either left child or right child of the node is not null, null othewise. If root hash is null, we are writing all zeros (of hash function output length) instead of it.

### Signing A Transaction

To spend a box a spending transaction tx has as an input, one needs to use bytesToSign(tx) (note that different inputs can be signed in parallel, however, the coins being spent are to be specified before signing), as well as the current state of the blockchain, or context. The signer also can extend the context by putting values there.

By having this data, a signer (or a prover) of an input first reduces the guarding proposition for the input box by evaluating, it using the context. Possible results of the reduction are:

• abort if estimated upper-bound cost of evaluation (and verification) is too high.
• true means that the box is spendable by anyone
• false means that the box is not spendable at all (at least according to the current context)
• expression still containing predicates over the context. That means context is not enough to evaluate some predicates over it. Prover can look into its own not revealed yet secrets in order to extend context. If the secrets are found, prover is reducing the expression further and doing the next step, if there is nothing more to evaluate. Otherwise the prover aborts.
• expression containing only expressions over secret information provable via \Sigma-protocols. This is the most common case, and we will explain it in detail further.

We are having possible complex expression, like dlog(x_1) \lor (dlog(x2) /\ dlog(x3)), where dlog(x) means "prove me knowledge of a secret w, such as for a known group with generator g, g^w = x, via a non-interactive form of the Schnorr protocol". Internally, this exression is represented as a tree (TODO). This proof is to be proven and then serialized into a binary spending proof (which could be included into a transaction) as follows:

Proving steps for a tree:

1. bottom-up: mark every node real or simulated, according to the following rule. DLogNode -- if you know the secret, then real, else simulated. \lor: if at least one child real, then real; else simulated. \land: if at least one child simulated, then simulated; else real.

Note that all descendants of a simulated node will be later simulated, even if they were marked as real. This is what the next step will do.

Root should end up real according to this rule -- else you won't be able to carry out the proof in the end.

1. top-down: mark every child of a simulated node \"simulated.\" If two or more more children of a real \lor are real, mark all but one simulated.
2. top-down: compute a challenge for every simulated child of every \lor and \land, according to the following rules. If \lor, then every simulated child gets a fresh random challenge. If \land (which means \land itself is simulated, and all its children are), then every child gets the same challenge as the \land.
3. bottom-up: For every simulated leaf, simulate a response and a commitment (i.e., second and first prover message) according to the Schnorr simulator. For every real leaf, compute the commitment (i.e., first prover message) according to the Schnorr protocol. For every \lor/\land node, let the commitment be the union (as a set) of commitments below it.
4. Compute the Schnorr challenge as the hash of the commitment of the root (plus other inputs -- probably the tree being proven and the message).
5. top-down: compute the challenge for every real child of every real \lor and \land, as follows. If \lor, then the challenge for the one real child of \lor is equal to the XOR of the challenge of \lor and the challenges for all the simulated children of \lor. If \land, then the challenge for every real child of \land is equal to the the challenge of the \land.

Note that simulated \land and \lor have only simulated descendants, so no need to recurse down from them.

Now, how to get a flat binary string containing (e, z) pairs (challenge and prover's response for a leafsub-protocol) from the tree:

### Transaction Validation Rules

We split validation of a single transaction into two stages. There are stateless checks which could be done by the transaction only being presented. Stateful checks are requiring knowledge of the current state, in the form of the whole UTXO set or a part of it, namely concrete boxes a transaction is destroying along with proof of authenticity for them ( against a root hash included into a last block header).

Stateless checks are:

• a transaction must spend at a least one input and create at least one output. A transaction spends no more than 32767 inputs and creates no more than 32767 outputs.
• all the output amounts must be non-negative.
• an output can not contain more than 4 assets. All the assets amounts must be positive.
• transaction outputs collectively could not contain more than 16 assets.

Notes

• Should we allow 0-value iutputs?
• Check box and transaction sizes
• describe precisely during https://github.com/ergoplatform/ergo/issues/581

Stateful checks are:

• all the input boxes are members of the UTXO set or where created by other transactions of this block.
• all the data input boxes are members of the UTXO set or where created by other transactions of this block.
• total input and output ergo amounts must be the same. Adding up should be done with overflow checks.
• all the inputs have valid spending proofs.
• total transaction cost which consists of cost of all spending proofs verification plus the cost of all tokens containing in transaction inputs and outputs validation (calculated as (\sum_{i=1}^{n_{in}} m_{i} + m_{tx} + \sum_{i=1}^{n_{out}} k_{i} + k_{tx}) * e, where n_{in} - number of inputs, m_{i} - number of tokens in i'th input, m_{tx} - number of tokens in all inputs in total, n_{out} - number of outputs, k_{i} - number of tokens in i'th output, k_{tx} - number of tokens in all outputs in total, e - cost of accessing a single token (adjustable via miners voting)) should not be greater than a limit per block (which is adjustable via miners voting as well).
• for each kind of asset in the outputs, total output amount for the asset should be no more than the total input amount, if the asset identifier is not equals to identifier of the first input; otherwise, the total output amount must be positive. The latter case corresponds to issuance of a new asset, while the former sets asset preservation rule.

Please note that for total input amount of an asset we do not require for strict equality of the input and output amounts: the output amount could be less than input amount (or zero).

### Unified Transactions

• fee as boxes
• absence of out-of-thin-air emission in the "coinbase" transaction.

### Full-Block Validation Rules

Below are rules for block validation when a node is verifying transactions (VerifyTransactions = 1)

• every transaction in a block is referencing to inputs from the UTXO set or created by previous transactions in the block.
• Please note that it is not possible for an input to refer to an output of some follow-up transaction of the block.
• every transaction in a block is valid (see Section 4.6 for transaction validation rules).
• total cost of validation of all the inputs of all the transactions in the block is no more than allowed limit.
• root hash of the authenticated UTXO set after application of the block transactions is the same as in the header.
• for a node keeping UTXO, hash of the calcualted state transformations proof is the same as announced in the header of the block.


text:
# Table Asian Handicap Ykkonen

Table
LIVE
All Home Away

Table games teams start match Handicap (team starts the match with a majority or loss 0.5,1.5,2.5 or 3.5 goals). By default, sorts the tables by winning matches with Handicap-0.5

Team handicap -0.5 handicap -1.5 handicap -2.5 handicap +0.5 handicap +1.5 handicap +2.5 H2H
# Team GP W L W L W L W L W L W L H2H
1 VPS 0 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%
2 Mikkelin Palloilijat 0 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%
3 Musan Salama 0 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%
4 MYPA 0 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%
5 SJK Akatemia 0 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%
6 KPV 0 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%
7 IF Gnistan 0 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%
8 AC Oulu 0 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%
9 AC Kajaani 0 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%
10 EIF 0 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%
11 FC KTP 0 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%
12 FF Jaro 0 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0% 0%


text:
# Datasets:financial_phrasebank

Languages: English
Multilinguality: monolingual
Size Categories: 1K<n<10K
Language Creators: found
Annotations Creators: expert-generated
Source Datasets: original
Dataset Preview
sentence (string)label (class label)
"According to Gran , the company has no plans to move all production to Russia , although that is where the company is growing ."
1 (neutral)
"For the last quarter of 2010 , Componenta 's net sales doubled to EUR131m from EUR76m for the same period a year earlier , while it moved to a zero pre-tax profit from a pre-tax loss of EUR7m ."
2 (positive)
"In the third quarter of 2010 , net sales increased by 5.2 % to EUR 205.5 mn , and operating profit by 34.9 % to EUR 23.5 mn ."
2 (positive)
"Operating profit rose to EUR 13.1 mn from EUR 8.7 mn in the corresponding period in 2007 representing 7.7 % of net sales ."
2 (positive)
"Operating profit totalled EUR 21.1 mn , up from EUR 18.6 mn in 2007 , representing 9.7 % of net sales ."
2 (positive)
"Finnish Talentum reports its operating profit increased to EUR 20.5 mn in 2005 from EUR 9.3 mn in 2004 , and net sales totaled EUR 103.3 mn , up from EUR 96.4 mn ."
2 (positive)
"Clothing retail chain Sepp+ñl+ñ 's sales increased by 8 % to EUR 155.2 mn , and operating profit rose to EUR 31.1 mn from EUR 17.1 mn in 2004 ."
2 (positive)
"Consolidated net sales increased 16 % to reach EUR74 .8 m , while operating profit amounted to EUR0 .9 m compared to a loss of EUR0 .7 m in the prior year period ."
2 (positive)
"Foundries division reports its sales increased by 9.7 % to EUR 63.1 mn from EUR 57.5 mn in the corresponding period in 2006 , and sales of the Machine Shop division increased by 16.4 % to EUR 41.2 mn from EUR 35.4 mn in the corresponding period in 2006 ."
2 (positive)
"HELSINKI ( AFX ) - Shares closed higher , led by Nokia after it announced plans to team up with Sanyo to manufacture 3G handsets , and by Nokian Tyres after its fourth-quarter earnings report beat analysts ' expectations , dealers said ."
2 (positive)
"Its board of directors will propose a dividend of EUR0 .12 per share for 2010 , up from the EUR0 .08 per share paid in 2009 ."
2 (positive)
"MegaFon 's subscriber base increased 16.1 % in 2009 to 50.5 million users as of December 31 , while its market share by the number of customers amounted to 24 % as of late 2009 , up from 23 % as of late 2008 , according to TeliaSonera estimates ."
2 (positive)
"Net income from life insurance doubled to EUR 6.8 mn from EUR 3.2 mn , and net income from non-life insurance rose to EUR 5.2 mn from EUR 1.5 mn in the corresponding period in 2009 ."
2 (positive)
"Net sales increased to EUR193 .3 m from EUR179 .9 m and pretax profit rose by 34.2 % to EUR43 .1 m. ( EUR1 = USD1 .4 )"
2 (positive)
"Net sales surged by 18.5 % to EUR167 .8 m. Teleste said that EUR20 .4 m , or 12.2 % , of the sales came from the acquisitions made in 2009 ."
2 (positive)
"Nordea Group 's operating profit increased in 2010 by 18 percent year-on-year to 3.64 billion euros and total revenue by 3 percent to 9.33 billion euros ."
2 (positive)
"Operating profit for the nine-month period increased from EUR13 .6 m , while net sales increased from EUR394 .7 m , as compared to the corresponding period in 2005 ."
2 (positive)
"Operating profit for the three-month period increased from EUR1 .2 m , while revenue increased from EUR20 .2 m , as compared to the corresponding period in 2005 ."
2 (positive)
"The company 's net profit rose 11.4 % on the year to 82.2 million euros in 2005 on sales of 686.5 million euros , 13.8 % up on the year , the company said earlier ."
2 (positive)
"The Lithuanian beer market made up 14.41 million liters in January , a rise of 0.8 percent from the year-earlier figure , the Lithuanian Brewers ' Association reporting citing the results from its members ."
2 (positive)
"Viking Line 's cargo revenue increased by 5.4 % to EUR 21.46 mn , and cargo volume increased by 2.4 % to 70,116 cargo units ."
2 (positive)
"The fair value of the property portfolio doubled as a result of the Kapiteeli acquisition and totalled EUR 2,686.2 1,259.7 million ."
2 (positive)
"10 February 2011 - Finnish media company Sanoma Oyj HEL : SAA1V said yesterday its 2010 net profit almost tripled to EUR297 .3 m from EUR107 .1 m for 2009 and announced a proposal for a raised payout ."
2 (positive)
"A Helsinki : ELIiV today reported EPS of EUR1 .13 for 2009 , an increase over EPS of EUR1 .12 in 2008 ."
2 (positive)
"Commission income increased by 22 % to EUR 4.4 mn , and lending volume rose by 13.5 % ."
2 (positive)
"In January , traffic , measured in revenue passenger kilometres RPK , went up by 3.2 % and capacity , measured in available seat kilometres ASK , rose by 12.2 % ."
2 (positive)
"In January-September 2010 , Fiskars ' net profit went up by 14 % year-on-year to EUR 65.4 million and net sales to EUR 525.3 million from EUR 487.7 million ."
2 (positive)
"Net income from life insurance rose to EUR 16.5 mn from EUR 14.0 mn , and net income from non-life insurance to EUR 22.6 mn from EUR 15.2 mn in 2009 ."
2 (positive)
"Sales have risen in other export markets ."
2 (positive)
"Sales increased due to growing market rates and increased operations ."
2 (positive)
"The agreement strengthens our long-term partnership with Nokia Siemens Networks ."
2 (positive)
"The company 's order book stood at 1.5 bln euro $2.2 bln on September 30 , 2007 , up by 24.2 pct on the year , with international orders amounting to 365 mln euro$ 534.3 mln ."
2 (positive)
"The company said that paper demand increased in all of its main markets , including of publication papers , and that it increased average paper prices by 4 percent compared with last year ."
2 (positive)
"The world 's second largest stainless steel maker said net profit in the three-month period until Dec. 31 surged to euro603 million US$781 million , or euro3 .33 US$ 4.31 per share , from euro172 million , or euro0 .94 per share , the previous year ."
2 (positive)
"Shares of Standard Chartered ( STAN ) rose 1.2 % in the FTSE 100 , while Royal Bank of Scotland ( RBS ) shares rose 2 % and Barclays shares ( BARC ) ( BCS ) were up 1.7 % ."
2 (positive)
"Shares of Nokia Corp. rose Thursday after the cell phone maker said its third-quarter earnings almost doubled and its share of the global handset market increased ."
2 (positive)
"In its financial report , published on Friday , SEB said its net profit soared to SEK6 .745 bn in 2010 from a year-earlier SEK1 .114 bn and proposed a 50 % dividend increase to SEK1 .50 per share ."
2 (positive)
"At the request of Finnish media company Alma Media 's newspapers , research manager Jari Kaivo-oja at the Finland Futures Research Centre at the Turku School of Economics has drawn up a future scenario for Finland 's national economy by using a model developed by the University of Denver ."
1 (neutral)
"STOCK EXCHANGE ANNOUNCEMENT 20 July 2006 1 ( 1 ) BASWARE SHARE SUBSCRIPTIONS WITH WARRANTS AND INCREASE IN SHARE CAPITAL A total of 119 850 shares have been subscribed with BasWare Warrant Program ."
1 (neutral)
"A maximum of 666,104 new shares can further be subscribed for by exercising B options under the 2004 stock option plan ."
1 (neutral)
"Tiimari operates 194 stores in six countries -- including its core Finnish market -- and generated a turnover of 76.5 mln eur in 2005 ."
1 (neutral)
"The acquisition will considerably increase Kemira 's sales and market position in the Russian metal industry coatings market ."
2 (positive)
"In January-September 2007 , Finnlines ' net sales rose to EUR 505.4 mn from EUR 473.5 mn in the corresponding period in 2006 ."
2 (positive)
"Adjusted for changes in the Group structure , the Division 's net sales increased by 1.7 % ."
2 (positive)
"4 February 2011 - Finnish broadband data communication systems provider Teleste Oyj HEL : TLT1V saw its net profit jump to EUR2 .1 m for the last quarter of 2010 from EUR995 ,000 for the same period of 2009 ."
2 (positive)
"Finnish Aktia Group 's operating profit rose to EUR 17.5 mn in the first quarter of 2010 from EUR 8.2 mn in the first quarter of 2009 ."
2 (positive)
"Finnish Bank of +àland 's consolidated net operating profit increased from EUR 4.8 mn in the first quarter of 2005 to EUR 6.4 mn in the first quarter of 2006 ."
2 (positive)
"Finnish financial group Aktia reports operating profit of EUR 44.4 mn in January-September 2009 , up from EUR 37.3 mn in the corresponding period in 2008 ."
2 (positive)
"Finnish high technology provider Vaahto Group reports net sales of EUR 41.8 mn in the accounting period September 2007 - February 2008 , an increase of 11.2 % from a year earlier ."
2 (positive)
"Net sales of Finnish food industry company L+ñnnen Tehtaat 's continuing operations increased by 13 % in 2008 to EUR 349.1 mn from EUR 309.6 mn in 2007 ."
2 (positive)
"Biohit already services many current Genesis customers and the customer base is expected to expand as a result of this agreement ."
2 (positive)
"Both operating profit and turnover for the three-month period increased , respectively from EUR0 .9 m and EUR8 .3 m , as compared to the corresponding period in 2005 ."
2 (positive)
"Circulation revenue has increased by 5 % in Finland and 4 % in Sweden in 2008 ."
2 (positive)
"Clothing chain Sepp+ñl+ñ 's net sales increased by 7.0 % to EUR 30.8 mn ."
2 (positive)
"Construction volumes meanwhile grow at a rate of 10-15 percent annually ."
2 (positive)
"However , Biohit estimates its total net sales will continue to grow in 2009 , and that favourable trends in net sales will lead to a profit in 2009 ."
2 (positive)
"In 2009 , Fiskars ' cash flow from operating activities amounted to EUR121m , up from EUR97m in the previous year ."
2 (positive)
"In Lithuania , operating profit rose to EUR 190,000 from EUR 70,000 in the corresponding period in 2005 ."
2 (positive)
"In the fourth quarter of 2008 , net sales increased by 2 % to EUR 1,050.7 mn from EUR 1,027.0 mn in the fourth quarter of 2007 ."
2 (positive)
"International sales rose by 59.8 % to EUR 1,244.4 mn ."
2 (positive)
"Net sales grew in the period to x20ac 402 million $585US million from x20ac 401 million in 2006 ." 2 (positive) "Net sales increased to EUR655m in April to June 2010 from EUR438m a year earlier ." 2 (positive) "Net sales rose by 25.5 % year-on-year to EUR59 .6 m , as the number of chargers delivered went up by 41 % to 65.9 million pieces ." 2 (positive) "Net sales totaled EUR 93.6 mn , up from EUR 93.2 mn in the corresponding period in 2005 ." 2 (positive) "Operating profit increased by 145.1 % to EUR 8.3 mn from EUR 3.4 mn ." 2 (positive) "Operating profit margin increased from 11.2 % to 11.7 % ." 2 (positive) "Operating profit rose to EUR 3.11 mn from EUR 1.22 mn in the corresponding period in 2009 ." 2 (positive) "Operating profit rose to EUR 5mn from EUR 2.8 mn in the fourth quarter of 2008 ." 2 (positive) "Operating profit was EUR 24.5 mn , up from EUR 23.0 mn ." 2 (positive) "Ramirent 's net sales in the second quarterended June 30 were EURO 128.7 million about U.S.$ 163 million , a 3.3-percent increase compared with EURO 124.6 million for thesecond quarter last year ."
2 (positive)
"Revenue grew by 2 percent to x20ac 580 million \$ 743 million , from x20ac 569 million ."
2 (positive)
"Ruukki 's delivery volumes and selling prices showed favourable development and the company 's comparable net sales grew by 50 % year-on-year to EUR647m , CEO Sakari Tamminen said ."
2 (positive)
"The company 's consolidated operating profit amounted to EUR 15.86 mn , up from EUR 4.14 mn year-on-year ."
2 (positive)
"The Department Store Division reported an increase in sales of 4 per cent ."
2 (positive)
"The fair value of the company 's investment properties grew to EUR 2.803 billion at the end of March 2009 from EUR 2.691 million a year ago ."
2 (positive)
"The last quarter was the best quarter of 2009 in net sales , and the operating margin rose to 12.2 % ."
2 (positive)
"The major breweries increased their domestic beer sales by 4.5 per cent last year , to 256.88 million litres from 245.92 million litres in 2004 ."
2 (positive)
"- Operating profit rose by 26.9 % to EUR 105.8 ( 83.4 ) million ."
2 (positive)
"21 October 2010 - Finnish fishing tackle company Rapala VMC Corp ( HEL : RAP1V ) said today its net profit rose to EUR18 .9 m for the first nine months of 2010 from EUR15 .1 m for the same period a year earlier ."
2 (positive)
"According to Finnish Metso Minerals , the value of the company 's orders has gone up to EUR 1.9 bn in 12 months ."
2 (positive)
"Finnish Bank of +àland reports its operating profit rose to EUR 21.3 mn in the second quarter of 2009 from EUR 6.1 mn in the corresponding period in 2008 ."
2 (positive)
"Finnish financial group Aktia 's operating profit for 2009 increased to EUR 47.0 mn from EUR 6.6 mn in 2008 ."
2 (positive)
"Finnish forest machinery manufacturer Ponsse 's net sales grew to EUR 51.3 mn in the first quarter of 2010 from EUR 37.5 mn in the corresponding period in 2009 ."
2 (positive)
"Finnish KCI Konecranes has raised its net sales growth estimate for 2006 from over 25 % to over 35 % ."
2 (positive)
"According to HKScan Finland , the plan is to increase J+ñrvi-Suomen Portti 's net sales to EUR 80mn to EUR 100mn ."
2 (positive)
"Advertising and circulation revenues grew by 3.4 % and by 0.4 % , respectively ."
2 (positive)
"At the end of March 2007 , the group 's order book was at EUR 39.6 mn , up 42 % from the corresponding period in 2006 ."
2 (positive)
"At the same time profit of the company increased by 10 % in H1 and reached Ls 79,000 ."
2 (positive)
"Both operating profit and net sales for the 12-month period increased , respectively from EUR10 .5 m and EUR28 .8 m , as compared to the financial year 2004 ."
2 (positive)
"Both operating profit and net sales for the 12-month period increased , respectively from EUR20 .8 m and EUR177 .7 m , as compared to the financial year 2004 ."
2 (positive)
"Both operating profit and net sales for the 12-month period increased , respectively from EUR21 .5 m and EUR196 .1 m , as compared to 2005 ."
2 (positive)
"Both operating profit and net sales for the 12-month period increased , respectively from EUR4 .7 m and EUR26 .7 m , as compared to 2004 ."
2 (positive)
"Both operating profit and net sales for the nine-month period increased , respectively by 26.6 % and 3.4 % , as compared to the corresponding period in 2006 ."
2 (positive)
"Both operating profit and net sales for the six-month period increased , respectively , from EUR13 .8 m and EUR143 .6 m , as compared to the corresponding period in 2007 ."
2 (positive)
"Both operating profit and net sales for the six-month period increased , respectively from EUR0 .4 m and EUR3 .2 m , as compared to the corresponding period in 2005 ."
2 (positive)
"Both operating profit and net sales for the six-month period increased , respectively from EUR18 .1 m and EUR127 .6 m , as compared to the corresponding period in 2006 ."
2 (positive)
"Both operating profit and net sales for the six-month period increased , respectively from EUR7 .5 m and EUR655 .5 m , as compared to the corresponding period in 2005 ."
2 (positive)
"Both operating profit and net sales for the three-month period increased , respectively from EUR15 .1 m and EUR131 .5 m , as compared to the corresponding period in 2005 ."
2 (positive)
"Both operating profit and net sales for the three-month period increased , respectively from EUR16 .0 m and EUR139m , as compared to the corresponding quarter in 2006 ."
2 (positive)
"Both operating profit and sales for the three-month period increased , respectively from EUR0 .3 m and EUR13 .1 m , as compared to the corresponding period in 2005 ."
2 (positive)
End of preview (truncated to 100 rows)

# Dataset Card for financial_phrasebank

### Dataset Summary

Polar sentiment dataset of sentences from financial news. The dataset consists of 4840 sentences from English language financial news categorised by sentiment. The dataset is divided by agreement rate of 5-8 annotators.

Sentiment Classification

English

## Dataset Structure

### Data Instances

{ "sentence": "Pharmaceuticals group Orion Corp reported a fall in its third-quarter earnings that were hit by larger expenditures on R&D and marketing .",
"label": "negative"
}

### Data Fields

• sentence: a tokenized line from the dataset
• label: a label corresponding to the class as a string: 'positive', 'negative' or 'neutral'

### Data Splits

There's no train/validation/test split.

However the dataset is available in four possible configurations depending on the percentage of agreement of annotators:

sentences_50agree; Number of instances with >=50% annotator agreement: 4846 sentences_66agree: Number of instances with >=66% annotator agreement: 4217 sentences_75agree: Number of instances with >=75% annotator agreement: 3453 sentences_allagree: Number of instances with 100% annotator agreement: 2264

## Dataset Creation

### Curation Rationale

The key arguments for the low utilization of statistical techniques in financial sentiment analysis have been the difficulty of implementation for practical applications and the lack of high quality training data for building such models. Especially in the case of finance and economic texts, annotated collections are a scarce resource and many are reserved for proprietary use only. To resolve the missing training data problem, we present a collection of ∼ 5000 sentences to establish human-annotated standards for benchmarking alternative modeling techniques.

The objective of the phrase level annotation task was to classify each example sentence into a positive, negative or neutral category by considering only the information explicitly available in the given sentence. Since the study is focused only on financial and economic domains, the annotators were asked to consider the sentences from the view point of an investor only; i.e. whether the news may have positive, negative or neutral influence on the stock price. As a result, sentences which have a sentiment that is not relevant from an economic or financial perspective are considered neutral.

### Source Data

#### Initial Data Collection and Normalization

The corpus used in this paper is made out of English news on all listed companies in OMX Helsinki. The news has been downloaded from the LexisNexis database using an automated web scraper. Out of this news database, a random subset of 10,000 articles was selected to obtain good coverage across small and large companies, companies in different industries, as well as different news sources. Following the approach taken by Maks and Vossen (2010), we excluded all sentences which did not contain any of the lexicon entities. This reduced the overall sample to 53,400 sentences, where each has at least one or more recognized lexicon entity. The sentences were then classified according to the types of entity sequences detected. Finally, a random sample of ∼5000 sentences was chosen to represent the overall news database.

#### Who are the source language producers?

The source data was written by various financial journalists.

### Annotations

#### Annotation process

This release of the financial phrase bank covers a collection of 4840 sentences. The selected collection of phrases was annotated by 16 people with adequate background knowledge on financial markets.

Given the large number of overlapping annotations (5 to 8 annotations per sentence), there are several ways to define a majority vote based gold standard. To provide an objective comparison, we have formed 4 alternative reference datasets based on the strength of majority agreement:

#### Who are the annotators?

Three of the annotators were researchers and the remaining 13 annotators were master's students at Aalto University School of Business with majors primarily in finance, accounting, and economics.

## Considerations for Using the Data

### Discussion of Biases

All annotators were from the same institution and so interannotator agreement should be understood with this taken into account.

### Citation Information

@article{Malo2014GoodDO,
title={Good debt or bad debt: Detecting semantic orientations in economic texts},
author={P. Malo and A. Sinha and P. Korhonen and J. Wallenius and P. Takala},
journal={Journal of the Association for Information Science and Technology},
year={2014},
volume={65}
}

### Contributions

Thanks to @frankier for adding this dataset.