# POET: Training Neural Networks on Tiny Devices
with Integrated Rematerialization and Paging

Shishir G. Patil  Paras Jain  Prabal Dutta  Ion Stoica  Joseph E. Gonzalez

###### Abstract

Fine-tuning models on edge devices like mobile phones would enable privacy-
preserving personalization over sensitive data. However, edge training has
historically been limited to relatively small models with simple architectures
because training is both memory and energy intensive. We present POET, an
algorithm to enable training large neural networks on memory-scarce battery-
operated edge devices. POET jointly optimizes the integrated search search
spaces of rematerialization and paging, two algorithms to reduce the memory
consumption of backpropagation. Given a memory budget and a run-time
constraint, we formulate a mixed-integer linear program (MILP) for energy-
optimal training. Our approach enables training significantly larger models on
embedded devices while reducing energy consumption while not modifying
mathematical correctness of backpropagation. We demonstrate that it is
possible to fine-tune both ResNet-18 and BERT within the memory constraints of
a Cortex-M class embedded device while outperforming current edge training
methods in energy efficiency. POET is an open-source project available at
https://github.com/ShishirPatil/poet

Edge Training, Rematerialization, Paging, Machine Learning, ICML

##  1 Introduction

Deep learning models are widely deployed for inference on edge devices like
smartphones and embedded platforms. In contrast, training is still
predominantly done on large cloud servers with high-throughput accelerators
such as GPUs. The centralized cloud training model requires transmitting
sensitive data from edge devices to the cloud such as photos and keystrokes,
thereby sacrificing user privacy and incurring additional data movement costs.

To enable users to personalize their models without relinquishing privacy, on-
device training methods such as federated learning (Li et al., 2020) perform
local training updates without the need to consolidate data to the cloud.
These methods have been widely deployed to personalize keyboard suggestions in
Google Gboard (Hard et al., 2018) and to improve Automatic Speech Recognition
(ASR) on iPhones (Paulik et al., 2021).

Figure 1: POET optimizes state-of-the-art ML models for training on Edge
devices. Operators of the ML model are profiled on target edge device to
obtain fine-grained profiles. POET adopts an integrated integrated
rematerialization and paging to produce an energy-optimal training schedule.

At the same time, current on-device training methods cannot support training
modern architectures and large models. For example, Google Gboard fine-tunes a
simple logistic regression model. Training larger models on edge devices is
infeasible primarily due to the limited device memory which cannot store
activations for backpropagation. A single training iteration for ResNet-50 (He
et al., 2016) requires 200$\times$ more memory than inference.

Prior work has proposed strategies including paging to auxiliary memory (Peng
et al., 2020) and rematerialization (Chen et al., 2016; Jain et al., 2020;
Kirisame et al., 2021) to reduce the memory footprint of training in the
cloud. However, these methods result in a significant increase in total energy
consumption. The data transfers associated with paging methods often require
more energy than recomputing the data. Alternatively, rematerialization
increases energy consumption at a rate of $O(n^{2})$ as the memory budget
shrinks.

In this work, we show that _paging and rematerialization are highly
complementary_. By carefully rematerializing cheap operations while paging
results of expensive operations to auxiliary memory such as a flash or an SD
card, we can scale effective memory capacity with minimal energy overhead. By
combining these two methods, we demonstrate it is possible to train models
like BERT on mobile-class edge devices. By framing edge training as an
optimization problem, we discover optimal schedules with provably minimal
energy consumption at a given memory budget. While the focus of this paper is
edge deployemnts, the energy objective is increasingly becoming relevant even
for cloud deployments (Patterson et al., 2022).

We present POET (Private Optimal Energy Training), an algorithm for energy-
optimal training of modern neural networks on memory-constrained edge devices
(Fig 1). Given that it is prohibitively expensive to cache all activation
tensors for backpropagation, POET optimally pages and rematerializes
activations, thereby reducing memory consumption by up to 2x. We reformulate
the edge training problem as an integer linear program (ILP) and find it is
solved to optimality in under ten minutes by commodity solvers.

For models deployed on real-world edge devices, training happens when the edge
device is relatively idle and spare compute cycles are available. For example,
Google Gboard schedules model updates when the phone is put to charge. Hence
POET also incorporates a hard training constraint. Given a memory constraint
and the number of training epochs, POET generates solutions that also satisfy
the given training deadline. POET transparently develops a comprehensive cost
model by profiling the target hardware with the target network’s operators.
Finally, POET is mathematically value preserving (_i.e,_ it makes no
approximations), and it works for existing architectures out-of-the-box.

The novel contributions of this work include:

  1. 1.

A formulation of an integer linear program to find the energy-optimal schedule
to train modern deep neural networks with a) memory and b) runtime as hard
constraints.

  2. 2.

A unified algorithm for hybrid activation recomputation and paging.

  3. 3.

The first demonstration of how to train ResNet-18 and BERT on tiny Cortex M
class devices with memory and timing constraints.

##  2 Related Work

Scarcity of compute and memory is one of the largest constraint for machine
learning on edge devices. Large models with state-of-the-art performance have
largely been exorbitantly expensive for edge devices. The research community
has predominantly focused on addressing inference on edge devices via methods
like efficient DNN architecture (Iandola et al., 2016; Tan & Le, 2021),
quantization (Dong et al., 2019) or pruning (Blalock et al., 2020).

Instead, we aim to make training large neural networks feasible on tiny edge
devices. While compute is the limiting resource for inference on the edge,
limited memory capacity constraints prevent training large models on the edge.
Training via vanilla backpropagation requires caching the output of all
intermediate layers (activations). We categorize methods to reduce memory
usage of training as activation (1) compression, (2) rematerialization, and
(3) paging. We then discuss prior work in energy-efficient training.

Activation quantization: Chen et al. (2021), Park et al. (2017), and others
have proposed techniques to quantize activations while performing full-
precision multiply-accumulates (MACs). However, these techniques compromise
accuracy and correctness. Moreover, poor hardware support for quantized
operations under 8 bits limits the practical savings of these techniques. We
do not consider methods for pruning during training like Frankle & Carbin
(2019) as they do not reduce the size of activations.

Rematerialization: Rematerialization discards activations in the forward pass
and recomputes those values during gradient calculation. Chen et al. (2016)
proposed a simple and widely used algorithm for rematerialization where every
$O(\sqrt{n})$ layer is retained for the backward pass. Griewank & Walther
(2000) propose an optimal algorithm for rematerialization on unit-cost linear
auto-diff graphs. However, they force the strong assumption that models have
uniform compute requirements across layers. Checkmate (Jain et al., 2020)
identifies the optimal rematerialization schedule for arbitrary static graphs.
Shah et al. (2021) extends Checkmate with operator implementation selection,
but this is orthogonal to our work’s scheduling problem. Dynamic Tensor
Rematerialization (DTR) (Kirisame et al., 2021) finds an approximation of
Checkmate that is near-optimal for common computer-vision models. Our work
addresses the following limitations of Checkmate: (1) Checkmate does not
consider energy nor latency as a constraint and (2) Checkmate does not page
activations to secondary memory. POET is the first work that demonstrates
provably optimal integrated paging and rematerialization.

