# PUF Probe: A PUF-based Hardware Authentication Equipment for IEDs ††thanks:
This work was carried out under PGCoE, funded by Power Grid Corporation of
India.

Vishal D. Jadhav  Dept. of Electronic Systems Engg.
Indian Institute of Science
Bangalore, India
<EMAIL_ADDRESS>Narahari N. Moudhgalya  Dept. of Electronic Systems
Engg.
Indian Institute of Science
Bangalore, India
<EMAIL_ADDRESS>Tapabrata Sen  Dept. of Electronic Systems Engg.
Indian Institute of Science
Bangalore, India
<EMAIL_ADDRESS>T V Prabhakar  Dept. of Electronic Systems Engg.
Indian Institute of Science
Bangalore, India
<EMAIL_ADDRESS>
###### Abstract

Intelligent Electronic Devices (IEDs) are vital components in modern
electrical substations, collectively responsible for monitoring electrical
parameters and performing protective functions. As a result, ensuring the
integrity of IEDs is an essential criteria. While standards like IEC 61850 and
IEC 60870-5-104 establish cyber-security protocols for secure information
exchange in IED-based power systems, the physical integrity of IEDs is often
overlooked, leading to a rise in counterfeit and tainted electronic products.
This paper proposes a physical unclonable function (PUF)-based device (IEDPUF
probe) capable of extracting unique hardware signatures from commercial IEDs.
These signatures can serve as identifiers, facilitating the authentication and
protection of IEDs against counterfeiting. The paper presents the complete
hardware architecture of the IEDPUF probe, along with algorithms for signature
extraction and authentication. The process involves the central computer
system (CCS) initiating IED authentication requests by sending random
challenges to the IEDPUF probe. Based on the challenges, the IEDPUF probe
generates responses, which are then verified by the CCS to authenticate the
IED. Additionally, a two-way authentication technique is employed to ensure
that only verified requests are granted access for signature extraction.
Experimental results confirm the efficacy of the proposed IEDPUF probe. The
results demonstrate its ability to provide real-time responses possessing
randomness while uniquely identifying the IED under investigation. The
proposed IEDPUF probe offers a simple, cost-effective, accurate solution with
minimal storage requirements, enhancing the authenticity and integrity of IEDs
within electrical substations.

###### Index Terms:

hardware security, Physical Unclonable Function (PUF), Intelligent Electronic
Device (IED), power system security, hardware signature, two-way authe

##  I Introduction

In the field of electric power industry, the intelligent electronic device
(IED) serves as an integrated microprocessor-based controller for power system
equipment [1]. IEDs utilise digital controls and includes relays, fault
recorders, circuit breakers, and other components. Consequently, a typical IED
configuration consists of analog & digital inputs from power equipment and
sensors, analog-to-digital (ADC) modules, Digital Signal Processors (DSP),
internal memory, Flex-logic, and a display [1]. These IEDs operate
collaboratively, exchanging data over a network to facilitate data collection
and control actions. However, this interconnectedness also renders them
susceptible to various types of attacks, classified as hardware-related,
firmware-related, software-related, and communication-related vectors [2].
Such attacks can result in the theft of cryptographic keys or introduction of
rogue nodes, and thus compromising the overall security of IED-based power
systems.

PUFs leverage inherent manufacturing variations to create identities that are
extremely difficult to replicate. These identities serve as a foundation for
various applications, such as device identification, generating encryption
keys for data storage and transmission, and ensuring traceability to prevent
the introduction of clones or rogue devices into the network [5]. PUFs can be
employed either as standalone identities or to complement and reinforce the
identities generated through stored identifiers.

In this work, PUFs are utilised to generate identities for commercial IEDs.
The primary contributions of this paper are summarized as in the following.

  * •

The paper proposes an PUF for IED ($\mathrm{IED_{PUF}}$) probe that extracts
hardware signatures in real-time from COTS components and hardware modules of
a commercial IED.

  * •

The proposed $\mathrm{IED_{PUF}}$ probe employs a two-way authentication
protocol with the central computer system in the process of verifying the
authenticity of the IED.

  * •

A simple, efficient algorithm has been proposed to largely reduce storage
overhead present in traditional solutions.

  * •

The extracted signatures from different IEDs possess randomness for random
challenges, but repeatable (for same challenge) and uniquely identifies the
IED.

The features of the proposed $\mathrm{IED_{PUF}}$ probe can be summarized as:
(i) low-cost, portable, accurate solution for authenticating IEDs in real-
time; (ii) offers minimal storage requirement; (iii) the solution exploits the
variations in the different hardware modules of the IEDs; (iv) the solution is
IED device-specific.

This paper is organised as follows: Section III discusses the working
methodology of the proposed $\mathrm{IED_{PUF}}$ probe, Section IV presents
the details of the $\mathrm{IED_{PUF}}$ probe electronics, experimental
results are reported in Section V, and Section VI concludes the paper.

##  II Related Work

To address these challenges, in this work Physically Unclonable Functions
(PUFs) [4] are employed to generate unique digital fingerprints or identifiers
for hardware devices. PUFs can be generated from custom circuits [6, 7], off-
the-shelf components [8, 9], and memories [10]. Key properties of PUFs include
uniqueness, randomness, reliability, and repeatability [4].

Moreover, the risks of counterfeiting and tainting is a serious concern with
all types of embedded electronic devices [3]. These risks encompass the
infiltration of malware and the unauthorised usage of substandard or
counterfeit components. Hence, the irrefutable identity of the IED is at the
heart of securing the IED-based power system automation. Existing solutions
primarily rely on digital codes stored in non-volatile memory, which are
susceptible to identity theft attacks.

While the literature extensively covers the extraction of PUF signatures from
electronic systems, limited research has been conducted on extracting PUF
signatures from commercially available information and communication
technology (ICT) or Internet of Things (IoT) products. [9] proposes a solution
to generate IoT device identifier by extracting PUF signatures from clock
oscillators and ADCs in-built in MCUs. Machine-learning (ML) model has been
employed for creating the device identifiers using extracted PUF signatures.
In similar works in [11, 12], signatures are extracted from sources such as
the current profile of electromagnetic relays and MCU General-Purpose
Input/Output (GPIO) pins. In other works in [13, 14], unique identifiers are
generated for printed circuit boards (PCB) by leveraging variations in surface
mount passive components and wire trace patterns. A arbiter PUF-based hardware
security solution for protecting smart power grids from cyber threats is
proposed in [15]. This solution introduces a new algorithm that utilizes PUF
signatures and timestamps from a GPS clock. These works discuss PUF signature
extraction and its usage in creating identifiers for IoT devices. However, the
scopes for PUF extraction directly from an existing COTS IoT product (such as
a commercial IED) have not been explored largely. Moreover, conventional PUF
solutions typically require significant memory resources to store PUF
challenge-response pairs.

##  III Hardware Architecture of $\mathrm{IED_{PUF}}$ probe

The detailed architecture of the $\mathrm{IED_{PUF}}$ probe is brought out in
this section. First, the different sources for PUF extraction from a
commercial IED (SEL-311C [16]) are illustrated. Following this, the complete
system-level schematic of the $\mathrm{IED_{PUF}}$ probe is presented. It
needs to be clarified here that the proposed $\mathrm{IED_{PUF}}$ probe is
optimized for the IED SEL-311C. IEDs from different manufacturers may require
modification of the $\mathrm{IED_{PUF}}$ probe electronics. However, the
communication protocol between $\mathrm{IED_{PUF}}$ probe and CCS, signature
formation and authentication process does not require any modification. As a
result, developing customized PUF probes for different IED manufacturers can
be considered as a reasonable solution.

###  III-A Measurement Principle for PUF Extraction from Diode Cut-in region,
internal regulated voltages, and time period

A typical IED has several output relay ports, communication modules (include
serial and ethernet), data conversion modules (include ADC and DAC), power
Supply modules (include LDOs, DC-DC converters), current & potential
transformers, GPS, digital & analog ports, etc. Thus, identifying the possible
sources for PUF signature extraction from the SEL-311C IED was carried out at
first. The identified PUF sources are – (i) Cut-in region voltages of the
protective diodes across the output relay ports, (ii) internal regulated
voltages, and (iii) internal clock period.

####  III-A1 Diode Voltages

IEDs utilize relay outputs in power substations for critical functions such as
tripping circuit breakers, activating alarms, controlling substation devices,
enforcing interlocking rules, and enabling emergency shutdowns. On inspection
of the SEL-311C IED, it was found that the output relay ports have mechanical
relays and associated fast recovery protection diodes connected across it. Due
to fabrication process variations, the characteristics of these diodes, such
as voltage-current response, are expected to differ. Table I presents the
recorded voltages obtained by measuring the diode voltages using a
$5\nicefrac{{1}}{{2}}$-digit multimeter. The table shows the variation among
the diodes voltages at the output ports of an IED, with twelve adjacent ports
chosen for this demonstration.

TABLE I: Voltage variations among the output port diodes of an IED

| Output
---
Port No.*
| Diode
---
Voltage (mV)
| Output
---
Port No.
| Diode
---
Voltage (mV)
OUT201 | 500.8 | OUT207 | 514.3
OUT202 | 516.8 | OUT208 | 502.0
OUT203 | 513.4 | OUT209 | 516.1
OUT204 | 514.2 | OUT210 | 517.6
OUT205 | 511.5 | OUT211 | 515.1
OUT206 | 514.1 | OUT212 | 514.4

Notes: * Same as in the SEL-311C IED

Figure 1: Basic schematic for PUF extraction from IED output protection diodes

####  III-A2 Signature Extraction from Diode Cut-in Region

