# Jet Tagging with More-Interaction Particle Transformer

Yifan Wu  College of Science, University of Shanghai for Science and
Technology, Shanghai 200093, China  Kun Wang<EMAIL_ADDRESS>College of
Science, University of Shanghai for Science and Technology, Shanghai 200093,
China  Jingya Zhu  School of Physics and Electronics, Henan University,
Kaifeng 475004, China

###### Abstract

In this study, we introduce the More-Interaction Particle Transformer
(MIParT), a novel deep learning neural network designed for jet tagging. This
framework incorporates our own design, the More-Interaction Attention (MIA)
mechanism, which increases the dimensionality of particle interaction
embeddings. We tested MIParT using the top tagging and quark-gluon datasets.
Our results show that MIParT not only matches the accuracy and AUC of
LorentzNet but also significantly outperforms the ParT model in background
rejection. Specifically, it improves background rejection by approximately 25%
at a 30% signal efficiency on the top tagging dataset and by 3% on the quark-
gluon dataset. Additionally, MIParT requires only 30% of the parameters and
47% of the computational complexity needed by ParT, proving that high
performance can be achieved with reduced model complexity and without
extensive pretraining on large datasets. The results suggest that MIParT has
the potential to advance efficiency benchmarks for jet tagging and event
identification in particle physics.

##  I Introduction

Jet identification has become a key area where machine learning is applied in
high-energy physics, and has made significant progress in the last few decades
[1, 2]. Jets are collimated sprays of particles produced in high-energy
collisions, typically from quarks, gluons, or the hadronic decay of heavy
particles. The process known as jet tagging, which involves identifying the
particle that initiated the jet, is complex and challenging. This complexity
arises because the initial particle decays into a jet through multiple stages,
increasing the number of particles within the jet and obscuring the
characteristics of the initiating particle.

By analyzing the constituents of a jet, it is possible to determine the type
of particle that initiated the jet. This identification is critical for
revealing fundamental physical processes and discovering new particles.
Initially, jet tagging relied heavily on quantum chromodynamics (QCD) theory,
which provided methodologies for distinguishing between quark and gluon jets
[3, 4, 5, 6, 7, 8, 9]. With the advent of machine learning, a variety of new
jet tagging methods have been introduced that utilize different machine
learning models to improve the breadth and accuracy of the techniques [10, 11,
12, 13, 14, 15]. Recent advances in deep learning have further refined jet
tagging methods, allowing modern algorithms to effectively process large and
complex datasets. These algorithms are adept at identifying subtle patterns
that differentiate various types of jets, significantly improving the accuracy
and efficiency of jet tagging [16, 17, 18, 19, 20]. The exceptional ability of
deep learning to handle large data sets has been instrumental in these
advances, leading to the discovery of new physical phenomena and deepening our
understanding of particle interactions [20].

Jet tagging has undergone many changes over the years. Initially, traditional
methods relied heavily on expert-designed features based on physical
principles. The introduction of machine learning brought more advanced
approaches, starting with the concept of jet images. These images,
representing pixelated depictions of the energy deposited by particles in a
detector, marked a pivotal development in the field. The earliest application
of jet images dates back to 1991, when Pumplin introduced the idea of
representing jets as images [21]. Subsequent studies, starting around 2014,
were inspired by computer vision. These studies used techniques such as
Fisher’s Linear Discriminant, originally used in face recognition technology,
to improve jet tagging [10]. By 2015, deep neural networks (DNNs) were being
applied to top tagging [11], and later convolutional neural networks (CNNs)
were widely adopted in jet tagging [12, 13, 14, 22, 15], demonstrating
significant improvements in jet tagging performance.

In 2016, sequence-based representations began to gain traction in the field of
jet tagging, using recurrent neural networks (RNNs) to process ordered data.
This period marked a significant advancement with the pioneering use of Long
Short-Term Memory (LSTM) networks for classification purposes [23].
Subsequently, Gated Recurrent Units (GRUs) were also used for event topology
classification, further extending the applications of RNNs in this domain
[18]. At the same time, an innovative approach combining CNNs and LSTMs, known
as DeepJet, was developed. This hybrid model significantly improved the
performance of quark-gluon tagging [24]. Additionally, several studies using
RNNs introduced new methods and insights [25, 26]. These methods have
successfully overcome the limitations associated with input size in jet
tagging, providing a more flexible approach to analyzing and utilizing jet
data.

In 2017, the introduction of graph-based representations using graph neural
networks (GNNs) marked a significant leap forward in jet tagging [27].
Subsequently, GNNs began to be widely used in particle identification, greatly
expanding the capabilities of the field [28, 29, 30, 31]. This broad
application of GNNs has opened new avenues for accurately classifying and
understanding complex particle interactions.

In 2018, the exploration of point cloud representations, which treat jets as
unordered sets of particles, marked a notable advancement. Komiske et al.
introduced the concept of Energy Flow Networks (EFNs), which can deal with
variable-length unordered particle sets effectively [32]. This method utilizes
the “Deep Sets” concept, developed by Zaheer et al. in 2017 [33], which treats
jets specifically as sets of particles and represents a significant advance in
jet tagging. Crucially, it made the algorithms permutation-invariant, thereby
enhancing their capability to represent complex particle interactions.

In 2019, Qu et al. introduced ParticleNet [34], building on the Dynamic Graph
Convolutional Neural Network (DGCNN) framework developed by Wang et al. in
2018 [35] . ParticleNet, which also treats jets as unordered sets of
particles, marked significant advancements in this field. Recently, in 2022,
Qu et al. further extended their contributions by developing the Particle
Transformer (ParT) [36], which is based on the Transformer architecture [37].
Utilizing their own extensive dataset, JetClass, ParT underwent pre-training,
significantly enhancing its capabilities. At the same time, by incorporating
pairwise particle interaction inputs, it significantly improved performance on
jet tagging.

However, the currently most efficient jet tagging models, the pre-trained ParT
models, not only require pre-training, but also have a significant number of
parameters. In addition, other transformer-based jet taggers fail to surpass
the DGCNN-based ParticleNet due to an insufficient number of jets in the
training samples. This indicates that transformer-based models are effective
at utilizing larger training datasets by utilizing the attention mechanism.
And we observed that pairwise particle interaction inputs play a crucial role
in ParT. Therefore, we aim to construct a transformer-based jet tagging model
with an increased focus on particle interaction inputs, aiming for optimal
results without pre-training.

In this paper, we propose a new jet tagging method based on the Transformer
architecture, called More-Interaction Particle Transformer (MIParT). We
enhanced the algorithm of ParT by modifying the attention mechanism and
increasing the embedding dimensions of the pairwise particle interaction
inputs while reducing the total number of parameters and computational
complexity. We tested MIParT on two widely used jet tagging benchmarks and
found that it achieves improvements over existing methods.

The remainder of this manuscript is organized as follows. In Sec. II, we
provide an overview of various deep learning models and specifically focus on
the architecture of the MIParT. In Sec. III, we detail the experimental
process and follow this with an extensive discussion of the results obtained
from our analysis. In Sec. IV, we end the paper by summarizing the main
conclusions and discussing their implications for future research in this
area.

##  II MIParT Model Architecture

Traditional deep learning models such as CNNs and RNNs face significant
challenges in representing jets effectively. Image representations often
struggle with incorporating particle identity, which affects performance
improvement [10]. Similarly, sequence[23] and tree[25] representations impose
artificial ordering on jet particles, which inherently possess no sequential
structure. Considering a jet as an unordered collection of its constituent
particles provides a more natural representation. This format not only
facilitates the inclusion of particle-specific features, but also guarantees
permutation invariance. Among models that adopt this perspective, ParticleNet
describes jets as “particle clouds” drawing a parallel to the point cloud
technique in 3D shape analysis in computer vision. ParticleNet uses the DGCNN
architecture, with its EdgeConv operations effectively using the local spatial
structures of particle clouds to achieve significant performance improvements.

ParT, a transformative variant based on the Class-Attention in Image
Transformers (CaiT) framework [38], integrates interaction variables as a
secondary input. The self-attention mechanism of this architecture uniquely
addresses all positions within the input sequence, capturing extensive range
dependencies efficiently and maintaining invariance to particle order. By
refining the Multi-Head Attention (MHA) mechanism to include jet particle
interaction variables, ParT not only surpasses traditional transformer models,
but also sets a new benchmark in jet tagging. These modifications position
ParT as the leading model in jet tagging.

Figure 1:  Schematic of the More-Interaction Particle Transformer (MIParT)
architecture. The particle features $\mathbf{x}_{1}$ are processed
sequentially through $K$ MI particle attention blocks and $L$ particle
attention blocks. The interaction features $\mathbf{U}_{1}$ are first fed to
$K$ MI particle attention blocks, then dimensionally reduced by a 1D pointwise
convolution to $\mathbf{U}_{2}$, and then fed to $L$ particle attention
blocks. The MIParT architecture ends with the application of the Class-
Attention in Image Transformers (CaiT) methodology, which uses a class token
$\mathbf{x}_{\rm class}$ to systematically extract and summarize information
from $\mathbf{x}_{3}$ in the class attention blocks.  Figure 2:  Schematic of
the More-Interaction Attention (MIA) architecture. The shape of $\mathbf{U}$
is $(N,N,C)$, while both the input $\mathbf{x}$ and the output
$\mathbf{x^{\prime}}$ have the shape $(N,C)$. MIA maintains a one-to-one
correspondence between the feature dimensions of $\mathbf{U}$, $\mathbf{x}$,
and the heads of MHA $C$.  Figure 3:  Schematic of the MI-Particle Attention
Block / Particle Attention Block architecture. Here, LN represents Layer
Normalization, and GELU represents the Gaussian Error Linear Unit activation
function. The block forms the MI-Particle Attention Block when using MIA and
the Particle Attention Block when using P-MHA.

Based on the ParT framework, we develop the MIParT to enhance the input of
interaction data, as depicted in Fig. 1. MIParT adopts ParT’s input formats
and processes jet data with two distinct inputs:

  * •

Particle Input $\mathbf{x}_{1}$: This comprises a list of $C$ features per
particle, arranged into an array of shape $(N,C)$, where $N$ represents the
number of particles within a jet.

  * •

Interaction Input $\mathbf{U}_{1}$: It includes a matrix of $C^{\prime}$
features for each particle pair, formatted as an array of shape
$(N,N,C^{\prime})$.