Paging: Huang et al. (2020) and Ren et al. (2021) page activations off a
memory-scarce GPU to the CPU when out of memory. However, we find paging is
very energy-intensive and is often less efficient than rematerialization.
Capuchin (Peng et al., 2020) uses the Memory Saving Per Second (MSPS)
heuristic to decide what to page. Only if paging is insufficient will Capuchin
rematerialize activations thereby making it sub-optimal as demonstrated in Sec
6.1. POFO (Beaumont et al., 2021) formulates finding finding the optimal
sequence combining rematerialization and paging as a dynamic programming
problem. POFO makes many assumptions that limit generality: POFO only supports
chain (linear) model graphs while we support arbitrary graphs such as BERT
(Fig 3). POFO limits layers to a single rematerialization or page operation
while POET can remat/page layers repeatedly. POFO forces all page-out
operations to occur prior to calculating the loss while we have no such
restriction. And finally, while POFO assumes paging is asynchronous (e.g.,
CUDA) but this is not universally true for the edge devices we evaluate.
Notice that POET is not only optimizing a different metric (energy vis-a-vis
time) but a) adhere’s to strict timing guarantees and b) is _provably
optimal_.

Energy-efficient training: We are not the first to consider energy-optimal
training. Prior work on energy-optimal training for the edge either a)
required the design of new architectures (Cai et al., 2019; Tan & Le, 2021),
or proposed b) new techniques of training by dropping activations, updating
only select layers of the network, or c) used a different optimizer (Wang et
al., 2019). Compared to these techniques, POET is a) mathematically value
preserving (makes no approximations, or modifications), and b) works for
existing and new architectures out-of-the-box.

Method |  | General
---
Graphs
| Compute
---
Aware
| Memory
---
Aware
| Power
---
Aware
Checkpoint all (PyTorch) | $\surd$ | $\times$ | $\times$ | $\times$
Griewank & Walther (2000) | $\times$ | $\times$ | $\times$ | $\times$
Chen et al. (2016) $\sqrt{n}$ | $\times$ | $\times$ | $\times$ | $\times$
Chen et al. (2016) greedy | $\times$ | $\times$ | $\sim$ | $\times$
Checkmate (Jain et al., 2020) | $\surd$ | $\surd$ | $\surd$ | $\times$
POFO (Beaumont et al., 2021) | $\times$ | $\surd$ | $\surd$ | $\times$
DTR (Kirisame et al., 2021) | $\surd$ | $\surd$ | $\surd$ | $\times$
POET (ours) | $\surd$ | $\surd$ | $\surd$ | $\surd$

Table 1: Comparison of baseline methods under power, compute, memory and
generality metrics. POET satisfies all criteria, enabling end-to-end training
on the edge.

##  3 Background

Figure 2: Rematerialization and paging are complementary. This plot visualizes
the execution schedule for an eight layer neural network. We represent logical
timesteps in increasing order on the y-axis while different layers are
represented by the x-axis. Layers 2 and 3 are cheap-to-compute operators and
therefore can be rematerialized at low cost. However, layers 5 and 6 are
compute intensive so it is more energy-efficient to page them to secondary
flash storage.

A growing demand exists for edge machine learning applications for greater
autonomy. In response, the community has developed systems to enable machine
learning on edge devices. EdgeML (Dennis et al., 2019), CoreML (Kapoor, 2019)
and TensorFlow Lite (Lee et al., 2019) from Google are all efforts to meet
this demand.

However, each of these efforts is application-specific and proposes new
algorithms or optimizations to address the computational and memory
requirements for machine learning inference on the edge (Lane et al., 2016).
While inference is already commonly deployed on edge devices, training remains
ad-hoc and infeasible for large models.

Training on the edge is critical for privacy, cost, and connectivity. First,
due to privacy concerns, many edge applications cannot transmit data to the
cloud. Second, the energy consumed by bulk data transmission can significantly
reduce battery life (Levis et al., 2004). Third, applications such as ocean
sensing and communication (Jang & Adib, 2019), and those deployed in farms
(Vasisht et al., 2017) are designed for offline operations – with no access to
the internet.

Our objective of optimizing for energy is a non-trivial contribution. On edge
devices, the energy objective can oftentimes conflict with the objective of
running to completion. For example, on a given platform, rematerializing might
consume lower energy, but paging might be quicker. This is because, on edge
devices, it is common practise to turn-off/duty-cycle components that are not
utilized (e.g., SD card, DMA, etc.) The energy profile may vary depending on
the size of the tensor, and if the PCIe/DMA/SPI/I2C memory bus needs to be
activated, etc. Exploiting this enables POET to find the most energy-efficient
schedule which would not have been possible had we not optimized for energy.

While definitions differ on which devices are included in “the edge” (e.g.,
mobile phones, routers, gateways, or even self-driving cars). In the context
of this paper, the edge refers to mobile phones and microcontrollers (Table
2). These devices are characterized by limited memory (ranging from KBs to a
few GBs) and are commonly battery-powered ($\sim$ few hundred mAh) for real-
world deployment. Further, in our research we found that it is quite common
for these edge devices to be augmented with an off-chip secondary storage such
as a flash or an SD card as seen in (Vasisht et al., 2017; Jang & Adib, 2019;
Patil et al., 2019). This presents us with an opportunity to exploit the off-
chip memory for paging.

##  4 Integrated paging and rematerialization

Rematerialization and paging are two techniques to lower the memory
consumption of large, state-of-the-art ML models. In rematerialization, an
activation tensor is deleted as soon as they are no longer needed, most often,
during a forward pass. This frees up precious memory that can be used to store
the activations of the following layers. When the deleted tensor is needed
again, for example, to compute gradients during backpropagation, it is
recomputed from the other dependent activations as dictated by the lineage.
Paging, also known as offloading, is a complementary technique to reduce
memory. In paging, an activation tensor that is not immediately needed is
paged-out from the primary memory to a secondary memory such as a flash or an
SD card. When the tensor is needed again, it is paged back in.

This is best understood with the representative neural-network training
timeline from Figure 2. Along the X-axis, each cell corresponds to a single
layer of an eight-layered, linear, neural-network. The Y-axis represents the
logical timesteps over one epoch. An occupied cell indicates that an operation
(forward/backward pass computation, rematerialization, or paging) is executed
at the corresponding timestep. For example, we can see that the activation for
Layer 1 (L1) is computed at the first timestep (T1). At timestep T2 and T3,
the activations of L2 and L3 are computed respectively. Suppose layers L2 and
L3 happen to be memory-intensive but cheap-to-compute operators, such as non-
linearities (tanH, ReLU, etc,) then rematerialization becomes the optimal
choice. We can delete the activations ({T3, L2}, {T4, L3}) to free up memory,
and when these activations are needed during backward propagation we can
rematerialize them ({T14, L3}, {T16, L2}).

Suppose layers L5 and L6 are compute-intensive operators such as convolutions,
dense matrix-multiplication, etc. For such operations, rematerializing the
activations would lead to an increase in run-time and energy and is sub-
optimal. For these layers, it is optimal to page-out the activation tensor to
secondary storage ({T6,L5}, {T7, L6}), and page-in when they are needed
({T10,L6}, {T11, L5}).

One major advantage of paging is that depending on how occupied the memory bus
is, it can be pipelined to hide latency. This is because modern systems have
DMA (Direct Memory Access) which can move the activation tensor from the
secondary storage to the primary memory while the compute engine is running in
parallel. For example, at timestep T7, we are both paging L6 out and computing
L7. However, rematerialization is compute-intensive, cannot be parallelized.
This leads to an increase in run-time. For example, we have to dedicate
timestep T14 to recompute L3 thereby delaying the rest of the backward pass
execution.