Our approach considers the diode cut-in voltage region and associated
combinations of diode pairs. As mentioned earlier, twelve output relay ports,
and thus, corresponding twelve diodes ($\mathrm{D_{0}}$, $\mathrm{D_{1}}$, …,
$\mathrm{D_{11}}$) were selected for measurement. $\mathrm{MUX_{1}}$ and
$\mathrm{MUX_{2}}$ (${16}\times{1}$ multiplexers) operate as analog
multiplexer/demultiplexer. The diodes were connected to the terminals
$\mathrm{A_{0}}$, $\mathrm{A_{1}}$, …, $\mathrm{A_{11}}$ of $\mathrm{MUX_{1}}$
and $\mathrm{MUX_{2}}$ as in Fig. 1. The terminals $\mathrm{Y_{1}}$ and
$\mathrm{Y_{2}}$ of $\mathrm{MUX_{1}}$ and $\mathrm{MUX_{2}}$ were pulled to
the supply voltage $V_{cc}$ using the resistors $R_{B1}$ and $R_{B2}$. Under
this configuration, when one of the terminals (say, $A_{0}$) of
$\mathrm{MUX_{1}}$ is connected to $\mathrm{Y_{1}}$, (through appropriate
logic levels at the multiplexer selector pins), a finite current (say,
$I_{S}$) flows to forward bias the diode $\mathrm{D_{0}}$. Similarly, using
$\mathrm{MUX_{2}}$, one of the other diodes (between $\mathrm{D_{1}}$ to
$\mathrm{D_{11}}$) can be forward biased. The terminals $\mathrm{Y_{1}}$ and
$\mathrm{Y_{2}}$ were directly connected to a low offset voltage ($<1$ mV)
differential comparator chip (OC) as shown in Fig. 1.

Under the aforementioned setup, the twelve diode voltages were successively
compared to those of the other eleven diodes. As a result, we will get
$N(N-1)$ diode comparisons (where $N=12$ in this case). A 1-bit output will be
produced for every comparison. Let us consider one instance to elaborate this.
The terminals $A_{0}$ of $\mathrm{MUX_{1}}$ and $A_{1}$ of $\mathrm{MUX_{2}}$
were selected for comparing the cut-in region voltages of a diode-pair, say
$\mathrm{D_{0}}$ and $\mathrm{D_{1}}$. Under this setting, the voltages at Y1
and Y2 terminals are, ideally, equal to the voltages (say, $V_{D0}$ and
$V_{D1}$) across $\mathrm{D_{0}}$ and $\mathrm{D_{1}}$. The comparator output
$V_{OC}$ can be expressed as:

${V_{OC}}={1}\,\,{\rm{for}}\,\,{V_{D0}}>{V_{D1}}\,\,\,\,{\rm{and}}\,\,\,\,{V_{OC}}=0\,\,{\rm{for}}\,\,{V_{D0}}\leq{V_{D1}}$

The procedure was repeated and $V_{D0}$ was compared to the diode voltages
$V_{D1}$ to $V_{D_{11}}$ to generate a 11-bit signature. Repeating the above
procedure, each diode was compared with the remaining diodes. Thus,
considering twelve output ports of the IED, ${12}\times{11}$ or 132-bit
signature was formed. The recorded bit-streams (say, $SIG_{1}$ and $SIG_{2}$)
for two such IEDs are shown below. The signatures are expected to be unique to
the individual IEDs under investigation.

$\displaystyle SIG_{1}=000000000000101111111001100010010000101011$
$\displaystyle 010000100000010000101010010000101111010000100000000$
$\displaystyle 000101111110001111111111001111111111101101111110000$
$SIG_{2}=000010100001101011111111100010100001111011\\\
111111000000000000101010111101000010000001101010100\\\
001101010110001101010111001101011111101000010000000$

####  III-A3 IED Regulated Voltages and Internal Oscillator Clock Period

The SEL-311C IED offers a serial port API to extract and display the clock
period (say, $T_{P}$) and internal regulator voltages (say, $V_{RG}$) of the
IED. The IED SEL-311C contains three internal voltage regulators with nominal
voltages of 3.3 V, 5 V, and 15 V. However, actual voltages may exhibit slight
deviations due to fabrication process variations across regulator chips. As a
result, $V_{RG}$ can serve as potential PUF sources for different IEDs.
Furthermore, the time period $T_{P}$ of the internal oscillator within the IED
was extracted through serial communication using appropriate commands. The
nominal value of $T_{P}$ is 20 nS. The deviation of $T_{P}$ is anticipated to
be distinct for each IED, and thus presenting an additional parameter suitable
for PUF generation.

TABLE II: Variations in $V_{RG}$ and $T_{P}$ values in two IEDs | IED
---
No.
| $\bf{V_{RG1}}$
---
= 3.3 V
| $\bf{V_{RG2}}$
---
= 5 V
| $\bf{V_{RG3}}$
---
= 15 V
|  $\bf{T_{P}}$ =
---
20 nS
IED-1 | 3.26 | 4.95 | 14.85 | 19.999945
IED-2 | 3.29 | 4.99 | 14.86 | 20.000063

####  III-A4 Signature Extraction from Regulated Voltages and Clock Period

In order to affirm the uniqueness of the regulated three voltages ($V_{RG1}$,
$V_{RG2}$, and $V_{RG3}$) and $T_{P}$, two SEL-311C IEDs were tested. Table II
shows the results for this comparison. The regulated voltages and $T_{P}$
values were recorded over serial terminal a few hundred times to check the
repeatability, and thus affirming their viability as distinctive
characteristics for PUF-based applications. Table II reveals that the
uniqueness in the regulated voltages and $T_{P}$ values for the two IEDs can
be observed in their deviations (say, $\Delta{V_{RG}}$ and $\Delta{T_{P}}$)
from the respective nominal values. For example, in the case of IED-1,
$\Delta{V_{RG1}}=40$ mV, $\Delta{V_{RG2}}=50$ mV, and $\Delta{V_{RG3}}=150$
mV. On the other hand, for IED-2, the corresponding values for
$\Delta{V_{RG1}}$, $\Delta{V_{RG2}}$, and $\Delta{V_{RG3}}$ are 10 mV, 10 mV,
and 140 mV, respectively. Similarly, $\Delta{T_{P}}$ values for the two IEDs
are measured as 55 femtoseconds (fs) and $-63$ fs, respectively. Signatures
were formed using these parameters by converting the absolute decimal values
of $\Delta{V_{RG1}}$, $\Delta{V_{RG2}}$, $\Delta{V_{RG3}}$, and
$\Delta{T_{P}}$ to corresponding binary (disregarding order information such
as units (e.g., mV, fs) and any trailing zeros in the $\Delta{V_{RG}}$
values). Additionally, an extra bit was added to the left of each binary code
(as the most significant bit (MSB)) to denote polarity, with a 1 indicating a
negative value and 0 representing a positive value. For instance,
$\Delta{T_{P}}$ values of 55 fS and $-63$ fS were transformed into binary as
0110111 and 1111111, respectively. Similarly, the $\Delta{V_{RG}}$ values were
also converted to binary, and finally, all the four parameters were
concatenated in the same order as presented in Table II. The resulting 22-bit
signatures for the two IEDs are illustrated below.

$SIG_{1}=0010000101011110110111$ $SIG_{2}=0000100001011101111111$

###  III-B Working Circuit for $\mathrm{IED_{PUF}}$ probe

Figure 2: System-level schematic of $\mathrm{IED_{PUF}}$ probe

Earlier, in Section III-A2, a basic circuit schematic for extracting
signatures from the twelve output port diodes ($\mathrm{D_{0}}$,
$\mathrm{D_{1}}$, …, $\mathrm{D_{11}}$) of a SEL-311C IED was presented. The
measurement principle was simple. In the working circuit we address issues,
such as high on-resistance (say, $R_{ON}$) of the multiplexer switches, offset
voltage of comparator, mismatches in the resistors $R_{B1}$ and $R_{B2}$,
variation of $R_{ON}$ with power-supply and temperature changes.

The system-level schematic of the working $\mathrm{IED_{PUF}}$ probe is shown
in Fig. 2. It incorporates various electronic hardware modules, including
analog multiplexer/demultiplexer ($\mathrm{MUX_{1}}$ and $\mathrm{MUX_{2}}$),
an ADC, a microcontroller unit (MCU), a constant current source (CS), and a
display unit. Similar to Fig. 1, twelve diodes ($\mathrm{D_{0}}$,
$\mathrm{D_{1}}$, …, $\mathrm{D_{11}}$) are connected to the inputs
($\mathrm{A_{0}}$, $\mathrm{A_{1}}$, …) of $\mathrm{MUX_{1}}$. In this design,
the diodes are forward biased by a constant current (say, $I_{S}$) generated
by the CS. The CS unit utilizes a precision reference voltage and a PNP
transistor-based configuration [17]. As shown in Fig. 2, $I_{S}$ flows from
the $\mathrm{Y_{1}}$ terminal of $\mathrm{MUX_{1}}$ to the terminals
$\mathrm{A_{0}}$, $\mathrm{A_{1}}$ through $\mathrm{A_{11}}$, sequentially.
The selection of $\mathrm{MUX_{1}}$ channels is controlled by applying
appropriate logic levels to the selector pins $\mathrm{S_{0}}$ to
$\mathrm{S_{3}}$.

The voltage (say, $V_{O1}$) at the $\mathrm{Y_{1}}$ terminal of
$\mathrm{MUX_{1}}$ is related to the voltages across the diodes. However,
$V_{O1}$ also contains a component related with the voltage drop ($V_{sw}$)
across the internal resistance ($R_{ON}$) of $\mathrm{MUX_{1}}$ caused by the
current $I_{S}$ flowing through $\mathrm{MUX_{1}}$. The $V_{sw}$ component is
significantly high and depends on temperature and power supply variations. To
address this issue, $\mathrm{MUX_{2}}$ has been introduced. The selector pins
of $\mathrm{MUX_{1}}$ and $\mathrm{MUX_{2}}$ are tied together, as in Fig. 2,
ensuring the selection of the same channels in both $\mathrm{MUX_{1}}$ and
$\mathrm{MUX_{2}}$ during channel sweeping. The terminal $\mathrm{Y_{2}}$ of
$\mathrm{MUX_{2}}$ is connected to an op-amp (OP)-based voltage follower
circuit. By leveraging the low bias current of the op-amp, the effect of
$R_{ON}$ is compensated.

The output of the op-amp is then passed through a simple second-order low-pass
filter before being fed into a high-resolution ADC. The cutoff frequency of
the filter is set at approximately 15 Hz. From Table I, it can be observed
that the differences among the diode voltages can be of the order of 1 mV or
even lower. As a result, selection of a suitable ADC is crucial for accurately
resolving these voltages. Moreover, the measured diode voltages are static in
nature. Considering these, a DC optimized Delta-Sigma ($\Delta$-$\Sigma$) ADC
is selected as will be detailed in Section V-A.

As mentioned in Section III-A3, the regulated voltages and $T_{P}$ parameters
of the IED were acquired through serial terminal. The deployed MCU performs
this serial communication operation with the IED and is also responsible for
controlling other operations of the $\mathrm{IED_{PUF}}$ probe, such as
applying appropriate logic levels to the multiplexer selector pins, managing
the ADC & the display modules, implementing algorithms for signature
extraction, and transmission operations.