The particle input is first transformed by a Multilayer Perceptron (MLP) to
project feature dimensions to $D_{1}$, resulting in an array $\mathbf{x}_{1}$
with dimensions $(N,D_{1})$. Similarly, the interaction input undergoes
Pointwise 1D Convolution processing, yielding $\mathbf{U}_{1}$ with dimensions
$(N,N,D_{1})$. $\mathbf{x}_{1}$ then passes through $K$ MI-Particle Attention
Blocks to generate $\mathbf{x}_{2}$ of the same shape. In each block,
$\mathbf{U}_{1}$ serves as an additional input and is dimensionally reduced by
a Pointwise 1D Convolution to $\mathbf{U}_{2}$, having dimensions
$(N,N,D_{2})$.

Following the structural framework of ParT, $\mathbf{x}_{2}$ progresses
through $L$ Particle Attention Blocks, enhancing with $\mathbf{U}_{2}$ at each
layer, to produce $\mathbf{x}_{3}$. Subsequently, using the CaiT methodology,
a class token $\mathbf{x}_{\text{class}}$ is used to systematically extract
and summarize information from $\mathbf{x}_{3}$ in the class attention blocks.
Finally, this summarized information forms a single vector that is input into
a linear classifier through an MLP and a softmax function to derive the
classification scores.

###  II.1 Particle Attention Block

The Particle Attention Block, a crucial element of the ParT framework, has
been seamlessly integrated into our MIParT model. The architecture of this
block is based on the NormFormer design, specifically using the Layer
Normalization instead of the Batch Normalization. Layer Normalization
optimizes normalization by adjusting each layer individually for every single
sample, enhancing model stability and overall performance across diverse
datasets. The architecture of the Particle Attention Block is illustrated in
Fig. 3. Furthermore, in this configuration, the traditional Multi-Head
Attention (MHA) is substituted by Particle-Multi-Head Attention (P-MHA). This
modification allows for the incorporation of particle interaction features
directly into the attention mechanism, enriching the model’s capability to
capture complex particle dynamics. The P-MHA mechanism, which is key to the
Particle Attention Block, is mathematically expressed as

$\displaystyle\text{P-MHA}(Q,K,V)=\text{SoftMax}\left(\frac{QK^{T}}{\sqrt{d_{k}}}+\mathbf{U}\right)V,$
(1)

where $Q$, $K$, and $V$ are the linear projections of the particle embedding
$x$, and $\mathbf{U}$ represents the interaction embedding. The dimensions of
$\mathbf{U}$ are precisely aligned with the attention heads in the MHA
mechanism, thereby facilitating the integration of particle interaction
features. The specific implementation of P-MHA can be found in Ref. [36]. This
integration significantly enhances the model’s ability to capture complex
particle interactions, which is crucial in particle physics applications.

###  II.2 MI-Particle Attention Blocks

In the original P-MHA mechanism, the feature dimensions of $\mathbf{U}$ align
one-to-one with the heads of MHA, both denoted as $C$. Increasing the feature
dimensions of $\mathbf{U}$ necessitates a proportional increase in the number
of attention heads, which significantly adds to the model’s complexity. To
mitigate this issue, we introduce More-Interaction Attention (MIA) and the MI-
Particle Attention Block. These components replace P-MHA with MIA, as
illustrated in Fig. 2 (MIA architecture) and Fig. 3 (MI-Particle Attention
Block/Particle Attention Block architecture). The MI-Particle Attention Block
incorporates Layer Normalization and the Gaussian Error Linear Unit (GELU)
activation function. When the red block in the Fig. 3 uses MIA, it forms the
MI-Particle Attention Block. Conversely, when it uses P-MHA, it forms the
Particle Attention Block. This approach allows the model to effectively use
interaction inputs without significantly increasing complexity. The MIA is
calculated using the following formula:

$\displaystyle\text{MIA}(\mathbf{U},V)=\text{SoftMax}(\mathbf{U})V,$ (2)

where $V$ is a linear projection of the particle embedding $\mathbf{x}$. In
MIA, each feature dimension of $\mathbf{U}$ and $\mathbf{x}$, as well as each
head, are denoted by $C$, ensuring a one-to-one correspondence.

By increasing the feature dimensions of $\mathbf{U}$, MIA effectively exploits
the interaction inputs without significantly increasing the complexity of the
model. Moreover, the MI-Particle Attention Block, which incorporates self-
attention on $\mathbf{x}$, acts as a supplement in front of the Particle
Attention Block rather than replacing it.

Figure 4:  Schematic of the Class Attention Block architecture. Here, LN
represents Layer Normalization, GELU represents the Gaussian Error Linear Unit
activation function, and MHA stands for the Multi-Head Attention block.

###  II.3 Class Attention Block

We incorporated the Class Attention Block from the ParT framework, inspired by
the CaiT architecture. This block uses a class token
$\mathbf{x}_{\text{class}}$ to efficiently extract information through
attention mechanisms, as depicted in Fig. 4. The Multi-Head Attention inputs
are defined as follows:

$\displaystyle Q$ $\displaystyle=W_{q}\mathbf{x}_{\text{class}}+b_{q},$ (3)
$\displaystyle K$ $\displaystyle=W_{k}\mathbf{z}+b_{k},$ (4) $\displaystyle V$
$\displaystyle=W_{v}\mathbf{z}+b_{v}$ (5)

where $\mathbf{z}=[\mathbf{x}_{\text{class}},\mathbf{x}]$, and $W$ and $b$
represent learnable parameters. This design ensures a lower computational
overhead for the Class Attention mechanism by utilizing the concatenated
vector $\mathbf{z}$.

The Class Attention Block significantly enhances feature extraction from the
input $\mathbf{x}$ by capitalizing on the class token, thereby improving the
model’s focus on essential aspects of the data. This enhancement significantly
improves jet classification performance, making the Class Attention Block as a
crucial component within the ParT framework.

##  III Result and Discussion

Table 1:  Summary of kinematic and particle identification variables included in the top tagging (TOP) and quark-gluon (QG) datasets. Variables present in each dataset are indicated by a star symbol ($\star$). The table lists seven kinematic variables, which describe the physical characteristics of particles relative to the jet axis, and six particle identification variables, which categorize particles based on their type and charge.  Category | Variable | TOP | QG
---|---|---|---
| $\Delta\eta$ | $\star$ | $\star$
| $\Delta\phi$ | $\star$ | $\star$
| log $p_{\rm T}$ | $\star$ | $\star$
Kinematics | log $E$ | $\star$ | $\star$
| $\log{p_{\rm T}}/{p_{\rm T}{\rm(jet)}}$ | $\star$ | $\star$
| $\log{E}/{E{\rm(jet)}}$ | $\star$ | $\star$
| $\Delta R$ | $\star$ | $\star$
| charge |  | $\star$
| Electron |  | $\star$
Particle | Muon |  | $\star$
identification | Photon |  | $\star$
| Charged Hadron |  | $\star$
| Neutral Hadron |  | $\star$

We developed the MIParT model using the PyTorch framework [39], implemented
based on the Weaver111Weaver provides a streamlined yet flexible machine
learning R&D framework for high energy physics,
https://github.com/hqucms/weaver-core., and also referred to the
implementation of particle transformer222The official implementation of
Particle Transformer for Jet Tagging, which includes the code and pre-trained
models, https://github.com/jet-universe/particle_transformer.. The
architecture of our MIParT model includes $K=5$ MI-particle attention blocks,
$L=5$ particle attention blocks, and 2 class attention blocks. For particle
embeddings $\mathbf{x}_{1}$, a three-layer Multi-Layer Perceptron (MLP) is
used, with each layer containing 128, 512, and 64 neurons respectively. This
configuration results in embeddings with a dimensionality of $D_{1}=64$. Each
layer incorporates GELU as the activation function and Layer Normalization.
Additionally, a three-layer, 64-channel Pointwise 1D Convolution is used for
the interaction embeddings $\mathbf{U}_{1}$, performing convolutions only
along the feature dimension. The $\mathbf{U}_{1}$ embeddings are further
processed through a single-layer, 8-channel Pointwise 1D Convolution to
generate $\mathbf{U}_{2}$, achieving a dimensionality of $D_{2}=8$. The MI-
particle attention blocks implement MIA with 64 heads, while the P-MHA and
Class Multi-Head Attention in the particle and class attention blocks utilize
8 heads each. A dropout rate of 0.1 is maintained in all MI-particle and
particle attention blocks, with the class attention blocks being exempt from
dropout. The model was trained on an NVIDIA RTX 4090 GPU, using a learning
rate of 0.001 and a batch size of 256. Training was limited to 15 epochs to
prevent overfitting.

We evaluated the MIParT model on two widely used jet tagging benchmark
datasets, top tagging [16] and quark-gluon datasets [40]. Both datasets
incorporate kinematic variables as particle input features, with particle
identification information included only in the quark-gluon dataset. All these
input features for the two datasets are shown in Table 1.

The seven kinematic input features in the top tagging and quark-gluon datasets
are:

  * •

$\Delta\eta$: the difference in pseudorapidity $\eta$ between the particle and
the jet axis;

  * •

$\Delta\phi$: the difference in azimuthal angle $\phi$ between the particle
and the jet axis;

  * •

$\log p_{\rm T}$: the logarithm of the particle’s transverse momentum $p_{\rm
T}$;

  * •

$\log E$: the logarithm of the particle’s energy;

  * •

$\log{p_{\rm T}}/{p_{\rm T}{\rm(jet)}}$: the logarithm of the particle’s
$p_{\rm T}$ relative to the jet $p_{\rm T}$;

  * •

$\log{E}/{E{\rm(jet)}}$: the logarithm of the particle’s energy relative to
the jet energy;

  * •

$\Delta R$: the angular separation between the particle and the jet axis.

The six particle identification features in the quark-gluon dataset are:

  * •

“Charge”: the electric charge of the particle;

  * •

“Electron”: whether the particle is an electron;

  * •

“Muon”: whether the particle is a muon;

  * •

“Photon”: whether the particle is a photon;

  * •

“Charged Hadron”: whether the particle is a charged hadron;

  * •

“Neutral Hadron”: whether the particle is a neutral hadron.

For particle interaction features, we consider four logarithmic
characteristics $(\ln\Delta,\ln k_{T},\ln z,\ln m^{2})$ derived from the
energy-momentum four-vector $p=(E,p_{x},p_{y},p_{z})$ [41]. These features are
defined as follows:

$\displaystyle\Delta$
$\displaystyle=\sqrt{(y_{a}-y_{b})^{2}+(\phi_{a}-\phi_{b})^{2}},$ (6)
$\displaystyle k_{T}$ $\displaystyle={\rm min}(p_{{\rm T},a},p_{{\rm
T},b})\Delta,$ (7) $\displaystyle z$ $\displaystyle={\rm min}(p_{{\rm
T},a},p_{{\rm T},b})/(p_{{\rm T},a}+p_{{\rm T},b}),$ (8) $\displaystyle m^{2}$
$\displaystyle=(E_{a}+E_{b})^{2}-|{\mathbf{p}_{a}+\mathbf{p}_{b}}|^{2}\,,$ (9)

where $y_{i}$ is the rapidity, $\phi_{i}$ is the azimuthal angle, $p_{{\rm
T},i}$ is the transverse momentum, and $\mathbf{p}_{i}$ is the momentum
3-vector of the particle $i=a,b$. The motivation for selecting these variables
comes from their widespread adoption in several advanced neural networks [34,
36].

Table 2:  Comparative performance of various models on the top tagging dataset. This figure illustrates the results for the MIParT model alongside those of other prominent models such as Particle Flow Network (PFN) [40], particle-level convolutional neural network (P-CNN), ParticleNet [34], Point Cloud Transformer (PCT) [42], LorentzNet [43], and ParT [36]. Metrics of other models are quoted from their published results.  | Accuracy | AUC | $\text{Rej}_{50\%}$ | $\text{Rej}_{30\%}$
---|---|---|---|---
PFN | — | 0.9819 | 247±3 | 888±17
P-CNN | 0.930 | 0.9803 | 201±4 | 759±24
PCT | 0.940 | 0.9855 | 392±7 | 1533±101
LorentzNet | 0.942 | 0.9868 | 498±18 | 2195±173
ParticleNet | 0.940 | 0.9858 | 397±7 | 1615±93
ParT | 0.940 | 0.9858 | 413±16 | 1602±81
MIParT | 0.942 | 0.9868 | 505±8 | 2010±97
Table 3:  Comparative performance of various models on the quark-gluon dataset. This table outlines the results for the MIParT model along with other significant models, including Particle Flow Network (PFN) [40], attention-based Cloud Net (ABCNet) [44], Point Cloud Transformer (PCT) [42], LorentzNet [43], and ParT [36]. Metrics of other models are cited from their published results.  | Accuracy | AUC | $\text{Rej}_{50\%}$ | $\text{Rej}_{30\%}$
---|---|---|---|---
PFN | — | 0.9052 | 37.4±0.7 | —
ABCNet | 0.840 | 0.9126 | 42.6±0.4 | 118.4±1.5
PCT | 0.841 | 0.9140 | 43.2±0.7 | 118.0±2.2
LorentzNet | 0.844 | 0.9156 | 42.4±0.4 | 110.2±1.3
ParT | 0.849 | 0.9203 | 47.9±0.5 | 129.5±0.9
MIParT | 0.851 | 0.9215 | 49.3±0.4 | 133.9±1.4
Table 4:  Parameters, FLOPs, and Accuracy of various models on the top tagging (TOP) and quark-gluon (QG) datasets. Parameters refer to the number of trainable elements within a model, while FLOPs (Floating Point Operations Per Second) measure the computational complexity involved in processing data through the model.  | TOP | QG | Params | FLOPs
---|---|---|---|---
PFN | — |  | 86.1k | 4.62M
P-CNN | 0.930 | — | 354k | 15.5M
ParticleNet | 0.940 | — | 370k | 540M
ParT | 0.940 | 0.849 | 2.14M | 340M
MIParT | 0.942 | 0.851 | 720.9k | 160M
Figure 5:  Performance metrics comparison of MIParT with other models on the
top tagging dataset. This figure displays the Accuracy, AUC, ${\rm
Rej}_{50\%}$, and ${\rm Rej}_{30\%}$ metrics for the MIParT model alongside
Particle Flow Network (PFN) [40], particle-level convolutional neural network
(P-CNN) [34], ParticleNet [34], Point Cloud Transformer (PCT) [42], LorentzNet
[43], and ParT [36]. Metrics of other models are quoted from their published
results. Detailed outcomes are provided in Table 2.  Figure 6:  Performance
metrics comparison of MIParT with other models on the quark-gluon dataset.
This figure displays the Accuracy, AUC, ${\rm Rej}_{50\%}$, and ${\rm
Rej}_{30\%}$ metrics for the MIParT model alongside Particle Flow Network
(PFN) [40], attention-based Cloud Net (ABCNet) [44], Point Cloud Transformer
(PCT) [42], LorentzNet [43], and ParT [36]. Metrics of other models are quoted
from their published results. Detailed outcomes are provided in Table 2.

To evaluate the performance of the MIParT model, we conducted comparative
evaluations with several popular models using the top tagging and quark-gluon
datasets. Our evaluation focused on several key metrics:

  * •

Accuracy: This metric quantifies the proportion of correct predictions made by
the model, including both true positive and true negative identifications.
Mathematically, accuracy is defined as:

$\displaystyle\text{Accuracy}=\frac{TP+TN}{TP+TN+FN+FP}\,,$ (10)

where $TP$ is true positives, $TN$ is true negatives, $FN$ is false negatives,
and $FP$ is false positives.

  * •

AUC (Area Under the Curve): AUC provides a comprehensive measure of model
performance across all classification thresholds. This metric is derived from
the Receiver Operating Characteristic (ROC) curve, which plots the true
positive rate (sensitivity) against the false positive rate (1-specificity)
for various thresholds. This curve illustrates the trade-off between
sensitivity and specificity. An AUC value can range from 0.5, which indicates
no discriminatory ability (similar to random guessing), to 1.0, which
represents perfect discrimination and indicates the model’s excellent ability
to discriminate between classes.

  * •

Background Rejection at a Certain Signal Efficiency, ${\rm Rej}_{X\%}$: This
metric calculates the inverse of the false positive rate (FPR) when the true
positive rate (TPR) is fixed at a certain percentage, commonly referred to as
${\rm Rej}_{X\%}$. It is mathematically expressed as:

$\displaystyle{\rm Rej}_{X\%}=\frac{1}{\text{FPR}}\bigg{|}_{\text{TPR}=X\%}$
(11)

For example, a ${\rm Rej}_{30\%}$ value of 2500 indicates that at a TPR of
30%, the inverse of the FPR is 2500. This equates to only one false positive
for every 2500 negative instances, highlighting the exceptional specificity
and minimal error rate of the model at this level.

Top tagging is a critical task in jet tagging, which is often used in the
search for new physics at the LHC. For this study, we used a top tagging
dataset [16] consisting of 2 million jets, with $t\to bqq^{\prime}$ as the
signal and $q/g$ as the background. This dataset only provides the energy-
momentum four-vectors (kinematic features) for each particle.

In Fig. 5, we showed the performance of our MIParT model compared to other
popular models on the top tagging dataset. The MIParT model achieved accuracy
and AUC metrics nearly identical to those of LorentzNet [43], and its ${\rm
Rej}_{50\%}$ and ${\rm Rej}_{30\%}$ metrics are within the error range
comparable to LorentzNet. Moreover, both MIParT and LorentzNet significantly
outperformed other models, including Particle Flow Network (PFN) [40],
Particle-level Convolutional Neural Network (P-CNN) [34], ParticleNet [34],
Point Cloud Transformer (PCT) [42], and ParT [36], with metrics quoted from
their published results. Detailed comparison results are presented in Table 2.
The MIParT model significantly outperformed ParT in the top tagging benchmark,
with approximately 25% better background rejection at a 30% signal efficiency.
Among the models evaluated, MIParT, along with LorentzNet, ranks at the top
tier, showcasing some of the most robust performances.

Quark-gluon tagging is another crucial jet tagging task. Unlike the top
tagging dataset, the quark-gluon dataset [40] includes not only the kinematic
features of each particle, but also particle identification information. This
dataset allows for a more detailed categorization of particles, including
specific distinctions among electrically charged and neutral hadrons, such as
pions, kaons, and protons. Additionally, like the top tagging dataset, the
quark-gluon dataset contains 2 million jets, with quarks and gluons designated
as the signal and background, respectively.

In Fig. 6, we showed the performance of our MIParT model compared to other
popular models on the quark-gluon dataset. Within this dataset, the MIParT
model significantly outperforms LorentzNet across all metrics, including
accuracy, AUC, ${\rm Rej}_{50\%}$, and ${\rm Rej}_{30\%}$, as well as several
other models. Moreover, only the ParT model approaches the performance of our
model in several metrics, but MIParT still maintains an overall lead over
ParT. In comparison with other models, such as PFN [40], ABCNet [44], and PCT
[42], MIParT demonstrates a substantial lead, with metrics quoted from their
published results. Detailed comparison results on the quark-gluon dataset are
presented in Table 3. MIParT achieves the best performance across all
evaluation metrics, improving background rejection power by approximately 3%
compared to ParT.

In Table 4 we present the parameters, FLOPs (Floating Point Operations Per
Second), and accuracy of various models on the top tagging and quark-gluon
datasets. Parameters denote the number of trainable elements within a model,
which indicates the capacity of the model to learn. Conversely, more
parameters generally increase the complexity of the model. FLOPs measure the
computational complexity required to process data through the model. Reducing
the number of parameters typically reduces FLOPs, simplifying the model and
making it more computationally efficient.

However, reducing the number of parameters to reduce FLOPs usually results in
lower accuracy. In contrast, our MIParT model has only 30% of the parameters
and 47% of the FLOPs of the ParT model, significantly reducing model
complexity. Despite this reduction, there is no compromise in accuracy; in
fact, accuracy improves on both top tagging and quark-gluon datasets.

##  IV Conclusion

In this paper, we propose a novel deep learning approach for jet tagging,
MIParT. MIParT increases the dimensionality of particle interaction embeddings
through More-Interaction Attention (MIA) to better utilize particle
interaction inputs. We tested our model on two popular datasets and compared
it with other models:

  * •

On the Top Tagging Dataset: The MIParT model achieved accuracy and AUC metrics
nearly identical to those of LorentzNet, and its ${\rm Rej}_{50\%}$ and ${\rm
Rej}_{30\%}$ metrics are comparable within the error range to LorentzNet. The
MIParT model significantly outperformed ParT in the top tagging benchmark,
achieving approximately 25% better background rejection at a 30% signal
efficiency. Among the models evaluated, MIParT, along with LorentzNet, ranks
at the top tier, showcasing some of the most robust performances.

  * •