##  5 POET: Private Optimal Energy Training

We introduce Private Optimal Energy Training (POET), a graph-level compiler
for deep neural networks that rewrites training DAGs for large models to fit
within the memory constraints of edge devices while remaining energy-
efficient. POET is hardware-aware and first traces the execution of the
forward and backward pass with associate memory allocation requests, runtime,
and per-operation memory and energy consumption. This fine-grained profiling
for each workload happens only once for a given hardware, is automated, cheap,
and provides the most accurate cost model for POET. POET then generates a
Mixed Integer Linear Programming (MILP) which can be efficiently solved. The
POET optimizer searches for an efficient rematerialization and paging schedule
that minimizes end-to-end energy consumption subject to memory constraints.
The resulting schedule is then used to generate a new DAG to execute on the
edge device. While the MILP is solved on commodity hardware, the generated
schedule shipped to the edge device is only a few hundred bytes, making it
highly memory efficient.

Rematerialization is most efficient for operations that are cheap-to-compute
yet memory-intensive. These operations can be recalculated with low energy
overhead. Paging, however, is best suited to compute-intensive operations
where rematerialization would otherwise incur significant energy overhead.
POET jointly considers both rematerialization and paging in an integrated
search space.

Without a minimum training throughput limit, it is possible that the energy
optimal strategy is also far too slow to train in practical applications. In
reality, training needs to run while the device is idle where spare compute
cycles are available. For example, Google Android schedules ML model updates
when the phone is charging. To maintain high training throughputs, the POET
optimizer can maintain a minimum training throughput to ensure that training
completes during downtime.

Given a memory budget $\mu_{RAM}$ and a training time budget $\mu_{deadline}$,
POET finds an energy optimal schedule by choosing to either a) rematerialize
or b) page the tensors to/from secondary storage such as an SD card. Our
method scales to complex, realistic architectures and is _hardware-aware_
through the use of microcontroller-specific, profile-based cost models. We
build upon the formulation proposed by Checkmate (Jain et al., 2020) and adapt
it to jointly consider integrated rematerialization and paging, to optimize
for an energy objective rather than the runtime, and to implement a minimum
throughput constraint.

∑_T [R Φ_compute + M_in Φ_pagein + M_out Φ_pageout]_T R_t, i + S^RAM_t, i≥R_t,
j ∀t ∈V ∀(v_i, v_j) ∈E R_t-1, i + S^RAM_t-1, i + M^in_t-1, i≥S^RAM_t, i∀k ∈K
∀t ≥2 ∀i S^AUX_t-1, i + M^out_t-1, i≥S^AUX_t, i∀t ≥2 ∀i S^AUX_t, i≥M^in_t, i∀k
∈K ∀t ≥2 ∀i S^RAM_t, i≥M^out_t, i∀k ∈K ∀t ≥2 ∀i U^RAM_t,i≤μ_RAM∀t ∈V ∀i ∈V ∑_T
[R Ψ_compute]_T≤μ_deadline S_1, i=0∀i ∈V Rv,v= 1∀v ∈V R, S_SD, S_RAM, M_in,
M_out∈{0, 1}^T ×T

Algorithm 1 POET optimizer: The complete memory constrained MILP with
$O(|V||E|)$ variables and constraints. The definition of $U$ (not listed) is
from Jain et al. (2020), Equations 2 and 3.

Assumptions: We assume operations execute sequentially on edge devices without
inter-operator parallelism. Moreover, we assume parameters and gradients are
stored in a contiguous memory region without paging. Unlike prior work in
rematerialization (Chen et al., 2016; Kirisame et al., 2021), we do not limit
rematerialization to occur once. We assume auxiliary storage (e.g., flash/ SD
card) is available. However, if auxiliary storage is not available, the POET
optimizer will fall back to only performing rematerialization.

###  5.1  Optimal Rematerialization

Following the design of Checkmate (Jain et al., 2020), we introduce the
formulation of the rematerialization problem. Given a directed acyclic
dataflow graph $G=(V,E)$ with $n$ nodes, a topological ordering
$\\{v_{1},\ldots,v_{n}\\}$ is computed which constrains execution to that
order of instructions. Two key decision variables are introduced: (1)
$R\in\\{0,1\\}^{n\times n}$ where $r_{t,i}$ represents the decision to
(re)materialize an operation $v_{i}$ at timestep $t$ and (2)
$S\in\\{0,1\\}^{n\times n}$ where $s_{t,i}$ represents whether the result of
an operation $v_{i}$ is resident in memory at timestep $t$.

From the rematerialzation matrix $R$, and the storage matrix $S$, we define a
series of constraints to maintain graph dependencies. All arguments for an
operation $j$ must be resident in memory prior to running that operation,
yielding constraint $R_{t,i}+S_{t,i}\geq R_{t,j}~{}~{}\forall(i,j)\in
E~{}~{}\forall t\in\\{1,\ldots,n\\}$. Similarly, the result of an operation is
only resident in memory in one of the two cases: a) if it was already resident
in memory before, or b) if it was (re)materialized ($S_{t,i}\leq
S_{t-1,i}+R_{t-1,i}~{}~{}\forall i\in V~{}~{}\forall t\in\\{1,\ldots,n\\}$).

To adhere to the strict constraints on the peak memory used during training,
an intermediate variable $U\in\mathbb{R}^{n\times n}$ is defined. $U_{t,i}$ is
the total memory used by the system during training at timestep $t$ when
evaluating operation $i$. By bounding the maximum value of
$U_{t,i}~{}~{}\forall i\in V~{}~{}\forall t\in\\{1,\ldots,n\\}$ to the user-
specified memory limit $\mu_{RAM}$, we limit the total memory consumption
during training.

###  5.2 Optimal integrated paging and rematerialization

While rematerialization can provide significant memory savings, it introduces
significant energy consumption overheads from duplicate recomputations.
Similarly, paging if done wrong will result in a wasteful shuffling of data
between memories. Here, we formalize a joint search space for
rematerialization and paging to enable the discovery of the energy-optimal
hybrid schedule.

Like rematerialization, the discovery of the optimal paging schedule is a
challenging combinatorial search problem. However, we find that independently
solving for paging first, and then solving for rematerialization will not
produce globally optimal solutions. As an example, consider a graph where the
output depends on the result of two operations $v_{1}$ and $v_{2}$ where both
nodes have equivalent memory costs but $v_{2}$ is cheaper to evaluate. A
paging strategy may evict $v2$ which would force rematerialization to
recompute the more expensive $v_{1}$ rather than $v_{2}$.

We represent a schedule as a series of nodes that are either being saved
$S^{RAM}$, (re)computed $R$ or paged from secondary storage $S^{AUX}$. To
model when a node is copied from secondary storage to RAM, we introduce a
variable $M^{in}\in\\{0,1\\}^{n\times n}$ where $M^{in}_{t,i}$ represents
paging a tensor from secondary storage to RAM between timesteps $t-1$ and $t$.
Similarly, we model page-out with $M^{out}$.

We now present the intuition behind adding the following constraints to the
optimization problem in order to search over optimal schedules for paging and
rematerialization:

  * 1c