Figure 3: Complete flow-chart showcasing the IED authentication mechanism
performed by the CCS and the $\mathrm{IED_{PUF}}$ probe

##  IV Working Principle of $\mathrm{IED_{PUF}}$ probe

Fig. 3 depicts the authentication process for $\mathrm{IED_{PUF}}$ probe, as
well as, the IED device. The signature extraction process involves a series of
sequences executed when the CCS requests for IED signature extraction. The
following steps outline this procedure:

  1. 1.

The CCS initiates communication by pinging the $\mathrm{IED_{PUF}}$ probe
through the serial terminal.

  2. 2.

The $\mathrm{IED_{PUF}}$ probe and CCS execute Phase I, which involves
verifying the authentication of the IED access request originating from the
CCS, as well as, authenticating the $\mathrm{IED_{PUF}}$ probe.

  3. 3.

Upon successful authentication in Phase I, the CCS proceeds to Phase II by
transmitting random port numbers (corresponding to the twelve output port
under investigation) as challenges to the $\mathrm{IED_{PUF}}$ probe.

  4. 4.

The $\mathrm{IED_{PUF}}$ probe generates a response to the challenges
presented by the CCS in Phase II. This response is then transmitted back to
the CCS, where it undergoes further verification processes to authenticate the
IED.

Phase I performs mutual authentication between the CCS and the
$\mathrm{IED_{PUF}}$ probe. To accomplish this, we extract ADC PUF (ADCMCU)
hardware signature using the procedure elaborated in [9]. Using this
procedure, we estimate the mean ($\mu$) and standard deviation ($\sigma$) of
the 12-bit ADC present in the MCU. Phase II focuses on implementing a
challenge-response-based mechanism to authenticate the IED on the CCS side.
These two phases will be further elaborated in the subsequent subsections.

###  IV-A Phase I - Authenticating CCS

The Phase I starts with an initial authentication request issued by the CCS
and ends with an authentication acknowledgement. Upon receiving the
authentication request, the $\mathrm{IED_{PUF}}$ probe sends three parameters
to the CCS: a randomly generated number $N_{k}$, $\mu$, and $\sigma$. These
two ADC parameters are obtained from the ADCMCU PUF. The CCS compares these
values with previously stored references. If the comparison yields a match,
the authenticity of the $\mathrm{IED_{PUF}}$ probe is validated. Following
this stage, the CCS transmits a hash value $H_{k}$, generated using a MD5 hash
function and $N_{k}$ as an input. The $\mathrm{IED_{PUF}}$ probe also
generates its hash response $H_{k}^{\prime}$ to the same input $N_{k}$.
$H_{k}$ and $H_{k}^{\prime}$ are compared for a match to authenticate the CCS
access request. Conversely, if $H_{k}$ and $H_{k}^{\prime}$ do not match, the
Phase I is deemed unsuccessful, and access is denied. The aforementioned
sequences are illustrated under Phase I in Fig. 3.

Figs. LABEL:ADC1 and LABEL:ADC2 show that the histogram of ADC output values
for two identical MCU devices. The measurements were taken over 10,000 samples
in differential mode. $\mu$ and $\sigma$ values, indicated in the figures,
demonstrate uniqueness for the two MCU devices.

(a)

(b)

Figure 4: Histograms of ADC output values for two identical MCUs acquired in
differential mode .

###  IV-B Phase II - Authenticating IED

Upon successful completion of Phase I, the CCS proceeds with the
authentication of the IED as shown under Phase II of Fig. 3. As mentioned
previously, the CCS securely stores reference signatures ($SIG_{R}$) of all
IEDs in its database. For the authentication process, the CCS transmits a
random challenge ($C_{k}$) to the $\mathrm{IED_{PUF}}$ probe, consisting of
random port numbers (say, $N_{i}$ where $N\in[1,12]$ for $i=1,2,...12$). The
different $N_{i}$ values corresponds to a port number, between Port 1 to Port
12. The number of ports challenged in each $C_{k}$ will vary randomly, such as
challenging eight ports in one instance and all twelve ports in another. After
issuing the challenge, the CCS will generate an anticipated response
($R_{k}^{\prime}$) from its database of reference signatures, which includes
the following relevant data of the corresponding IED device: (i) clock period
($T_{P}$), (ii) three regulated voltages ($V_{RG1}$, $V_{RG2}$, and
$V_{RG3}$), and (iii) a partial bit-stream, formed by utilizing the known
$C_{k}$ and the reference $SIG_{R}$. Upon receiving $C_{k}$, the
$\mathrm{IED_{PUF}}$ probe will retrieve the signatures from the IED.
Subsequently, it will generate a bit-stream specific to the challenged ports
and combine it with the $T_{P}$ and $V_{RG}$ signatures, forming the response
$R_{k}$ which is transmitted back to the CCS. The CCS compares $R_{k}$ with
$R_{k}^{\prime}$ to authenticate the IED.

Figure 5: Experimental Setup

##  V Experimental Evaluation

###  V-A Experimental Setup

Fig. 5 shows the complete experimental setup employed for the characterization
and authentication of an SEL-311C IED using the proposed $\mathrm{IED_{PUF}}$
probe. As previously mentioned, twelve output ports of the IED are chosen for
signature extraction, utilizing the protection diodes and a dedicated PCB
strip facilitates this process. To establish the connection between the
$\mathrm{IED_{PUF}}$ probe and the IED, a flat-ribbon cable and the
aforementioned PCB strip are employed. The MCU module is implemented using an
NRF52840-based microcontroller unit. $\mathrm{MUX_{1}}$ and $\mathrm{MUX_{2}}$
are designed using CD4067-based analog multiplexers. Furthermore, the ADC
module has been implemented utilizing the ADS1115 16-bit $\Delta$-$\Sigma$
converter. The serial communication between the $\mathrm{IED_{PUF}}$ probe and
the IEDs are realized through an RS232 to TTL serial interface module. The CCS
is implemented on a laptop computer, and the algorithms on the CCS side are
coded in Python.

###  V-B Experimental Results

The experiments were conducted with two commercial SEL-311C IEDs, as
previously mentioned. Preliminary results for these IEDs are illustrated in
Fig. 6. These figures display the diode voltages obtained from continuous
acquisition of 150 samples at a constant current of ${1}$ mA. The twelve diode
voltages of IED-1, shown in Fig. LABEL:IED1basic, exhibit variations within
the range 495 mV to 513 mV. On the other hand, IED-2 demonstrates diode
voltage variations ranging from 495 mV to 520 mV. It can be observed that in
Fig. LABEL:IED1basic, 11 of the 12 line-plots are distinctly visible, while in
Fig. LABEL:IED2basic, 10 lines are distinct. This indicates the presence of
collisions in very few of the diode voltages for both IEDs. Moreover, the
horizontal characteristics of the line-plots affirms excellent repeatability
in the measurements.

Fig. 7 further clarifies the diode signature patterns for the two IEDs. The
results in Fig. 7 were obtained by monitoring the diode voltages over a span
of two weeks. During this experiment, the power supply of the IEDs was varied
over 70 V to 230 V to study the robustness of the signatures. Fig.
LABEL:IED1voltage and LABEL:IED2voltage present the worst-case variations
observed in the diode voltages for the two IEDs. It is evident from these
plots that the characteristics of the two IEDs exhibit distinctive patterns,
signifying their uniqueness.

In order to examine the robustness performance of the $\mathrm{IED_{PUF}}$,
the following common metrics [13] of PUF signatures are assessed. These
parameters are evaluated using the full 154-bit PUF signature derived from the
datasets of Fig. 7.

(a)

(b)

Figure 6: Preliminary results showing the diode voltages plotted over 150
sample points. (a) response for IED-1, (b) response for IED-2.The results
demonstrated repeatability and uniqueness in the measurement.

(a)

(b)

Figure 7: Voltage characteristics of the IED output port protection diodes,
taken over two weeks under varying IED supply voltage. (a) response for IED-1,
(b) response for IED-2.

  1. 1.

Uniqueness: This parameter is determined by assessing the inter-device
variation. This involves performing an XOR operation on the bit-strings
obtained from two separate IEDs, summing the result, and then the sum is
divided by the length of the bit-strings. The desired value for inter-device
variation is 0.5. The worst-case values of uniqueness between IED-1 and IED-2
were evaluated to be approximately 0.31.

  2. 2.

Stability: Intra-device variation quantifies this parameter. To evaluate
stability XOR operation is performed on two bit-strings measured from a
particular IED, the result is summed and the sum is divided by the length of
the bit-string. Ideally, the intra-device variation is expected to be zero.
The worst-case values of stability for IED-1 and IED-2 were found to be 0.09
and 0.06, respectively.

  3. 3.

Bias: Bias is calculated by dividing the sum of the bit-string by the length
of the bit-string. The desired bias value is 0.5. The bias for the signatures
of IED-1 and IED-2 were determined to be 0.51 and 0.52, respectively.

TABLE III: Occurrence of the twelve diodes in random sequence as challenge for
PUF response generation

| S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | S9 | S10 | S11 | S12
---|---|---|---|---|---|---|---|---|---|---|---|---
D0 | 843 | 825 | 830 | 828 | 844 | 820 | 859 | 798 | 830 | 864 | 817 | 842
D1 | 800 | 843 | 835 | 861 | 836 | 861 | 830 | 841 | 865 | 826 | 806 | 796
D2 | 824 | 801 | 864 | 873 | 772 | 816 | 880 | 814 | 818 | 848 | 836 | 854
D3 | 836 | 847 | 794 | 855 | 793 | 783 | 886 | 853 | 836 | 830 | 798 | 889
D4 | 868 | 810 | 823 | 820 | 839 | 859 | 785 | 863 | 817 | 800 | 850 | 866
D5 | 828 | 821 | 849 | 843 | 859 | 844 | 825 | 848 | 812 | 822 | 832 | 817
D6 | 854 | 851 | 831 | 788 | 842 | 795 | 824 | 847 | 824 | 859 | 857 | 828
D7 | 851 | 836 | 827 | 811 | 887 | 848 | 817 | 848 | 788 | 840 | 826 | 821
D8 | 794 | 851 | 855 | 836 | 823 | 854 | 784 | 831 | 869 | 814 | 853 | 836
D9 | 811 | 902 | 795 | 835 | 823 | 853 | 852 | 823 | 845 | 804 | 824 | 833
D10 | 851 | 769 | 870 | 836 | 863 | 812 | 837 | 834 | 788 | 854 | 872 | 814
D11 | 840 | 844 | 827 | 814 | 819 | 855 | 821 | 800 | 908 | 839 | 829 | 804

