This paper presents what is known as `Sammon's mapping`. This method produces points in any $\mathbb{R}^n$ space using only a distance function between points. You can define any distance function $d^*$ that represents relationships between points. This function can even be non-symmetric. The power is that any relationship encoded into a distance function or distance matrix can be visualized.

For mapping $n$ points from some dimension in another the algorithm starts by generating $n$ random points in the space (called d-space) that you would like to map the points to. You can just pick these at random because they will be moved later. 

The algorithm then performs gradient decent to minimize the *Sammon's stress* which can also be called the objective function.

$$
\text{Sammon's stress} = \frac{1}{
\sum\limits_{i<j} d^{*}_{ij}} 
\sum_{i<j}
\frac{ ( d^{*}_{ij}-d_{ij})^2}
{d^{*}_{ij}}
$$

To minimize this objective function a partial derivative is taken with respect to each dimension of each point in d-space. For each dimension $y$ the distance between points $p$ and $q$ are modified using a scaled partial derivative and a learning rate. The paper calls this a "magic factor" MF but it is referred to today as a learning rate $\lambda$.

$$y_{pq}' = y_{pq}-\lambda \Delta_{pq}$$

The partial is scaled by the second derivative:

$$\Delta_{pq}=\left.\frac{\partial E}{\partial y_{pq}} \middle/  \frac{\partial^2 E}{\partial y_{pq}^2}\right.$$

Using the second derivative might be overkill for this. The objective function should also be minimized using only the first derivative. Possibly using new update rules for stochastic optimization like \cite{conf/colt/DuchiHS10} or \cite{journals/corr/KingmaB14} may be more efficient.

A common problem in phylogenetics is:

1. I have $p(\text{DNA sequences} | \text{tree})$ and $p(\text{tree})$.
2. I've used these to run an MCMC algorithm and generate many (approximate) samples from $p(\text{tree} | \text{DNA sequences})$.
3. I want to evaluate $p(\text{tree} | \text{DNA sequences})$.

The first solution you might think of is to add up how many times you saw each *tree topology* and divide by the total number of MCMC samples; referred to in this paper as *simple sample relative frequencies* (SRF). An obvious problem with this method is that if you didn't happen to sample a tree topology you will assign it zero probability.

This paper focuses on producing a better solution to this problem, by defining a distribution over trees that's easy to fit and provides support over the entire space of tree topologies.

What is a Subsplit Bayesian Network?
==============================

Phylogenies are leaf-labeled bifurcating trees, binary trees with labeled leaves. **Clades** are nonempty subsets of the leaf labels; labeled in the following figure as $C_1 \to C_7$:

https://i.imgur.com/khS3uSo.png

To build a phylogeny, I can just take the full set of leaves and recursively split them into clades as described in the above diagram. This means that the distribution over phylogenies is equivalent to the distribution over clades. To make this distribution tractable, it is typically assumed that clades are conditionally independent given parent clades; called the *Conditional Clade Distribution* (CCD) assumption, attributed here to [Larget][] and [Hohna][].

So, a phylogeny may be described by its clades, this paper proposes that these clades may be described by their **subsplits**; the splitting process placing leaf nodes into one of two clades. Then, the authors note this process is a directed Bayesian network and that this Bayesian network must include all possible clade splits. It is therefore a complete binary tree with depth $N-1$ (where $N$ is the number of leaf nodes).

Fitting This Parameterisation to MCMC Samples
=====================================

Under this parameterisation the likelihood of observing a given tree is:
$$
p(\text{tree}) = p(S_1 = s_{1,k}) \prod_{i>1} p(S_i = s_{i,k} | S_{\pi_i} = s_{\pi_i, k}),
$$
assuming a collection of subsplits $T_k = \{ S_i = s_{i,k}, i \geq 1 \}$. In this definition $S_{\pi_i}$ is index set of parent nodes of $S_i$; ie a subsplit can depend on any of the parent nodes.

The maximum likelihood probabilities for possible subsplits can be solved in closed form; algorithmically involving counting the occurrences of subsplits and dividing by the number of trees observed. If this seems exactly the same as SRF, that's because it is; I [checked the published code to verify this][sbn_ds1].