For $S_{t,i}^{RAM}$ to be in memory at time-step $t$, either compute $R_{t,i}$
at timestep $t$, or retain $S_{t,i}^{RAM}$ in memory from the previous
timestep $t-1$, or page-in if $S_{t-1,i}^{RAM}$ is resident on flash (at
$t-1$).

  * 1d

Each node $i$ can reside on flash $S_{t,i}^{AUX}$, either if it resided on
flash at timestep $t-1$ ($S_{t-1,i}^{AUX}$), or it was paged out at time-step
$t-1$ ($M_{t-1,i}^{out}$).

  * 1e

To page-in $M_{t,i}^{in}$ at time-step $t$, it has to be resident on flash
$S_{t,i}^{AUX}$ at timestep $t$.

  * 1f

Each node $i$ can reside in memory $S_{t,i}^{RAM}$ at timestep $t$, only if it
was paged out of flash ($M_{t,i}^{out}$).

Algorithm 1 defines the complete optimization problem.

###  5.3 Expressing an energy consumption objective

If we only consider rematerialization, then minimizing runtime will generally
correlate with decreased energy usage. However, this is no longer true when
considering paging; paging can be more energy-efficient than rematerializing a
compute-intensive operation. To address this, we introduce a new objective
function to the optimization problem that minimizes the combined energy
consumption due to computation, page-in, and page-out.

When paging occurs on an edge device, the vast majority of energy consumed is
due to powering-on the flash/SD block device. As this power is in addition to
any power the CPU is consuming, the total power consumption is a linear
combination of paging and CPU energy. We precompute each of these values,
generally as the integral of the power of active components of the edge device
integrated over the runtime of the operation. $\Phi_{compute}$,
$\Phi_{pagein}$ and $\Phi_{pageout}$ represent the energy consumed for each
node for computing, paging in, and paging out respectively.

Therefore, the new objective function combining paging and rematerialization
energy usage is:

$\sum_{T}\left[R\Phi_{compute}+M_{in}\Phi_{pagein}+M_{out}\Phi_{pageout}\right]_{T}$
(1)

###  5.4 Ensuring minimum training throughput

If we attempt to find the minimum energy schedule subject to only a memory
constraint, the POET solver may select solutions with poor end-to-end training
throughput. Ideally, training should occur in the downtime between interactive
workloads on an edge device. To ensure this, we introduce a new constraint to
the optimization problem that ensures schedules meet a minimum training
throughput threshold. This constraint effectively trades off between energy
consumption and training throughput.

To enforce a particular throughput, we compute a latency target. Via
profiling, we capture $\Psi_{compute}$ denoting the runtime of each operation.
We then constrain total runtime with the constraint:

$\sum_{T}[R\Psi_{compute}]_{T}\leq\mu_{deadline}$ (2)

###  5.5 Paging latency hiding via transfer planner

POET outputs the DAG schedule in terms of which nodes of the graph ($k$) to
rematerialize, and which to page-in ($M^{in}_{t,k}$) or page-out
($M^{out}_{t,k}$) at each time-step ($t$). Our Algorithm 2 takes the ILP
solves to generate and dictate the strategy that determines which tensors are
resident-in-memory ($S^{aux}_{t,k}$) at a fine-grained (operator) level.

We factor in the latency introduced by paging. As described in Section 6.1,
POET is hardware-aware by profiling the latency per platform for paging
activations to secondary storage. Fine-grained profiling helps in fine-tuning
when to start paging, such that the activation tensors arrive just-in-time. We
then modify the page-in ($M^{in}_{t,k}$) and the page-out ($M^{out}_{t,k}$)
schedule to ensure there is no contention for the memory bus as the tensors
are paged-in just-in-time. For example, if ($M^{in}_{t,i}$) can contend with
($M^{in}_{t,j}$), then we schedule one of them to page-in at an earlier time
($M^{in}_{t-1,i}$) and update the in-memory schedule ($S^{aux}_{t-1,i}$) to
account for the earlier paging-in. While this ensures the activations are
paged in just-in-time, in parallel, ($R_{t^{\prime},j}$) informs the PyTorch
DAG scheduler to deallocate the tensors that we have chosen to rematerialize
($S^{aux}_{t,k}$) at a future timestep ($t^{\prime}$).

Input: Graph $G=(V,E)$, schedule $R,M_{in},M_{out}$

for  _t=1,.., $|V|$_ do

for  _k=1,.., $|V|$_ do

if  _$M^{in}_{t}$_ then

add %r = pagein $v_{k}$ to $P$

if  _$R_{t,k}$_ then

add %r = compute $v_{k}$ to $P$

if  _$M^{out}_{t,k}$_ then

add %r = pageout $v_{k}$ to $P$

for  _$i\in\text{DEPS}[k]\cup\\{k\\}$_ do

if  _$M^{out}_{t,k}\lor\text{FREE}_{t,i,k}$_ then

add deallocate %r to $P$

Output: execution plan $P=(v_{1},..,v_{n})$

Algorithm 2 Training Graph Execution Plan

##  6 Evaluation

Device | Clock | RAM | FPU?
---|---|---|---
M0 (MKR1000) | 48 MHz | 32 KB | $\times$
M4 (nrf52840) | 64 MHz | 256 KB | $\surd$
A72 (RPi-4B+). | 1.5 GHz | 2 GB | $\surd$
A57 (Jetson TX2) | 2 GHz | 8 GB | $\surd$
Table 2: We evaluate a wide variety of battery-powered edge devices. All
devices have at least 32GB of flash memory via an SD card or flash to enable
paging of activations or tensors. FPU is floating-point unit.

In our evaluation of POET we seek to answer three key questions. First, how
much energy consumption does POET reduce across different models and
platforms? Second, how does POET benefit from the hybrid paging and
rematerialization strategy? Lastly, how does POET adapt to different runtime
budgets?

###  6.1 Experimental setup

We evaluate POET on four distinct hardware devices listed in Table 2: the ARM
Cortex M0 class MKR1000, ARM Cortex M4F class nrf52840, A72 class Raspberry Pi
4B+, and Nvidia Jetson TX2. POET is fully hardware-aware and relies on fine-
grained profiling. For example, on the Jetson-TX2 hardware we profile each
operator along with its variations in dimensionality (e.g., conv2d with
varying kernel-sizes, strides, padding, etc.) These fine-grained time, energy,
and memory profiles then inform POET about the exact specifications. These
devices test a diverse set of memory, compute, and power configurations. As
POET is hardware and energy-aware, it takes device-specific characteristics
into account.

We evaluate POET on VGG16 (Simonyan & Zisserman, 2014) and ResNet-18 (He et
al., 2016) trained on the CIFAR-10 dataset as well as BERT (Devlin et al.,
2018). In all of our baselines, we limit all MILP solves to no more than 10
min on commodity CPUs. Our experiments are with a batch-size of 1. We compare
POET to work PyTorch’s default scheduler, Chen et al. (2016), Griewank &
Walther (2000), DTR (Kirisame et al., 2021), and Checkmate (Jain et al.,
2020).

Hyperparameters: POET only decides on the optimal scheduling of nodes in the
training graph and does $not$ change the training routine (learning rate,
optimizer, etc.). Hence, our system is robust to hyper-parameters.