On the Quark-gluon Dataset: The MIParT model significantly outperforms
LorentzNet across all metrics, including accuracy, AUC, ${\rm Rej}_{50\%}$,
and ${\rm Rej}_{30\%}$, as well as several other models. MIParT achieved the
best performance across all evaluation metrics, improving background rejection
power by approximately 3% compared to ParT.

Overall, MIParT outperformed ParT on both the top tagging and quark-gluon
tagging tasks while also exhibiting lower computational complexity and fewer
parameters. Previously, it was generally assumed that transformer-based models
required large-scale dataset pretraining to achieve optimal results. Our
MIParT model demonstrates that with higher-dimensional particle interaction
embeddings, top-tier performance can be achieved without pretraining on large
datasets, even surpassing ParT.

Furthermore, while pretraining ParT on the larger multi-class JETCLASS dataset
and subsequently fine-tuning it on the top tagging dataset can enhance
performance, we plan to explore this approach for MIParT in future work.
Moreover, MIParT is not limited to jet tagging but can also be applied to
event identification, which could be immensely helpful in the search for new
physics signals.

###### Acknowledgements.

The authors would like to thank Huilin Qu for helpful discussions. This work
was supported by the National Natural Science Foundation of China (NNSFC)
under grant Nos. 12275066 and 11605123.

## References

  * Larkoski  _et al._ [2020] A. J. Larkoski, I. Moult, and B. Nachman, Phys. Rept. 841, 1 (2020), arXiv:1709.04464 [hep-ph] .
  * Feickert and Nachman [2021] M. Feickert and B. Nachman, (2021), arXiv:2102.02770 [hep-ph] .
  * Gallicchio and Schwartz [2011] J. Gallicchio and M. D. Schwartz, Phys. Rev. Lett. 107, 172001 (2011), arXiv:1106.3076 [hep-ph] .
  * Gallicchio and Schwartz [2013] J. Gallicchio and M. D. Schwartz, JHEP 04, 090 (2013), arXiv:1211.7038 [hep-ph] .
  * Larkoski  _et al._ [2014] A. J. Larkoski, J. Thaler, and W. J. Waalewijn, JHEP 11, 129 (2014), arXiv:1408.3122 [hep-ph] .
  * Bhattacherjee  _et al._ [2015] B. Bhattacherjee, S. Mukhopadhyay, M. M. Nojiri, Y. Sakaki, and B. R. Webber, JHEP 04, 131 (2015), arXiv:1501.04794 [hep-ph] .
  * Ferreira de Lima  _et al._ [2017] D. Ferreira de Lima, P. Petrov, D. Soper, and M. Spannowsky, Phys. Rev. D 95, 034001 (2017), arXiv:1607.06031 [hep-ph] .
  * Gras  _et al._ [2017] P. Gras, S. Höche, D. Kar, A. Larkoski, L. Lönnblad, S. Plätzer, A. Siódmok, P. Skands, G. Soyez, and J. Thaler, JHEP 07, 091 (2017), arXiv:1704.03878 [hep-ph] .
  * Frye  _et al._ [2017] C. Frye, A. J. Larkoski, J. Thaler, and K. Zhou, JHEP 09, 083 (2017), arXiv:1704.06266 [hep-ph] .
  * Cogan  _et al._ [2015] J. Cogan, M. Kagan, E. Strauss, and A. Schwarztman, JHEP 02, 118 (2015), arXiv:1407.5675 [hep-ph] .
  * Almeida  _et al._ [2015] L. G. Almeida, M. Backović, M. Cliche, S. J. Lee, and M. Perelstein, JHEP 07, 086 (2015), arXiv:1501.05968 [hep-ph] .
  * de Oliveira  _et al._ [2016] L. de Oliveira, M. Kagan, L. Mackey, B. Nachman, and A. Schwartzman, JHEP 07, 069 (2016), arXiv:1511.05190 [hep-ph] .
  * Komiske  _et al._ [2017] P. T. Komiske, E. M. Metodiev, and M. D. Schwartz, JHEP 01, 110 (2017), arXiv:1612.01551 [hep-ph] .
  * Kasieczka  _et al._ [2017] G. Kasieczka, T. Plehn, M. Russell, and T. Schell, JHEP 05, 006 (2017), arXiv:1701.08784 [hep-ph] .
  * Macaluso and Shih [2018] S. Macaluso and D. Shih, JHEP 10, 121 (2018), arXiv:1803.00107 [hep-ph] .
  * Butter  _et al._ [2019] A. Butter _et al._ , SciPost Phys. 7, 014 (2019), arXiv:1902.09914 [hep-ph] .
  * Kagan [2020] M. Kagan, (2020), arXiv:2012.09719 [physics.data-an] .
  * de Lima [2021] R. T. de Lima, (2021), arXiv:2102.06128 [physics.data-an] .
  * Kheddar  _et al._ [2024] H. Kheddar, Y. Himeur, A. Amira, and R. Soualah, (2024), arXiv:2403.11934 [hep-ph] .
  * Mondal and Mastrolorenzo [2024] S. Mondal and L. Mastrolorenzo, (2024), arXiv:2404.01071 [hep-ex] .
  * Pumplin [1991] J. Pumplin, Phys. Rev. D 44, 2025 (1991).
  * Lin  _et al._ [2018] J. Lin, M. Freytsis, I. Moult, and B. Nachman, JHEP 10, 101 (2018), arXiv:1807.10768 [hep-ph] .
  * Guest  _et al._ [2016] D. Guest, J. Collado, P. Baldi, S.-C. Hsu, G. Urban, and D. Whiteson, Phys. Rev. D 94, 112002 (2016), arXiv:1607.08633 [hep-ex] .
  * Bols  _et al._ [2020] E. Bols, J. Kieseler, M. Verzetti, M. Stoye, and A. Stakia, JINST 15, P12012 (2020), arXiv:2008.10519 [hep-ex] .
  * Louppe  _et al._ [2019] G. Louppe, K. Cho, C. Becot, and K. Cranmer, JHEP 01, 057 (2019), arXiv:1702.00748 [hep-ph] .
  * Cheng [2018] T. Cheng, Comput. Softw. Big Sci. 2, 3 (2018), arXiv:1711.02633 [hep-ph] .
  * Henrion  _et al._ [2017] I. Henrion, K. Cranmer, J. Bruna, K. Cho, J. Brehmer, G. Louppe, and G. Rochette (2017).
  * Abdughani  _et al._ [2019] M. Abdughani, J. Ren, L. Wu, and J. M. Yang, JHEP 08, 055 (2019), arXiv:1807.09088 [hep-ph] .
  * Arjona Martínez  _et al._ [2019] J. Arjona Martínez, O. Cerri, M. Pierini, M. Spiropulu, and J.-R. Vlimant, Eur. Phys. J. Plus 134, 333 (2019), arXiv:1810.07988 [hep-ph] .
  * Ren  _et al._ [2020] J. Ren, L. Wu, and J. M. Yang, Phys. Lett. B 802, 135198 (2020), arXiv:1901.05627 [hep-ph] .
  * Ju  _et al._ [2020] X. Ju _et al._ , 33rd Annual Conference on Neural Information Processing Systems (2020), arXiv:2003.11603 [physics.ins-det] .
  * Komiske  _et al._ [2019a] P. T. Komiske, E. M. Metodiev, and J. Thaler, JHEP 01, 121 (2019a), arXiv:1810.05165 [hep-ph] .
  * Zaheer  _et al._ [2017] M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. Salakhutdinov, and A. Smola, (2017), arXiv:1703.06114 [cs.LG] .
  * Qu and Gouskos [2020] H. Qu and L. Gouskos, Phys. Rev. D 101, 056019 (2020), arXiv:1902.08570 [hep-ph] .
  * Wang  _et al._ [2018] Y. Wang, Y. Sun, Z. Liu, S. E. Sarma, M. M. Bronstein, and J. M. Solomon, (2018), arXiv:1801.07829 [cs.CV] .
  * Qu  _et al._ [2022] H. Qu, C. Li, and S. Qian,  _Proceedings of the 39th International Conference on Machine Learning_ , , 18281 (2022), arXiv:2202.03772 [hep-ph] .
  * Vaswani  _et al._ [2017] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, in  _31st International Conference on Neural Information Processing Systems_ (2017) arXiv:1706.03762 [cs.CL] .
  * Cord [2021] M. Cord, in  _IEEE/CVF International Conference on Computer Vision (ICCV)_ (2021).
  * Paszke  _et al._ [2019] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, _et al._ , Advances in neural information processing systems 32 (2019).
  * Komiske  _et al._ [2019b] P. T. Komiske, E. M. Metodiev, and J. Thaler, Journal of High Energy Physics 2019, 1 (2019b).
  * Dreyer and Qu [2021] F. A. Dreyer and H. Qu, JHEP 03, 052 (2021), arXiv:2012.08526 [hep-ph] .
  * Mikuni and Canelli [2021] V. Mikuni and F. Canelli, Mach. Learn. Sci. Tech. 2, 035027 (2021), arXiv:2102.05073 [physics.data-an] .
  * Gong  _et al._ [2022] S. Gong, Q. Meng, J. Zhang, H. Qu, C. Li, S. Qian, W. Du, Z.-M. Ma, and T.-Y. Liu, JHEP 07, 030 (2022), arXiv:2201.08187 [hep-ph] .
  * Mikuni and Canelli [2020] V. Mikuni and F. Canelli, Eur. Phys. J. Plus 135, 463 (2020), arXiv:2001.05311 [physics.data-an] .


# A Digital Marketplace Combining WS-Agreement, Service Negotiation Protocols
and Heterogeneous Services

Ralph Vigne  Faculty of Computer Science
University of Vienna
Vienna, Austria
<EMAIL_ADDRESS>Juergen Mangler  Faculty of Computer Science
University of Vienna
Vienna, Austria
<EMAIL_ADDRESS>Erich Schikuta  Faculty of Computer Science
University of Vienna
Vienna, Austria
<EMAIL_ADDRESS>
###### Abstract