In addition to these parameters, the randomness of the signatures can be
evaluated by measuring the entropy, which can be estimated from the data in
Table III. As described in Section IV-B, CCS challenges the
$\mathrm{IED_{PUF}}$ probe with a sequence of twelve random port numbers
denoted as S1, S2, …, S12 in Table III. About 10,000 sequences were generated
to evaluate the randomness. In the table, the first row labeled D0 represents
the number of occurrences of the diode D0 in the sequence positions S1, S2, …,
S12 across the challenges. Similarly, the rows labeled D1, D2, and so on,
represent the occurrences of diodes D1, D2, and subsequent ones. The entropy
(say, $H_{k}$) of the sequence at the $k$-th position can be calculated using
the formula: $H_{k}=-\Sigma{P(D_{i})}\times{\log_{2}{P(D_{i})}}$, where
$P(D_{i})$ is the probability of occurrence of the $i$-th diode appearing in
$S_{k}$. The maximum entropy ($H_{max}$) for any $S_{k}$ occurs when
$P(D_{0})=P(D_{1})=...P(D_{11})$, resulting in $H_{max}=3.585$. On evaluation
of the entropies for S1, S2, …, S12 from Table III, all entropy values were
approximately equal to $H_{max}$, with an error of less than $0.03\%$.

##  VI Conclusion

This paper introduces a hardware-level security solution specifically designed
for commercial IEDs. The solution incorporates (PUF)-based techniques to
extract unique signatures from the IEDs. The primary objective of this study
is to enhance the security of IEDs, mitigating the risks associated with
counterfeiting. In this work, the $\mathrm{IED_{PUF}}$ probe has been
presented as a complete solution, encompassing both its hardware architecture
and software development. The proposed $\mathrm{IED_{PUF}}$ probe is a simple,
low-cost embedded device that can be easily customized to accommodate various
IED models. To validate the effectiveness of the proposed $\mathrm{IED_{PUF}}$
probe, extensive experimental evaluations have been conducted, yielding
promising results. Additionally, the experimental results highlight the scopes
for further PUF hardening against external variations like power supply and
aging. As part of our future work, we intend to focus on addressing these
challenges and exploring the extraction of signatures from IEDs of different
manufacturers.

## References

  * [1] S. Hussain, J. H. Fernandez, A. K. Al-Ali and A. K. Shikfa, “Vulnerabilities and Countermeasures in Electrical Substations,” in Int. J. of Critical Infrastructure Protection. 33, 2021.
  * [2] J. Wang and D. Shi, “Cyber-Attacks Related to Intelligent Electronic Devices and Their Countermeasures: A Review,” Int. Univ. Power Engg. Conf. (UPEC), Glasgow, UK, 2018, pp. 1-6.
  * [3] The Open Group. “ISO/IEC 20243-1:2018” iso.org. https://www.iso.org/standard/74399.html (accessed May 22, 2023).
  * [4] S. Joshi, S. P. Mohanty and E. Kougianos, “Everything You Wanted to Know About PUFs,” in IEEE Potentials, vol. 36, no. 6, pp. 38–46, Nov.-Dec. 2017.
  * [5] J. R. Hamlet et al. “Deterrence of device counterfeiting, cloning, and subversion by substitution using hardware fingerprinting,” US 8,848,905, Sept. 30, 2014, https://www.osti.gov/biblio/1159918, Accessed on May 22, 2023. [Online].
  * [6] J. W. Lee, et al., “A technique to build a secret key in integrated circuits for identification and authentication applications,” Symp. on VLSI Circuits. Digest of Technical Papers, Honolulu, USA, 2004, pp. 176–179.
  * [7] G. E. Suh and S. Devadas, “Physical Unclonable Functions for Device Authentication and Secret Key Generation,” ACM/IEEE Design Automation Conf., San Diego, CA, USA, 2007, pp. 9–14.
  * [8] A. Duncan, L. Jiang and M. Swany, “Repurposing SoC analog circuitry for additional COTS hardware security,” IEEE Int. Symp. on Hardware Oriented Security and Trust (HOST), Washington, DC, USA, 2018, pp. 201–204.
  * [9] G. Vaidya, A. Nambi, T. V. Prabhakar, V. Kumar T and S. Sudhakara, “IoT-ID: A Novel Device-Specific Identifier Based on Unique Hardware Fingerprints,” IEEE/ACM 5th Int. Conf. on IoT Design and Implementation (IoTDI), Sydney, NSW, Australia, 2020, pp. 189-202.
  * [10] D. Holcomb, W. Burleson and K. Fu, (2007). “Initial SRAM State as a Fingerprint and Source of True Random Numbers for RFID Tags,” Proc. Conf. RFID Secur., vol. 7, pp. 1-12, Jan. 2007.
  * [11] G. Vaidya and T. V. Prabhakar, “Hardware based identification for Intelligent Electronic Devices,” IEEE/ACM 7th Int. Conf. on IoT Design and Implementation (IoTDI), Milano, Italy, 2022, pp. 82-94.
  * [12] G. Vaidya, T. V. Prabhakar and L. Manjunath, “GPIO PUF For IoT Devices,” IEEE Global Comm. Conf., Taipei, Taiwan, 2020, pp. 1-6.
  * [13] J. R. Hamlet, M. T. Martin and N. J. Edwards, “Unique signatures from printed circuit board design patterns and surface mount passives,” Int. Carnahan Conf. on Security Tech. (ICCST), Madrid, Spain, 2017, pp. 1-6.
  * [14] N. J. Edwards et al. “Authenticating a Printed Circuit Board,” US 10,594,492, Jun 16, 2017, https://www.osti.gov/biblio/1637851, Accessed on May 22, 2023. [Online].
  * [15] M. Ebrahimabadi, M. Younis and N. Karimi, ”Hardware Assisted Smart Grid Authentication,” ICC 2021 - IEEE International Conference on Communications, Montreal, QC, Canada, 2021, pp. 1-6.
  * [16] Schweitzer Engineering Laboratories. “SEL-311C Protection and Automation System.” selinc.com. https://selinc.com/api/download/3032 (accessed May 22, 2023).
  * [17] Texas Instruments, “LM185/LM285/LM385 Adjustable Micropower Voltage References,” LM385 datasheet, Feb. 2000 [Revised April. 2013].


Copyright for this paper by its authors. Permitted under Creative Commons
License Attribution 4.0 International (CC BY 4.0).

IberLEF 2023, September 2023, Jaén, Spain

<EMAIL_ADDRESS>] [1] [1]

<EMAIL_ADDRESS>] [2]

<EMAIL_ADDRESS>] [3]

<EMAIL_ADDRESS>] [4]

[1]Corresponding author.

# Experimenting with UD Adaptation of an Unsupervised Rule-based Approach for
Sentiment Analysis of Mexican Tourist Texts

Olga Kellert  Universidade da Coruña, Grupo LyS, CITIC, Depto. de Ciencias de
la Computación y Tecnologías de la Información, Campus de Elviña s/n, 15071 A
Coruña, Spain  Mahmud Uz Zaman  University of Göttingen, Seminar für
Romanische Philologie, Humboldtallee 19, 37073 Göttingen, Germany  Nicholas
Hill Matlis  Center for Free-Electron Laser Science CFEL, Deutsches
Elektronen-Synchrotron DESY, Germany  Carlos Gómez-Rodríguez  Universidade da
Coruña, Grupo LyS, CITIC, Depto. de Ciencias de la Computación y Tecnologías
de la Información, Campus de Elviña s/n, 15071 A Coruña, Spain

(2023)

###### Abstract

This paper summarizes the results of experimenting with Universal Dependencies
(UD) adaptation of an Unsupervised, Compositional and Recursive (UCR) rule-
based approach for Sentiment Analysis (SA) submitted to the Shared Task at
Rest-Mex 2023 (Team Olga/LyS-SALSA) (within the IberLEF 2023 conference). By
using basic syntactic rules such as rules of modification and negation applied
on words from sentiment dictionaries, our approach exploits some advantages of
an unsupervised method for SA: (1) interpretability and explainability of SA,
(2) robustness across datasets, languages and domains and (3) usability by
non-experts in NLP. We compare our approach with other unsupervised approaches
of SA that in contrast to our UCR rule-based approach use simple heuristic
rules to deal with negation and modification. Our results show a considerable
improvement over these approaches. We discuss future improvements of our
results by using modality features as another shifting rule of polarity and
word disambiguation techniques to identify the right sentiment words.

###### keywords:

Sentiment Analysis Unsupervised Rule-based Sentiment dictionary

##  1 Introduction

The intensity of a sentiment expressed in words, sentences and paragraphs
strongly depends on the syntactic context in which sentiment words like nice
appear. For instance, this hotel is very nice expresses a stronger positive
sentiment due to the intensifier very than just the statement this hotel is
nice and the use of negation can reverse the polarity of the sentiment as in
this hotel is not nice. Modification of sentiment words by intensifiers like
very and negation are among the basic syntactic rules influencing the semantic
interpretation of sentiment words. Our main contribution in this article is a)
to exploit an unsupervised (knowledge-based) model for compositional and
recursive sentiment analysis (SA) driven by basic syntactic rules (Vilares et
al., 2017 [1]) and to adapt it to the formalism of Universal Dependencies (UD)
which is a universal framework for annotation of grammar across different
human languages [2], b) to test our adaptation on the dataset provided by the
Shared Task Rest-Mex 2023 organizers [3] and finally c) to compare the results
of our unsupervised approach with other unsupervised methods that use
heuristic rules to address modification and negation (Hutto and Gilbert, 2014
[4]) as well as other teams that participated at the Shared Task Rest-Mex
2023.

The remainder of this article is structured as follows. §2 reviews related
work. §3 introduces the adapted formalism for syntactic operations. §4
presents experimental results of the Shared Task participation and compares
the results with other unsupervised approaches that use heuristic rules.
Finally, §5 concludes and discusses directions for future work.

##  2 Related work

The most widely used approaches to perform sentiment analysis (SA) include
Machine Learning/Deep Learning based methods, lexicon-based methods and hybrid
methods.

###  2.1 Machine Learning/Deep Learning methods

