# Tactile Estimation of Extrinsic Contact Patch for Stable Placement

Kei Ota1,2, Devesh K. Jha3, Krishna Murthy Jatavallabhula4, Asako Kanezaki2,
and Joshua B. Tenenbaum4 1Kei Ota is with Mitsubishi Electric Corporation,
Kanagawa, Japan<EMAIL_ADDRESS>K. Jha is with
Mitsubishi Electric Research Labs, Cambridge, MA, USA.3Kei Ota and Asako
Kanezaki are with Tokyo Institute of Technology, Japan.4Krishna Murthy
Jatavallabhula and Joshua B. Tenenbaum are with Massachusetts Institute of
Technology, Cambridge, MA, USA.

###### Abstract

Precise perception of contact interactions is essential for the fine-grained
manipulation skills for robots. In this paper, we present the design of
feedback skills for robots that must learn to stack complex-shaped objects on
top of each other (see Fig. 1). To design such a system, a robot should be
able to reason about the stability of placement from very gentle contact
interactions. Our results demonstrate that it is possible to infer the
stability of object placement based on tactile readings during contact
formation between the object and its environment. In particular, we estimate
the contact patch between a grasped object and its environment using force and
tactile observations to estimate the stability of the object during a contact
formation. The contact patch could be used to estimate the stability of the
object upon the release of the grasp. The proposed method is demonstrated on
various pairs of objects that are used in a very popular board game.

Figure 1: Estimating extrinsic contact from tactile sensing: This work studies
how _extrinsic_ contact (indirect contact between a manipulated object and the
environment) can be estimated in the context of stable placement of an object
in an environment with partial support. The figure above shows an object
stacking scenario using two lightweight wooden game pieces (from the popular
_Bandu_ puzzle). (Left) The contact area between the two objects being stacked
is critical to the success (or failure) of the stack. Vision-based tactile
sensors mounted on the end effector and force-torque sensor provide us with a
composite signal that includes both intrinsic (direct) and (partially
observable) extrinsic contacts. Our key innovation is to propose a learning-
based method to estimate the extrinsic contact patch using only the composite
tactile signal and the knowledge of the force applied by the end effector.
(Right) This enables the robot to stack a highly irregularly shaped object on
top of a very unstable tower.

11footnotetext: Kei Ota is with Mitsubishi Electric Corporation, Kanagawa,
Japan<EMAIL_ADDRESS>Devesh K. Jha is
with Mitsubishi Electric Research Labs (MERL), Cambridge, MA,
USA.33footnotetext: Kei Ota and Asako Kanezaki are with Tokyo Institute of
Technology, Japan.44footnotetext: Krishna Murthy Jatavallabhula and Joshua B.
Tenenbaum are with Massachusetts Institute of Technology, Cambridge, MA, USA.

##  I Introduction

Humans can perform very complex and precise manipulation tasks effortlessly.
Consider, for example, gently stacking two lightweight objects on top of each
other without looking at them as shown in Fig. 1. Successful execution of this
task requires that the object not topple upon release of the grasp. In these
scenarios, stability is not directly observable; it must be implicitly
inferred from tactile signals that entangle both _intrinsic_ (direct) contact
between the end effector and the grasped object and _extrinsic_ (indirect)
contact between the grasped object and the environment. For example, it is
difficult to distinguish the stability of the configuration on the left from
the right by looking at it visually (as seen in Fig. 1). This work is
motivated by how humans are able to disentangle a composite tactile signal to
determine the nature of extrinsic contact; and are able to further predict
whether a given stack configuration is stable. We present a closed-loop system
that similarly reasons about object stability using tactile signals that arise
out of extrinsic contacts.

Object stability could be estimated from the contact forces experienced by an
object during placement. The stability of an object is governed by the
relative location of the environmental contact and the center of mass location
of the object. The forces observed by the force-torque (F/T) sensor mounted on
the wrist of the robot as well as the deformation observed by the tactile
sensors co-located at the gripper fingers depend on the contact patch between
the object and its environment, as well as the geometric and physical
properties of the object. As a simplification, we assume that the geometry of
the objects is fixed, so the robot works with known pieces. Under this
assumption, the problem of estimating the stability of placement from tactile
observations is simplified. With this understanding, we try to estimate the
contact patch between the object and the environment using tactile signals.
However, the estimation of contact patches from a single tactile observation
is a partially observable problem. Thus, it is not possible to get a perfect
estimation of contact from a single interaction.

To solve the partial observability problem, we present a method for
aggregating information from multiple observations. The proposed method
collects tactile observations by interacting with the environment multiple
times and updates its belief of the underlying contact formation. We show that
we are able to monotonically improve our estimate of the contact formation
between the environment and the grasped object. This estimate is used to move
the object towards a stable configuration so that it can be released in a
stable pose. This is demonstrated using several pairs of objects from a
popular board game where the objective is to incorporate a new block on an
existing tower without destabilizing the tower. We also perform ablations to
understand which sensing modality, the F/T sensor or the vision-based tactile
sensors is helpful in understanding the phenomena during the considered
contact phenomena.

Contributions: In summary, our contributions are the following.

  1. 1.

We present a method to estimate extrinsic contact patches from end-effector
tactile signals that compose both intrinsic and extrinsic contacts.

  2. 2.

Our probabilistic filtering approach for use in a feedback control loop can
stably stack a set of extremely challenging real-world objects using solely
tactile sensing.

Figure 2: Pipeline: Our method comprises four components. First, a robot
probes the environment to establish contact between the grasped object and the
target object upon which it must be stacked. During this probing phase, we
acquire a sequence of force/torque measurements and tactile images. We then
estimate the extrinsic contact patch and, in turn, the potential stability of
the resultant configuration. Subsequently, we aggregate the information from
multiple interactions to update the belief map of the contact state. We pick
the action that maximizes the contact patch between the objects.

##  II Related Work

Block stacking. Block stacking is one of the most widely studied problems in
robotics. Several studies have addressed the problem of robot stacking through
various approaches. These include learning to schedule auxiliary tasks for
reinforcement learning (RL) [1], combining demonstrations and RL [2, 3],
employing sim-to-real transfer [2, 4, 5], and using task-and-motion planning
[6]. The focus of these works primarily revolves around stacking simple cubes.
Lee _et al._ [7] propose a benchmark that introduces relatively irregular
rectangles generated by deforming cubes. However, these objects still maintain
convexity and simplicity. Furrer _et al._ [8] and Yifang _et al._ [9] have
explored the stacking of irregular stones. Another related work that reasons
about vision-based contact support could be found in [10]. But this assumed
access to the geometry of the object and was indeed reasoning about the
relative placement between blocks given the object geometries. Nonetheless,
these studies make assumptions regarding knowledge of geometry and assume that
objects possess wide support and high friction, simplifying the problem and
enabling basic pick-and-place strategies. Most importantly, these works do not
reason about stability using contact information but rather perform placement
using open-loop controllers. However, the pick-and-place-based stacking would
not work if there is ambiguity in the location of the environment (for
example, the scenario shown in Figure 1). To address this problem, our
proposed method considers the local contact phenomenon in which the object can
topple and fall, if not placed with proper support. Moreover, we remove
assumptions regarding the geometry of the underlying objects, necessitating
the estimation of stability through interactions.

External contact localization Prior works represent contacts as a set of
points [11, 12] and lines [13, 14]. Although line contacts give us more
information compared to point contacts, they require active exploration
involving changes in the orientation of the gripper [13, 14], making it
difficult to apply them in our setting where the tower is very unstable. The
closest work to ours is the neural contact fields (NCF) of Higuera et al.
[15], where the authors estimate the contact patch between a grasped object
and its environment. While NCF is evaluated on a simulation and a limited
number of objects, we tested our method on unknown geometries of the
environment which can be used for an appropriate downstream task.

##  III Problem Statement

We are interested in performing stable placement in environments where the
object might have partial support for placement. Consider, for example, the
scenario shown in Figure 1, where it is not enough to establish contact with
the bottom piece but rather estimate stability of the object in the resulting
contact formation. Thus, we consider the problem of estimating the stability
of an object when in contact with its environment, in an attempt to release
and place the object in a stable pose during a task. This happens to be a
partially observable task, as we cannot observe the full state of the system,
and thus stability needs to be estimated from sensor observations. We assume
that the robot has access to tactile sensors co-located at the gripper fingers
as well as a Force/Torque (F/T) sensor at the wrist. A certain contact
formation is stable if the object can remain stable after being released from
the grasp.

The stability of a contact formation depends on the relative position of the
center of mass of the object and the contact patch between the object and the
environment. However, this cannot be directly observed during a contact
formation, and thus leads to partial-observability. A robot can usually
observe force-torque signals and/or tactile images during interaction. The
observed signals depend not only on the contact formation but also on the
geometry and physical parameters of the grasped object. Thus, although these
data have a lot of information, these are all entangled and thus it is very
difficult to extract specific information, e.g. estimate contact patch. The
stability estimation problem in its full scope requires reasoning about the
sensor observations while considering the geometric information of the
objects. To simplify the estimation problem, we make the following assumptions
to limit the scope of current study:

  1. 1.

Geometry and physical parameters of the grasped objects are fixed.

  2. 2.

All objects are rigid and have flat surfaces.

It is important to emphasize that the robot is unfamiliar with the shape of
the underlying objects and needs to explore a stable configuration through
several probing attempts. These assumptions restrict the use of our proposed
objects to known objects. A full, in-depth study of the problem is left as a
future exercise.

##  IV Method

The main idea here is to estimate the contact patch between an object and its
environment using force and tactile measurements. This is based on the fact
that sensor observations are generated by the contact formation between the
object and its environment. We propose a framework consisting of four key
components. First, the robot estimates the contact patch between the grasped
object and its environment from an observation obtained by interacting with
the environment. Then, it assesses stability based on the estimated contact
patch; and releases the grasped object if it believes the current
configuration is stable; otherwise, it aggregates information from multiple
estimated contact patches to predict the belief map, which gives us a sense of
the contact surface of the environment. Then it can assess the stability.
Finally, the robot selects an action that moves the object towards a position
that it believes can improve stability. In this section, we describe more
details of these four modules.

###  IV-A Contact Patch Estimation

Given the observed tactile image $o^{\text{Tac}}$ and F/T measurements
$o^{\text{FT}}$, our objective is to learn a model that generates a
probabilistic contact patch $\hat{S}$, which consists of a set of
probabilities indicating which part of the grasped object is in contact.

Contact representation. To estimate the contact patch, we discretize the
contact surface of the grasped object $S$ into $N$ points as
$S\approx\\{s_{1},...,s_{N}\\}$ each of which corresponds to a specific
location on the contact surface of the grasped object (see Fig. 3 right). For
each point $s_{j}$, we predict the probability of being in contact or
remaining uncontacted $p(s_{j})$. Consequently, we represent the probabilistic
contact patch $\hat{S}$ as a set of probabilities
$\hat{S}_{i}=\\{p(s_{1}),...,p(s_{N})\\}$.

Data collection by interaction. During a duration of $T$ seconds, the robot
applies a downward force along the negative Z axis for $d$ mm, while
collecting $o^{\text{Tac}},o^{\text{FT}}$ from tactile and force-torque
sensors at a frequency of $10$ Hz. Specifically,
$o^{\text{Tac}}=\\{o^{\text{Tac}}_{t}\\}_{t=0}^{T}$, where
$o^{\text{Tac}}_{t}\in\mathbb{R}^{252}$ with $252=2\times 2\times 7\times 9$,
where we use two tactile sensors mounted on each finger and measure marker
displacements on the $XY$ axis in the tactile image, and $7\times 9$ is the
number of markers in column and row (see Fig. 2), which can be obtained by
post-processing the tactile image $I^{\text{Tac}}_{t}$. Similarly,
$o^{\text{FT}}=\\{o^{\text{FT}}_{t}\\}_{t=0}^{T}$,
$o^{\text{FT}}_{t}\in\mathbb{R}^{6}$ is the F/T measurement. We use a suitable
impedance control to prevent the object from falling by using excessive force.
In the data collection process, we add displacements in the $XY$ plane such as
$x\sim\\{x_{\mathtt{min}},x_{\mathtt{max}}\\}$ and
$y\sim\\{y_{\mathtt{min}},y_{\mathtt{max}}\\}$ whose origin is the center
position of the contact surface of the lower object $O$ (see Fig. 3), and the
minimum and maximum range are defined to ensure contact between the flat
surfaces of the upper and lower objects. We use known geometries and
displacements to generate ground-truth contact patches for training a model.