With the ever increasing importance of web services and the Cloud as a
reliable commodity to provide business value as well as consolidate IT
infrastructure, electronic contracts have become very important. WS-Agreement
has itself established as a well accepted container format for describing such
contracts. However, the semantic interpretation of the terms contained in
these contracts, as well as the process of agreeing to contracts when multiple
options have to be considered (negotiation), are still pretty much dealt with
on a case by case basis. In this paper we address the issues of diverging
contracts and varying contract negotiation protocols by introducing the
concept of a contract aware marketplace, which abstracts from the
heterogeneous offers of different services providers. This allows for the
automated consumption of services solely based on preferences, instead of
additional restrictions such as understanding of contract terms and/or
negotiation protocols. We also contribute an evaluation of several existing
negotiation concepts/protocols. We think that reducing the complexity for
automated contract negotiation and thus service consumption is a key for the
success of future service and Cloud infrastructures.

##  I Introduction

Over the last years, WS-Agreement (WSAG) [1, 2] has become a broadly used
standard in the research field of Grid and Cloud computing for providing
electronic contracts [3, 4, 5, 6]. Their success is based on a flexible means
to (1) define involved parties, (2) define the context of agreements, and (3)
provide necessary terms for guarantees. This makes them observable and
consumable and therefore enables automated service integration in Grid and
Cloud based systems (see e.g. [7, 8]).

While the flexibility of WSAG allowed it to become the de-facto standard for
defining electronic contracts, there is no similar standard to describe
negotiation protocols. Research defines automated service negotiation (e.g.
[9, 6, 10, 11, 12, 13, 14]) as the process of establishing business relations
between service providers and consumers. It builds on the fact that services
providers can guarantee different levels of service to consumers
(traditionally: bandwidth, cpu, …). These service properties of course (1)
have effects on each other, (2) lead to different prices, and (3) have to be
matched to the preferences of service consumers. FIPA already standardized
some custom negotiation protocols (e.g. [15]) for the Grid / Cloud
communities. These protocols often are very specific to their respective
application domains, i.e. dealing with a specific set of properties, how to
balance them, and how to match them to user preferences in order to maximize
the benefit for all participants. However, for all these approaches, providers
and consumers have to implement and conform to the negotiation protocol. A
generic way to describe complex protocols is still missing.

The contribution of this paper is a means to integrate arbitrary negotiation
protocols and enable service domains to leverage WSAG-based electronic
contracts. The vision is to allow service consumers to participate in
negotiations solely based on their preferences, not on their understanding of
the negotiation protocol, thus allowing for the coexistence of negotiation
protocols, instead of their standardization.

In order to achieve this feat we built on the Marketplace presented in Vigne
et al. [16]. The basic idea behind this Marketplace is to provide a repository
of heterogeneous services (different APIs, protocols) and a set of microflows
(small code snippets in a process language like e.g. BPEL). While similar
approaches (semantic repositories; UDDI+OWLS) concentrate on finding services
through semantic annotations, the Marketplace focuses on standardizing the
interaction with services for particular application domains. We further
improve on this marketplace concept by …

  1. 1.

Utilizing the Marketplace information and conventions in order to
automatically generate contracts. This allows participating service providers
to benefit from WSAG without the burden of building WSAG handling and
negotiation into their services.

  2. 2.

Explaining how to facilitate the basic concepts of the Marketplace in order to
standardize electronic contracts for similar services from different service
providers.

  3. 3.

Explaining how to use the concept of microflows (see above) in order to
realize bilateral (one-to-one) and multilateral (one-to-many) automated
service negotiation. The goal is to abstract from particular services, and
instead allow service consumers to participate in a negotiation solely based
on their preferences, not based on their knowledge of negotiation protocols.

We further provide an evaluation of the viability of our approach by means of
a case study. This case study consists of a categorization of analysis of
current Grid and Cloud negotiation protocols and how they can be realized in
the Marketplace framework.

Our research in this area is based on our experience with large scale data
stores [17] and complex applications in Grids and Clouds [18, 19, 20], and
strongly motivated by our focus on Web-based workflow optimizations [21, 22]
and their respective management [23].

In Section II we provide a short recap about the used Marketplace and its
provided concepts and functionality. In Section III we discuss related work
from the fields of WSAG negotiation for Grid- and Cloud-based systems. How
WSAG handling is integrated into the Marketplace is discussed in Section IV. A
case study about bilateral and multilateral negotiation protocols and
additionally an example for strategic negotiation is given in Section V. In
Section VII we conclude this work and provide an outlook for future work.

##  II The Marketplace

As this work is based on the Marketplace presented by Vigne et al. [16], it is
essential for further discussions to have a basic understanding of the
implemented concepts and functionality.

Figure 1: The Marketplace

As can be seen in Figure 1, the Marketplace holds a set of microflows that
describe how to interact with services. The Marketplace is strictly passive,
connotes it does not act as a middleware or proxy. Its purpose is to allow a
service consumer to implement a consumer logic against a standardized API for
a particular application domain.

There are two kinds of microflows contained in the Marketplace:

  * •

Service microflows that implement an interaction with a particular service
regarding the requirements of the domain API. This group of microflows is from
now on referred to as instance level operations.

  * •

Domain microflows that implement logic to fetch and invoke service microflows
to select particular services for particular inputs. Each microflow correlates
with one operation in the domain API. Thus we will further on refer to this
group of microflows as class level operations.

From the service consumer’s point of view, the process of doing business with
service providers that participate in the Marketplace is totally transparent:

  * The consumer logic fetches the microflow that represent a particular class level operation from the Marketplace.

  * The consumer logic instantiates a Workflow Engine (WFE) with the microflow, and invokes the microflow with a set of input parameters (the required input parameters are also defined at the class level, e.g. as a contract).

  * While the class level microflow is running, it fetches and executes further instance level operations from the Marketplace, in order to find the service provider best matching the consumer’s preferences and use it. This (potentially complex) selection of services is furthermore called negotiation, and is one of the subjects of this paper. An instance level microflow (also executed by the WFE) directly interacts with a service, and transforms / filters information to make it usable for class level microflows.

  * When a particular class level microflow is finished, its results can be used as part of the consumer logic.

For this paper we again reuse the Cinemas example presented in [16]. The
cinema domain consist of three class level operations: (1) Search to search
for shows of a particular movie, (2) Book to book tickets for a particular
show and (3) Search & Book which combines the two (to demonstrate a complex,
multi-part negotiation).

##  III Related Work

As mentioned before, WS-Agreements have become the de-facto standard for
electronic contracts in the web service context. In this section we give an
overview of WSAG and autonomous Service Level Agreement (SLA) negotiation
related research.

Since Andrieux et al. specified WSAG [2] in 2004 it has become a widely used
standard in the area of web services to define contracts between two or more
parties. Inside a WSAG, all agreed information is structured into different
parts. The main parts are namely:

  1. 1.

Context: This part contains the meta-data of the agreement e.g. participant’s
and life-time.

  2. 2.

Terms: This part contains data about the agreement itself. It consists of
Service Terms, which represent the functionality that will be delivered (so
called Items), and the Guarantee Terms, which define assurances on the service
quality associated with the defined Service Terms.

This formalized and comprehensive way of describing agreements and the
according guarantees make WSAG automatically computable and observable [8,
24]. Sakellariou et al. [4] extended Guarantee Terms to be represented as the
result of a function instead of static values and therefore making it more
flexible when observing complex ones.

As WSAG is originally designed for SOAP-based services, Kuebert et al. [25]
introduced a way to use them also for RESTful services which increased in
numbers rapidly over the last few years.

Haq identifies in [5] the compensation of the service consumer’s high
dependency on the service provider, as a result of using WSAG, as an
additional reason for their common use in the field of Grid and Cloud
computing. He further states that the emerging of Composite Service Providers
leads to complex value chains and therefore consist of aggregated WSAG. While
our approach provides a simple concatenation of these WSAGs, he states that
not every information, created during the composition, should be exposed to
each participating party. Therefore he introduced SLA-Views, which are
basically a customized view of the aggregated WSAG for each participating
party.

Broberg et al. [3] gives an overview about state-of-the-art and future
directions in the field of market-based Grid and Utility computing. Although
they focus on negotiation strategies related to scheduling problems, they
additionally conclude that it is important to overcome the restrictions in
flexibility of negotiation protocols to exploit the benefits for service
consumers generated by a market with competing service providers.

Zulkernine et al. [6, 26] developed a flexible system for WSAG negotiation
with the focus on multilateral negotiation strategies based on decision
support systems. They also conclude that a way to define flexible and provider
specific protocols would further increase the quality of negotiation results.

Faratin et al. [14] give a detailed discussion how such sets of decisions and
preferences could look like. Within their example implementation of autonomous
service negotiation, different offers are evaluated and counteroffers are
created on the base of a value scoring algorithm. They define negotiation
tactic as the short-term decision making focused on a narrow set of criteria
while the negotiation strategy represents the weighting of criteria over time.

As more complex negotiation protocols come into focus of research, WSAG
reaches its limitation as it offers only two messages, namely offer (as an
input for negotiation) and agreement (as the output of an negotiation) and
therefore makes it only feasible for the “Contract Net Interaction Protocol”
[27] (see also Figure 4). Hung et al. elaborated that a formalized negotiation
must consist of three different parts which they further used as groundwork
when developing the “WS-Negotiation Specification” [28]. These three parts are
namely:

  1. 1.

Negotiation Message describes the messages which are sent and received during
a negotiation. These messages can be of different types, namely Offer,
Counteroffer, Rejected, Accepted, Expired, SinglePartySigned, Signed, and
Unsigned.

  2. 2.

Negotiation Protocol defines a set of rules and mechanisms the negotiating
parties must follow. It uses negotiation primitives to describe different
interactions between the parties and what pre- and post-conditions are
associated to each primitive (similar to declarative workflow descriptions).
The following primitives are defined: Call for Proposal, Propose, Accept,
Terminate, Reject, Acknowledge, Modify, and Withdraw.

  3. 3.

Negotiation Decision Making represents an internal and private decision making
process based on a cost-benefit function and therefore represents the
negotiation strategy.

Venugopal et al. [9] focused on the negotiation protocol and proposed
Rubinstein’s approach of “Alternating Offers” [29] (see also Figure 5) as one
way to increase the quality of bilateral service negotiation. A multilateral
adaptation of this protocol has been standardized by [15]. Yan et al. [7]
further extended this protocol (see also Figure 6) because of its shortcomings
in negotiation coordination i.e. coordinating multiple counteroffers for
various service providers.

##  IV WS-Agreements & The Marketplace

As stated in the introduction, we try to reuse the Marketplace to commoditize
the utilization of contracts (in our case WS-Agreements (WSAG)). We envision
this to work similar to the way the Marketplace deals with heterogeneous
services (i.e. same application domain but different APIs, slightly different
semantics).