Supervised approaches using machine learning, deep learning and pre-trained
models like BERT and RoBERTa are a common practice in SA [5], [6], [7], [8],
[9], [10], [11]. In machine learning and deep learning-based approaches, the
dataset is separated into training and testing datasets. A training dataset is
used during the training process to learn correlations between the specific
input text and the sentiment polarity. The testing dataset is then used to
predict sentiment polarity on the basis of learned associations during the
training period. The performance of these approaches is known to be relatively
high if the learning and prediction tasks are performed on a similar dataset
or corpus, as in the case of the present Shared Task of the Rest-Mex 2023 [3].
The downside of these approaches is that they require a huge amount of data
for learning and prediction, which makes them sub-optimal for the use in real
life situations where huge amounts of data are often missing or users do not
have enough expertise in training and using these models. In addition, the
learned associations between input and output are often obscure to be easily
understood or explained.

###  2.2 Lexicon-based approaches

The lexicon-based methodology makes use of a sentiment dictionary that
contains sentiment words with corresponding polarity scores in order to find
out the overall opinion or polarity of a sentence or text [12, 4, 1, 13].
These approaches fall into various branches depending on how they deal with
syntactic rules that can shift or intensify the polarity. Non-compositional
and non-recursive rule based approaches such as Vader [4] use heuristic rules
to account for polarity changes due to negation, modification or other
syntactic processes. Other unsupervised approaches use a more general
architecture to account for SA by exploiting general syntactic rules that
influence sentiment polarity [1]. Lexicon-based methods are considered to be
simple to use and cost effective as there is no need to train huge amounts of
data. However, they must deal with syntactic rules that influence the polarity
of sentiment words like negation and modification. We briefly describe here
two unsupervised methods that deal with syntactic rules in a completely
different way.

####  2.2.1 Non-compositional Rule Based Approach Vader

Vader is a rule-based model for SA which is considered one of the best
sentiment classifiers of its kind (Mello et al., 2022 [14]). It is relatively
easy to implement and does not require a large number of computational
resources. Therefore, it is computationally efficient and is suitable for
large-scale applications and real-time analysis. The creators of the Vader
sentiment analysis system asked a number of human raters to provide sentiment
scores for the sentiment words enlisted in the sentiment dictionary. The human
ratings were then averaged for each word with the aim of creating a robust
sentiment dictionary that is based on the opinions of many human raters. Vader
was designed to handle punctuation, capitalization, emoticons, acronyms, and
slang [4]. For instance, capitalization of a sentiment word like NICE instead
of nice is used as an intensifier of the word being capitalized. To account
for modification or negation of sentiment words, Vader uses the distance
between the sentiment word and the modifier or negation. Farther modifying
words or negation words have a relatively smaller effect on the sentiment word
than words in close proximity.

Vader was primarily designed for English text analysis, but it also offers a
multilingual sentiment analysis via translation [4]. Vader gives a probability
measure between 0 and 1 (1=highest probability) for the positive, negative,
neutral and compound or mixed sentiment of the input text as can be seen from
the following examples in English and Spanish:

  * •

`English sentence` : "VADER is VERY SMART, handsome, and FUNNY!!!"

  * •

`score output for English sentence` : ’neg’: 0.0, ’neu’: 0.233, ’pos’: 0.767,
’compound’: 0.9342

  * •

`Spanish sentence` : ¡¡¡VADER es MUY INTELIGENTE, guapo y DIVERTIDO!!!

  * •

`score output for Spanish sentence` : ’neg’: 0.0, ’neu’: 0.27, ’pos’: 0.73,
’compound’: 0.9387

The performance of multilingual Vader was tested on a multilingual corpus
including English and Portuguese texts, which has shown better results for
English than for Portuguese SA [14].

####  2.2.2 Unsupervised, Compositional and Recursive rule-based approach

Vilares et al., 2017 [1] use the first unsupervised compositional and
recursive rule-based approach for SA. Its main concept is introduced
informally here. We refer the reader to the details and formalism in the paper
[1].

In a nutshell, this approach exploits dependency relations between words in a
sentence to deal with the scope of negation, modification and other syntactic
processes that can shift, strengthen or weaken the polarity of sentiment
words. In this approach, the first task is to search for sentiment words taken
from a sentiment dictionary in the input text such as the sentiment word
handsome in the sentence in Figure 1 and then to traverse the dependency tree
and to check whether negation words or modifiers change the polarity of
sentiment words.

Figure 1:  A simplified version of a fragment of a dependency tree from
Vilares et al., 2017

The system uses a set of compositional operations to propagate changes to the
semantic orientations of the nodes in the tree in a particular order. The
order is basically scope driven. First, changes to polarity due to
intensification apply and only after, changes to polarity due to negation
apply. As a consequence, negation has scope over an intensified sentiment word
as is also reflected by the hierarchical structure in Figure 1. The node of
the negation word is higher than the node of the intensifier. Once all
relevant operations have been executed, the processed sentiment score of the
sentence is stored at the root node, which is not represented for simplicity
in Figure 1.

##  3 Our Experimentation with UD Adaptation of an Unsupervised Rule-based
Approach

We experimented with an adaptation of an unsupervised compositional and
recursive approach in SA (Vilares et al., 2017 [1] ) to the Universal
Dependencies (UD) formalism [2], as it has since become the de facto standard
for multilingual dependency parsing (the approach in [1] used Universal
Treebanks instead, which was the latest precursor of UD available at that
time). Figure 2 shows a dependency structure for an English sentence and a
CoNLL-U Format which represents word lines containing the annotation of a
word/token with respect to various linguistic properties such as part of
speech (POS), lemma, dependency relation of the word to its head,
morphological features, etc. The dependency structure and linguistic
properties of word/tokens as in CoNLL-U Format are an integral part of UD.