Training. Finally, we train a contact patch estimation model
$f^{\text{contact}}$ that takes observation $o^{\text{Tac}},o^{\text{FT}}$ and
learns to generate a probabilistic contact surface $\hat{S}$ as:

$\hat{S}=f^{\text{contact}}(o^{\text{Tac}},o^{\text{FT}}).$ (1)

This model is trained by minimizing the binary cross-entropy loss for each
data point $s_{j}$. To capture patterns in time series data, we use LSTM to
build the model.

Figure 3: Definition of the probabilistic contact patch. (Left) The
displacement $(x,y)$ is added from the origin of the bottom object $O$ during
data collection. This displacement and known contact surfaces of the two
objects give the ground-truth contact surface $S$. (Right) The discretized
contact patch $\hat{S}$ consists of a set of probabilities $p(s_{j})$ that
represents whether a specific position $s_{j}$ of the contact surface of the
grasped object is in contact or not.

###  IV-B Stability Estimation

We utilize the estimated contact patch $\hat{S}$ to estimate the stability of
the current configuration. To do that, we first construct a convex hull
$C\in\text{Convex}(\hat{S})$ (see Fig. 2 (b)) using points whose associated
probability exceeds a predefined threshold denoted by $\delta$, which we use
$\delta=0.9$ for our experiments. Subsequently, we check that the convex hull
includes the position of the center of mass of the grasped object. In the
affirmative case, the gripper releases the grasped object. Otherwise, the
gripper aggregates information and moves towards a stable position by an
action selection strategy described in the following sections.

###  IV-C Aggregating Information from Multiple Interactions

Since the contact patch estimation from tactile signals is a partially
observable task, i.e., multiple different contact patches can yield similar
tactile signals, it is difficult to reliably estimate the contact patch from a
single interaction. Therefore, we aggregate information from multiple
interactions to disambiguate the estimate.

We denote the aggregated contact patch at the time step $i$ as
$\hat{S}_{i}^{B}$, which again represents a probabilistic contact surface of
the _bottom_ object $\hat{S}_{i}^{B}=\\{p(s_{1,i}^{B}),...,p(s_{M,i}^{B})\\}$,
where $M$ is the number of discrete points. Following [16], the probabilistic
formulation of the contact $p(s_{i}^{B})$ (note we remove lowercase $m$ for
simplification) given past observation and action can be formulated as

$\begin{split}p(s_{i}^{B}|&o_{1:i-1},a_{1:i-1})\\\ &=\int
p(s_{i}^{B}|s_{i-1}^{B},a_{i-1})p(s_{i-1}^{B}|o_{1:i-1},a_{1:i-1}),\end{split}$
(2)

where the first term is $1$ as we assume deterministic dynamics, and the
second term is initialized with the prior distribution and can be obtained
through recursion. The posterior can be computed as:

$p(s_{i}^{B}|o_{1:i},a_{1:i-1})\propto
p(o_{i}|s_{i}^{B})p(s_{i}^{B}|o_{1:i-1},a_{1:i-1}),$ (3)

where the first term is given by the contact patch estimation model
$f^{\text{contact}}$ and the second term can be computed from Eq.(2).
Specifically, we initialize the probability with
$p(s_{0}^{B})=\text{Bernoulli}(0.5)$ since we do not know whether the specific
point is in contact or not before interaction.

###  IV-D Action Selection

To realize a stable configuration, we design a policy that maximizes the
contact surface area in the next step. The policy begins by calculating the
central position of the convex hull of the aggregated contact patch
$s_{C^{B}}=\cfrac{\sum_{i\in|C^{B}|}s_{i}^{B}}{|C^{B}|}$, where $C^{B}$ is
again the convex hull of the aggregated contact map, and subsequently directs
the robot to navigate in the direction to this central position from the
current position. Additionally, to mitigate a large movement at each step, we
restrict movement within $d^{\text{move}}$ mm if the norm exceeds
$d^{\text{move}}$. We specifically set $d^{\text{move}}=3$ mm.

##  V Experiments

###  V-A Settings

Tactile sensor. We use a commercially available GelSight Mini [20] tactile
sensor, which provides 320×240 compressed RGB images at a rate of
approximately 25 Hz, with a field of view of 18.6 × 14.3 millimeters. We use
gels that have 63 tracking markers.

Robot platform. The MELFA RV-5AS-D Assista robot, a collaborative robot with 6
DoF, is used in this study. The tactile sensor is mounted on the WSG-32
gripper (see Fig. 2). We use a Force-Torque (F/T) sensor, which is mounted on
the wrist of the robot. The F/T sensor is used two-fold. First, we collect
force observations which are used as input to the contact patch estimation
model $f^{\text{contact}}$. Second, the stiffness control of the position-
controlled robot.

Bandu. We use pieces from Bandu for our experiment. Bandu is a toy game that
involves stacking objects onto a base plate. The players take turns stacking
these objects and compete to see who can stack the most. Each piece has a
highly irregular shape, requiring robots to estimate stable placements based
on the shape of the objects. Figure 4 illustrates the Bandu pieces used in our
experiments. The challenge in the game is to accommodate an irregular piece
into an existing tower without destabilizing it.

Figure 4: The 3D printed board and Bandu pieces used in our experiments. (a)
We use the 3D printed board for training data collection. The board includes
small and large circles with diameters of $15$ and $25$ mm and one square
whose length is $15$ mm. (b) The first two pieces on the left serve as the
bottom objects (or the environment), while the subsequent three on the right
are designated as the grasped (top) objects. These pieces have been assigned
the following names: Short, Long, Mushroom, Barrel, and Pot from left to
right.  Figure 5: Distribution of contact patches: (a) Training data
distribution with Pot as the grasped object and three different 3D printed
shapes as the bottom objects (see Fig. 4). Each row shows the data obtained
from different primitive shapes and each column shows the distribution of
different data types: tactile displacements on the $XY$ axes, moments on the
$XY$ axis, and force $F_{z}$. The horizontal and vertical axes show the
displacements randomly added during data collection (see Fig. 3), and the
black circle or rectangle in each graph shows the contour of the bottom
object. (b) Example contact patch sampled from the star points ($\bigstar$) in
the left distributions. Although these contact patches are very different, the
tactile signals look quite similar as seen in the data around the star point,
showing the difficulty of the task; i.e., similar tactile signals can lead to
very different contact patches.

###  V-B Data Collection

Settings. We first show the distribution of the observed tactile signals to
understand the difficulties of the task. We collect $2000$ tactile signals for
each pair of top-bottom objects to train the contact patch estimation model
$f^{\text{contact}}$ by interacting with a 3D printed board as shown in Fig. 4
(a), resulting in $6000$ training samples. During data collection, we add
random displacements on the $XY$ axis as defined in Fig. 3, and let the robot
go down for $d=1.5$ mm after establishing contact with the bottom object for
$T=2$ seconds using the stiffness controller whose gain parameter is
$(K_{x},K_{y},K_{z})=(30,30,15)$ [N/mm]. We use the grasping force of $10$
[N].

Results and Analysis. Fig. 5 shows the data distribution (left) and example
contact patches (right). From the first to the fourth columns, we can observe
the inherent difficulties of the estimation task. We do not observe any
symmetric distribution of $o^{\text{Tac}}_{x}$, $o^{\text{Tac}}_{y}$ and the
moment measurements $T_{x},T_{y}$ about $X=0$ or $Y=0$. This could possibly be
attributed to the inaccuracy in the 3D printing of the board or the slip of
the object in the grasp during the contact interaction. Fig. 5 (b) shows three
contact patches sampled from the star positions in each row. While tactile
signals near the star positions are very similar, the resulting contact
patches are very different. This highlights the partial observability of the
underlying contact formation, indicating that a single tactile observation may
not be sufficient to localize the contact formation. This ambiguity makes
training of a machine learning model very difficult because similar inputs
(i.e., tactile observations) can lead to totally different outputs (i.e.,
contact patches).

###  V-C Contact Patch Estimation

Settings. Next, we compare the performance of the contact patch estimation on
different input modalities. We train the model $f^{\text{contact}}$ for each
top object using the dataset collected in Sec. V-B, and we evaluate the model
using the intersection-over-union (IoU) and binary classification metric. We
compare the performance with three different input modalities, a F/T sensor,
tactile sensors, and the combination of the two denoted as FT, Tac, and
FT+Tac, respectively. The evaluation is carried out using _unseen_ two Bandu
pieces (see Fig. 4), which we denote as Short and Long. We used a 3D-printed
jig to ensure that the robot always grasps the same position of the top object
and collected $400$ interactions with random displacements.

Results and Analysis. The results are presented in Table I. When comparing the
three modalities, we can clearly see that the combination of tactile sensors
and the F/T sensor (FT+Tac) yields the best performance. Consequently, for our
subsequent experiments, we will utilize both of these modalities. However, it
should be noted that the model is not confident enough to estimate the contact
patch. This is because the same tactile signals can lead to different contact
patches, as discussed in Sec. V-B. Therefore, in the next experiment, we will
aggregate information from multiple interactions and compare performance in
stability estimation.

TABLE I: Comparison of the contact patch estimation performance on different
input modalities measured by IoU and binary classification accuracy. Bold
numbers show the best results among the three different input modalities. The
S and L of the bottom objects correspond to the Short and Long objects,
respectively (see Fig. 4).

|  | Mushroom | Barrel | Pot
---|---|---|---|---
|  | S | L | S | L | S | L
IoU | FT | $27.4$ | $37.7$ | $29.6$ | $\bm{44.5}$ | $23.8$ | $53.2$
Tac | $33.6$ | $22.2$ | $31.5$ | $42.6$ | $16.5$ | $37.5$
FT+Tac | $\bm{38.4}$ | $\bm{50.7}$ | $\bm{31.9}$ | $41.2$ | $\bm{24.8}$ | $\bm{54.8}$
Acc | FT | $67.4$ | $65.5$ | $75.3$ | $73.1$ | $68.0$ | $71.9$
Tac | $72.9$ | $60.4$ | $76.5$ | $\bm{77.5}$ | $66.9$ | $71.7$
FT+Tac | $\bm{77.9}$ | $\bm{73.8}$ | $\bm{77.0}$ | $75.4$ | $\bm{67.3}$ | $\bm{74.9}$

###  V-D Stability Estimation

Settings. Next, we assess the stability estimation performance of the proposed
method. We reuse the same data as used in the previous experiments with an
additional binary label indicating whether the current configuration is stable
by checking whether the geometric center of the bottom surface of the grasped
object (i.e., the projection of the center of mass of the grasped object on
the bottom surface) lies inside the contact patch. We compare our method with
a baseline model that directly produces the stability probability by replacing
the final layer of $f^{\text{contact}}$ with a fully connected layer with a
single unit and sigmoid activation. We name it Implicit because it implicitly
estimates stability, while our framework explicitly predicts it through the
estimated contact patch.

Results and Analysis. Table II shows the qualitative results. Single
interaction leads to poor performance, as seen in the results of the baseline
(Implicit) as well as our method with single interaction (Ours $n=1$).
However, by aggregating the estimates of multiple interactions, the stability
estimation performance improves significantly, leading to an average accuracy
of $90$%. Figure 6 shows how the probability of a contact patch changes during
interactions. It shows that the method corrects the initial inaccurate
estimate and improves accuracy with additional interactions, and the method
finally reconstructs the contact surface of the bottom object with reasonable
accuracy.