Sensitivity to Batch-size: POET is mathematically preserving and can be easily
scaled to arbitrary batch sizes without loss of generality. Of course, this is
conditioned on the underlying device’s memory capacity. It is possible that as
batch size varies, the underlying operator implementation might change. POET,
with its fine-grained profiling is robust to these changes and transparently
adapts to artifacts.

###  6.2 How much energy consumption does POET reduce across models and
platforms?

Figure 3:  POET consumes less energy across diverse models and devices: We profile the energy usage of each method relative to a full-memory configuration as the device’s available memory capacity shrinks. For ResNet-18 (top row), VGG (middle row) and BERT (bottom), POET outperforms competitive methods in most configurations. When training ResNet-18 on the TX2, POET consumes up to 35% less energy than DTR while discovering solutions at tighter memory budgets.  Figure 4: Both rematerialization and paging are necessary for low-energy schedules with limited memory: We compare ablations of POET on VGG for CIFAR-10 and find that both rematerialization and paging are required to achieve low-energy solutions at limited memory budgets across all runtime constraint values.  Figure 5: Optimal integrated rematerialization and paging outperforms Capuchin (log scale): POET incurs 73% to 140% less energy overhead relative to a full-memory baseline by rematerializing earlier alongside paging. Capuchin strongly prefers paging before falling-back on rematerializing activations which makes it sub-optimal.  | ResNet-18 Training
---|---
| POET | POFO (Beaumont et al. 2021)
Memory | 285,873 kB | 311,808 kB
Runtime | 82.36 ms | 94.79 ms
Table 3: POET’s MILP formulation lowers peak memory consumption by 8.3% and
improves throughput by 13% compared to POFO (Beaumont et al., 2021) on
Nvidia’s Jetson TX2 edge device

Figure 3 shows the energy consumed for a single epoch of training. Each column
represents a unique hardware platform as defined in Table 2. We notice that
across all platforms, POET generates the most energy-optimal (Y-axis) schedule
all the while reducing the peak memory consumed (X-axis) and adhering to the
timing budget.

For the BERT model on the Cortex M4 and the TX2 platform, we noticed an
interesting behavior: our ILP solves time-out. This is because we limit all
solves to no more than 10 min. With a longer ILP solve budget ($<$30 min),
POET can predictably find more optimal solutions. Further, notice that a) POET
has an additional timing budget which none of the other baselines do, and b)
all of our baselines are already mature. Checkmate (Jain et al., 2020) is
provably optimal for rematerialization, while DTR (Kirisame et al., 2021)
closely approximated Checkmate. Furthermore, POET tried to solve a much
“harder” problem as its search space with rematerialization and paging
together is larger.

###  6.3 How does POET benefit from integrated rematerialization and paging?

We compare our joint optimal paging and rematerialization schedule with
Capuchin which optimizes each with a heuristic. Capuchin will effectively page
until no longer feasible and only then will it begin to rematerialize.
Instead, POET begins rematerializing cheap operations like ReLU much earlier
which yields considerable energy savings (up to 141% lower overhead).

In Figure 5, we benchmark POET and Capuchin when training ResNet-18 on the
A72. As the RAM budget decreases (to the right), Capuchin consumes 73% to 141%
more energy than a baseline with full memory. In comparison, POET incurs less
than a 1% energy overhead. This trend holds for all architectures and
platforms we tested.

In Table 3 we benchmark POET and POFO when training ResNet-18 on Nvidia’s
Jetson TX2. We find that POET finds an integrated rematerialization and paging
schedule that lowers peak memory consumption by 8.3%  and improves throughput
by 13%. This showcases the benefit of POET’s Mixed-integer linear programming
(MILP) solver, which is able to optimize over a much larger search-space.
While POFO only supports linear models, POET generalizes to non-linear models
as demonstrated in Fig 3.

###  6.4 How does POET adapt to varying runtimes?

Figure 4 highlights the benefit of the integrated strategies that POET adopts
across different timing constraints. The run-time budget refers to the total
time available for one epoch of training naïvely (without paging or
rematerialization). For each of the runtimes, we plot the total energy
consumed if we were to restrict to either of a) paging or b) rematerialization
only, and the c) integrated solution.

We find that rematerialization is energy-optimal compared to paging at higher
(looser) timing budgets. This is reflected in the POET (paging+remat) green
curve, closely tracking the POET (remat only) yellow curve at runtime budgets
of $0.6$ \- $0.9$ ms. However, at lower runtime budget ($0.5$ ms), paging is
preferable as rematerialization strategies become infeasible. This is because,
rematerialization is a compute intensive serial operation, however, our
Algorithm 2 benefits from the ability to hide paging latencies by pipelining
(see Section 6.2) to realize the tighter deadline bounds. POET’s optimal,
integrated solution consumes up to ${40\%}$ lower energy compared to paging or
rematerialization only solutions.

##  7 Conclusion

Enabling large models to be trained on edge devices is important due to
privacy constraints as well as offline operation. Edge devices deployed in the
real-world are powered by tiny microcontrollers that are low-powered, and have
limited memory (e.g. $32$ KB). The low-power and limited memory, coupled with
tight timing constraints imposed by real-time systems makes training on the
edge challenging.

Our novel mixed-integer linear programming based Power Optimal Edge Training
(POET) algorithm enables training on tiny chips with memory as low as 32 KB.
Given a memory budget and a timing constraint, POET finds the most energy
optimal schedule to train the model by choosing to either rematerialize or
page the tensors to secondary storage.

Across a diverse set of models and devices, we discover low-power training
schedules at less memory than baselines. POET enables new applications for
privacy-preserving personalization of large models like BERT on tiny devices
at the edge for the first time. Future directions include integrating
activation compression as well as expanding POET’s search space to paging
parameters.

## Acknowledgement

We thank Prateek Jain, Charles Packer, Daniel Rothchild, Alex Smola, Pete
Warden, and the anonymous reviewers whose insightful comments, and feedback
helped improve the paper. This research is supported by a NSF CISE Expeditions
Award CCF-1730628, and gifts from Amazon Web Services, Ant Group, Ericsson,
Facebook, Futurewei, Google, Intel, Microsoft, Scotiabank, and VMware. This
work was supported in part by the CONIX Research Center, one of six centers in
JUMP, a Semiconductor Research Corporation (SRC) program sponsored by DARPA.