The authors then consider the case of unrooted trees, where the log likelihood of observed trees can't be easily factorised. They then present a [simple averaging][sa] (not sure where this variational method is discussed in that paper, appears to be under a different name?) and an EM algorithm to fit SBN models over such distributions. They also discuss conditional probability sharing (parameterising conditional on parent-child relationships) immediately before this and it's not clear if this is used in the distribution fit by SA or EM.

Experiments show the distributions fit using the EM algorithm perform well according to KL divergence from a "true" distribution defined by fitting a distribution using SRF to a larger dataset. They also show less dispersion estimating the probability of sampled trees versus that estimated by this "ground truth".

[sa]: https://people.eecs.berkeley.edu/~wainwrig/Papers/WaiJor08_FTML.pdf

[sbn_ds1]: https://github.com/morrislab/sbn/blob/master/experiments/DS1.ipynb

[larget]: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3676676/
[hohna]: https://academic.oup.com/sysbio/article/61/1/1/1676649

This work is a direct improvement of Collaborative Metric Learning. While CML tries to retrieve user and item embeddings in a direct way by placing them in metric space and adjusting with triplet loss, this paper focuses on introduction of latent relational vectors.

 A relational vector $r$ must describe relation between user $p$ and item $q$ in a way that  $s(p,q)=\parallel \ p + r - q \parallel \approx 0$.

Vectors $r$ are introduced as a softmax-weighted linear combination of vectors from Latent Relational Attentive Memory (LRAM).

The net is trained with BPR-like loss via negative sampling $max(0, s(p,q) - s(p', q') + margin)$

During the past few years, sellers have increasingly offered discounted or free products to selected reviewers of ecommerce platforms in exchange for their reviews. Such incentivized (and often very positive) reviews can improve the rating of a product which in turn sways other users’ opinions about the product. 

Here, we examine the problem of detecting and characterizing incentivized reviews in two primary categories of Amazon products.  We show that the key features of EIRs and normal reviews exhibit different characteristics. 

https://i.imgur.com/1BdwsK4.png

Furthermore, we illustrate how the prevalence of EIRs has evolved and been affected by Amazon’s ban. 

https://i.imgur.com/1XsSaxX.png

Our examination of the temporal pattern of submitted reviews for sample products reveals promotional campaigns by the corresponding sellers and their effectiveness in attracting other users. 
https://i.imgur.com/TvQiDlc.png

Finally, we demonstrate that a classifier that is trained by EIRs (without explicit keywords) and normal reviews can accurately detect other EIRs as well as implicitly incentivized reviews. Overall, this analysis sheds an insightful light on the impact of EIRs on Amazon products and users.

This paper compares methods to calculate the marginal likelihood, $p(D | \tau)$, when you have a tree topology $\tau$ and some data $D$ and you need to marginalise over the possible branch lengths $\mathbf{\theta}$ in the process of Bayesian inference. In other words, solving the following integral:

$$
\int_{ [ 0, \infty ]^{2S - 3} } p(D | \mathbf{\theta}, \tau ) p( \mathbf{\theta} | \tau) d \mathbf{\theta}
$$

There are some details about this problem that are common to phylogenetic problems, such as an exponential prior on the branch lengths, but otherwise this is the common problem of approximate Bayesian inference. This paper compares the following methods:

* ELBO (appears to be [BBVI][])
* Gamma Laplus Importance Sampling
* Variational Bayes Importance Sampling
* Beta' Laplus
* Gamma Laplus
* Maximum un-normalized posterior probability
* Maximum likelihood
* Naive Monte Carlo
* Bridge Sampling
* Conditional Predictive Ordinates
* Harmonic Mean
* Stabilized Harmonic Mean
* Nested Sampling
* Pointwise Predictive Density
* Path Sampling
* Modified Path Sampling
* Stepping Stone
* Generalized Stepping Stone

I leave the in depth description of each algorithm to the paper and appendices, although it's worth mentioning that Laplus is a Laplace approximation where the approximating distribution is constrained to be positive.

Some takeaways from the empirical results:

* If runtime is not a concern power posterior methods are preferred:

>  The power posterior methods remain the best general-purpose tools for phylogenetic modelcomparisons, though they are certainly too slow to explore the tree space produced by PT.

* Bridge sampling is the next choice, if you need something faster.
* Harmonic Mean is a bad estimator for phylogenetic tree problems.
* Gamma Laplus is a good fast option.
* Naive Monte Carlo is a poor estimator, which is probably to be expected.
* Gamma Laplus is the best option for very fast algorithms:

> Empirical posterior distributions on branch lengths are clearly not point-masses, and yet simply normalizing the unnormalized posterior at the maximum outperforms 6 of the 19 tested methods.

All methods were compared on metrics important to phylogenetic inference, such as *average standard deviation of split frequencies" (ASDSF), which is typically used to confirm whether parallel MCMC chains are sampling from the same distribution over tree topologies. Methods were also compared on KL divergence to the true posterior and RMSD (appears to be the mean squared error between CDFs?).

[bbvi]: https://arxiv.org/abs/1401.0118

## Idea
Use implicit feedback and item features to project users and items into the same latent space to use with kNN later. Learned metric encodes user-item, user-user and item-item relationships.
## Loss
Users and items are represented by vectors $u_i \in \mathcal{R}^r, v_i \in \mathcal{R}^r$.

We define euclidean distance as $d(i,j)= \parallel u_i-v_j\  \parallel$

Loss function consists of 3 parts:
$$\mathcal{L}=\mathcal{L}_m + \lambda_f\mathcal{L}_f + \lambda_c\mathcal{L}_c$$

### Weighted Triplet Loss
Sample user $i$, positive item $j$ and negative item $k$.
$$\mathcal{L}_m=\sum_{i,j,k}w_{ij}[d(i,j)^2-d(i,k)^2+m]_{+}$$
where $[z]_{+}=max(0,z)$ and $m>0$ is the margin size.

$w_{i,j}$ is calculated in WARP fashion, but sampling $U$ negative items for each positive pair $(i,j)$ instead of sampling until imposter is met.
$$w_{i,j}=log(\lfloor |Items| \frac{M}{U}\rfloor + 1)$$
where $M$ is the number of imposters in $U$ sampled negative items.

### Loss for features
Let $x_j \in \mathcal{R}^m$ denote raw feature vector of item $j$. We want it to be close to corresponding item vector $v_j$.
$$\mathcal{L}_f=\sum_j \parallel f(x_j) - v_j\ \parallel ^2$$
where $f$ is some transformation (MLP with dropout) to process item features.

### Regularization
kNN is ineffective ineffective in high-dimensional sparse space, so we bound user and item vectors to a unit sphere.
$$\parallel \ u_* \parallel ^2 \leq 1$$
$$\parallel \ v_* \parallel ^2 \leq 1$$
$L_2$ norm is not used because it pulls every object toward the origin which does not have any specific meaning in our case. Covariance regularization is used instead to de-correlate dimensions of the learned metric.

The covariances between all pairs of dimensions $i$ and $j$ form a matrix $C$.
$$C_{i,j} = \frac{1}{N} \sum_n (y_i^n - \mu_i^n)(y_j^n - \mu_j^n)$$
where $\mu_i = \frac{1}{N}(\parallel C \parallel_f - \parallel diag(C) \parallel_2^2)$ and $\parallel \cdot \parallel_f$ is the Frobenius norm

The paper: "Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask" by Zhou et al., 2019 found that by just learning binary masks one can find random subnetworks that do much better than chance on a task. This new paper builds on this method by proposing a strong algorithm than Zhou et al. for finding these high-performing subnetworks.https://i.imgur.com/vxDqCKP.png

The intuition follows: "If a neural network with random weights (center) is sufficiently overparameterized, it will contain a subnetwork (right) that performs as well as a trained neural network (left) with the same number of parameters."

While Zhou et al. learned a probability for each weight this paper learns a score for each weight and takes the top k percent at evaluation. The scores are learned through their primary contribution that they call the edge-popup algorithm: 

https://i.imgur.com/9KcIbxd.png

"In the edge-popup Algorithm, we associate a score with each edge. On the forward pass we choose the top edges by score. On the backward pass we update the scores of all the edges with the straight-through estimator, allowing helpful edges that are “dead” to re-enter the subnetwork. *We never update the value of any weight in the network, only the score associated with each weight.*"

They're able to find higher-performing random subnetworks than Zhou et al.

https://i.imgur.com/T3D7OsZ.png

Proposes a two-stage approach for continual learning. An active learning phase and a consolidation phase. The active learning stage optimizes for a specific task that is then consolidated into the knowledge base network via Elastic Weight Consolidation (Kirkpatrick et al., 2016). The active learning phases uses a separate network than the knowledge base, but is not always trained from scratch - authors suggest a heuristic based on task-similarity. Improves EWC by deriving a new online method so parameters don’t increase linearly with the number of tasks.