TABLE II: Stability estimation performance measured by binary accuracy. $n$
indicates the number of interactions and bold numbers show the best results.

|  | Mushroom | Barrel | Pot
---|---|---|---|---
|  | S | L | S | L | S | L
Implicit | $73.7$ | $73.0$ | $63.9$ | $69.8$ | $64.2$ | $66.0$
Ours | $n=1$ | $69.8$ | $81.0$ | $63.7$ | $71.4$ | $61.7$ | $69.4$
$n=2$ | $88.4$ | $93.0$ | $92.7$ | $88.9$ | $83.2$ | $83.9$
$n=3$ | $\bm{93.0}$ | $\bm{93.2}$ | $\bm{97.3}$ | $\bm{92.1}$ | $\bm{91.1}$ | $\bm{85.7}$

Figure 6: An example of how the proposed method aggregates multiple
estimations and updates contact probability map. The circle in a solid line
shows the ground-truth contour of the bottom object. The initial estimate
($n=1$) is incorrect, but with multiple interactions, the estimation accuracy
monotonically improves ($n=3,5$).

###  V-E Stacking

Settings. Finally, we evaluate the stacking performance of the method. We
always initialize the first interaction from an unstable contact state (i.e.,
the object would topple upon release of grasp). We run the method $10$ times
for each piece and evaluate whether the robot successfully places the piece in
a stable configuration. Furthermore, we also test the method in a harder
scenario, where the Long piece is already stacked onto the Short piece (see
Fig. 4 for the definition of the pieces), and we stack a top piece on top of
these two objects. We compare our method with a Pick & Place baseline, where
it releases the piece without estimating the stability.

Results and Analysis. Table III shows the results. The pick-and-place baseline
fails in all trials. The proposed method improves performance by predicting
the contact patch at each iteration and aggregating information to improve the
estimation accuracy. Although the success rate drops when the number of bottom
objects is increased, the method can still succeed with a success rate of
around $60$%. Figure 7 shows a qualitative result of how it moves to the more
stable position.

TABLE III: Success rate of stacking. One and Two means stacking on top of a
single and two objects, respectively.

|  | Mushroom | Barrel | Pot
---|---|---|---|---
|  | S | L | S | L | S | L
One | Pick & Place | $0/10$ | $0/10$ | $0/10$ | $0/10$ | $0/10$ | $0/10$
Ours | $8/10$ | $6/10$ | $8/10$ | $5/10$ | $7/10$ | $6/10$
Two | Ours | $6/10$ | $5/10$ | $7/10$ | $5/10$ | $6/10$ | $5/10$

Figure 7: The robot moves towards a stable configuration and successfully
stacks the Barrel piece on top of an already built tower consisting of Short
and Long.

##  VI Conclusion

Designing systems that can interpret and disentangle useful contact
information from observed tactile measurements is the key to performing
precise and fine manipulation. We proposed a framework for estimating
extrinsic contact patches from tactile and force-torque measurements. The
contact-patch estimation allows us to estimate the stability of the placement
of several different objects in novel and unstable environments. We tested the
proposed approach for the placement of several pieces of the game of Bandu,
which is known to be a difficult stacking task. In the future, we would like
to improve the performance by training on a wider variety of objects and
relaxing the assumption of the known geometry so that the trained model can be
used for the stacking task with arbitrary objects.

## References

  * [1] M. Riedmiller, R. Hafner, T. Lampe, M. Neunert, J. Degrave, T. van de Wiele, V. Mnih, N. Heess, and J. T. Springenberg, “Learning by playing solving sparse reward tasks from scratch,” in _Proceedings of the 5th Conference on Robot Learning (CoRL)_ , ser. Proceedings of Machine Learning Research, J. Dy and A. Krause, Eds., vol. 80. PMLR, 10–15 Jul 2018, pp. 4344–4353. [Online]. Available: https://proceedings.mlr.press/v80/riedmiller18a.html
  * [2] Y. Zhu, Z. Wang, J. Merel, A. Rusu, T. Erez, S. Cabi, S. Tunyasuvunakool, J. Kramár, R. Hadsell, N. de Freitas, and N. Heess, “Reinforcement and imitation learning for diverse visuomotor skills,” in _Proceedings of International Conference on Learning Representations (ICLR)_ , 2018.
  * [3] S. Cabi, S. G. Colmenarejo, A. Novikov, K. Konyushkova, S. Reed, R. Jeong, K. Zolna, Y. Aytar, D. Budden, M. Vecerik, O. Sushkov, D. Barker, J. Scholz, M. Denil, N. de Freitas, and Z. Wang, “Scaling data-driven robotics with reward sketching and batch reinforcement learning,” 2020.
  * [4] L. Hermann, M. Argus, A. Eitel, A. Amiranashvili, W. Burgard, and T. Brox, “Adaptive curriculum generation from demonstrations for sim-to-real visuomotor control,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , 2020, pp. 6498–6505.
  * [5] R. Jeong, Y. Aytar, D. Khosid, Y. Zhou, J. Kay, T. Lampe, K. Bousmalis, and F. Nori, “Self-supervised sim-to-real adaptation for visual robotic manipulation,” in _Proceedings of IEEE International Conference on Robotics and Automation (ICRA)_ , 2020, pp. 2718–2724.
  * [6] M. D. Noseworthy, C. Moses, I. Brand, S. Castro, L. P. Kaelbling, T. Lozano-Pérez, and N. Roy, “Active learning of abstract plan feasibility,” _Robotics Science and System (RSS)_.
  * [7] A. X. Lee, C. M. Devin, Y. Zhou, T. Lampe, K. Bousmalis, J. T. Springenberg, A. Byravan, A. Abdolmaleki, N. Gileadi, D. Khosid, C. Fantacci, J. E. Chen, A. Raju, R. Jeong, M. Neunert, A. Laurens, S. Saliceti, F. Casarini, M. Riedmiller, r. hadsell, and F. Nori, “Beyond pick-and-place: Tackling robotic stacking of diverse shapes,” in _Proceedings of the 5th Conference on Robot Learning (CoRL)_ , ser. Proceedings of Machine Learning Research, A. Faust, D. Hsu, and G. Neumann, Eds., vol. 164. PMLR, 08–11 Nov 2022, pp. 1089–1131. [Online]. Available: https://proceedings.mlr.press/v164/lee22b.html
  * [8] F. Furrer, M. Wermelinger, H. Yoshida, F. Gramazio, M. Kohler, R. Siegwart, and M. Hutter, “Autonomous robotic stone stacking with online next best object target pose planning,” in _Proceedings of IEEE International Conference on Robotics and Automation (ICRA)_ , 2017, pp. 2350–2356.
  * [9] Y. Liu, J. Choi, and N. Napp, “Planning for robotic dry stacking with irregular stones,” in _Field and Service Robotics_ , G. Ishigami and K. Yoshida, Eds. Singapore: Springer Singapore, 2021, pp. 321–335.
  * [10] O. Kroemer, S. Leischnig, S. Luettgen, and J. Peters, “A kernel-based approach to learning contact distributions for robot manipulation tasks,” _Autonomous Robots_ , vol. 42, pp. 581–600, 2018.
  * [11] L. Manuelli and R. Tedrake, “Localizing external contact using proprioceptive sensors: The contact particle filter,” in _Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2016, pp. 5062–5069.
  * [12] S. Kim, D. K. Jha, D. Romeres, P. Patre, and A. Rodriguez, “Simultaneous tactile estimation and control of extrinsic contact,” _arXiv preprint arXiv:2303.03385_ , 2023.
  * [13] D. Ma, S. Dong, and A. Rodriguez, “Extrinsic contact sensing with relative-motion tracking from distributed tactile measurements,” in _Proceedings of IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2021, pp. 11 262–11 268.
  * [14] S. Kim and A. Rodriguez, “Active extrinsic contact sensing: Application to general peg-in-hole insertion,” in _Proceedings of IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2022, pp. 10 241–10 247.
  * [15] C. Higuera, S. Dong, B. Boots, and M. Mukadam, “Neural contact fields: Tracking extrinsic contact with tactile sensing,” in _Proceedings of IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2023, pp. 12 576–12 582.
  * [16] K. Ota, D. K. Jha, H.-Y. Tung, and J. B. Tenenbaum, “Tactile-filter: Interactive tactile perception for part mating,” _Robotics Science and System (RSS)_ , 2023.


# Probabilistic Metric Learning with Adaptive Margin for Top-K Recommendation

Chen Ma  McGill University<EMAIL_ADDRESS>,  Liheng Ma  McGill
University<EMAIL_ADDRESS>,  Yingxue Zhang  Huawei Noah’s Ark Lab
Montreal<EMAIL_ADDRESS>,  Ruiming Tang  Huawei Noah’s Ark Lab
<EMAIL_ADDRESS>,  Xue Liu  McGill University<EMAIL_ADDRESS>and
Mark Coates  McGill University<EMAIL_ADDRESS>
###### Abstract.

Personalized recommender systems are playing an increasingly important role as
more content and services become available and users struggle to identify what
might interest them. Although matrix factorization and deep learning based
methods have proved effective in user preference modeling, they violate the
triangle inequality and fail to capture fine-grained preference information.
To tackle this, we develop a distance-based recommendation model with several
novel aspects: (i) each user and item are parameterized by Gaussian
distributions to capture the learning uncertainties; (ii) an adaptive margin
generation scheme is proposed to generate the margins regarding different
training triplets; (iii) explicit user-user/item-item similarity modeling is
incorporated in the objective function. The Wasserstein distance is employed
to determine preferences because it obeys the triangle inequality and can
measure the distance between probabilistic distributions. Via a comparison
using five real-world datasets with state-of-the-art methods, the proposed
model outperforms the best existing models by 4-22% in terms of recall@K on
Top-K recommendation.

##  1\. Introduction

Internet users can easily access an increasingly vast number of online
products and services, and it is becoming very difficult for users to identify
the items that will appeal to them out of a plethora of candidates. To reduce
information overload and to satisfy the diverse needs of users, personalized
recommender systems have emerged and they are beginning to play an important
role in modern society. These systems can provide personalized experiences,
serve huge service demands, and benefit both the user-side and supply-side.
They can: (i) help users easily discover products that are likely to interest
them; and (ii) create opportunities for product and service providers to
better serve customers and to increase revenue.

In all kinds of recommender systems, modeling the user-item interaction lies
at the core. There are two common ways used in recent recommendation models to
infer the user preference: matrix factorization (MF) and multi-layer
perceptrons (MLPs). MF-based methods (e.g., (Hu et al., 2008; Rendle et al.,
2009)) apply the inner product between latent factors of users and items to
predict the user preferences for different items. The latent factors strive to
depict the user-item relationships in the latent space. In contrast, MLP-based
methods (e.g., (He et al., 2017b; Covington et al., 2016)) adopt (deep) neural
networks to learn non-linear user-item relationships, which can generate
better latent feature combinations between the embeddings of users and items
(He et al., 2017b).

However, both MF-based and MLP-based methods violate the triangle inequality
(Shrivastava and Li, 2014), and as a result may fail to capture the fine-
grained preference information (Hsieh et al., 2017). As a concrete example in
(Park et al., 2018), if a user accessed two items, MF or MLP-based methods
will put both items close to the user, but will not necessarily put these two
items close to each other, even if they share similar properties.

To address the limitations of MF and MLP-based methods, metric (distance)
learning approaches have been utilized in the recommendation model (Hsieh et
al., 2017; Park et al., 2018; Tay et al., 2018; Li et al., 2020), as the
distance naturally satisfies the triangle inequality. These techniques project
users and items into a low-dimensional metric space, where the user preference
is measured by the distance to items. Specifically, CML (Hsieh et al., 2017)
and LRML (Tay et al., 2018) are two representative models. CML minimizes the
Euclidean distance between users and their accessed items, which facilitates
user-user/item-item similarity learning. LRML incorporates a memory network to
introduce additional capacity to learn relations between users and items in
the metric space.