Figure 2: UD formalism.
(http://universaldependencies.org/eacl17tutorial/infrastructure.pdf).

For our experimentation of an unsupervised approach to UD formalism, we used
Stanza, which is a natural language toolkit based on UD-formalism that
provides a basic analysis of the input text such as lemmatization, part-of-
speech (POS) and dependency parsing (Peng Qi et al., 2020 ([15]). The
dependency parser is based on UD parser from Qi et al. 2018 ([16]. For
simplicity, we do not represent all features associated with each word and
focus only on those features that are relevant for SA. As we experimented with
Mexican Spanish reviews from the Shared Task of Rest-Mex 2023 for our
adaptation, our examples are taken from this dataset [3]. We did very little
preprocessing of the dataset (conversion of all the uppercase letters into
lowercase letters) for lemmatization and parsing reasons. Let’s consider a
Spanish example No es excelente ‘It is not excellent’ and the associated
dictionary entries with token ids, text, lemma, POS (‘upos’), morphological
features (‘feats’), head ids and dependency relations (‘deprel’):

  * •

`first word` : ‘id’: 1, ‘text’: ‘no’, ‘lemma’: ‘no’, ‘upos’: ‘ADV’, ‘feats’:
‘Polarity=Neg’, ‘head’: 3, ‘deprel’: ‘advmod’

  * •

`second word` : ‘id’: 2, ‘text’: ‘es’, ‘lemma’: ‘ser’, ‘upos’: ‘AUX’, ‘feats’:
‘feats’: ‘Mood=Ind|…’, ‘head’: 3, ‘deprel’: ‘cop’

  * •

`third word` : ‘id’: 3, ‘text’: ‘excelente’, ‘lemma’: ‘excelente’, ‘upos’:
‘ADJ’, ‘feats’: ‘Number=Sing’, ‘head’: 0, ‘deprel’: ‘root’

Head ids and dependency relations play an important role in our approach as
they provide information about the syntactic relation of words and the
hierarchical structure of the sentence. Head ids contain information about
parent-child relations. Take for instance, the negation word no and the
copular word es in the previous example, which have excelente as their head.
This means that the word excelente is the highest node and the children no and
es are the lowest nodes in the structure. This head-child relation can be used
to define the scope of negation. If the negation is a child of a sentiment
word as its head, the polarity of the sentiment word needs to be shifted.

In order to be able to calculate the polarity score of a sentence, we
performed several steps that can be described in a nutshell as follows:

  * •

`Step 1` : Find sentiment words in the input text and assign polarity scores
to the sentiment words

  * •

`Step 2` : Create a dictionary of head ids and their correspondent children
ids

  * •

`Step 3` : Identify target words that influence the sentiment word such as
negation

  * •

`Step 4` : Calculate the polarity score for the input sentence

Let us illustrate these steps by looking at the given Spanish example. First,
we identify the sentiment word excelente in the input text and add new entries
to the dictionary associated with this word, namely the elementType: ‘count’
and the polarity score or ‘elementScore’: 5. We use the dictionaries by SO-CAL
for Spanish ([12], [1]), in which the polarity score for sentiment words
ranges from -5 (the most negative) to +5 (the most positive).

  * •

`Sentence` : No es excelente ‘It’s not excellent’

  * •

`Step 1` : label sentiment words

  * •

`dictionary of the sentiment word` : ‘id’: 3, ‘text’: ‘excelente’, ‘lemma’:
‘excelente’, ‘upos’: ‘ADJ’, ‘feats’: ‘Number=Sing’, ‘head’: 0, ‘deprel’:
‘root’, ‘elementType’: ‘count’, ‘elementScore’: 5

Step 2 consists of creating a dictionary with head ids as keys and a list of
children as a key value in order to find potential polarity shifters or target
words such as negation and modification. Each key-value pair of this
dictionary represents a head-child tree branch as represented in Figure 3.

Figure 3: Example of a head-child tree branch

In the UD-formalism, the head id 0 and its child represent the highest tree
branch and the child of the head id 0 and its children represent the second
highest branch. In our example, the second highest branch is also the lowest
branch:

  * •

`Sentence` : No es excelente

  * •

`Step 2` : Create a dictionary with heads as keys and their correspondent
children as values

  * •

`head-child-dictionary` : 3: [1, 2], 0: [3]

Head-child branches represent an important unit in linguistics and NLP. In
linguistics, head-child branches are better known under the terms phrases or
maximal projections [17], [18] and they are used to describe syntactic
properties or rules. In NLP, head-child branches have been used to define the
domain for Machine Translation, for example [19]. We use head-child branches
for SA and more precisely to identify target words that can shift, weaken or
strengthen the polarity of sentiment words.

Step 3 consists of identifying target words that can modify the sentiment word
identified in step 1. In order to achieve this goal, we loop through branches
upwards and check if we can find the sentiment word, negation and/or
modification in the same branch. For this, we calculate the order of branches
from the lowest to the highest branch associated with a sentence. In the given
sentence example no es excelente, the sentiment word and negation are in the
same branch.

Step 4 consists of calculating the polarity score for each branch upwards by
applying the formula for the calculation of the polarity score in (1) from
Vilares et al. 2017 [1], where the variable a equals the elementScore of a
sentiment word such as excelente, the variable b equals a value that depends
on the strength of the intensifier such as muy taken from a list of
intensifiers and negation has a score of -4 or +4 depending on the positive or
negative value of a:

  * •

`Step 4` : Calculate the polarity score for the branch 3: [1, 2]

$\ a*(1+b)+(sign(a)*-4)=polarityscore$ (1)

According to the formula in (1), the polarity score for the lowest branch
3:[1, 2] equals 1, if we calculate 5*(1+0)-4. As the highest branch simply
expresses an identity relation between the root and the head of the previous
branch, the polarity score remains the same, namely 1, and the calculation
finishes with the highest branch. We take the polarity score of the highest
branch to be the final result for the polarity calculation.

We now discuss an example in Figure 4 with more branches.

Figure 4: Example with several branches

We distinguish between qualitative and quantitative modifiers. Quantitative
modifiers like big as in big problem act like intensifiers as they intensify
the sentiment word problem, similar to very. In our approach, quantitative
modifiers can never be sentiment words and their only function is to
contribute the value b in the formula (1). Qualitative adjectives like good,
however, describe the quality of the referent expressed by the noun, they are
not quantifying and they contribute the value a in the formula (1).

Turning to our example in Figure 4, we first compute the intensification of
the qualitative adjective buena ‘good’ by the intensifier muy ‘very’. We
follow the idea of assigning intensifiers like muy a score of 0.25 [1] . The
result for this calculation is 2*(1+0.25)=2.3. We assign the score 2.3 to the
nominal head comida ‘food’ as the result of the nominal modification.
Collecting information from the lowest branch and bringing it up to the
highest branch (e.g. nominal phrase) is a common step in formal grammars such
as Head-driven Phrase Structure Grammar (HPSG) [17] or Minimalist Grammar
([18]). As the negation is a child of the nominal head with a polarity score
2.3, the negation has scope over the nominal head. As a result, we subtract 4
from the polarity score 2.3 of the nominal head. The output of this
calculation is -1.7.

The calculation finishes with the highest branch, which expresses an identity
relation between the root and its child. The calculation steps are summarized
as follows:

  * •

`Sentence` : No es una comida muy buena ‘It’s not a very good food’

  * •

`polarity score of the lowest branch ` : 2 * (1 + 0.25) = 2.3

  * •

`polarity score of the higher branch ` : 2.3 -4 = -1.7

  * •

`polarity score of the highest branch ` : -1.7 (final polarity score)

So far we only considered short single sentences with only one sentiment word.
If the input text represents a longer sentence or several sentences with more
than one sentiment word as in the case of reviews at the Shared Task Rest-Mex
2023, the polarity score needs to be calculated for the whole review text. One
possibility is to calculate the mean of all sentence scores of a review
(metrics a). Another option is to provide more weight to "relevant" sentences
such as the last sentence of a review under the assumption that humans often
say the most relevant things at the end of a review (metrics b). The third
option is to consider only extreme positive or negative values (metrics c)
under the assumption that humans pay more attention to extreme sentiments in a
review. We illustrate the differences between the metrics by a review example
and correspondent sentence scores:

  * •

`I did not like this hotel.` -1

  * •

`The room was ok.` 2

  * •

`The breakfast was mediocre.` -1

  * •

`The service was not so great.` 1

  * •

`In sum, not recommendable!` -4

According to the metrics b and c, the polarity for the review is -4. According
to the metrics a, the review score is -0.6. For our experiments, we used the
extreme value calculation (metrics c).

##  4 Experimental results

We compare our adapted system of an unsupervised rule-based approach with
another lexicon-based unsupervised approach Vader, which is extensively used
in research and industry ([4], Mello et al., 2020). In addition, we compare
our results achieved in the Shared Task (Team Olga/LyS-SALSA) with supervised
approaches on the basis of the test dataset submitted to the Shared Task Rest-
Mex 2023. In both comparisons, we use accuracy as our evaluation metrics. As
sentiment dictionaries, we use the dictionaries used by SO-CAL for Spanish [1]
. The content of these dictionaries and their parameters are not modified or
tuned. In order to calculate the sentiment score for the review, we used the
extreme value metrics (metrics c).

###  4.1 Comparison with non-compositional rule based approaches

We used the training dataset from Rest-Mex 2023 to compare our system with
Vader as we do not have access to the polarity scores of the test set. The
polarity scoring system used at the Shared Task is from 1 to 5, where 1 is the
lowest polarity and 5 the highest. We assumed a simple mapping between our
scoring system and the one used for the Shared Task (1= >-5 and <=-3, 2= >-3
and <=-1, 3= >-1 and <=1, 4= >1 and <=3, 5= >3 and <=5). We used titles from
the training dataset of Rest-Mex 2023 with positive polarity (5) and negative
polarity (1) to compare the classification of our system and Vader. In order
to be able to compare the polarity scores from the training dataset with
Vader’s scoring system that uses probability measures for polarity scores, we
used three comparison metrics. In the first comparison metrics (Vader 1), we
defined negative or positive scores, if the value for ‘pos’ or ‘neg’ in
Vader’s output was >0.7. In the second comparison metrics (Vader 2), the
positive and negative values were defined more strictly (‘pos’ or ‘neg’ >0.8)
and finally in the third metrics, the probability for positive and negative
scores equals 1 (Vader 3). Table 1 shows that our system (Olga/Lys-SALSA) is
much better at SA than the best Vader system (see 0.27 vs. 0.62 for overall
accuracy).

Table 1: Comparison between unsupervised approaches for SA based on Titles from the Training dataset Rest-Mex 2023 unsupervised | Accuracy
---|---
Vader1 | 0.27
Vader2 | 0.13
Vader3 | 0.10
Olga/LyS-SALSA | 0.62

###  4.2 Comparison with supervised approaches

For the participation at the Shared Task Rest-Mex 2023, participants were
asked to classify the polarity of a test set. We used titles of the reviews as
the input text for our polarity classification, if the title contained
sentiment words such as "very good restaurant, but not so cheap". Otherwise,
we used the full review text for polarity classification.

The best performing approaches used in the Shared Task of SA at Rest-Mex 2023
are supervised approaches which have been trained on the training dataset and
which predicted polarity scores for the test dataset of the same domain or
corpus as the training dataset [3]. It is thus not surprising to see that our
results are behind the results of supervised approaches as shown in Table 2.

Table 2: Comparison between our system and supervised systems at Shared Task Rest-Mex 2023 Teams | Accuracy(Polarity)
---|---
LKE-LLMAS-Team | 0.75
Javier Alonso-Team | 0.74
Olga/LyS-SALSA | 0.56

However, it has been shown by [1] that these methods are not so robust when
compared across different domains, languages and datasets. One important note
regarding the comparison of our system and supervised approaches is that we do
not know from the results provided to us from the organizers of the Shared
Task, whether the supervised methods used both titles and reviews or just one
of the two methods as the input text for the training and/or prediction task.
Given that titles are very short, it is very likely that the training period
was not performed on titles alone as it would probably lead to a worse
performance of supervised methods. Note that our unsupervised rule-based
approach does not depend much on the shortness of the text. On the contrary,
in case titles contain single sentiment words like "recommendable!", no
dependency parsing is required and the word score for "recommendable" directly
represents the polarity score for the whole review. Finally, we would like to
mention that our participation at the Shared Task was not motivated by winning
the Shared Task, but by experimenting with an unsupervised rule-based
approach.

##  5 Discussion

There are several issues that need to be accounted for in a lexicon-based SA
system. One issue is the implementation of several syntactic rules that can
shift, weaken or strengthen the polarity. One important point of this
implementation is the scope of negation. We have suggested to use a head-child
dependency relation to control for the scope of negation. As a result, in our
approach the negation word No in the example No! Es excelente! ‘No! It’s
excellent!’ is ignored, although the negation word stands in very close
proximity to the sentiment word. This is because the negation and the
sentiment word excelente do not have a head-child dependency relation. In
other words, excelente is not the head of the negation word No. A similar case
applies to the negation no in the sentence Es excelente, no? ‘It’s excellent,
isn’t it?’ Note that according to Vader, close proximity of the negation to
the sentiment word counts as a trigger for shifting the sentiment polarity. As
a consequence, Vader would incorrectly predict a shift in polarity for the
above mentioned examples with negation.

Scope of negation is not a trivial issue and has caused some headache to
(computational) linguists, because the scope of negation does not only depend
on the dependency relation, but also on semantic features of the elements
negation has scope over. Take for instance, the difference between definite
and indefinite nouns. Negation has usually scope over indefinite nouns, but
not over definite nouns. This is because definite nouns express
presuppositions and presuppositions are preserved under negation [20].
Consider the relevant examples: It’s not this amazing hotel, it’s the other
one vs. It’s not an amazing hotel. Negation has scope over the adjective
amazing in the latter, but not in the former example, because in the former
example it is presupposed to be true that the hotel is amazing. We will review
various cases of scope of negation in the future.

Another issue is the verb modality. Take for instance the sentiment word great
which has a positive polarity in a sentiment dictionary. However, if the
sentiment word occurs with counterfactual verbs like would have been as in
Everything in this hotel would have been great if it only were not so far from
the center, the verb modality weakens the polarity of the sentiment word
great. To account for the modality, we will experiment with verbal features
represented in ‘feats’ in UD such as feats: Mood=xx, VerbForm=yyy in future
research. We assume that capturing the verb modality of a sentence will
considerably improve unsupervised SA.

Another issue is agent-based modality. Current NLP tasks express the need for
a more structured sentiment analysis that accounts for the agent-based
modality (SemEval 2022, Task 10 [21]). Sentiment words can be associated with
different agents or opinion holders as in According to Trip-Advisor, this
hotel is great, but I don’t think so.. Quotation is another example which
shows that the opinion expressed inside quotations does not need to correspond
to the opinion of the reviewer as in "this restaurant is the best" says Trip
Advisor. We will look into modalities in more detail in the future research.

One important issue is word ambiguity. Take for instance the word vieja ‘old’.
It has a negative score in our sentiment dictionary. However, if it is used in
a proper name as in Havana vieja it does not have a negative sentiment.
Depending on the domain, old can have a positive value as in old tradition.
Several approaches have been dealing with Word Sense Disambiguation (WSD)
including WSD for lexicon-based approaches for SA [22, 13], most of which are
exploring WordNet [23]). Other more current approaches use neural language
models for WSD ([24]). We will deal with WSD in SA in the future.

The final issue is the calculation of the polarity score of a whole text or
review that contains several sentences. We have shown that the correct
prediction of sentiment scores is not only a matter of syntactic rules, but
also a matter of finding the right scoring metrics that optimally represents
how humans generally write reviews. As with syntactic rules that determine the
syntactic context of polarity, we can assume that there are stylistic rules
that determine the stylistic context of polarity. Such stylistic rules can
reflect the optimal organization or structure of a text [25]. Marking relevant
sentences by sentence or word order, key words like "in sum", capitalization,
repetition, etc. can be part of these stylistic rules. Determining these rules
will considerably improve unsupervised rule-based approaches and is therefore
reserved for the future research.

##  6 Acknowledgments

We acknowledge the European Research Council (ERC), which has funded this
research under the Horizon Europe research and innovation programme (SALSA,
grant agreement No 101100615), ERDF/MICINN-AEI (SCANNER-UDC,
PID2020-113230RB-C21), Xunta de Galicia (ED431C 2020/11), and Centro de
Investigación de Galicia “CITIC”, funded by Xunta de Galicia and the European
Union (ERDF - Galicia 2014–2020 Program), by grant ED431G 2019/01.

##  7 Appendices

## References

  * Vilares et al. [2017] D. Vilares, C. Gómez-Rodríguez, M. A. Alonso,  Universal, unsupervised (rule-based), uncovered sentiment analysis,  Knowledge-Based Systems 118 (2017) 45–55. URL: https://doi.org/10.10162Fj.knosys.2016.11.014. doi:10.1016/j.knosys.2016.11.014.
  * Zeman et al. [2023] D. Zeman, J. Nivre, M. Abrams, E. Ackermann, N. Aepli, H. Aghaei, Ž. Agić, A. Ahmadi, L. Ahrenberg, C. K. Ajede, S. F. Akkurt, G. Aleksandravičiūtė, I. Alfina, A. Algom, K. Alnajjar, C. Alzetta, E. Andersen, L. Antonsen, T. Aoyama, K. Aplonova, A. Aquino, C. Aragon, G. Aranes, M. J. Aranzabe, B. N. Arıcan, H͡. Arnardóttir, G. Arutie, J. N. Arwidarasti, M. Asahara, K. Ásgeirsdóttir, D. B. Aslan, C. Asmazoğlu, L. Ateyah, F. Atmaca, M. Attia, A. Atutxa, L. Augustinus, M. Avelãs, E. Badmaeva, K. Balasubramani, M. Ballesteros, E. Banerjee, S. Bank, V. Barbu Mititelu, S. Barkarson, R. Basile, V. Basmov, C. Batchelor, J. Bauer, S. T. Bedir, S. Behzad, K. Bengoetxea, I. Benli, Y. Ben Moshe, G. Berk, R. A. Bhat, E. Biagetti, E. Bick, A. Bielinskienė, K. Bjarnadóttir, R. Blokland, V. Bobicev, L. Boizou, E. Borges Völker, C. Börstell, C. Bosco, G. Bouma, S. Bowman, A. Boyd, A. Braggaar, A. Branco, K. Brokaitė, A. Burchardt, M. Campos, M. Candito, B. Caron, G. Caron, C. Carvalheiro, R. Carvalho, L. Cassidy, M. C. Castro, S. Castro, T. Cavalcanti, G. Cebiroğlu Eryiğit, F. M. Cecchini, G. G. A. Celano, S. Čéplö, N. Cesur, S. Cetin, Ö. Çetinoğlu, F. Chalub, L. Chamila, S. Chauhan, E. Chi, T. Chika, Y. Cho, J. Choi, J. Chun, J. Chung, A. T. Cignarella, S. Cinková, A. Collomb, Ç. Çöltekin, M. Connor, D. Corbetta, F. Costa, M. Courtin, M. Cristescu, I. L. Dale, P. Daniel, E. Davidson, L. F. de Alencar, M. Dehouck, M. de Laurentiis, M.-C. de Marneffe, V. de Paiva, M. O. Derin, E. de Souza, A. Diaz de Ilarraza, C. Dickerson, A. Dinakaramani, E. Di Nuovo, B. Dione, P. Dirix, K. Dobrovoljc, A. Doyle, T. Dozat, K. Droganova, P. Dwivedi, C. Ebert, H. Eckhoff, M. Eguchi, S. Eiche, M. Eli, A. Elkahky, B. Ephrem, O. Erina, T. Erjavec, F. Essaidi, A. Etienne, W. Evelyn, S. Facundes, R. Farkas, F. Favero, J. Ferdaousi, M. Fernanda, H. Fernandez Alcalde, A. Fethi, J. Foster, C. Freitas, K. Fujita, K. Gajdošová, D. Galbraith, F. Gamba, M. Garcia, M. Gärdenfors, F. F. Gerardi, K. Gerdes, L. Gessler, F. Ginter, G. Godoy, I. Goenaga, K. Gojenola, M. Gökırmak, Y. Goldberg, X. Gómez Guinovart, B. González Saavedra, B. Griciūtė, M. Grioni, L. Grobol, N. Grūzītis, B. Guillaume, C. Guillot-Barbance, T. Güngör, N. Habash, H. Hafsteinsson, J. Hajič, J. Hajič jr., M. Hämäläinen, L. Hà Mỹ, N.-R. Han, M. Y. Hanifmuti, T. Harada, S. Hardwick, K. Harris, D. Haug, J. Heinecke, O. Hellwig, F. Hennig, B. Hladká, J. Hlaváčová, F. Hociung, P. Hohle, M. Huerta Mendez, J. Hwang, T. Ikeda, A. K. Ingason, R. Ion, E. Irimia, Ọ. Ishola, A. Islamaj, K. Ito, S. Jannat, T. Jelínek, A. Jha, K. Jiang, A. Johannsen, H. Jónsdóttir, F. Jørgensen, M. Juutinen, H. Kaşıkara, N. Kabaeva, S. Kahane, H. Kanayama, J. Kanerva, N. Kara, R. Karahóǧa, A. Kåsen, T. Kayadelen, S. Kengatharaiyer, V. Kettnerová, J. Kirchner, E. Klementieva, E. Klyachko, A. Köhn, A. Köksal, K. Kopacewicz, T. Korkiakangas, M. Köse, A. Koshevoy, N. Kotsyba, J. Kovalevskaitė, S. Krek, P. Krishnamurthy, S. Kübler, A. Kuqi, O. Kuyrukçu, A. Kuzgun, S. Kwak, K. Kyle, V. Laippala, L. Lambertino, T. Lando, S. D. Larasati, A. Lavrentiev, J. Lee, P. Lê Hồng, A. Lenci, S. Lertpradit, H. Leung, M. Levina, L. Levine, C. Y. Li, J. Li, K. Li, Y. Li, Y. Li, K. Lim, B. Lima Padovani, Y.-J. J. Lin, K. Lindén, Y. J. Liu, N. Ljubešić, O. Loginova, S. Lusito, A. Luthfi, M. Luukko, O. Lyashevskaya, T. Lynn, V. Macketanz, M. Mahamdi, J. Maillard, I. Makarchuk, A. Makazhanov, M. Mandl, C. Manning, R. Manurung, B. Marşan, C. Mărănduc, D. Mareček, K. Marheinecke, S. Markantonatou, H. Martínez Alonso, L. Martín Rodríguez, A. Martins, C. Martins, J. Mašek, H. Matsuda, Y. Matsumoto, A. Mazzei, R. McDonald, S. McGuinness, G. Mendonça, T. Merzhevich, N. Miekka, A. Miller, K. Mischenkova, A. Missilä, C. Mititelu, M. Mitrofan, Y. Miyao, A. Mojiri Foroushani, J. Molnár, A. Moloodi, S. Montemagni, A. More, L. Moreno Romero, G. Moretti, S. Mori, T. Morioka, S. Moro, B. Mortensen, B. Moskalevskyi, K. Muischnek, R. Munro, Y. Murawaki, K. Müürisep, P. Nainwani, M. Nakhlé, J. I. Navarro Horñiacek, A. Nedoluzhko, G. Nešpore-Bērzkalne, M. Nevaci, L. Nguyễn Thị, H. Nguyễn Thị Minh, Y. Nikaido, V. Nikolaev, R. Nitisaroj, A. Nourian, H. Nurmi, S. Ojala, A. K. Ojha, H. Óladóttir, A. Olúòkun, M. Omura, E. Onwuegbuzia, N. Ordan, P. Osenova, R. Östling, L. Øvrelid, Ş. B. Özateş, M. Özçelik, A. Özgür, B. Öztürk Başaran, T. Paccosi, A. Palmero Aprosio, A. Panova, H. H. Park, N. Partanen, E. Pascual, M. Passarotti, A. Patejuk, G. Paulino-Passos, G. Pedonese, A. Peljak-Łapińska, S. Peng, S. L. Peng, R. Pereira, S. Pereira, C.-A. Perez, N. Perkova, G. Perrier, S. Petrov, D. Petrova, A. Peverelli, J. Phelan, J. Piitulainen, Y. Pinter, C. Pinto, T. A. Pirinen, E. Pitler, M. Plamada, B. Plank, T. Poibeau, L. Ponomareva, M. Popel, L. Pretkalniņa, S. Prévost, P. Prokopidis, A. Przepiórkowski, R. Pugh, T. Puolakainen, S. Pyysalo, P. Qi, A. Querido, A. Rääbis, A. Rademaker, M. Rahoman, T. Rama, L. Ramasamy, J. Ramos, F. Rashel, M. S. Rasooli, V. Ravishankar, L. Real, P. Rebeja, S. Reddy, M. Regnault, G. Rehm, A. Riabi, I. Riabov, M. Rießler, E. Rimkutė, L. Rinaldi, L. Rituma, P. Rizqiyah, L. Rocha, E. Rögnvaldsson, I. Roksandic, M. Romanenko, R. Rosa, V. Rosca, D. Rovati, B. Rozonoyer, O. Rudina, J. Rueter, K. Rúnarsson, S. Sadde, P. Safari, A. Sahala, S. Saleh, A. Salomoni, T. Samardžić, S. Samson, M. Sanguinetti, E. Sanıyar, D. Särg, M. Sartor, M. Sasaki, B. Saulīte, Y. Sawanakunanon, S. Saxena, K. Scannell, S. Scarlata, N. Schneider, S. Schuster, L. Schwartz, D. Seddah, W. Seeker, M. Seraji, S. Shahzadi, M. Shen, A. Shimada, H. Shirasu, Y. Shishkina, M. Shohibussirri, M. Shvedova, J. Siewert, E. F. Sigurðsson, J. Silva, A. Silveira, N. Silveira, S. Silveira, M. Simi, R. Simionescu, K. Simkó, M. Šimková, H. B. Símonarson, K. Simov, D. Sitchinava, T. Sither, M. Skachedubova, A. Smith, I. Soares-Bastos, P. E. Solberg, B. Sonnenhauser, S. Sourov, R. Sprugnoli, V. Stamou, S. Steingrímsson, A. Stella, A. Stephen, M. Straka, E. Strickland, J. Strnadová, A. Suhr, Y. L. Sulestio, U. Sulubacak, S. Suzuki, D. Swanson, Z. Szántó, C. Taguchi, D. Taji, F. Tamburini, M. A. C. Tan, T. Tanaka, D. Tanaya, M. Tavoni, S. Tella, I. Tellier, M. Testori, G. Thomas, S. Tonelli, L. Torga, M. Toska, T. Trosterud, A. Trukhina, R. Tsarfaty, U. Türk, F. Tyers, S. H͡órðarson, V. H͡orsteinsson, S. Uematsu, R. Untilov, Z. Urešová, L. Uria, H. Uszkoreit, A. Utka, E. Vagnoni, S. Vajjala, S. Vak, R. van der Goot, M. Vanhove, D. van Niekerk, G. van Noord, V. Varga, U. Vedenina, G. Venturi, V. Vincze, N. Vlasova, A. Wakasa, J. C. Wallenberg, L. Wallin, A. Walsh, J. N. Washington, M. Wendt, P. Widmer, S. Wigderson, S. H. Wijono, S. Williams, M. Wirén, C. Wittern, T. Woldemariam, T.-s. Wong, A. Wróblewska, M. Yako, K. Yamashita, N. Yamazaki, C. Yan, K. Yasuoka, M. M. Yavrumyan, A. B. Yenice, O. T. Yıldız, Z. Yu, A. Yuliawati, Z. Žabokrtský, S. Zahra, A. Zeldes, H. Zhou, H. Zhu, Y. Zhu, A. Zhuravleva, R. Ziane, Universal dependencies 2.12, 2023. URL: http://hdl.handle.net/11234/1-5150, LINDAT/CLARIAH-CZ digital library at the Institute of Formal and Applied Linguistics (ÚFAL), Faculty of Mathematics and Physics, Charles University.
  * Álvarez-Carmona et al. [2023] M. Á. Álvarez-Carmona, Á. Díaz-Pacheco, R. Aranda, A. Y. Rodríguez-González, L. Bustio-Martínez, V. Muñis-Sánchez, A. P. Pastor-López, F. Sánchez-Vega,  Overview of rest-mex at iberlef 2023: Research on sentiment analysis task for mexican tourist texts,  Procesamiento del Lenguaje Natural 71 (2023).
  * Hutto and Gilbert [2014] C. Hutto, E. Gilbert,  Vader: A parsimonious rule-based model for sentiment analysis of social media text,  Proceedings of the International AAAI Conference on Web and Social Media 8 (2014). URL: https://ojs.aaai.org/index.php/ICWSM/article/view/14550. doi:10.1609/icwsm.v8i1.14550.
  * Socher et al. [2013] R. Socher, A. Perelygin, J. Wu, J. Chuang, C. D. Manning, A. Ng, C. Potts,  Recursive Deep Models for Semantic Compositionality Over a Sentiment Treebank,  in: EMNLP 2013. 2013 Conference on Empirical Methods in Natural Language Processing. Proceedings of the Conference, ACL, Seattle, Washington, USA, 2013, pp. 1631–1642.
  * Devlin et al. [2019] J. Devlin, M.-W. Chang, K. Lee, K. Toutanova,  BERT: Pre-training of deep bidirectional transformers for language understanding,  in: Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), Association for Computational Linguistics, Minneapolis, Minnesota, 2019, pp. 4171–4186. URL: https://aclanthology.org/N19-1423. doi:10.18653/v1/N19-1423.
  * Rezaeinia et al. [2017] S. M. Rezaeinia, A. Ghodsi, R. Rahmani, Improving the accuracy of pre-trained word embeddings for sentiment analysis, 2017. arXiv:1711.08609.
  * Hong and Fang [2015] J. Hong, M. Fang,  Analysis with deeply learned distributed representations of variable length texts,  2015\.
  * Ainapure et al. [2023] B. S. Ainapure, R. N. Pise, P. Reddy, B. Appasani, A. Srinivasulu, M. S. Khan, N. Bizon,  Sentiment analysis of covid-19 tweets using deep learning and lexicon-based approaches,  Sustainability 15 (2023). URL: https://www.mdpi.com/2071-1050/15/3/2573. doi:10.3390/su15032573.
  * Chun [2021] J. Chun,  Sentimentarcs: A novel method for self-supervised sentiment analysis of time series shows SOTA transformers can struggle finding narrative arcs,  CoRR abs/2110.09454 (2021). URL: https://arxiv.org/abs/2110.09454. arXiv:2110.09454.
  * Huang et al. [2020] J. Huang, Y. Meng, F. Guo, H. Ji, J. Han,  Weakly-supervised aspect-based sentiment analysis via joint aspect-sentiment topic embedding,  in: Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), Association for Computational Linguistics, Online, 2020, pp. 6989–6999. URL: https://aclanthology.org/2020.emnlp-main.568. doi:10.18653/v1/2020.emnlp-main.568.
  * Taboada et al. [2011] M. Taboada, J. Brooke, M. Tofiloski, K. Voll, M. Stede,  Lexicon-based methods for sentiment analysis,  Computational Linguistics 37 (2011) 267–307.
  * Vashishtha and Susan [2019] S. Vashishtha, S. Susan,  Fuzzy rule based unsupervised sentiment analysis from social media posts,  Expert Systems with Applications 138 (2019) 112834. URL: https://www.sciencedirect.com/science/article/pii/S0957417419305366. doi:https://doi.org/10.1016/j.eswa.2019.112834.
  * Caio Mello [2022] G. T. Caio Mello, Gullal S. Cheema,  Combining sentiment analysis classifiers to explore multilingual news articles covering London 2012 and Rio 2016 Olympics,  Int J Digit Humanities (2022). doi:https://doi.org/10.1007/s42803-022-00052-9.
  * Qi et al. [2020] P. Qi, Y. Zhang, Y. Zhang, J. Bolton, C. D. Manning,  Stanza: A python natural language processing toolkit for many human languages,  in: Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations, Association for Computational Linguistics, Online, 2020, pp. 101–108. URL: https://aclanthology.org/2020.acl-demos.14. doi:10.18653/v1/2020.acl-demos.14.
  * Qi et al. [2018] P. Qi, T. Dozat, Y. Zhang, C. D. Manning,  Universal Dependency parsing from scratch,  in: Proceedings of the CoNLL 2018 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies, Association for Computational Linguistics, Brussels, Belgium, 2018, pp. 160–170. URL: https://aclanthology.org/K18-2016. doi:10.18653/v1/K18-2016.
  * Müller et al. [2021] S. Müller, A. Abeillé, R. D. Borsley, J.-P. Koenig (Eds.), Head Driven Phrase Structure Grammar, number 9 in Empirically Oriented Theoretical Morphology and Syntax, Language Science Press, Berlin, 2021. doi:10.5281/zenodo.5543318.
  * Graf and Marcinek [2014] T. Graf, B. Marcinek,  Evaluating evaluation metrics for minimalist parsing,  in: V. Demberg, T. O’Donnell (Eds.), Proceedings of the Fifth Workshop on Cognitive Modeling and Computational Linguistics, CMCL@ACL 2014, Baltimore, Maryland, USA, June 26, 2014, Association for Computational Linguistics, 2014, pp. 28–36. URL: https://doi.org/10.3115/v1/W14-2004. doi:10.3115/v1/W14-2004.
  * Meng et al. [2015] F. Meng, Z. Lu, M. Wang, H. Li, W. Jiang, Q. Liu,  Encoding source language with convolutional neural network for machine translation,  CoRR abs/1503.01838 (2015). URL: http://arxiv.org/abs/1503.01838. arXiv:1503.01838.
  * Atlas [1976] J. D. Atlas, On the Semantics of Presupposition and Negation: An Essay in Philosophical Logic and the Foundations of Linguistics, Ph.D. thesis, Princeton University, 1976\.
  * Barnes et al. [2022] J. Barnes, L. Oberlaender, E. Troiano, A. Kutuzov, J. Buchmann, R. Agerri, L. Øvrelid, E. Velldal,  SemEval 2022 task 10: Structured sentiment analysis,  in: Proceedings of the 16th International Workshop on Semantic Evaluation (SemEval-2022), Association for Computational Linguistics, Seattle, United States, 2022, pp. 1280–1295. URL: https://aclanthology.org/2022.semeval-1.180. doi:10.18653/v1/2022.semeval-1.180.
  * Vilares et al. [2013] D. Vilares, M. A. Alonso, C. Gómez-Rodríguez,  Supervised polarity classification of Spanish tweets based on linguistic knowledge,  in: DocEng’13. Proceedings of the 13th ACM Symposium on Document Engineering, ACM, Florence, Italy, 2013, pp. 169–172.
  * Hung and Chen [2016] C. Hung, S.-J. Chen,  Word sense disambiguation based sentiment lexicons for sentiment classification,  Knowledge-Based Systems 110 (2016) 224–232. URL: https://www.sciencedirect.com/science/article/pii/S0950705116302453. doi:https://doi.org/10.1016/j.knosys.2016.07.030.
  * Giulianelli et al. [2020] M. Giulianelli, M. Del Tredici, R. Fernández,  Analysing lexical semantic change with contextualised word representations,  in: Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, Association for Computational Linguistics, Online, 2020, pp. 3960–3973. URL: https://aclanthology.org/2020.acl-main.365. doi:10.18653/v1/2020.acl-main.365.
  * Wilson [2019] D. Wilson,  Relevance theory,  Oxford Research Encyclopedia of Linguistics (2019).

##  Appendix A Online Resources

The files used for the experiment are available on GitHub.

  * •

GitHub