###  IV-A Concepts

For services in the same application domain, it is possible to provide a
unified contract template [30], that covers possible terms and restrictions
for all services, but has a certain characteristic for particular services. We
again propose a split analog to the class level / instance level
differentiation described in Section II:

  * •

By providing domain contracts that define the interaction with the
Marketplace, as well as common criteria for selecting any service from the
domain.

  * •

By providing service contracts that all have the same structure and define the
level of service (quality) that can be expected from particular services.

Contracts are not some information that is fetched from a repository, but they
are something that is tightly coupled to the usage of services. They are
created, negotiated, and accepted while using certain class level operations
of the Marketplace. Contracts may of course differ from customer to customer,
and are strongly depending on the kind of service that a service consumer
tries to utilize (i.e. the input parameters).

Thus before the consumer logic can execute certain operations from the
Marketplace (i.e. fetch microflows and execute them in a WFE as describe in
Section II), it has to ensure that the properties of a service match its
preferences. This can be done by means of a WSAG.

The typical effort for utilizing WSAG includes (1) fetching a contract
template, (2) making an offer, and (3) receiving the agreement (or rejection).
Of course additional logic may be necessary to (a) ponder which services to
actually make an offer, and (b) decide between multiple possible agreements
(under the condition that it is not necessary to enact on all agreements).

Furthermore we have to consider that services may know nothing about WSAG, by
still offer an API to achieve something similar. We conclude: it will be
necessary to (1) transform WSAG, or (2) implement logic to create WSAG
templates and / or decide if a service accepts an offer. This logic can, as
explained in Section II be expressed in microflows at service level.

Figure 2: Abstract Communication Overview of Using the Marketplace

For Figure 2 keep in mind, that the Marketplace is no middleware. It just
depicts which kind of information have to be fetched by the WFE, and which
kind of information has to be provided by the user and services in order to
enable WSAG and SLA negotiation.

As illustrated, the service consumer, after having received a domain level
template, a user has to provide the necessary information to create a domain
offer i.e. WSAG offer. This domain offer is used as input for the according
domain operation (microflow enacted by the WFE).

First the operation collects (COL) the templates of all service providers.
This is done executing the according class and succeeding instance level
microflows. When all templates are collected, they are filtered using the
information provided via the domain offer.

Next, these templates are aggregated and presented to the user who selects
(SEL) according to personal preferences. Now the selected templates are
supplemented with information included in the domain offer and therefore
become service offers.

During the negotiation (NEG) this service offers are used to negotiate with
the according service providers (see Section V for details about negotiation
protocols) using a negotiating class level operation (microflow) and in
succession the specific instance level operation. At the end of the
negotiation, a service agreement, authorizing for the usage of the service, is
defined.

Providing this service agreement, the service consumer’s WFE can use the
service (USAGE). How this is done is discussed in detail in [16].

After the service is used, a domain agreement is created, using among others
the service agreement received during the negotiation. This domain agreement
and the execution results of the service execution, representing the defined
output of the domain operation, are made persistent for the user.

###  IV-B Implementation

The implementation of a WSAG aware system requires utilizing existing
information from the Marketplace about the (1) included services (their
properties) and (2) their usage.

  * •

Service properties are a set of static attributes that each service provider
must provide to participate in a certain domain of the Marketplace. Examples
for the cinema domain are address, number of cinemas/seats, smoking allowed,
food corner available, …Service properties lead to simple WSAG guarantee
terms, with a particular unit and/or value range, that may be observable from
the outside. Also these properties can be used to create the WSAG business
values.

  * •

Required input to class level operations (which is transformed to suitable
input for services in instance level operations). Examples include the actual
seat to book. The presence of such input parameters may be required or
optional, and again expressed in particular units or as a value range. Thus
such input parameters lead to WSAG qualifying conditions and/or creation
constraints (how to fill out a WSAG template in order to create a valid
offer).

  * •

Output of class level operations are the most important part. For them the
main purpose of WSAG, to monitor the quality of results, fully applies. They
lead to WSAG guarantee terms with a particular unit and/or value range. The
outside observability may of course be very different across a range of
services. Thus it has to be linked to a class level operation, that in turn
may invoke monitoring functionality at the instance level (e.g. Sakellariou et
al. [4]).

The creation of a WSAG domain template is strictly internal, and fully
transparent for the Marketplace consumers. For its implementation we are
building on the existing mechanisms of the Marketplace, mainly the definition
of properties, and input / output schemas.

Listing 1: Properties Schema

⬇

1<rng:grammar xmlns:datatypeLibrary=”…” xmlns:rng=”…” xmlns:prop=”…”
xmlns:wsag=”…”>

2 <rng:start>

3 <prop:properties xmlns:prop=”…” xmlns:d=”…”>

4 <rng:element name=”prop:address”>

5 <d:caption xml:lang=”en”>Address</d:caption>

6 <d:caption xml:lang=”de”>Adresse</d:caption>

7 <rng:element name=”prop:ZIP” wsag:item=”Zip”>

8 <d:caption xml:lang=”en”>ZIP Code</d:caption>

9 <d:caption xml:lang=”de”>PLZ</d:caption>

10 <rng:data type=”integer”><!– 4 digits –>

11 <param name=”minInclusive”>1000</param>

12 <param name=”maxInclusive”>9999</param>

13 </rng:data>

14 <wsag:extension>

15 <!– specific WSAG information –>

16 </wsag:extension>

17 </rng:element>

18 …

19 </rng:element>

20 </prop:properties>

21 <wsag:general>

22 <!–

23 General information about the WS-A template

24 –>

25 </wsag:general>

26 </rng:start>

27</rng:grammar>

As can be seen in Listing 1, we added a WSAG specific section to the already
existing XML RNG Schema, to allow for WSAG specific information to be added
(wsag:item). As properties are class level information, it is up to a service
domain expert to shape this basis for all contracts.

Listing 2: Class Level Input Message Schema

⬇

1<rng:grammar xmlns:datatypeLibrary=”…” xmlns:rng=”…”>

2 <rng:start>

3 …

4 <rng:element name=”input-message”>

5 …

6 <rng:element xmlns:d=”…” name=”date” wsag:Item=”DateOfShow”>

7 <d:caption xml:lang=”en”>Date</d:caption>

8 <d:caption xml:lang=”de”>Datum</d:caption>

9 <rng:data type=”date”/>

10 <wsag:extension>

11 <!– specific WSAG information –>

12 </wsag:extension>

13 </rng:element>

14 <rng:element xmlns:d=”…” name=”seats” wsag:Item=”NumberOfSeats”>

15 <d:caption xml:lang=”en”>Seats</d:caption>

16 <d:caption xml:lang=”de”>Sitze</d:caption>

17 <rng:data type=”integer”>

18 <param name=”minInclusive”>1</param>

19 <param name=”maxInclusive”>6</param>

20 </rng:data>

21 <wsag:extension>

22 <!– specific WSAG information –>

23 </wsag:extension>

24 </rng:element>

25 </rng:element>

26 <wsag:general>

27 <!–

28 General information about the WSAG template

29 –>

30 </wsag:general>

31 </rng:start>

32</rng:grammar>

In Listing 2 an example class level input schema can be seen. Again it is
possible to reuse datatype related information, but additionally units and/or
expected ranges could be further described in WSAG.

###  IV-C Aggregation

Figure 3: Class Level Templates: Aggregation and Transformation of Interfaces

As defined in [16] the Marketplace allows to define class level operations
(microflows) that in turn invoke instance level operations (microflows).
Invocation does not mean that the microflows are executed by the Marketplace,
but can be fetched from the marketplace in order to execute them in a Workflow
Engine (WFE) at the service consumer’s side.

But for class level operations it is also allowed to invoke other class level
operations in order to e.g. realize a search & book operation, which is the
fusion of existing operations. As the domain designer has full control over
the class level (API), it is not possible that semantically identical
parameters with different names may be used (except as an error by the domain
designer). Thus aggregating WSAG is straight forward, pieces of information
can just be concatenated, duplicate information can be removed.

As properties are valid at class level for all operations, when concatenating
the pieces, identifiers have to be prefixed.

Listing 3: Class Level Template

⬇

1<wsag:Template xmlns:xsi=”…” xmlns:xs=”…”

2 xmlns:wsag=”…” xsi:schemaLocation=”…”

3 xmlns:prop=”…” xmlns:msg=”…”>

4

5 <wsag:Name>Cinemas Domain: Search and Book</wsag:Name>

6 <wsag:Context/><!– contains general information –>

7 <wsag:CreationConstraints>

8 <wsag:Item wsag:name=”Zip”>

9 <wsag:Location>

10 //wsag:ServiceDescriptionTerm/prop:address/prop:ZIP

11 </wsag:Location>

12 <xs:minInclusive xs:value=”1000”/>

13 <xs:maxInclusive xs:value=”9999”/>

14 </wsag:Item>

15 <wsag:Item wsag:name=”DateOfShow”>

16 <wsag:Location>

17 //wsag:ServiceDescriptionTerm/msg:date

18 </wsag:Location>

19 </wsag:Item>

20 </wsag:CreationConstraints>

21 <!– additionl generated information is palced here –>

22</wsag:Template>

This results in a simple concatenation algorithm depicted in Listing 3. As
already described in Subsection IV-A, the aggregated WSAG template can then be
filled out by a user and utilized to make offers for a subset of services.

##  V Case Study

In this Section we justify our approach by analyzing a set of negotiation
protocols. As already mentioned in the introduction, negotiation is the
process of establishing business relations between service providers and
consumers. In the context of this paper this means that a WS-Agreement (WSAG)
can be derived, which can be used in order to call services. Existing class
level operations can be extended to include the functionality to:

  * (1) Collect WSAG templates by invoking instance level operations.

  * (2) Present aggregated templates to users, by utilizing callbacks that can be injected into class level operations (microflows) as presented in [16]. It is important to note that all templates will have the same structure / terms included, but may contain different WSAG creation constraints.

  * (3) Present offers to services by invoking instance level operations with filled out WSAG templates.

  * (4) Enact service calls as a result of accepted offers.

The instance level operations (microflows) mentioned in (1) and (3) can
contain any kind of calls to actual services. This allows for a high degree of
flexibility: (a) for WSAG unaware services, the logic to create a WSAG could
be either embedded in a microflow, or (b) for WASG aware services results can
be just transformed.