## References

  * Beaumont et al. (2021) Beaumont, O., Eyraud-Dubois, L., and Shilova, A.  Efficient combination of rematerialization and offloading for training dnns.  In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), _Advances in Neural Information Processing Systems_ , volume 34, pp. 23844–23857. Curran Associates, Inc., 2021.  URL https://proceedings.neurips.cc/paper/2021/file/c8461bf13fca8a2b9912ab2eb1668e4b-Paper.pdf.
  * Blalock et al. (2020) Blalock, D., Gonzalez Ortiz, J. J., Frankle, J., and Guttag, J.  What is the state of neural network pruning?  In Dhillon, I., Papailiopoulos, D., and Sze, V. (eds.), _Proceedings of Machine Learning and Systems_ , volume 2, pp. 129–146, 2020\.  URL https://proceedings.mlsys.org/paper/2020/file/d2ddea18f00665ce8623e36bd4e3c7c5-Paper.pdf.
  * Cai et al. (2019) Cai, H., Zhu, L., and Han, S.  ProxylessNAS: Direct neural architecture search on target task and hardware.  In _International Conference on Learning Representations_ , 2019.  URL https://arxiv.org/pdf/1812.00332.pdf.
  * Chen et al. (2021) Chen, J., Zheng, L., Yao, Z., Wang, D., Stoica, I., Mahoney, M. W., and Gonzalez, J. E.  Actnn: Reducing training memory footprint via 2-bit activation compressed training.  In _International Conference on Machine Learning_ , 2021.
  * Chen et al. (2016) Chen, T., Xu, B., Zhang, C., and Guestrin, C.  Training deep nets with sublinear memory cost.  _CoRR_ , abs/1604.06174, 2016.  URL http://arxiv.org/abs/1604.06174.
  * Dennis et al. (2019) Dennis, D. K., Gopinath, S., Gupta, C., Kumar, A., Kusupati, A., Patil, S. G., and Simhadri, H. V.  EdgeML: Machine Learning for resource-constrained edge devices.  2019\.  URL https://github.com/Microsoft/EdgeML.  http://github.com/Microsoft/EdgeML.
  * Devlin et al. (2018) Devlin, J., Chang, M., Lee, K., and Toutanova, K.  BERT: pre-training of deep bidirectional transformers for language understanding.  _CoRR_ , abs/1810.04805, 2018.  URL http://arxiv.org/abs/1810.04805.
  * Dong et al. (2019) Dong, Z., Yao, Z., Gholami, A., Mahoney, M. W., and Keutzer, K.  Hawq: Hessian aware quantization of neural networks with mixed-precision.  In _The IEEE International Conference on Computer Vision (ICCV)_ , October 2019.
  * Frankle & Carbin (2019) Frankle, J. and Carbin, M.  The lottery ticket hypothesis: Finding sparse, trainable neural networks.  In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net, 2019.  URL https://openreview.net/forum?id=rJl-b3RcF7.
  * Griewank & Walther (2000) Griewank, A. and Walther, A.  Algorithm 799: Revolve: An implementation of checkpointing for the reverse or adjoint mode of computational differentiation.  _ACM Trans. Math. Softw._ , 26(1):19–45, March 2000.  ISSN 0098-3500.  doi: 10.1145/347837.347846.  URL https://doi.org/10.1145/347837.347846.
  * Hard et al. (2018) Hard, A., Rao, K., Mathews, R., Ramaswamy, S., Beaufays, F., Augenstein, S., Eichner, H., Kiddon, C., and Ramage, D.  Federated learning for mobile keyboard prediction.  _arXiv preprint arXiv:1811.03604_ , 2018.
  * He et al. (2016) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * Huang et al. (2020) Huang, C.-C., Jin, G., and Li, J.  _SwapAdvisor: Pushing Deep Learning Beyond the GPU Memory Limit via Smart Swapping_ , pp. 1341–1355.  Association for Computing Machinery, New York, NY, USA, 2020.  ISBN 9781450371025.  URL https://doi.org/10.1145/3373376.3378530.
  * Iandola et al. (2016) Iandola, F. N., Han, S., Moskewicz, M. W., Ashraf, K., Dally, W. J., and Keutzer, K.  Squeezenet: Alexnet-level accuracy with 50x fewer parameters and ¡0.5mb model size, 2016.
  * Jain et al. (2020) Jain, P., Jain, A., Nrusimha, A., Gholami, A., Abbeel, P., Keutzer, K., Stoica, I., and Gonzalez, J. E.  Checkmate: Breaking the memory wall with optimal tensor rematerialization.  _arXiv preprint arXiv:1910.02653_ , 2020.
  * Jang & Adib (2019) Jang, J. and Adib, F.  Underwater backscatter networking.  In _Proceedings of the ACM Special Interest Group on Data Communication_ , SIGCOMM ’19, pp. 187–199, New York, NY, USA, 2019. Association for Computing Machinery.  ISBN 9781450359566.  doi: 10.1145/3341302.3342091.  URL https://doi.org/10.1145/3341302.3342091.
  * Kapoor (2019) Kapoor, G. e. a.  Coreml, apple.  2019\.  URL https://developer.apple.com/documentation/coreml.
  * Kirisame et al. (2021) Kirisame, M., Lyubomirsky, S., Haan, A., Brennan, J., He, M., Roesch, J., Chen, T., and Tatlock, Z.  Dynamic tensor rematerialization.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=Vfs_2RnOD0H.
  * Lane et al. (2016) Lane, N. D., Bhattacharya, S., Georgiev, P., Forlivesi, C., Jiao, L., Qendro, L., and Kawsar, F.  DeepX: A software accelerator for low-power deep learning inference on mobile devices.  In _Proceedings of the 15th International Conference on Information Processing in Sensor Networks_ , IPSN ’16. IEEE Press, 2016.  ISBN 9781509008025.
  * Lee et al. (2019) Lee, J., Chirkov, N., Ignasheva, E., Pisarchyk, Y., Shieh, M., Riccardi, F., Sarokin, R., Kulik, A., and Grundmann, M.  On-device neural net inference with mobile GPUs.  _CoRR_ , abs/1907.01989, 2019.  URL http://arxiv.org/abs/1907.01989.
  * Levis et al. (2004) Levis, P., Patel, N., Culler, D., and Shenker, S.  Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks.  In _Proceedings of the 1st Conference on Symposium on Networked Systems Design and Implementation - Volume 1_ , NSDI’04, pp. 2, USA, 2004. USENIX Association.
  * Li et al. (2020) Li, T., Sahu, A. K., Talwalkar, A., and Smith, V.  Federated learning: Challenges, methods, and future directions.  _IEEE Signal Processing Magazine_ , 37(3):50–60, 2020.  doi: 10.1109/MSP.2020.2975749.
  * Park et al. (2017) Park, E., Ahn, J., and Yoo, S.  Weighted-entropy-based quantization for deep neural networks.  In _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 7197–7205, July 2017.  doi: 10.1109/CVPR.2017.761.
  * Patil et al. (2019) Patil, S. G., Dennis, D. K., Pabbaraju, C., Shaheer, N., Simhadri, H. V., Seshadri, V., Varma, M., and Jain, P.  Gesturepod: Enabling on-device gesture-based interaction for white cane users.  In _Proceedings of the 32Nd Annual ACM Symposium on User Interface Software and Technology_ , UIST ’19, pp. 403–415, New York, NY, USA, 2019. ACM.  ISBN 978-1-4503-6816-2.  doi: 10.1145/3332165.3347881.  URL http://doi.acm.org/10.1145/3332165.3347881.
  * Patterson et al. (2022) Patterson, D., Gonzalez, J., Hölzle, U., Le, Q., Liang, C., Munguia, L.-M., Rothchild, D., So, D., Texier, M., and Dean, J.  The carbon footprint of machine learning training will plateau, then shrink.  _arXiv preprint arXiv:2204.05149_ , 2022.
  * Paulik et al. (2021) Paulik, M., Seigel, M., Mason, H., Telaar, D., Kluivers, J., van Dalen, R. C., Lau, C. W., Carlson, L., Granqvist, F., Vandevelde, C., Agarwal, S., Freudiger, J., Byde, A., Bhowmick, A., Kapoor, G., Beaumont, S., Cahill, Á., Hughes, D., Javidbakht, O., Dong, F., Rishi, R., and Hung, S.  Federated evaluation and tuning for on-device personalization: System design & applications.  _CoRR_ , abs/2102.08503, 2021.  URL https://arxiv.org/abs/2102.08503.
  * Peng et al. (2020) Peng, Q., Shi, X., Dai, H., Jin, H., Ma, W., Xiong, Q., Yang, F., and Qian, X.  Capuchin: Tensor-based gpu memory management for deep learning.  In _ASPLOS_ , March 2020.  URL https://www.microsoft.com/en-us/research/publication/capuchin-tensor-based-gpu-memory- management-for-deep-learning/.
  * Ren et al. (2021) Ren, J., Rajbhandari, S., Aminabadi, R. Y., Ruwase, O., Yang, S., Zhang, M., Li, D., and He, Y.  ZeRO-Offload: Democratizing Billion-Scale model training.  In _2021 USENIX Annual Technical Conference (USENIX ATC 21)_ , pp. 551–564. USENIX Association, July 2021.  ISBN 978-1-939133-23-6.  URL https://www.usenix.org/conference/atc21/presentation/ren-jie.
  * Shah et al. (2021) Shah, A., Wu, C.-Y., Mohan, J., Chidambaram, V., and Kraehenbuehl, P.  Memory optimization for deep networks.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=bnY0jm4l59.
  * Simonyan & Zisserman (2014) Simonyan, K. and Zisserman, A.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.
  * Tan & Le (2021) Tan, M. and Le, Q. V.  Efficientnetv2: Smaller models and faster training.  _CoRR_ , abs/2104.00298, 2021.  URL https://arxiv.org/abs/2104.00298.
  * Vasisht et al. (2017) Vasisht, D., Kapetanovic, Z., Won, J., Jin, X., Chandra, R., Sinha, S., Kapoor, A., Sudarshan, M., and Stratman, S.  Farmbeats: An iot platform for data-driven agriculture.  In _14th $\\{$USENIX$\\}$ Symposium on Networked Systems Design and Implementation ($\\{$NSDI$\\}$ 17)_, pp. 515–529, 2017.
  * Wang et al. (2019) Wang, Y., Jiang, Z., Chen, X., Xu, P., Zhao, Y., Lin, Y., and Wang, Z.  E2-train: Training state-of-the-art cnns with over 80% energy savings.  In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems 32_ , pp. 5138–5150. Curran Associates, Inc., 2019.  URL http://papers.nips.cc/paper/8757-e2-train-training-state-of-the- art-cnns-with-over-80-energy-savings.pdf.