Figure 1. A motivating example of handling uncertainties of learned
embeddings.

Although existing distance-based methods have achieved satisfactory results,
we argue that there are still several avenues for enhancing performance.
First, previous distance-based methods (Hsieh et al., 2017; Park et al., 2018;
Tay et al., 2018; Li et al., 2020) learn the user and item embeddings in a
deterministic manner without handling the uncertainty. Relying solely on the
learned deterministic embeddings may lead to an inaccurate understanding of
user preferences. A motivating example is shown in Figure 1. After having
accessed two songs $s_{1}$ and $s_{2}$ with different genres, the user $u$ may
be placed between of $s_{1}$ and $s_{2}$. If we only consider deterministic
embeddings, $s_{4}$ should be a good candidate. But if we consider the
embeddings from a probabilistic perspective, $s_{3}$ can be a better
recommendation and it has the same genre as $s_{1}$. Second, most of the
existing methods (Hsieh et al., 2017; Tay et al., 2018; Park et al., 2018)
adopt the margin ranking loss (hinge loss) with a fixed margin as the hyper-
parameter. We argue that the margin value should be adaptive and relevant to
corresponding training samples. Furthermore, different training phases may
need different magnitudes of margin values. Setting a fixed value may not be
an optimal solution. Third, previous distance-based methods (Hsieh et al.,
2017; Tay et al., 2018; Park et al., 2018; Li et al., 2020) do not explicitly
model user-user and item-item relationships. Closely-related users are very
likely to share the same interests, and if two items have similar attributes
it is likely that a user will favour both. When inferring a user’s
preferences, we should explicitly take into account the user-user and item-
item similarities.

To address the shortcomings, we propose a Probabilistic Metric Learning model
with an Adaptive Margin (PMLAM) for Top-K recommendation. PMLAM consists of
three major components: 1) a user-item interaction module, 2) an adaptive
margin generation module, and 3) a user-user/item-item relation modeling
module. To capture the uncertainties in the learned user and item embeddings,
each user or item is parameterized with one Gaussian distribution, where the
distribution related parameters are learned by our model. In the user-item
interaction module, we adopt the Wasserstein distance to measure the distances
between users and items, thus not only taking into account the means but also
the uncertainties. In the adaptive margin generation module, we model the
learning of adaptive margins as a bilevel (inner and outer) optimization
problem (Sinha et al., 2018), where we build a proxy function to explicitly
link the learning of margin related parameters with the outer objective
function. In the user-user and item-item relation modeling module, we
incorporate two margin ranking losses with adaptive margins for user-pairs and
item-pairs, respectively, to explicitly encourage similar users or items to be
mapped closer to one another in the latent space. We extensively evaluate our
model by comparing with many state-of-the-art methods, using two performance
metrics on five real-world datasets. The experimental results not only
demonstrate the improvements of our model over other baselines but also show
the effectiveness of the proposed modules.

To summarize, the major contributions of this paper are:

  * •

To capture the uncertainties in the learned user/item embeddings, we represent
each user and item as a Gaussian distribution. The Wasserstein distance is
leveraged to measure the user preference for items while simultaneously
considering the uncertainty.

  * •

To generate an adaptive margin, we cast margin generation as a bilevel
optimization problem, where a proxy function is built to explicitly update the
margin generation related parameters.

  * •

To explicitly model the user-user and item-item relationships, we apply two
margin ranking losses with adaptive margins to force similar users and items
to map closer to one another in the latent space.

  * •

Experiments on five real-world datasets show that the proposed PMLAM model
significantly outperforms the state-of-the-art methods for the Top-K
recommendation task.

##  2\. Related Work

In this section we summarize and discuss work that is related to our proposed
top-K recommendation model.

In many real-world recommendation scenarios, user implicit data (Wang et al.,
2015; Ma et al., 2019a), e.g., clicking history, is more common than explicit
feedback (Salakhutdinov et al., 2007) such as user ratings. The implicit
feedback setting, also called one-class collaborative filtering (OCCF) (Pan et
al., 2008), arises when only positive samples are available. To tackle this
challenging problem, effective methods have been proposed.

Matrix Factorization-based Methods. Popularized by the Netflix prize
competition, matrix factorization (MF) based methods have become a prominent
solution for personalized recommendation (Koren et al., 2009). In (Hu et al.,
2008), Hu et al. propose a weighted regularized matrix factorization (WRMF)
model to treat all the missing data as negative samples, while heuristically
assigning confidence weights to positive samples. Rendle et al. adopt a
different approach in (Rendle et al., 2009), proposing a pair-wise ranking
objective (Bayesian personalized ranking) to model the pair-wise relationships
between positive items and negative items for each user, where the negative
samples are randomly sampled from the unobserved feedback. To allow unobserved
items to have varying degrees of importance, He et al. in (He et al., 2016)
propose to weight the missing data based on item popularity, demonstrating
improved performance compared to WRMF.

Multi-layer Perceptron-based Methods. Due to their ability to learn more
complex non-linear relationships between users and items, (deep) neural
networks have been a great success in the domain of recommender systems. He et
al. in (He et al., 2017b) propose a neural network-based collaborative
filtering model, where a multi-layer perceptron is used to learn the non-
linear user-item interactions. In (Wu et al., 2016; Ma et al., 2018, 2019b),
(denoising) autoencoders are employed to learn the user or item hidden
representations from user implicit feedback. Autoencoder approaches can be
shown to be generalizations of many of the MF methods (Wu et al., 2016). In
(Xue et al., 2017; Guo et al., 2017), conventional matrix factorization and
factorization machine methods benefit from the representation ability of deep
neural networks for learning either the user-item relationships or the
interactions with side information. Graph neural networks (GNNs) have recently
been incorporated in recommendation algorithms because they can learn and
model relationships between entities (Wang et al., 2019; Sun et al., 2019; Ma
et al., 2020).

Distance-based Methods. Due to their capacity to measure the distance between
users and items, distance-based methods have been successfully applied in
Top-K recommendation. In (Hsieh et al., 2017), Hsieh et al. propose to compute
the Euclidean distance between users and items for capturing fine-grained user
preference. In (Tay et al., 2018), Tay et al. adopt a memory network
(Sukhbaatar et al., 2015) to explicitly store the user preference in external
memories. Park et al. in (Park et al., 2018) apply a translation emb edding to
capture more complex relations between users and items, where the translation
embedding is learned from the neighborhood information of users and items. In
(He et al., 2017a), He et al. apply a distance metric to capture how the user
interest shifts across sequential user-item interactions. In (Li et al.,
2020), Li et al. propose to measure the trilateral relationship from both the
user-centric and item-centric perspectives and learn adaptive margins for the
central user and positive item.

Our proposed recommendation model is different in key ways from all of the
methods identified above. In contrast to the matrix factorization (Hu et al.,
2008; Rendle et al., 2009; He et al., 2016) and neural network methods (He et
al., 2017b; Wu et al., 2016; Ma et al., 2018, 2019b; Xue et al., 2017; Guo et
al., 2017; Wang et al., 2019), we employ the Wasserstein distance that obeys
the triangle inequality. This is important for ensuring that users with
similar interaction histories are mapped close together in the latent space.
In contrast to most of the prior distance-based approaches, (Hsieh et al.,
2017; Tay et al., 2018; Park et al., 2018; Li et al., 2020), we employ
parameterized Gaussian distributions to represent each user and item in order
to capture the uncertainties of learned user preferences and item properties.
Moreover, we formulate a bilevel optimization problem and incorporate a neural
network to generate adaptive margins for the commonly applied margin ranking
loss function.

##  3\. Problem Formulation

The recommendation task considered in this paper takes as input the user
implicit feedback. For each user $i$, the user preference data is represented
by a set that includes the items she preferred, e.g.,
$\mathcal{D}_{i}=\\{I_{1},...,I_{j},...,I_{|\mathcal{D}_{i}|}\\}$, where
$I_{j}$ is an item index in the dataset. The top-$K$ recommendation task in
this paper is formulated as: given the training item set $\mathcal{S}_{i}$,
and the non-empty test item set $\mathcal{T}_{i}$ (requiring that
$\mathcal{S}_{i}\cup\mathcal{T}_{i}=\mathcal{D}_{i}$ and
$\mathcal{S}_{i}\cap\mathcal{T}_{i}=\emptyset$) of user $i$, the model must
recommend an ordered set of items $\mathcal{X}_{i}$ such that
$|\mathcal{X}_{i}|\leq K$ and $\mathcal{X}_{i}\cap\mathcal{S}_{i}=\emptyset$.
Then the recommendation quality is evaluated by a matching score between
$\mathcal{T}_{i}$ and $\mathcal{X}_{i}$, such as Recall@$K$.

##  4\. Methodology

In this section, we present the proposed model shown in Fig. 2. We first
introduce the user-item interaction module, which captures the user-item
interactions by calculating the Wasserstein distance between users’ and items’
distributions. Then we describe the adaptive margin generation module, which
generates adaptive margins during the training process. Next, we present the
user-user and item-item relation modeling module. Lastly, we specify the
objective function and explain the training process of the proposed model.

Figure 2. The demonstration of the proposed model. $\mathcal{J}^{U-I}$ denotes
the combined optimization regarding $\mathcal{J}_{inner}^{U-I}$ and
$\mathcal{J}_{outer}^{U-I}$. $\mathcal{J}^{U-U}$ and $\mathcal{J}^{I-I}$
follow the same manner with $\mathcal{J}^{U-I}$.

###  4.1. Wasserstein Distance for Interactions

Previous works (Hsieh et al., 2017; Tay et al., 2018) use the user and item
embeddings in a deterministic manner and do not measure or learn the
uncertainties of user preferences and item properties. Motivated by
probabilistic matrix factorization (PMF) (Salakhutdinov and Mnih, 2007), we
represent each user or item as a single Gaussian distribution. In contrast to
PMF, which applies Gaussian priors on user and item embeddings, users and
items in our model are parameterized by Gaussian distributions, where the
means $\mu$ and covariances $\Sigma$ are directly learned. Specifically, the
latent factors of user $i$ and item $j$ are represented as:

(1) $\displaystyle\mathbf{u}_{i}$
$\displaystyle\sim\mathcal{N}(\mathbf{\mu}^{(U)}_{i},\mathbf{\Sigma}^{(U)}_{i})\,,$
$\displaystyle\mathbf{v}_{j}$
$\displaystyle\sim\mathcal{N}(\mathbf{\mu}^{(I)}_{j},\mathbf{\Sigma}^{(I)}_{j})\,.$

Here $\mathbf{\mu}^{(U)}_{i}$ and $\mathbf{\Sigma}^{(U)}_{i}$ are the learned
mean vector and covariance matrix of user $i$, respectively;
$\mathbf{\mu}^{(I)}_{j}$ and $\mathbf{\Sigma}^{(I)}_{j}$ are the learned mean
vector and covariance matrix of item $j$. To limit the complexity of the model
and reduce the computational overhead, we assume that the embedding dimensions
are uncorrelated. Thus, $\mathbf{\Sigma}$ is a diagonal covariance matrix that
can be represented as a vector. Specifically, $\mathbf{\mu}\in\mathbb{R}^{h}$
and $\mathbf{\Sigma}\in\mathbb{R}^{h}$, where $h$ is the dimension of the
latent space.

Widely used distance metrics for deterministic embeddings, like the Euclidean
distance, do not properly measure the distance between distributions. Since
users and items are represented by probabilistic distributions, we need a
distance measure between distributions. Among the commonly used distance
metric between distributions, we adopt the Wasserstein distance to measure the
user preference for an item. The reasons are twofold: i) the Wasserstein
distance satisfies all the properties a distance should have; and ii) the
Wasserstein distance has a simple form when calculating the distance between
Gaussian distributions (Mallasto and Feragen, 2017). Formally, the $p$-th
Wasserstein distance between two probability measures $\mu$ and $\nu$ on a
Polish metric space (Srivastava, 2008) $(\mathcal{X},d)$ is defined (Givens
and Shortt, 1984):