Furthermore, as described in (2) the service consumer (user) can select a
subset of templates that match his preferences. As the service consumer (user)
has also an overview of its past decisions, it can employ strategic or tactic
negotiation as described in the related work. The same goes for service
providers as described in (3).

Because class level operations interact with all participating service
providers, its microflow represents a multilateral negotiation protocol. A
WSAF complaint class level operation has to define a WSAG offer (domain offer)
as an input and zero to many WSAG agreements (domain agreements) as output.

On the other hand passing a particular WSAG offer to an instance level
operation for a particular service, can be considered to be an example of a
bilateral negotiation protocol.

As already mentioned in the introduction, this separation between class and
instance level is perfectly suited to map arbitrary per service negotiation
protocols in a transparent fashion. The service consumer can just fetch and
execute microflows, without having to worry about transforming input or
results.

To further exemplify the invoked principles, we evaluated several common
concepts in more detail.

###  V-A Bilateral Negotiation Protocols

Bilateral negotiation protocols represent how a service consumer is able to
negotiate with a specific service provider (one-to-one). As for all
negotiations, at the beginning is a service offer (SO) and at the end there is
either a service agreement (SA) or a cancellation of the negotiation. What
happens in between is covered by the negotiation protocol (e.g. send offer,
confirm agreement or quit negotiation). In our concept, bilateral negotiation
protocols are always defined using instance level operations. This is
completely in line with their original intent to provide service specific
information to the service consumer which is also considered as one-to-one
information.

In the following, we illustrate our concept with two commonly used bilateral
negotiation protocols.

####  V-A1 Contract Net Interaction Protocol

The Contract Net Interaction Protocol was introduced by Smith [27] in 1980 and
represents the protocol which is today often referred to as “Supermarket
Approach”. This means that the service consumer offers a contract (send offer)
for the requested functionality and the service provider either accepts this
offer or rejects it, without providing any counteroffer (“take it or leave
it”). Because there is no counteroffer provided for the service consumer, its
strategic negotiation service is not necessary. As an example how a microflow,
representing this protocol in its simplest form (without any parameter
transformation), could look like see Figure 4.

Figure 4: Bilateral Negotiation: Contract Net Interaction Protocol [27]

We decided to include this protocol in our case study as it is widely used by
today’s real world services (e.g. online-shops, cinema service providers, …).
Furthermore is it referred in a lot of today’s research (e.g. [6, 12, 13, 2])
and thus relevant for the Marketplace.

####  V-A2 Alternate Offers Protocol

The “Alternate Offers Protocol” was defined by Rubinstein [29] in 1982 and
provides the possibility for service providers (SP) and service consumers (SC)
to bargain about the delivered functionality and usage conditions. As
illustrated in Figure 5 the protocol allows both parties to propose
counteroffers (SC: create counteroffer and SP: request counter template) if
one is not willing to accept the current offer. In WSAG, each term defines
permissible values [2] used as constraints when creating the counteroffer.
This cycle goes on until both parties either accept the current offer or one
party quits the negotiation process.

Because this protocol allows counteroffers, the service consumer must provide
a strategic negotiation logic, to decide how the negotiation should continue
and create counteroffers (see Section V-C for details). Doing so allows each
service consumer to realize his own bargaining strategy without customizing
the instance level operation defined by the service provider.

Figure 5: Bilateral Negotiation: Alternate Offers Protocol [29, 9]

Although, as to our best knowledge, not much of today’s real world services
support this protocol, it is quite popular among researchers (e.g. [31, 10,
7]). We agree with Rubinstein et al. [29] that bargaining is essential for the
creation of mature markets.

###  V-B Multilateral Negotiation Protocols

So far we focused on bilateral negotiation protocols, defining the interaction
between one specific service provider and a service consumer (one-to-one). In
this Section we extend our focus to multilateral negotiation protocols, as
only these allow a service consumer to use offers from competing service
providers (one-to-many) for its negotiation strategy. As discussed in e.g.
[29, 3], if this information is used to create counteroffers, the overall
benefits for the service consumer will significantly increase, because the
service consumer is completely informed about the market.

Multilateral Negotiation is similar to the “Alternate Offers Protocol” (see
Section V-A2), only this time the bargaining is defined at class level instead
of instance level. The according operation therefore executes the negotiation
protocols, defined by each service provider, every time a new service
agreement should be negotiated111It can therefore happen that the “Alternate
Offers Protocol” is used inside an iterated multilateral negotiation.. If re-
negotiation with a particular service providers is not desired, class level
logic can easily exclude them. Again, the service consumer provides a
strategic negotiation logic, which is in charge of creating counteroffers
representing the preferences of the service consumer.

The definition of such protocols is built on the interaction of class level
and instance level operations. As this interaction can be utilized in various
ways, a lot of room for domain specific customization is left open, e.g.
service enactment [31], service decomposition [7].

We decided to implement the “Iterated Contract Net Interaction Protocol”,
which was standardized by the FIPA [15] and extended with negotiation
coordination capabilities by Yan et al. [7].

Figure 6: Multilateral Negotiation: Iterated Contract Net Interaction Protocol
[15, 7]

As illustrated in Figure 6, during the negotiation service offers (SO) are
sent to various service providers (send offers) using the individual bilateral
negotiation protocol (Instance Level Operation: Negotiate) of each service
provider. Afterwards the collected service agreements (SA) are sent to the
strategic negotiation logic of the service consumer (check agreements). The
result of the strategic negotiation is either to accept some of the agreements
(confirm agreements), to quit the negotiation (quit negotiation) or to propose
counteroffers. If counteroffers are placed, first the counter templates (ST)
of the service providers are collected (request counter templates). Then the
strategic negotiation logic of the service consumer filters these templates
and creates counteroffers (SO) for all service providers included in the next
iteration (filter templates and create counteroffers).

This way of bargaining is also known as “reverse auction” where many different
service providers compete. Therefore, in each iteration either the price
decreases or the offered functionality increases.

###  V-C Strategic Negotiation

Strategic negotiation is used as a means to enact the service consumers /
providers preferences. Implementing strategic negotiation as part of class /
instance level operations allows to realize individual service preferences
without changing the negotiation protocol provided by the Marketplace and
focus on the outcome of a specific negotiation.

How these preferences are expressed and how competing offers are rated is
strongly affected by micro economics and therefore beyond the focus of this
paper. As pointed out by Faratin et al. [14], for autonomous service
negotiation three areas must be considered: (1) Negotiation Protocols, which
are discussed in this case study, (2) Negotiation Issues, which are covered by
WSAG (see Section IV), and (3) Negotiation Strategies to define a reasoning
model for the service customers preferences.

They further define that their approach for autonomous negotiation uses a
value scoring algorithm as a foundation. In this algorithm, each single
criteria of the negotiation is represented by a tactic. Tactics are functions
calculating the value of the assigned criteria. To create an offer, all
tactics are weighted and combined. By varying the weight of each tactic over
time, the long-term negotiation strategy is realized. As an example for a
negotiation strategy they allege that, in the beginning of multilateral
negotiations, the behavior of competing service providers may influence the
counteroffer more than the value of a single criteria. Therefore behavior
representing tactics are weighted higher than other tactics. However, at the
end of the negotiation phase, single criteria may gain importance. How tactics
and strategy have to be combined to achieve the best negotiation results, can
be educed from various sources e.g. historical data or user’s preferences.

In our approach all this logic is provided on behalf of the service consumer,
thus not directly affects the Marketplace.

##  VI Extended Cinemas Example

So far we introduced our concept for WSAG integration and flexible bilateral
and multilateral negotiation protocols. In this Section we integrate them into
the cinemas example introduced in Section II and [16] as illustrated in Figure
7.

Figure 7: Multilateral Negotiation: Cinemas Example

In order to use this operation, the service consumer provides a domain offer
for the class level operation Search & Book as only input.

Calling the class level operation Search is the same as described in [16].
Only the necessary parameter transformation before and after the call are
different, as the interface of Search & Book and the internal data
representation has changed.

Now that all offered shows are known, negotiations for each show are
performed. To do so the according class level operation is called (negotiate
show). It is defined inside the domain interface of this operation that a
reference to a particular show must be included in the input and agreements
for each show are the output. Using this input message, the operation is
capable to educe the correct service provider and calls its instance level
operation for negotiation (perform negotiation). Also parameter
transformations to create service offers (SO) and to compute service
agreements (SA) must be performed.

After all shows are negotiated, the service consumer (acting as the strategic
negotiation service) selects the preferred show (select show). Further must
all service agreements, expect the selected one, be canceled. This is done as
described in the agreement e.g. sending the agreement to a specific URI. It
must be noted that we excluded this message flow in our illustration to keep
it neat.

In the end, the selected service agreement (SA) is used as an input for the
class level operation Book. In our example this operation defines in its class
level operation interface that either a service agreement or a reference to a
particular show is valid input. Depending on this input, the operation decides
(parse input message) if it must negotiate the show (negotiate show) before
using it or not. In the end the service operation Book of the according
service provider can be called. It defines in its instance level operation
interface that a service agreement (SA) must be included to authorize the
usage. As output the execution results of the service are define.

This execution results and the selected service agreement represent the
defined output of Search & Book.

##  VII Conclusion and Future Work

In this paper we presented flexible ways to (a) define WSAG contracts for
arbitrary services, and to (b) transparently allow different services to
utilize custom negotiation algorithms and APIs. We showed that both goals
could be achieved by building on an existing Marketplace concept, that
promotes microflows (small pieces of code executable by a Workflow Engine) to
achieve a high level of abstraction for service consumers.

We first described how to extend the concept of unified interfaces to create
unified contracts. We then introduced how to use the concepts of class
(domain) and instance (service) level to provide flexible negotiation
protocols. Finally we provided a case study to justify our approach.

Within the case study we discussed how (1) bilateral negotiation protocols are
defined using instance level operations, (2) how multilateral negotiation
protocols are defined using class level operations, and (3) how service
consumers can include customized negotiation strategies. We presented how to
implement the “Contract Net Interaction Protocol” (because of its prevalence
for real world services) as well as the “Alternate Offers Protocol” (as
prerequisite for mature markets). For multilateral negotiation protocols we
presented the “Iterated Contract Net Interaction Protocol” in order to allow
various service providers to compete about business. Additionally we presented
one negotiation strategy based on a value scoring algorithm.

The conclusion we can draw from this work is, that by embracing existing
workflow-related concepts, it is possible to build a lightweight solution for
dealing with electronic contracts, in an environment where not all services
support them (or support them in the same way).