# ConTrip: Consensus Sentiment review Analysis and Platform ratings in a
single score

José Bonet
Department of Computational Biology
IRB Barcelona
Barcelona, Spain 08028
<EMAIL_ADDRESS>
& José Bonet
Institute of Pure and Applied Mathematics
Universitat Politècnica de València
Valencia, Spain 46071
<EMAIL_ADDRESS>

###### Abstract

People unequivocally employ reviews to decide on purchasing an item or an
experience on the internet. In that regard, the growing significance and
number of opinions have led to the development of methods to assess their
sentiment content automatically. However, it is not straightforward for the
models to create a consensus value that embodies the agreement of the
different reviews and differentiates across equal ratings for an item. Based
on the approach proposed by Nguyen et al. [8], we derive a novel consensus
value named ConTrip that merges their consensus score and the overall rating
of a platform for an item. ConTrip lies in the rating range values, which
makes it more interpretable while maintaining the ability to differentiate
across equally rated experiences. ConTrip is implemented and freely available
under MIT license at github.com/pepebonet/contripscore

_Keywords_ Consensus Score $\cdot$ Rating $\cdot$ Sentiment analysis

##  1 Introduction

Customers in the world wide web do not rely solely on their opinion to acquire
a product. Nowadays, ratings and reviews have proved their usefulness to
influence consumers on their purchases [1, 4]. The reason is that these
reviews facilitate decision-making, especially in experiences challenging to
assess if not consumed as in hotels, restaurants, tours, or destinations [7].
Therefore, people’s opinions put into words have significantly helped
platforms such as Booking111booking.com, Tripadvisor222tripadvisor.com,
Yelp333yelp.com, and others to increase the flow of people setting their next
experience through their platform.

Given the relevance of these reviews in customer behavior, outstanding efforts
have taken place to advance their automatic analysis [2]. As a consequence,
the field of sentiment analysis has recently risen [13]. Essentially, there
are two basic approaches for automatic sentiment categorization –machine-
learning (ML) [3, 14] and lexicon-based [5]. Lexicon-based methods use
handcrafted features and depend on a collection of lexical units and their
sentiment orientation –sentiment lexicons. On the other hand, supervised
machine learning methods (mainly used) identify word features that effectively
distinguish between positive and negative sentiments.

Regardless of the technology employed, it is not straightforward to derive a
measurement of agreement or disagreement between the reviews of a given
product. Nguyen et al. [8] proposed a score to measure the consensus of these
reviews for a single item based on the sentiment analysis and rating of each
critique. This new measurement allowed them to differentiate among ratings
that were initially equal. That is, for instance, the ability to separate
equivalent Tripadvisor ratings with their new inferred score.

However, the consensus score embodies a value between 0 and 1, with values
close to one representing total agreement and 0 disagreements in the reviews.
This fact poses two significant complications: people can agree to good or bad
reviews, and therefore one can not solely rely on the consensus value, and
second a value between 0 and 1 is not easily interpretable for a public used
to ratings between 1 and 5.

Therefore, based on the work from Nguyen et al. [8], we propose an extension
of their consensus value on our score named ConTrip. ConTrip is computed
through a straightforward mathematical expression taking as input the
consensus value of the reviews, for instance, as proposed by Nguyen et al. [8]
and the overall rating of the platform. As output, ConTrip encompasses a novel
consensus value merging both inputs and rendering an interpretable value
within the rating values. We argue that such a single value bringing together
both sources of information could substitute the current overall rating of the
platform to have a more truthful score of the experience to be purchased by
the customer.

##  2 Methods

###  2.1 ConTrip computation

ConTrip employs a consensus value ($y\in[0,1]$) of all the reviews as
computed, for instance, from Nguyen et al. [8] and the overall rating of an
item ($x\in[1,5]$). The consensus score embodies the sentiment analysis of
every review and displays the degree of agreement across them. On the other
hand, the overall rating represents the average of all the available ratings
for an item. Through both values, ConTrip is denoted by $m$ and is computed as
shown by Equation 1.

$m:={\underbrace{min(5,x+(y-0.5)\cdot\alpha)}_{\text{Term 1}}}\
-{\underbrace{\frac{(1-y)\cdot x}{\beta}}_{\text{Term 2}}}\
-{\underbrace{\frac{5-x}{\delta}}_{\text{Term 3}}}$ (1)

The first term embodies a consensus penalty. If the consensus rating $y<0.5$,
the rating will decrease, while if $y>0.5$, it will increase. A maximum value
of 5 is enforced. The second term penalizes disagreements in a non-linear
fashion –affecting disagreements more at higher ratings. The third and final
term enforces differentiation across similar ratings. All equation terms are
governed by a weight value ($\alpha$, $\beta$ and $\delta$). We fixed them
heuristically to the following values: $\alpha=0.5$, $\beta=10$ and
$\delta=100$.