$\mathcal{W}_{p}(\mu,\nu):=\Big{(}\inf_{J\in\mathcal{J}(\mu,\nu)}\int_{\mathcal{X}\times\mathcal{X}}d(x,y)^{p}dJ(x,y)\Big{)}^{\frac{1}{p}}\,,$

where $d(\cdot,\cdot)^{p}$ is an arbitrary distance with $p^{th}$ moment
(Casella and Berger, 2002) for a deterministic variable, $p\in[1,+\infty)$;
and $\mathcal{J}(\mu,\nu)$ denotes the set of all measures $J$ on
$\mathcal{X}\times\mathcal{X}$ which admit $\mu$ and $\nu$ as marginals. When
$p\geq 1$, the $p$-th Wasserstein distance preserves all properties of a
metric, including both symmetry and the triangle inequality.

The calculation of the general Wasserstein distance is computation-intensive
(Xie et al., 2019). To reduce the computational cost, we use Gaussian
distributions for the latent representations of users and items. Then when
$p=2$, the $2$-nd Wasserstein distance (abbreviated as $\mathcal{W}_{2}$) has
a closed form solution, thus making the calculation process much faster.
Specifically, we have the following formula to calculate the $\mathcal{W}_{2}$
distance between user $i$ and item $j$ (Givens and Shortt, 1984):

(2)
$\displaystyle\mathcal{W}_{2}\left(\mathcal{N}(\mathbf{\mu}^{(U)}_{i},\mathbf{\Sigma}^{(U)}_{i}),\,\mathcal{N}(\mathbf{\mu}^{(I)}_{j},\mathbf{\Sigma}^{(I)}_{j})\right)^{2}$
$\displaystyle=||\mathbf{\mu}^{(U)}_{i}-\mathbf{\mu}^{(I)}_{j}||_{2}^{2}+\mathrm{trace}\bigg{(}\mathbf{\Sigma}^{(U)}_{i}+\mathbf{\Sigma}^{(I)}_{j}-2\Big{(}(\mathbf{\Sigma}^{(U)}_{i})^{\frac{1}{2}}\mathbf{\Sigma}^{(I)}_{j}(\mathbf{\Sigma}^{(U)}_{i})^{\frac{1}{2}}\Big{)}^{\frac{1}{2}}\bigg{)}\,.$

In our setting, we focus on diagonal covariance matrices, thus
$\mathbf{\Sigma}^{(U)}_{i}\mathbf{\Sigma}^{(I)}_{j}=\mathbf{\Sigma}^{(I)}_{j}\mathbf{\Sigma}^{(U)}_{i}$.
For simplicity, we use $\mathcal{W}_{2}(i,j)^{2}$ to denote the left hand side
of Eq. 2. Then Eq. 2 can be simplified as:

(3)
$\mathcal{W}_{2}(i,j)^{2}=||\mathbf{\mu}^{(U)}_{i}-\mathbf{\mu}^{(I)}_{j}||_{2}^{2}+||(\mathbf{\Sigma}^{(U)}_{i})^{\frac{1}{2}}-(\mathbf{\Sigma}^{(I)}_{j})^{\frac{1}{2}}||^{2}_{2}\,.$

According to the above equation, the time complexity of calculating
$\mathcal{W}_{2}$ distance between the latent representations of users and
items is linear with the embedding dimension.

###  4.2. Adaptive Margin in Margin Ranking Loss

To learn the distance-based model, most of the existing works (Hsieh et al.,
2017; Tay et al., 2018) apply the margin ranking loss to measure the user
preference difference between positive items and negative items. Specifically,
the margin ranking loss makes sure the distance between a user and a positive
item is less than the distance between the user and a negative item by a fixed
margin $m>0$. The loss function is:

(4)
$\mathcal{L}_{Fix}(i,j,k;\Theta)=[d(i,j;\Theta)^{2}-d(i,k;\Theta)^{2}+m]_{+}\,,$

where $j\in\mathcal{S}_{i}$ is an item that user $i$ has accessed, and
$k\not\in\mathcal{S}_{i}$ is a randomly sampled item treated as the negative
example, and $[z]_{+}=\max(z,0)$. Thus, $(i,j,k)$ represents a training
triplet.

The safe margin $m$ in the margin ranking loss is a crucial hyper-parameter
that has a major impact on the model performance. A fixed margin value may not
achieve satisfactory performance. First, using a fixed value does not allow
for adaptation to distinguish the properties of the training triplets. For
example, some users have broad interests, so the margins for these users
should not be so large as to make potential preferred items too far from the
user. Other users have very focused interests, and it is desirable to have a
larger margin to avoid recommending items that are not directly within the
focus. Second, in different training phases, the model may need different
magnitudes of margins. For instance, in the early stage of training, the model
is not reliable enough to make strong predictions on user preferences, and
thus imposing a large margin risk pushing potentially positive items too far
from a user. Third, to achieve satisfactory performance, the selection of a
fixed margin involves tedious hyper-parameter tuning. Based on these
considerations, we conclude that setting a fixed margin value for all training
triplets may limit the model expressiveness.

To address the problems outlined above, we propose an adaptive margin
generation scheme which generates margins according to the training triplets.
Formally, we formulate the margin ranking loss with an adaptive margin as:

(5)
$\mathcal{L}_{Ada}(i,j,k;\Theta,\Phi)=[d(i,j;\Theta)^{2}-d(i,k;\Theta)^{2}+f(i,j,k;\Phi)]_{+}\,.$

Here $f(i,j,k;\Phi)$ is a function that generates the specific margin based on
the corresponding user and item embeddings and $\Phi$ is the learnable set of
parameters associated with $f(\cdot)$. Then we could consider optimizing
$\Theta$ and $\Phi$ simultaneously:

(6)
$\Theta^{*}=\underset{\Theta,\Phi}{\mathrm{argmin}}\>\sum_{i}\sum_{j\in\mathcal{S}_{i}}\sum_{k\not\in\mathcal{S}_{i}}\mathcal{L}_{Ada}(i,j,k;\Theta,\Phi)\,.$

Unfortunately, directly minimizing the objective function as in Eq. 6 does not
achieve the desired purpose of generating suitable adaptive margins. Since the
margin-related term explicitly appears in the loss function, constantly
decreasing the value of the generated margin is the straightforward way to
reduce the loss. As a result all generated margins have very small values or
are set to zero, leading to unsatisfactory results. In other words, the direct
optimization of $\mathcal{L}_{Ada}$ with respect to $\Phi$ harms the
optimization of $\Theta$.

####  4.2.1. Bilevel Optimization

We model the learning of recommendation models and the generation of adaptive
margins as a bilevel optimization problem (Colson et al., 2007):

(7)
$\displaystyle\underset{\Phi}{\mathrm{min}}\>\mathcal{J}_{outer}\left(\Theta^{*}(\Phi)\right):=\sum_{i}\sum_{j\in\mathcal{S}_{i}}\sum_{k\not\in\mathcal{S}_{i}}\mathcal{L}_{Fix}\left(i,j,k;\Theta^{*}(\Phi)\right)$
$\displaystyle\mathrm{s.t.}\>\Theta^{*}(\Phi)=\underset{\Theta}{\mathrm{argmin}}\>\mathcal{J}_{inner}(\Theta,\Phi):=\sum_{i}\sum_{j\in\mathcal{S}_{i}}\sum_{k\not\in\mathcal{S}_{i}}\mathcal{L}_{Ada}(i,j,k;\Theta,\Phi)\,.$

Here $\Theta$ contains the model parameters $\mathbf{\mu}$ and
$\mathbf{\Sigma}$. The objective function $\mathcal{J}_{inner}$ attempts to
minimize $\mathcal{L}_{Ada}$ with respect to $\Theta$ while the objective
function $\mathcal{J}_{outer}$ optimizes $\mathcal{L}_{Fix}$ with respect to
$\Phi$ through $\Theta^{*}(\Phi)$. For simplicity, the $m$ of
$\mathcal{L}_{Fix}$ in $\mathcal{J}_{outer}$ is set to $1$ for guiding the
learning of $f(\cdot;\Phi)$. Thus, we can have an alternating optimization to
learn $\Theta$ and $\Phi$:

  * •

$\Theta$ update phase (Inner Optimization): Fix $\Phi$ and optimize $\Theta$.

  * •

$\Phi$ update phase (Outer Optimization): Fix $\Theta$ and optimize $\Phi$.

####  4.2.2. Approximate Gradient Optimization

As most existing models utilize gradient-based methods for optimization, a
simple approximation strategy with less computation is introduced as follows:

(8)
$\displaystyle\nabla_{\Phi}\mathcal{J}_{outer}\left(\Theta^{*}(\Phi)\right)\approx\nabla_{\Phi}\mathcal{J}_{outer}\left(\Theta-\alpha\nabla_{\Theta}\mathcal{J}_{inner}(\Theta,\Phi)\right)\,.$

In this expression, $\Theta$ denotes the current parameters including
$\mathbf{\mu}$ and $\mathbf{\Sigma}$, and $\alpha$ is the learning rate for
one step of inner optimization. Related approximations have been validated in
(Rendle, 2012; Liu et al., 2019). Thus, we can define a proxy function to link
$\Phi$ with the outer optimization:

(9)
$\tilde{\Theta}(\Phi):=\Theta-\alpha\nabla_{\Theta}\mathcal{J}_{inner}(\Theta,\Phi)\,.$

For simplicity, we use two optimizers $\operatorname{OPT}_{\Theta}$ and
$\operatorname{OPT}_{\Phi}$ to update $\Theta$ and $\Phi$, respectively. The
iterative procedure is shown in Alg. 1.

Initialize optimizers $\operatorname{OPT}_{\Theta}$ and
$\operatorname{OPT}_{\Phi}$ ;

while  _not converged_ do

$\Theta$ Update (fix $\Phi^{t}$):

$\Theta^{t+1}\longleftarrow\operatorname{OPT}_{\Theta}\left(\Theta^{t},\nabla_{\Theta^{t}}\mathcal{J}_{inner}(\Theta^{t},\Phi^{t})\right)$
;

Proxy:

$\tilde{\Theta}^{t+1}(\Phi^{t}):=\Theta^{t}-\alpha\nabla_{\Theta^{t}}\mathcal{J}_{inner}(\Theta^{t},\Phi^{t})$
;

$\Phi$ Update (fix $\Theta^{t}$):

$\Phi^{t+1}\longleftarrow\operatorname{OPT}_{\Phi}\left(\Phi^{t},\nabla_{\Phi^{t}}\mathcal{J}_{outer}\big{(}\tilde{\Theta}^{t+1}(\Phi^{t})\big{)}\right)$
;

end while

Algorithm 1 Iterative Optimization Procedure

####  4.2.3. The design of $f(\cdot;\Phi)$

We parameterize $f(i,j,k;\Phi)$ with a neural network to generate the margin
based on $(i,j,k)$:

(10) $\displaystyle\mathbf{z}_{ijk}$
$\displaystyle=\mathrm{tanh}(\mathbf{W}_{1}\cdot\mathbf{s}_{ijk}+\mathbf{b}_{1})\,,$
$\displaystyle m_{ijk}$
$\displaystyle=\mathrm{softplus}(\mathbf{W}_{2}\cdot\mathbf{z}_{ijk}+\mathbf{b}_{2})\,.$