Future work will be to exploit the complexity of different types of
negotiation protocols and to implement some custom negotiation strategy
services. The possibilities to monitor complex guarantee terms using class
level operations in the context of service composition is also promising. This
can lead to much improved error handling and service selection, as it may
allow for the prediction of service behavior.

## References

  * [1] H. Ludwig, “WS-Agreement concepts and Use–Agreement-Based Service-Oriented architectures,” _IBM Research Division_ , 2006.
  * [2] A. Andrieux, K. Czajkowski, A. Dan, K. Keahey, H. Ludwig, T. Nakata, J. Pruyne, J. Rofrano, S. Tuecke, and M. Xu, “Web services agreement specification (WS-Agreement),” in _Global Grid Forum_ , 2004.
  * [3] J. Broberg, S. Venugopal, and R. Buyya, “Market-oriented grids and utility computing: The state-of-the-art and future directions,” _Journal of Grid Computing_ , vol. 6, no. 3, p. 255–276, 2008.
  * [4] R. Sakellariou and V. Yarmolenko, “On the flexibility of WS-agreement for job submission,” in _Proceedings of the 3rd international workshop on Middleware for grid computing_ , 2005, p. 1–6.
  * [5] I. Ul Haq, A. Huqqani, and E. Schikuta, “Aggregating hierarchical service level agreements in business value networks,” in _Business Process Management: 7th International Conference, BPM 2009, Ulm, Germany, September 8-10, 2009. Proceedings 7_. Springer, 2009, pp. 176–192.
  * [6] F. H. Zulkernine and P. Martin, “An adaptive and intelligent SLA negotiation system for web services,” _IEEE Transactions on Services Computing_ , vol. 4, no. 1, pp. 31–43, Jan. 2011.
  * [7] J. Yan, R. Kowalczyk, J. Lin, M. B. Chhetri, S. K. Goh, and J. Zhang, “Autonomous service level agreement negotiation for service composition provision,” _Future Generation Computer Systems_ , vol. 23, no. 6, pp. 748–759, Jul. 2007.
  * [8] H. Ludwig, A. Dan, and R. Kearney, “Cremona: an architecture and library for creation and monitoring of WS-agreents,” in _Proceedings of the 2nd International Conference on Service oriented computing_ , 2004, p. 65–74.
  * [9] S. Venugopal, X. Chu, and R. Buyya, “A negotiation mechanism for advance resource reservations using the alternate offers protocol,” in _Quality of Service, 2008. IWQoS 2008. 16th International Workshop on_ , 2008, p. 40–49.
  * [10] M. Comuzzi and B. Pernici, “An architecture for flexible web service qos negotiation,” in _Ninth IEEE International EDOC Enterprise Computing Conference (EDOC’05)_. IEEE, 2005, pp. 70–79.
  * [11] M. Parkin, D. Kuo, and J. Brooke, “A framework and negotiation protocol for service contracts,” in _2006 IEEE International Conference on Services Computing (SCC’06)_ , Chicago, IL, USA, Sep. 2006, pp. 253–256.
  * [12] P. Hasselmeyer, H. Mersch, B. Koller, H. N. Quyen, L. Schubert, and P. Wieder, “Implementing an SLA negotiation framework,” in _Proceedings of the eChallenges e-2007 Conference, Hague, Netherlands_ , 2007.
  * [13] A. Pichot, P. Wieder, O. Wäldrich, and W. Ziegler, “Dynamic SLA-negotiation based on WS-Agreement,” in _Proceedings of the 4th International conference on Web Information Systems and Technologies (WEBIST 2008)_ , 2008, p. 38–45.
  * [14] P. Faratin, C. Sierra, and N. R. Jennings, “Negotiation decision functions for autonomous agents,” _Robotics and Autonomous Systems_ , vol. 24, no. 3-4, p. 159–182, 1998.

  * [15] J. Odell, S. Poslad, and R. Levy, “FIPA iterated contract net interaction protocol specification,” Dec. 2002. [Online]. Available: http://www.fipa.org/http://fipa.org/specs/fipa00030/SC00030H.pdf
  * [16] R. Vigne, J. Mangler, E. Schikuta, and S. Rinderle-Ma, “A structured marketplace for arbitrary services,” _Future Generation Computer Systems_ , vol. 28, no. 1, pp. 48–57, 2012.
  * [17] E. Schikuta, T. Fuerle, and H. Wanek, “Vipios: The vienna parallel input/output system,” in _Euro-Par’98 Parallel Processing: 4th International Euro-Par Conference_. Springer, 1998, pp. 953–958.
  * [18] W. Mach and E. Schikuta, “A generic negotiation and re-negotiation framework for consumer-provider contracting of web services,” in _Proceedings of the 14th International Conference on Information Integration and Web-based Applications & Services_, 2012, pp. 348–351.
  * [19] E. Schikuta and T. Weishaupl, “N2grid: neural networks in the grid,” in _2004 IEEE International Joint Conference on Neural Networks (IEEE Cat. No. 04CH37541)_ , vol. 2. IEEE, 2004, pp. 1409–1414.
  * [20] E. Schikuta, F. Donno, H. Stockinger, H. Wanek, T. Weishäupl, E. Vinek, and C. Witzany, “Business in the grid: Project results,” in _1st Austrian Grid Symposium_. OCG, December 2005. [Online]. Available: http://eprints.cs.univie.ac.at/745/
  * [21] E. Schikuta, H. Wanek, and I. Ul Haq, “Grid workflow optimization regarding dynamically changing resources and conditions,” _Concurrency and Computation: Practice and Experience_ , vol. 20, no. 15, pp. 1837–1849, 2008.
  * [22] K. Kofler, I. ul Haq, and E. Schikuta, “A parallel branch and bound algorithm for workflow qos optimization,” in _2009 International Conference on Parallel Processing_. IEEE, 2009, pp. 478–485.
  * [23] G. Stuermer, J. Mangler, and E. Schikuta, “Building a modular service oriented workflow engine,” in _2009 IEEE international conference on service-oriented computing and applications (SOCA)_. IEEE, 2009, pp. 1–4.
  * [24] N. Oldham, K. Verma, A. Sheth, and F. Hakimpour, “Semantic WS-agreement partner selection,” in _Proceedings of the 15th international conference on World Wide Web_ , 2006, p. 697–706.
  * [25] R. Kübert, G. Katsaros, and T. Wang, “A RESTful implementation of the WS-Agreement specification,” in _Proceedings of the Second International Workshop on RESTful Design_ , 2011, p. 67–72.
  * [26] F. Zulkernine, P. Martin, C. Craddock, and K. Wilson, “A Policy-Based middleware for web services SLA negotiation,” in _IEEE International Conference on Web Services, 2009. ICWS 2009_. IEEE, Jul. 2009, pp. 1043–1050.
  * [27] R. G. Smith, “The contract net protocol: High-level communication and control in a distributed problem solver,” _Computers, IEEE Transactions on_ , vol. 100, no. 12, p. 1104–1113, 1980.
  * [28] P. C. Hung, H. Li, and J.-J. Jeng, “Ws-negotiation: an overview of research issues,” in _37th Annual Hawaii International Conference on System Sciences, 2004. Proceedings of the_. IEEE, 2004, pp. 10–pp.
  * [29] A. Rubinstein, “Perfect equilibrium in a bargaining model,” _Econometrica: Journal of the Econometric Society_ , p. 97–109, 1982.
  * [30] I. Brandic, D. Music, P. Leitner, and S. Dustdar, “VieSLAF framework: Enabling adaptive and versatile SLA-Management,” in _Grid Economics and Business Models_ , J. Altmann, R. Buyya, and O. F. Rana, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009, vol. 5745, pp. 60–73. [Online]. Available: http://www.springerlink.com/content/l380u04815284287/
  * [31] M. B. Chhetri, J. Lin, S. K. Goh, J. Yan, J. Y. Zhang, and R. Kowalczyk, “A coordinated architecture for the agent-based service level agreement negotiation of web service composition,” in _Software Engineering Conference, 2006. Australian_ , 2006, p. 10–pp.


*

2021

Alexander Hauptmann (Chair) | Carnegie Mellon University
---|---
Alan W. Black | Carnegie Mellon University
Kris Kitani | Carnegie Mellon University
Lu Jiang | Google Research

#  From Recognition to Prediction:
Analysis of Human Action and Trajectory Prediction in Video

Junwei Liang

(CMU-LTI-21-008)

###### Abstract

With the advancement in computer vision deep learning, systems now are able to
analyze an unprecedented amount of rich visual information from videos to
enable applications such as autonomous driving, socially-aware robot assistant
and public safety monitoring. Deciphering human behaviors to predict their
future paths/trajectories and what they would do from videos is important in
these applications. However, human trajectory prediction still remains a
challenging task, as scene semantics and human intent are difficult to model.
Many systems do not provide high-level semantic attributes to reason about
pedestrian future. This design hinders prediction performance in video data
from diverse domains and unseen scenarios. To enable optimal future human
behavioral forecasting, it is crucial for the system to be able to detect and
analyze human activities as well as scene semantics, passing informative
features to the subsequent prediction module for context understanding.

In this thesis, we conduct human action analysis and develop robust algorithms
and models for human trajectory prediction in urban traffic scenes. This
thesis consists of three parts. The first part analyzes human actions. We aim
to develop an efficient object detection and tracking system similar to the
perception system used in self-driving, and tackle the action recognition
problem under weakly-supervised learning settings. We propose a method to
learn viewpoint invariant representations for video action recognition and
detection with better generalization. In the second part, we tackle the
problem of trajectory forecasting with scene semantic understanding. We study
multi-modal future trajectory prediction using scene semantics and exploit 3D
simulation for robust learning. Finally, in the third part, we explore using
both scene semantics and action analysis for the prediction of human
trajectories. We show our model efficacy on a new challenging long-term
trajectory prediction benchmark with multi-view camera data in traffic scenes.

###### keywords:

Action Recognition, Trajectory Prediction, Action Prediction, Human Behavioral
Analysis, Future Prediction, Machine Perception, Autonomous Driving

Thank you to my academic adviser, Alex, the best teacher in the world, who has
guided me both in research and in life for the past six years. Thank you to
the committee who kept me on track and co-authors along the way that provided
me with great help and advice. Thank you to Lu, who mentored me and led me to
everything I know about computer science research. And finally, thank you to
Xinxin, my lovely wife, who traveled through Cambodia for a month to get to
the U.S., to accompany and support me during the COVID-19 pandemic, and to be
the pillar of my life.