###  2.2 ConTrip Scaling

Given the nature of Equation 1 to compute ConTrip, score values lower than one
can arise (minimum value 0.61). Therefore, to overcome difficulties in its
applicability, we re-scale the ConTrip values $m$ from a [0.61, 5] range to a
[1, 5] range employing the following equation:

$(t_{max}-t_{min})\cdot\frac{m-r_{min}}{r_{max}-r_{min}}+t_{min}$ (2)

where $t_{max}$ and $t_{min}$ denote the maximum and minimum of the range of
the desired target scaling respectively (5 and 1). On the other hand,
$r_{max}$ and $r_{min}$ denote the maximum and minimum of the range of the
measurement.

##  3 Results

The objective of the work is to create an interpretable score that can
differentiate across similarly rated items, all of this while merging the
information of the sentiment analysis and the overall rating of an experience
listed. This output score (ConTrip) would consist of a more informative
overall rating.

To assess the proposed score, we first studied the behavior of ConTrip for 50
different values of any consensus score varying between 0 and 1 and for five
overall ratings. For both cases, with and without scaling, Figures 1B and 1D
show two characteristics: one, both the consensus score and the overall rating
have significant contributions (For a Rating of 4, depending on the consensus
values, ConTrip score ranges between 3.340 for consensus value of 0 and 4.240
for a consensus value of 1), and, two, as the rating increases, disagreement
in the reviews (low consensus values) have a more powerful impact (A consensus
of 0 drives a rating of 5 to have a ConTrip score of 4.25. In contrast, the
same 0 consensus drives a rating of 2 only to 1.52).

Secondly, we investigate what occurs when we fix six consensus values, and 41
different ratings are studied. Figures 1A and 1C (without and with scaling
respectively) confirmed the previous trends and display the ability of ConTrip
to differentiate between similarly rated items. Among all the Consensus-Rating
pairs tested (246), the proposed ConTrip score achieved an overall
differentiation of 97.6 % (240 out of 246).

Figure 1: Analysis of the ConTrip score for different consensus values from
the sentiment analysis and different overall ratings for an item or experience
from a platform. A, C) ConTrip measurements for a set of consensus values
varying the platform rating. B,D) ConTrip measurements for a set of ratings
varying the consensus values. A and B represent the ConTrip score without
scaling and C and D with scaling.

##  4 Discussion

The current state of the sentiment analysis field is widely dominated by deep
learning (DL) models achieving state-of-the-art performances for a wide range
of tasks [13]. The latest research shows the application of Transformers,
Adversarial Learning and Graphical Neural Networks to Aspect-Based Sentiment
Analysis [6, 9], Sentiment Topic Extraction [10], and Emotion Caused Detection
[11, 12], among other tasks. However, how the model output is used to give
back information to the user may not be as straightforward.

For that reason, works such as the one proposed by Nguyen et al. [8], despite
not taking advantage of deep learning methodologies, are proven significant.
On outtake of the publication was the ability of their consensus measurement
to allow users to differentiate closely rated options. However, their proposed
evaluation lacked interpretability as the range between 0 and 1 is not user-
friendly, and values of 1, for instance, could be interpreted as both total
positive or negative agreement. Therefore, and building upon their work, we
developed ConTrip, a novel measurement that merges the consensus value of any
sentiment analysis and the overall rating of an item listed. We showed that
ConTrip does that while providing an interpretable and user-friendly
measurement that can differentiate across closely rated experiences.

We hypothesize that results from both lexicon-based and ML/DL approaches could
be used as the input to compute ConTrip. Either as the centroid-based approach
proposed by Nguyen et al. [8] or as an average of the classification scores
between Positive and Negative sentiment from a given method for a set of
reviews.

In summary, ConTrip poses an initial milestone to substitute overall rating
scores with a more informative measurement. User experience is crucial, and
including an additional value or a set of numbers may pose risks for the
website conversion rates. Therefore, ConTrip embodies all the information in a
single value and could be directly implemented. As DL continues to evolve and
the data extracted from reviews are more accurate and valuable, their possible
impact on the item rating will be higher. Therefore, their inclusion on the
overall rating will be even more compelling. ConTrip is just an initial step
in that direction.

##  5 Acknowledgements

The authors want to thank Nuria Agell, Albert Armisen and Jennifer Nguyen for
the discussion about their publication that made this possible.

## References

  * [1] Naveen Amblee and Tung Bui  “Harnessing the influence of social proof in online shopping: The effect of electronic word of mouth on sales of digital microproducts”  In _International journal of electronic commerce_ 16.2 Taylor & Francis, 2011, pp. 91–114
  * [2] Xing Fang and Justin Zhan  “Sentiment analysis using product review data”  In _Journal of Big Data_ 2.1 SpringerOpen, 2015, pp. 1–14
  * [3] Fatemeh Hemmatian and Mohammad Karim Sohrabi  “A survey on classification techniques for opinion mining and sentiment analysis”  In _Artificial Intelligence Review_ 52.3 Springer, 2019, pp. 1495–1545
  * [4] Ed Keller and Brad Fay  “Word-of-mouth advocacy: A new key to advertising effectiveness”  In _Journal of Advertising Research_ 52.4 Journal of Advertising Research, 2012, pp. 459–464
  * [5] Christopher SG Khoo and Sathik Basha Johnkhan  “Lexicon-based sentiment analysis: Comparative evaluation of six sentiment lexicons”  In _Journal of Information Science_ 44.4 SAGE Publications Sage UK: London, England, 2018, pp. 491–511
  * [6] Bin Liang et al.  “Aspect-invariant Sentiment Features Learning: Adversarial Multi-task Learning for Aspect-based Sentiment Analysis”  In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, 2020, pp. 825–834
  * [7] Zhiwei Liu and Sangwon Park  “What makes a useful online review? Implication for travel product websites”  In _Tourism management_ 47 Elsevier, 2015, pp. 140–151
  * [8] Jennifer Nguyen et al.  “Fusing hotel ratings and reviews with hesitant terms and consensus measures”  In _Neural Computing and Applications_ 32.19 Springer, 2020, pp. 15301–15311
  * [9] Haiyun Peng et al.  “Knowing what, how and why: A near complete solution for aspect-based sentiment analysis”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ 34.05, 2020, pp. 8600–8607
  * [10] Gabriele Pergola, Lin Gui and Yulan He  “A Disentangled Adversarial Neural Topic Model for Separating Opinions from Plots in User Reviews”  In _arXiv preprint arXiv:2010.11384_ , 2020
  * [11] Penghui Wei, Jiahao Zhao and Wenji Mao  “Effective inter-clause modeling for end-to-end emotion-cause pair extraction”  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , 2020, pp. 3171–3181
  * [12] Rui Xia, Mengran Zhang and Zixiang Ding  “RTHN: A rnn-transformer hierarchical network for emotion cause extraction”  In _arXiv preprint arXiv:1906.01236_ , 2019
  * [13] Ashima Yadav and Dinesh Kumar Vishwakarma  “Sentiment analysis using deep learning architectures: a review”  In _Artificial Intelligence Review_ 53.6 Springer, 2020, pp. 4335–4385
  * [14] Lei Zhang, Shuai Wang and Bing Liu  “Deep learning for sentiment analysis: A survey”  In _Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery_ 8.4 Wiley Online Library, 2018, pp. e1253