Here $\mathbf{W}_{*}$ and $\mathbf{b}_{*}$ are learnable parameters in
$f(\cdot;\Phi)$, $\mathbf{s}_{ijk}$ is the input to generate the margin, and
$m_{ijk}\in\mathbb{R}$ is the generated margin of $(i,j,k)$. The activation
function softplus guarantees $m_{ijk}>0$. To promote a discrimative
$\mathbf{s}_{ijk}$ that reflects the relation between $(i,j,k)$ and $m_{ijk}$,
the following form can be a fine-grained indicator:

(11) $\displaystyle\chi(\mathbf{u}_{i},\mathbf{v}_{j})$
$\displaystyle=[(u_{i,1}-v_{j,1})^{2},(u_{i,2}-v_{j,2})^{2},...,(u_{i,h}-v_{j,h})^{2}]^{\top}$
$\displaystyle\mathbf{s}_{ijk}$
$\displaystyle=[\chi(\mathbf{u}_{i},\mathbf{v}_{j});\,\chi(\mathbf{u}_{i},\mathbf{v}_{k});\,\chi(\mathbf{u}_{i},\mathbf{v}_{k})\ominus\chi(\mathbf{u}_{i},\mathbf{v}_{j})]\,.$

Here $\chi(\mathbf{u}_{i},\mathbf{v}_{j})\in\mathbb{R}^{h}$ is introduced to
mimic the calculation of Euclidean distance without summing over all
dimensions. $\ominus$ denotes element-wise subtraction and $[...;...]$ denotes
the concatenation operation. To improve the robustness of $f(\cdot;\Phi)$, we
take as inputs the sampled embeddings $\mathbf{u}_{i}$ and $\mathbf{v}_{j}$.
To perform backpropagation from $\mathbf{u}_{i}$ and $\mathbf{v}_{j}$, we
adopt the reparameterization trick (Kingma and Welling, 2014) for Eq. 1:

(12) $\displaystyle\mathbf{u}_{i}$
$\displaystyle=\mathbf{\mu}_{i}^{(U)}+(\mathbf{\Sigma}_{i}^{(U)})^{\frac{1}{2}}\odot\mathbf{\epsilon}_{1}\,,$
$\displaystyle\mathbf{v}_{j}$
$\displaystyle=\mathbf{\mu}_{j}^{(I)}+(\mathbf{\Sigma}_{j}^{(I)})^{\frac{1}{2}}\odot\mathbf{\epsilon}_{2}\,,$

where
$\mathbf{\epsilon}_{1},\mathbf{\epsilon}_{2}\sim\mathcal{N}(\mathbf{0},\mathbf{1})$
and $\odot$ is element-wise muliplication.

###  4.3. User-User and Item-Item Relations

It is important to model the relationships between pairs of users or pairs of
items when developing recommender systems and strategies for doing so
effectively have been studied for many years (Sarwar et al., 2001; Kabbur et
al., 2013; Ning et al., 2015). For example, item-based collaborative filtering
methods use item rating vectors to calculate the similarities between the
items. Closely-related users or items may share the same interests or have
similar attributes. For a certain user, items similar to the user’s preferred
items are potential recommendation candidates.

Despite this intuition, previous distance-based recommendation methods (Hsieh
et al., 2017; Tay et al., 2018) do not explicitly take the user-user or item-
item relationships into consideration. As a result of relying primarily on
user-item information, the systems may fail to generate appropriate user-user
or item-item distances. To model the relationships between similar users or
items, we employ two ranking margin losses with adaptive margins to encourage
similar users or items to be mapped closer together in the latent space.
Formally, the similarities between users or items are calculated from the user
implicit feedback, which can be represented by a binary user-item interaction
matrix. We set a threshold on the calculated similarities to identify the
similar users and items for a specific user $i$ and item $j$, respectively,
denoted as $\mathcal{N}^{U}_{i}$ and $\mathcal{N}^{I}_{j}$. We adopt the
following losses for user pairs and item pairs, respectively:

(15)
$\displaystyle\left\\{\begin{array}[]{rl}\mathcal{J}_{outer}^{U-U}&:=\sum_{i}\sum_{p\in\mathcal{N}_{i}^{U}}\sum_{q\not\in\mathcal{N}_{i}^{U}}\mathcal{L}_{Fix}(i,p,q;\tilde{\Theta}^{t+1}_{U-U})\,,\\\
\mathcal{J}_{inner}^{U-U}&:=\sum_{i}\sum_{p\in\mathcal{N}_{i}^{U}}\sum_{q\not\in\mathcal{N}_{i}^{U}}\mathcal{L}_{Ada}(i,p,q;\Theta^{t},\Phi^{t}_{U-U})\,,\end{array}\right.$
(18)
$\displaystyle\left\\{\begin{array}[]{rl}\mathcal{J}_{outer}^{I-I}&:=\sum_{j}\sum_{p\in\mathcal{N}_{j}^{I}}\sum_{q\not\in\mathcal{N}_{j}^{I}}\mathcal{L}_{Fix}(j,p,q;\tilde{\Theta}^{t+1}_{I-I})\,,\\\
\mathcal{J}_{inner}^{I-I}&:=\sum_{j}\sum_{p\in\mathcal{N}_{j}^{I}}\sum_{q\not\in\mathcal{N}_{j}^{I}}\mathcal{L}_{Ada}(j,p,q;\Theta^{t},\Phi^{t}_{I-I})\,,\end{array}\right.$

where $q$ is a randomly sampled user in Eq. 15 and a randomly sampled item in
Eq. 18. $U-U$ denotes the user-user relation and $I-I$ denotes the item-item
relation. We use $\Phi^{t}_{U-U}$ and $\Phi^{t}_{I-I}$ to update
$\Theta^{t+1}_{U-U}$ and $\Theta^{t+1}_{I-I}$, respectively, which are the
same as in Alg. 1. We denote the indicator in Eq. 11 as
$\mathbf{s}_{ijk}^{U-I}$, then we generate $\mathbf{s}_{ijq}^{U-U}$ and
$\mathbf{s}_{ijq}^{I-I}$ following the procedure described by Eq. 11.

###  4.4. Model Training

Let us denote the losses $\mathcal{J}_{inner}^{U-I}$ and
$\mathcal{J}_{outer}^{U-I}$ to capture the interactions between users and
items. Then we combine the loss functions presented in Section 4.3 to optimize
the proposed model:

(19)
$\displaystyle\mathcal{J}_{inner}=\mathcal{J}_{inner}^{U-I}+\mathcal{J}_{inner}^{U-U}+\mathcal{J}_{inner}^{I-I}\,,$
$\displaystyle\mathcal{J}_{outer}=\mathcal{J}_{outer}^{U-I}+\mathcal{J}_{outer}^{U-U}+\mathcal{J}_{outer}^{I-I}+\lambda||\Phi||_{F}^{2}\,,$

where $\lambda$ is a regularization parameter. We follow the same training
scheme of Section 4.2 to train Eq. 19. To mitigate the curse of dimensionality
issue (Bordes et al., 2013) and prevent overfitting, we bound all the
user/item embeddings within a unit sphere after each mini-batch training:
$||\mathbf{\mu}||\leqslant 1$ and $||\mathbf{\Sigma}||\leqslant 1$. When
minimizing the objective function, the partial derivatives with respect to all
the parameters can be computed by gradient descent with back-propagation.

Recommendation Phase. In the testing phase, for a certain user $i$, we compute
the distance $\mathcal{W}_{2}(i,j)^{2}$ between user $i$ and each item $j$ in
the dataset. Then the items that are not in the training set and have the
shortest distances are recommended to user $i$.

##  5\. Experiments

In this section, we evaluate the proposed model, comparing with the state-of-
the-art methods on five real-world datasets.

###  5.1. Datasets

The proposed model is evaluated on five real-world datasets from various
domains with different sparsities: Books, Electronics and CDs (He and McAuley,
2016), Comics (Wan and McAuley, 2018) and Gowalla (Cho et al., 2011). The
Books, Electronics and CDs datasets are adopted from the Amazon review dataset
with different categories, i.e., books, electronics and CDs. These datasets
include a significant amount of user-item interaction data, e.g., user ratings
and reviews. The Comics dataset was collected in late 2017 from the GoodReads
website with different genres, and we use the genres of comics. The Gowalla
dataset was collected worldwide from the Gowalla website (a location-based
social networking website) over the period from February 2009 to October 2010.
In order to be consistent with the implicit feedback setting, we retain any
ratings no less than four (out of five) as positive feedback and treat all
other ratings as missing entries for all datasets. To filter noisy data, we
only include users with at least ten ratings and items with at least five
ratings. Table 1 shows the data statistics.

We employ five-fold cross-validation to evaluate the proposed model. For each
user, the items she accessed are randomly split into five folds. We pick one
fold each time as the ground truth for testing, and the remaining four folds
constitute the training set. The average results over the five folds are
reported.

Table 1. The statistics of the datasets. Dataset | #Users | #Items | #Interactions | Density
---|---|---|---|---
Books | 77,754 | 66,963 | 2,517,343 | 0.048%
Electronics | 40,358 | 28,147 | 524,906 | 0.046%
CDs | 24,934 | 24,634 | 478,048 | 0.079%
Comics | 37,633 | 39,623 | 2,504,498 | 0.168%
Gowalla | 64,404 | 72,871 | 1,237,869 | 0.034%

###  5.2. Evaluation Metrics

We evaluate all models in terms of Recall@k and NDCG@k. For each user,
Recall@k (R@k) indicates the percentage of her rated items that appear in the
top $k$ recommended items. NDCG@k (N@k) is the normalized discounted
cumulative gain at $k$, which takes the position of correctly recommended
items into account.

###  5.3. Methods Studied

To demonstrate the effectiveness of our model, we compare to the following
recommendation methods.
Classical methods for implicit feedback:

  * •

BPRMF, Bayesian Personalized Ranking-based Matrix Factorization (Rendle et
al., 2009), which is a classic method for learning pairwise personalized
rankings from user implicit feedback.

Classical neural-based recommendation methods:

  * •

NCF, Neural Collaborative Filtering (He et al., 2017b), which combines the
matrix factorization (MF) model with a multi-layer perceptron (MLP) to learn
the user-item interaction function.

  * •

DeepAE, the deep autoencoder (Ma et al., 2018), which utilizes a three-hidden-
layer autoencoder with a weighted loss function.

State-of-the-art distance-based recommendation methods:

  * •

CML, Collaborative Metric Learning (Hsieh et al., 2017), which learns a metric
space to encode the user-item interactions and to implicitly capture the user-
user and item-item similarities.

  * •

LRML, Latent Relational Metric Learning (Tay et al., 2018), which exploits an
attention-based memory-augmented neural architecture to model the
relationships between users and items.

  * •

TransCF, Collaborative Translational Metric Learning (Park et al., 2018),
which employs the neighborhood of users and items to construct translation
vectors capturing the intensity of user–item relations.

  * •

SML, Symmetric Metric Learning with adaptive margin (Li et al., 2020), which
measures the trilateral relationship from both the user- and item-centric
perspectives and learns adaptive margins.

The proposed method:

  * •

PMLAM, the proposed model, which represents each user and item as Gaussian
distributions to capture the uncertainties in user preferences and item
properties, and incorporates an adaptive margin generation mechanism to
generate the margins based on the sampled user-item triplets.

###  5.4. Experiment Settings

In the experiments, the latent dimension of all the models is set to $50$ for
a fair comparison. All the models adopt the same negative sampling strategy
with the proposed model, unless otherwise specified. For BPRMF, the learning
rate is set to $0.001$ and the regularization parameter is set to $0.001$.
With these parameters, the model can achieve good results. For NCF, we follow
the same model structure as in the original paper (He et al., 2017b). The
learning rate is set to $0.001$ and the batch size is set to $1024$. For
DeepAE, we adopt the same model structure employed in the author-provided code
and set the batch size to $512$. The weight of the positive items is selected
from $\\{5,10,15,20\\}$ by a grid search and the weights of all other items
are set to $1$ as recommended in (Hu et al., 2008). For CML, we use the
authors’ implementation to set the margin to $m=1$ and the regularization
parameter to $\lambda_{c}=1$. For LRML, the learning rate is set to $0.001$,
and the number of memories is selected from $\\{5,10,20,25,50,100\\}$ by a
grid search. For TransCF, we follow the settings in the original paper to
select
$\lambda,\,\lambda_{nbr},\,\lambda_{dist}\in\\{0,\,0.001,\,0.01,\,0.1\\}$ and
set the margin to $1$ and batch size to $1000$, respectively. For SML, we
follow the author’s code to set the user and item margin bound $l$ to $1.0$,
$\lambda$ to $0.01$ and $\gamma$ to $10$, respectively.

For our model, both the learning rate and $\lambda$ are set to $0.001$. For
the $Electronics$ and $CDs$ datasets, we randomly sample $10$ unobserved users
or items as negative samples for each user and positive item. This number is
reduced to $2$ for the other datasets to speed up the training process. The
batch size is set to $5000$ for all datasets. The dimension $h$ is set to
$50$. The user and item embeddings are initialized by drawing each vector
element independently from a zero-mean Gaussian distribution with a standard
deviation of $0.01$. Our experiments are conducted with PyTorch running on GPU
machines (Nvidia Tesla P100).

Table 2. The performance comparison of all methods in terms of Recall@10 and NDCG@10. The best performing method is boldfaced. The underlined number is the second best performing method. $*$, $**$, $***$ indicate the statistical significance for $p<=0.05$, $p<=0.01$, and $p<=0.001$, respectively, compared to the best baseline method based on the paired t-test. Improv. denotes the improvement of our model over the best baseline method. | BPRMF | NCF | DeepAE | CML | LRML | TransCF | SML | PMLAM | Improv.
---|---|---|---|---|---|---|---|---|---
Recall@10
Books | 0.0553 | 0.0568 | 0.0817 | 0.0730 | 0.0565 | 0.0754 | 0.0581 | 0.0885** | 8.32%
Electronics | 0.0243 | 0.0277 | 0.0253 | 0.0395 | 0.0299 | 0.0353 | 0.0279 | 0.0469*** | 18.73%
CDs | 0.0730 | 0.0759 | 0.0736 | 0.0922 | 0.0822 | 0.0851 | 0.0793 | 0.1129*** | 22.45%
Comics | 0.1966 | 0.2092 | 0.2324 | 0.1934 | 0.1795 | 0.1967 | 0.1713 | 0.2417 | 4.00%
Gowalla | 0.0888 | 0.0895 | 0.1113 | 0.0840 | 0.0935 | 0.0824 | 0.0894 | 0.1331*** | 19.58%
NDCG@10
Books | 0.0391 | 0.0404 | 0.0590 | 0.0519 | 0.0383 | 0.0542 | 0.0415 | 0.0671** | 13.72%
Electronics | 0.0111 | 0.0125 | 0.0134 | 0.0178 | 0.0117 | 0.0148 | 0.0105 | 0.0234*** | 31.46%
CDs | 0.0383 | 0.0402 | 0.0411 | 0.0502 | 0.0420 | 0.0461 | 0.0423 | 0.0619*** | 23.30%
Comics | 0.2247 | 0.2395 | 0.2595 | 0.2239 | 0.1922 | 0.2341 | 0.1834 | 0.2753* | 6.08%
Gowalla | 0.0806 | 0.0822 | 0.0944 | 0.0611 | 0.0670 | 0.0611 | 0.0823 | 0.0984* | 4.23%

###  5.5. Implementation Details

To speed up the training process, we implement a two-phase sampling strategy.
We sample a number of candidates, e.g., 500, of negative samples for each user
every 20 epochs to form a candidate set. During the next 20 epochs, the
negative samples of each user are sampled from her candidate set. This
strategy can be implemented using multiple processes to further reduce the
training time.

Since none of the processed datasets has inherent user-user/item-item
information, we treat the user-item interaction as a user-item matrix and
compute the cosine similarity for the user and item pairs, respectively
(Sarwar et al., 2001). We set a threshold, e.g., $0.2$ on Amazon and Gowalla
datasets and $0.4$ on the Comics dataset, to select the neighbors. These
thresholds are chosen to ensure a reasonable degree of connectivity in the
constructed graphs.

(a) Recall@k on Books

(b) NDCG@k on Books

(c) Recall@k on Electronics

(d) NDCG@k on Electronics

(e) Recall@k on CDs

(f) NDCG@k on CDs

(g) Recall@k on Comics

(h) NDCG@k on Comics

(i) Recall@k on Gowalla

(j) NDCG@k on Gowalla

Figure 3. The performance comparison on all datasets.

###  5.6. Performance Comparison

The performance comparison is shown in Figure 3 and Table 2. Based on these
results, we have several observations.

Observations about our model. First, the proposed model, PMLAM, achieves the
best performance on all five datasets with both evaluation metrics, which
illustrates the superiority of our model.
Second, PMLAM outperforms SML. Although SML has an adaptive margin mechanism,
it is achieved by having a learnable scalar margin for each user and item and
adding a regularization term to prevent the learned margins from being too
small. It can be challenging to identify an appropriate regularization weight
via hyperparameter tuning. By contrast, PMLAM formulates the adaptive margin
generation as a bilevel optimization, avoiding the additional regularization.
PMLAM employs a neural network to generate the adaptive margin, so the number
of parameters related to margin generation does not increase with the number
of users or items.
Third, PMLAM achieves better performance than TransCF. One major reason is
that TransCF only considers the items rated by a user and the users who rated
an item as the neighbors of the user and item, respectively, which neglects
the user-user/item-item relations. PMLAM models the user-user/item-item
relations by two margin ranking losses with adaptive margins.
Fourth, PMLAM makes better recommendations than CML and LRML. These methods
apply a fixed margin for all user-item triplets and do not measure or model
the uncertainty of learned user/item embeddings. PMLAM represents each user
and item as a Gaussian distribution, where the uncertainties of learned user
preferences and item properties are captured by the covariance matrices.
Fifth, PMLAM outperforms NCF and DeepAE. These are MLP-based recommendation
methods with the ability to capture non-linear user-item relationships, but
they violate the triangle inequality when modeling user-item interaction. As a
result, they can struggle to capture the fine-grained user preference for
particular items (Hsieh et al., 2017).

Other observations. First, all of the results reported for the Comics dataset
are considerably better than those for the other datasets. The other four
datasets are sparser and data sparsity negatively impacts recommendation
performance.
Second, CML, LRML and TransCF perform better than SML on most of the datasets.
The adaptive margin regularization term in SML struggles to adequately
counterbalance SML’s tendency to reduce the loss by imposing small margins.
Although it is reported that SML outperforms CML, LRML and TransCF in (Li et
al., 2020), the experiments are conducted on three relatively small-scale
datasets with only several thousands of users and items. We experiment with
much larger datasets; identifying a successful regularization setting appears
to be more difficult as the number of users increases.
Third, TransCF outperforms LRML on most of the datasets. One possible reason
is that TransCF has a more effective translation embedding learning mechanism,
which incorporates the neighborhood information of users and items. TransCF
also has a regularization term to further pull positive items closer to the
anchor user.
Fourth, CML achieves better performance than LRML on most of the datasets. CML
integrates the weighted approximate-rank pairwise (WARP) weighting scheme
(Weston et al., 2010) in the loss function to penalize lower-ranked positive
items. The comparison between CML and LRML in (Tay et al., 2018) removes this
component of CML. The WARP scheme appears to play an important role in
improving CML’s performance.
Fifth, DeepAE outperforms NCF. The heuristic weighting function of DeepAE can
impose useful penalties to errors that occur during training when positive
items are assigned lower prediction scores.

Table 3. The ablation analysis on the CDs and Electronics datasets. cat
denotes the concatenation operation and add denotes the addition operation.

Architecture | CDs |  Electronics
---|---|---
R@10 | N@10 | R@10 | N@10
(1) ${Fix}^{U-I}$ \+ Deter_Emb | 0.0721 | 0.0371 | 0.0241 | 0.0090
(2) ${Fix}^{U-I}$ \+ Gauss_Emb | 0.0815 | 0.0434 | 0.0296 | 0.0110
(3) ${Ada}^{U-I}$ \+ Deter_Emb | 0.0777 | 0.0415 | 0.0338 | 0.0125
(4) ${Ada}^{U-I}$-$cat$ \+ Deter_Emb | 0.0408 | 0.0204 | 0.0139 | 0.0055
(5) ${Ada}^{U-I}$-$add$ \+ Deter_Emb | 0.0311 | 0.0158 | 0.0050 | 0.0018
(6) ${Ada}^{U-I}$ \+ Gauss_Emb | 0.0856 | 0.0454 | 0.0365 | 0.0155
(7) ${Ada}^{U-I}$ \+ ${Fix}^{U-U}$ \+ ${Fix}^{I-I}$ | 0.0966 | 0.0526 | 0.0429 | 0.0189
(8) PMLAM | 0.1129 | 0.0619 | 0.0469 | 0.0234

###  5.7. Ablation Analysis

To verify and assess the relative effectiveness of the proposed user-item
interaction module, the adaptive margin generation module, and the user-
user/item-item relation module, we conduct an ablation study. Table 3 reports
the performance improvement achieved by each module of the proposed model.
Note that we compute Euclidean distances between deterministic embeddings. In
(1), which serves as a baseline, we use the hinge loss with a fixed margin
(Eq. 4) on deterministic embeddings of users and items to capture the user-
item interaction ($m$ is set to $1$ which is commonly used in (Hsieh et al.,
2017; Tay et al., 2018; Park et al., 2018)). In (2), as an alternative
baseline, we apply the same hinge loss as in (1), but replace the
deterministic embeddings with parameterized Gaussian distributions (Section
4.1). In (3), we use the adaptive margin generation module (Section 4.2) to
generate the margins for deterministic embeddings. In (4), we concatenate the
deterministic embeddings of $(i,j,k)$ to generate $\mathbf{s}_{ijk}$ instead
of using Eq. 11. In (5), we sum the deterministic embeddings of $(i,j,k)$ to
generate $\mathbf{s}_{ijk}$ instead of using Eq. 11. In (6), we combine (2)
and (3) to generate the adaptive margins for Gaussian embeddings. In (7), we
augment (6) with user-user/item-item modeling but with a fixed margin, where
the margin is also set to $1$. In (8), we add the user-user/item-item modeling
with adaptive margins (Section 4.3) to replace the fixed margins in the
configuration of (7).

From the results in Table 3, we have several observations. First, from (1) and
(2), we observe that by representing the user and item as Gaussian
distributions and computing the distance between Gaussian distributions, the
performance improves. This suggests that measuring the uncertainties of
learned embeddings is significant. Second, from (1) and (3) along with (2) and
(6), we observe that incorporating the adaptive margin generation module
improves performance, irrespective of whether deterministic or Gaussian
embeddings are used. These results demonstrate the effectiveness of the
proposed margin generation module. Third, from (3), (4) and (5), we observe
that our designed inputs (Eq. 11) for margin generation facilitate the
production of appropriate margins compared to commonly used embedding
concatenation or summation operations. Fourth, from (2), (3) and (6), we
observe that (6) achieves better results than either (2) or (3), demonstrating
that Gaussian embedddings and adaptive margin generation are compatible and
can be combined to improve the model performance. Fifth, compared to (6), we
observe that the inclusion of the user-user and item-item terms in the
objective function (7) leads to a large improvement in recommendation
performance. This demonstrates that explicit user-user/item-item modeling is
essential and can be an effective supplement to infer user preferences. Sixth,
from (7) and (8), we observe that adaptive margins also improve the modelling
of the user-user/item-item relations.

Table 4. A case study of the generated margin of sampled training triplets.
The movie genre label is from the dataset.

User | Positive | Sampled Movie | Margin
---|---|---|---
405 | Scream (Thriller) |  Four Rooms (Thriller) | 1.2752
Toy Story (Animation) | 12.8004
French Kiss (Comedy) |  Addicted to Love (Comedy) | 2.6448
Batman (Action) | 12.4607
66 | Air Force One (Action) |  GoldenEye (Action) | 0.3216
Crumb (Documentary) | 5.0010
The Godfather (Crime) |  The Godfather II (Crime) | 0.0067
Terminator (Sci-Fi) | 3.6335

###  5.8. Case Study

In this section, we conduct case studies to confirm whether the adaptive
margin generation can produce appropriate margins. To achieve this purpose, we
train our model on the MovieLens-100K dataset. This dataset provides richer
side information about movies (e.g., movie genres), making it easier for us to
illustrate the results. Since we only focus on the adaptive margin generation,
we use deterministic embeddings of users and items to avoid the interference
of other modules. We randomly sample users from the dataset. For each user, we
sample one item that the user has accessed as the positive item and two items
the user did not access as negative items, where one item has a similar genre
with the positive item and the other does not. The case study results are
shown in Table 4.

As shown in Table 4, our adaptive margin generation module tends to generate a
smaller margin value when the negative movie has a similar genre with the
positive movie, while generating larger margins when they are distinct. The
generated margins thus encourage the model to embed items with a higher
probability of being preferred closer to the user’s embedding.

##  6\. Conclusion

In this paper, we propose a distance-based recommendation model for top-K
recommendation. Each user and item in our model are represented by Gaussian
distributions with learnable parameters to handle the uncertainties. By
incorporating an adaptive margin scheme, our model can generate fine-grained
margins for the training triples during the training procedure. To explicitly
capture the user-user/item-item relations, we adopt two margin ranking losses
with adaptive margins to force similar user and item pairs to map closer
together in the latent space. Experimental results on five real-world datasets
validate the performance of our model, demonstrating improved performance
compared to many state-of-the-art methods and highlighting the effectiveness
of the Gaussian embeddings and the adaptive margin generation scheme. The code
is available at https://github.com/huawei-noah/noah-
research/tree/master/PMLAM.

## References

  * (1)
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko. 2013\.  Translating Embeddings for Modeling Multi-relational Data. In _Advances in Neural Information Processing Systems_.
  * Casella and Berger (2002) George Casella and Roger L Berger. 2002.  _Statistical inference_.  Duxbury Pacific Grove, CA.
  * Cho et al. (2011) Eunjoon Cho, Seth A. Myers, and Jure Leskovec. 2011\.  Friendship and mobility: user movement in location-based social networks. In _Proc. ACM Conf. Knowledge Discovery and Data Mining_.
  * Colson et al. (2007) Benoît Colson, Patrice Marcotte, and Gilles Savard. 2007\.  An overview of bilevel optimization.  _Annals OR_ (2007).
  * Covington et al. (2016) Paul Covington, Jay Adams, and Emre Sargin. 2016\.  Deep Neural Networks for YouTube Recommendations. In _Proc. ACM Conf. Recommender Systems_.
  * Givens and Shortt (1984) Clark R. Givens and Rae Michael Shortt. 1984.  A class of Wasserstein metrics for probability distributions.  _The Michigan Mathematical Journal_ (1984).
  * Guo et al. (2017) Huifeng Guo, Ruiming Tang, Yunming Ye, Zhenguo Li, and Xiuqiang He. 2017.  DeepFM: A Factorization-Machine based Neural Network for CTR Prediction. In _Proc. Int. Joint Conf. Artificial Intelligence_.
  * He et al. (2017a) Ruining He, Wang-Cheng Kang, and Julian McAuley. 2017a.  Translation-based Recommendation. In _Proc. ACM Conf. Recommender Systems_.
  * He and McAuley (2016) Ruining He and Julian McAuley. 2016.  Ups and Downs: Modeling the Visual Evolution of Fashion Trends with One-Class Collaborative Filtering. In _Proc. Int. Conf. World Wide Web_.
  * He et al. (2017b) Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. 2017b.  Neural Collaborative Filtering. In _Proc. Int. Conf. World Wide Web_.
  * He et al. (2016) Xiangnan He, Hanwang Zhang, Min-Yen Kan, and Tat-Seng Chua. 2016.  Fast Matrix Factorization for Online Recommendation with Implicit Feedback. In _Proc. ACM Int. Conf. Research and Development in Information Retrieval_.
  * Hsieh et al. (2017) Cheng-Kang Hsieh, Longqi Yang, Yin Cui, Tsung-Yi Lin, Serge J. Belongie, and Deborah Estrin. 2017\.  Collaborative Metric Learning. In _Proc. Int. Conf. World Wide Web_.
  * Hu et al. (2008) Yifan Hu, Yehuda Koren, and Chris Volinsky. 2008.  Collaborative Filtering for Implicit Feedback Datasets. In _Proc. IEEE Int. Conf. Data Mining_.
  * Kabbur et al. (2013) Santosh Kabbur, Xia Ning, and George Karypis. 2013.  FISM: factored item similarity models for top-N recommender systems. In _Proc. ACM Conf. Knowledge Discovery and Data Mining_.
  * Kingma and Welling (2014) Diederik P. Kingma and Max Welling. 2014.  Auto-Encoding Variational Bayes. In _Proc. Int. Conf. Learning Representations_.
  * Koren et al. (2009) Yehuda Koren, Robert M. Bell, and Chris Volinsky. 2009\.  Matrix Factorization Techniques for Recommender Systems.  _IEEE Computer_ (2009).
  * Li et al. (2020) Mingming Li, Shuai Zhang, Fuqing Zhu, Wanhui Qian, Liangjun Zang, Jizhong Han, and Songlin Hu. 2020.  Symmetric Metric Learning with Adaptive Margin for Recommendation.  (2020).
  * Liu et al. (2019) Hanxiao Liu, Karen Simonyan, and Yiming Yang. 2019\.  DARTS: Differentiable Architecture Search. In _Proc. Int. Conf. Learning Representations_.
  * Ma et al. (2019a) Chen Ma, Peng Kang, and Xue Liu. 2019a.  Hierarchical Gating Networks for Sequential Recommendation. In _Proc. ACM Conf. Knowledge Discovery and Data Mining_.
  * Ma et al. (2019b) Chen Ma, Peng Kang, Bin Wu, Qinglong Wang, and Xue Liu. 2019b.  Gated Attentive-Autoencoder for Content-Aware Recommendation. In _Proc. ACM Int. Conf. Web Search and Data Mining_.
  * Ma et al. (2020) Chen Ma, Liheng Ma, Yingxue Zhang, Jianing Sun, Xue Liu, and Mark Coates. 2020\.  Memory Augmented Graph Neural Networks for Sequential Recommendation. In _AAAI_.
  * Ma et al. (2018) Chen Ma, Yingxue Zhang, Qinglong Wang, and Xue Liu. 2018\.  Point-of-Interest Recommendation: Exploiting Self-Attentive Autoencoders with Neighbor-Aware Influence. In _Proc. ACM Int. Conf. Information and Knowledge Management_.
  * Mallasto and Feragen (2017) Anton Mallasto and Aasa Feragen. 2017.  Learning from uncertain curves: The 2-Wasserstein metric for Gaussian processes. In _Advances in Neural Information Processing Systems_.
  * Ning et al. (2015) Xia Ning, Christian Desrosiers, and George Karypis. 2015\.  A Comprehensive Survey of Neighborhood-Based Recommendation Methods.  In _Recommender Systems Handbook_.
  * Pan et al. (2008) Rong Pan, Yunhong Zhou, Bin Cao, Nathan Nan Liu, Rajan M. Lukose, Martin Scholz, and Qiang Yang. 2008.  One-Class Collaborative Filtering. In _Proc. IEEE Int. Conf. Data Mining_.
  * Park et al. (2018) Chanyoung Park, Donghyun Kim, Xing Xie, and Hwanjo Yu. 2018\.  Collaborative Translational Metric Learning. In _Proc. IEEE Int. Conf. Data Mining_.
  * Rendle (2012) Steffen Rendle. 2012\.  Learning recommender systems with adaptive regularization. In _Proc. ACM Int. Conf. Web Search and Data Mining_.
  * Rendle et al. (2009) Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. 2009.  BPR: Bayesian Personalized Ranking from Implicit Feedback. In _Proc. Conf. Uncertainty in Artificial Intelligence_.
  * Salakhutdinov and Mnih (2007) Ruslan Salakhutdinov and Andriy Mnih. 2007.  Probabilistic Matrix Factorization. In _Advances in Neural Information Processing Systems_.
  * Salakhutdinov et al. (2007) Ruslan Salakhutdinov, Andriy Mnih, and Geoffrey E. Hinton. 2007\.  Restricted Boltzmann machines for collaborative filtering. In _Proc. Int. Conf. Machine Learning_.
  * Sarwar et al. (2001) Badrul Munir Sarwar, George Karypis, Joseph A. Konstan, and John Riedl. 2001.  Item-based collaborative filtering recommendation algorithms. In _Proc. Int. Conf. World Wide Web_.
  * Shrivastava and Li (2014) Anshumali Shrivastava and Ping Li. 2014.  Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS). In _Advances in Neural Information Processing Systems_.
  * Sinha et al. (2018) Ankur Sinha, Pekka Malo, and Kalyanmoy Deb. 2018.  A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applications.  _IEEE Trans. Evolutionary Computation_ (2018).
  * Srivastava (2008) Sashi Mohan Srivastava. 2008\.  _A course on Borel sets_.  Springer Science & Business Media.
  * Sukhbaatar et al. (2015) Sainbayar Sukhbaatar, Arthur Szlam, Jason Weston, and Rob Fergus. 2015.  End-To-End Memory Networks. In _Advances in Neural Information Processing Systems_.
  * Sun et al. (2019) Jianing Sun, Yingxue Zhang, Chen Ma, Mark Coates, Huifeng Guo, Ruiming Tang, and Xiuqiang He. 2019.  Multi-graph Convolution Collaborative Filtering. In _Proc. IEEE Int. Conf. Data Mining_.
  * Tay et al. (2018) Yi Tay, Luu Anh Tuan, and Siu Cheung Hui. 2018.  Latent Relational Metric Learning via Memory-based Attention for Collaborative Ranking. In _Proc. Int. Conf. World Wide Web_.
  * Wan and McAuley (2018) Mengting Wan and Julian McAuley. 2018.  Item recommendation on monotonic behavior chains. In _Proc. ACM Conf. Recommender Systems_.
  * Wang et al. (2015) Hao Wang, Naiyan Wang, and Dit-Yan Yeung. 2015.  Collaborative Deep Learning for Recommender Systems. In _Proc. ACM Conf. Knowledge Discovery and Data Mining_.
  * Wang et al. (2019) Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. 2019.  Neural Graph Collaborative Filtering. In _Proc. ACM Int. Conf. Research and Development in Information Retrieval_.
  * Weston et al. (2010) Jason Weston, Samy Bengio, and Nicolas Usunier. 2010\.  Large scale image annotation: learning to rank with joint word-image embeddings.  _Machine Learning_ (2010).
  * Wu et al. (2016) Yao Wu, Christopher DuBois, Alice X. Zheng, and Martin Ester. 2016.  Collaborative Denoising Auto-Encoders for Top-N Recommender Systems. In _Proc. ACM Int. Conf. Web Search and Data Mining_.
  * Xie et al. (2019) Yujia Xie, Xiangfeng Wang, Ruijia Wang, and Hongyuan Zha. 2019\.  A Fast Proximal Point Method for Computing Exact Wasserstein Distance. In _Proc. Conf. Uncertainty in Artificial Intelligence_.
  * Xue et al. (2017) Hong-Jian Xue, Xinyu Dai, Jianbing Zhang, Shujian Huang, and Jiajun Chen. 2017.  Deep Matrix Factorization Models for Recommender Systems. In _Proc. Int. Joint Conf. Artificial Intelligence_.