Desiderata for a continual learning solution:

- A continual learning method should not suffer from catastrophic forgetting. That is, it should be able to perform reasonably well on previously learned tasks. 

- It should be able to learn new tasks while taking advantage of knowledge extracted from previous tasks, thus exhibiting positive forward transfer to achieve faster learning and/or better final performance. 

- It should be scalable, that is, the method should be trainable on a large number of tasks. 

- It should enable positive backward transfer as well, which means gaining improved performance on previous tasks after learning a new task which is similar or relevant. 

- Finally, it should be able to learn without requiring task labels, and ideally, it should even be applicable in the absence of clear task boundaries.

Experiments:

- Sequential learning of handwritten characters of 50 alphabets taken from the Omniglot dataset.
- Sequential learning of 6 games in the Atari suite (Bellemare et al., 2012) (“Space Invaders”, “Krull”, “Beamrider”, “Hero”, “Stargunner” and “Ms. Pac-man”).
- 8 navigation tasks in 3D environments inspired by experiments with Distral (Teh et al., 2017).

One bad item can reduce perceived quality of recommendation list. Sometimes this may be particularly undesirable such as recommending horror movies to children. Authors argue that this happens when missing not at random data is handled improperly and separate groups of users and items overlap during the process of dimensionality reduction and computation of embeddings. Folding is a metric that measures the severity of described effect in a recommendation model.

To calculate folding we must introduce the notion of relatedness between user $i$ and item $j$ which captures the likelihood of interaction between $i$ and $j$, regardless of the rating. In a way this is a form of smoothing the interaction matrix. There are different ways to calculate relatedness, but authors propose to solve matrix factorization task using WALS with high weight for missing interactions or use SVD for this purpose.

Given predicted score and relatedness matrixes $S, R \in \mathbb{R}^{m \times n}$ we can calculate folding as the average across all interactions
$$Folding = \frac{1}{mn} \sum_{i,j}max(0, s_{ij}-r_{ij})$$

## Idea

When we recommend items to users, some of them are not chosen by the user. These rejected recommendations are usually treated as hard mistakes.

Authors argue that these bad recommendations still may influence user's choice even though they were not picked. For example user didn't click on "Die Hard" but watched another Bruce Willis movie. This seems to be a not so bad recommendation after all and maybe we should not penalize it as hard as we usually do.

Ultimate goal is to invent a metric that would have good correlation between offline results and real online performance.

## User study

Authors held a user study, showing people a set of 5 items: watched movie, 3 rejected recommendations and an item chosen after recommendation. Rejected recommendations were generated into 4 groups: 
- only high content similarity
- only high collaborative similarity
- only high popularity similarity
- all medium similarities

The question was "**How good is this recommendation 1-5?**"

| Content | Collaborative | Popularity | Other |
| ------- | ------------- | ---------- | ----- |
| 3.8     | 3.52          | 2.93       | 1.99  |

## Proposal
If standard precision is
$$p_u = \frac{|c_u \cap r_u|}{|r_u|}$$
where $c_u$ are items chosen by user and $r_u$ items recommended to user, then we can define a refined precision as 
$$p_u^{sim} = p_u + \frac{\sum_{i \in r_u \setminus c_u}max_{j \in \{ c_u:\ t(u,j) > t(u,i)\}}sim(i, j)}{|r_u|}$$
where $t(u,i)$ is the time when user $u$ interacted with item $i$.

## Evaluation
Authors used Xing dataset containing user interactions with a system for seeking employment opportunities. It contains logs of what was recommended and what was clicked.

### "Online" evaluation
Measure correlation between different refinement types of precision of RS presented in dataset and actual user clicks.

| Content | Collaborative | Regular |
| ------- | ------------- | ------- |
| 0.615   | 0.197         | 0.184   |

### Offline evaluation
Split logs 70/30 by time and measure correlation between number of clicks per user on test and metrics on train as if we were training a model on train part.



| Train clicks | Content | Collaborative | Random |
| ------------ | ------- | ------------- | ------ |
| 0.5          | 0.35    | 0.16          | 0.087  |


## Open question
What is the best way to calculate item similarity?