# Technical Specification of STRUNEE Prototype

This file is updated in July, 2023.
Authors: Gabriele Lenzini, Huseyin Demirci, Emre Kocyigit

## Content
This document consists of the following parts:
* Overview
* Definitions
* Installations & Requirements
* Files
* Architecture and Components

## Overview
The goal of this software is to have an initial implementation for a Trust Level Evaluation Engine (TLEE) using Subjective Logic (SL) theory. Subjective Logic is a mathematical framework for reasoning about uncertain and subjective information. It allows for the representation and manipulation of uncertain beliefs, opinions, and preferences using probability distributions.

This implementation considers the Subjective Trust Network approach where the network elements can be defined for different purposes such as an Automated Driving scenario. Once we have assigned opinion values to all edges in the graph of trust network, we can use subjective logic operators to combine these opinions and compute the overall trustworthiness of each entity in the network.

## Definitions
In this part we explain the basic terminology used in the TLEE implementation.

**Opinion:** In subjective logic, an opinion represents a degree of belief, disbelief, and uncertainty about a statement. It is represented as an opinion value, which consists of three components: a belief mass, a disbelief mass, and a base rate.

The agent $A$ has an opinion about a target variable $X$ means that there is a directed belief relationship from A to X, formally denoted as [A,X]. This relationship can be considered as directed edge in a graph. Therefore it can be denoted also as: $A \rightarrow X$ in terms of graph notation.

The opinion is a composite function $\omega^A_X = (b_X , u_X , a_X )$, consisting of the belief $b_X$, uncertainty $u_X$, and the base rate $a_X$ distributions. The belief mass represents the degree of confidence or support that an individual has in a statement being true. It can be interpreted as the proportion of evidence or arguments in favor of the statement that the individual finds convincing. The disbelief mass represents the degree of doubt or skepticism that an individual has in the statement being true. It can be interpreted as the proportion of evidence or arguments against the statement that the individual finds convincing. The base rate represents the prior probability of the statement being true, based on background knowledge or general assumptions.

Together, the belief mass, disbelief mass, and uncertainity add up to one, indicating that they represent all possible degrees of belief, disbelief, and uncertainty about the statement. The belief mass and disbelief mass can be seen as opposing forces that represent the degree of support and skepticism, respectively, for the statement. The base rate provides a neutral starting point that can be updated based on new evidence or reasoning.

An opinion is stated as $\omega^A_X$ where the subscript $X$ indicates the target variable or proposition to which the opinion applies, and the superscript $A$ indicates the subject agent who holds the opinion. Superscripts can be omitted when it is implicit or irrelevant who the belief owner is.
**Opinion scores:** The numerical values of the opinion tuples $(b,d,u,a,e)$ for belief, disbelief, uncertainty, base rate and projected probability, respectively.

**Agent:** An agent is the active entity that owns opinions about a set of propositions. An agent can be a person, an organization, a sensor, or an abstract entity such as a Sensor Unit that can reason about uncertain information.

**Proposition:** In subjective logic, a proposition is a statement that can either be true or false, and is associated with a belief state that describes the degree to which an agent believes the proposition to be true. The opinions are built on this Proposition. Propositions can be atomic (a single proposition related to an agent) or composite (union of multiple atomic propositions).
- Example Proposition: The speed of the Egovehicle is less than 10m/sec at a certain moment.

**Subjective Trust Network:** A subjective trust network is a graph in which nodes represent individuals or entities, and edges represent the level of trust between them. Each edge is associated with a trust degree, which is a measure of the degree of trust that one entity has in another. Trust Network represents trust relations as Directed Graphs and opinions are represented in the edges.

**Subjective Network:** The union of Subjective Trust Network with a Subjective Bayesian Network is called a Subjective Network.The elements of a Subjective Network is depicted as follows in Josag's book:
**Figure 1. Components of a Trust Network**

**Event:** A specific instance of variables.
**Trust Expression:** The text form of expression of trust which includes the expanded version of the tree form of the Subjective Trust Network elements combined with operators such as Discount, Fusion and Logic operations.
**Figure 2. A sample Trust Expression in Tree format**

**DSPG:** A graph is a DSPG (Directed Series-Parallel Graph) iff it can be decomposed as a combination of Series and Parallel graphs (Definition 15.1 of Josang's Book), and it only consists of directed edges that form paths without loops from the source to the sink.

**Outbound-Inbound Set (OIS):** Consider an ordered pair of nodes $(V_s,V_t )$ in a DSPG. We define the outbound-inbound set $(OIS)$ of the ordered pair to be the intersection of the outbound set of the first node Vs and the inbound set of the second node $V_t$.

**Parallel-Path Subnetwork:** Select an ordered pair $(V_s,V_t)$ of connected nodes in a DSPG. The subnetwork consisting of the pair’s OIS is a parallel path subnetwork (PPS) iff both the outbound degree of the first node $V_s$ in the OIS satisfies $OD(V_s) ≥ 2$, and the inbound degree of the second node $V_t$ in the OIS satisfies $ID(V_t ) ≥ 2.$

**Nesting Level:** Assume a DSPG consisting of multiple nodes connected via directed edges. The nesting level of an edge in the DSPG is equal to the number of PPSs (parallel-path subnetworks) that the edge is a part of.

**Network Synthesizing:** The transformation of a non-DSPG to a DSPG.

**Network Analysis (Derivation):** The transformation of a DSPG graph to a single edge as an expanded meta tree expression according to the graph analysis Algorithm in Josang's Book page 276.

**Expression Evaluation:** To calculate the numerical values for the opinion scores $(b,d,u,a,e)$ of the corresponding SL trust expression.

## Installation & Requirements
The software us developed with the following software languages and libraries.
- **Language and version:** Python 3.9
- **Libraries & packages:**
- **Networkx:** A Python library for creating, manipulating, visualization and studying large complex networks. It includes the necessary functions to handle large graphs effectively.
- **NumPy:** NumPy is a library for scientific computing with Python. It provides support for large, multi-dimensional arrays and matrices, along with a range of high-level mathematical functions to operate on these arrays.
- **Matplotlib:** Matplotlib is a plotting library for Python that provides a range of tools for creating visualizations, such as line plots, scatter plots, bar charts, histograms, and more.
- **itertools:** itertools is a library that provides a collection of functions for creating iterators, which are objects that allow you to iterate over a sequence of values. It includes functions for generating combinations, permutations, and other useful iterators.
- **math:** math is a built-in Python library that provides a range of mathematical functions, including basic arithmetic operations, trigonometric functions, logarithmic functions, etc. It is useful for performing mathematical calculations in Python programs.
- **anytree** anytree is a Python library for working with trees. It provides a flexible and easy-to-use API for creating, manipulating, and traversing tree data structures.

The required libraries can be installed by using pip or conda install commands.

## Files
We plan to use one main python file and 8 other auxilary files to execute the prototype. These files are listed as:
- **main.py**:
- It is the core of the TLEE system which coordinates the end-to-end flow of the process.
- It calls the other files which include the functions to perform the operations necessary to accomplish tasks such as network analysis and subjective logic operators.
- The final output is the opinion scores of SL the tree expression.

- **trust_expression_formation.py:**
- It takes the Proposition, Agent and meta logical operators as input.
- It produces the trust expression in a tree format as an output.

- **conditionals_solving.py:**
- It takes the conditional relationships between events, STN topology, meta Bayesian operators and the output of Trust Expression Formation component as inputs.
- It produces trust expression including conditionals in a tree format.

- **analyzer.py:**
- It takes the STN network info, meta agent operators and the output of Conditionals Solving component.
- It includes the required functions such as DSPG analysis (derivation) to transform a DSPG to a meta trust expression in tree format.
- The output is the expanded meta trust expression including derivations in a tree format.
- This part is generally the most time-consuming part of the code since it executes the required graph analysis operations like finding path from a source to a target.

- **evaluator.py:**
- The inputs are the meta trust expression tree which is produced by the analyzer, mapping table that stores meta operators and corresponding functions, and opinion scores.
- It calculates the final trust opinion scores calling the related functions considering meta operators in the tree expression.
- The output is the final trust opinion score tuple.
- Therefore it converts the tree expression form to numerical opinion score values which represent belief, disbelief, and uncertainty.

- **sl_operators.py:**
- It contains all the Subjective Logic operator functions such as Discount, Trust Fusion, Multiplication, etc.
- The table that maps the meta operators to the SL functions is also defined here.
- The evaluator will call the defined functions of this file to obtain the final opinion scores.

The inputs of the TLEE are be defined in the following files.
- **stns.py:**
It serves as the entry point to define the inputs of Trust Network graphs elements such as nodes, edges, opinion scores and the plotting coordinates.

- **conditionals.py:**
This file is used to define the conditional relationships between the events such as Abduction and Deduction.

- **proposition_and_agent.py:**
The inputs of the TLEE which consists of the proposition for which the trust is evalu-
ated and the relevant agent name for which trust is computed, are defined in this file.

## Architecture and Components

In this part we briefly introduce the architecture of the proposed system. We explain the main components: Trust Expression Former, Conditionals Solving, STN Analyzer, Evaluator and the related Inputs. The architecture of TLEE is depicted in Figure 3.

**Figure 3. The main TLEEarchitecture**

**INPUTS:**

The inputs of the TLEE system can be described as follows:

* **Proposition:** The basic statement that we want to evaluate the opinion of agents.
- We assume that all the agents are subjective to the same Proposition.
- Propositions can be atomic (regarding one single statement or composite which may be a union of atomic propositions combined with logical operators).

* **STN Topology:** It includes the network and relationship information of the all the agents in the system. Each agent may include a Subjective Trust Network (or not) and the agents may have logical dependencies among themselves as well.

* **Agent:** The relevant Agent for the Proposition.

* **Conditionals:** The Bayesian relationships between the events such as Abduction and Deduction are defined here in a dictionary format with the help of meta Bayesian operators.
* **Mapping Table:** The output of the STN Analyzer component is a trust expression contains meta operators which are only string. The Mapping Table stores these meta operators and corresponding functions such as Subjective Logic operators that are used in the evaluation of the meta-trust expression. We provide flexibility of changing the logic framework to the TLEE by this table.
* **Opinion Scores:** The opinion scores are trust values on propositions or agents in tuple format (b, d, u, a, e) representing belief, disbelief, uncertainty, base rate, and theprojected probability, respectively. They can be defined via prior knowledge such as benefiting from historical data from sensors or a bootstrapping process.

* **Meta operators:** The relevant meta operator definitions. Using a dictinary structure, the generic operations such as "META_TRUST_DISCOUNT" and "META_TRUST_FUSION": are assigned to specific operators according to the Trust Theory. For instance for Subjective Logic, these may correspond to Trust Discounting and Cumulative Fusion.

After defining the inputs we briefly define functionality, inputs and the outputs of the main components.

**Subjective Proposition Processor:**
- **Functionality:** It takes the Proposition and the relevant Agent as input and generates the trust expression in the tree format by using the Meta Logical Operators.
- **Inputs:** Propositions (defined as a root node of the tree), Agent, Meta Operators (defined in the form of dictionaries regarding logical operators such as "AND" corresponds to "META_MULTIPLICATION" and as agent related meta operators such as "TRUST_FILTERING" corresponds to "META_TRUST_DISCOUNT", Conditionals
- **Outputs:** Trust expression in tree format.

**Logic Conditionals Solver:**
- **Functionality:** It processes the tree expression by solving conditional relationships and expands the expression with meta conditionals operators
- **Inputs:** STN Topology, Conditionals and the trust expression coming from Trust Expression Former.
- **Outputs:** Trust expression in tree format including conditionals (See the example in Figure 2).

**Subjective Trust Network Analyzer:**
Thic component takes the STN Topology Graph as input and checks if for each opinion there exist a trust network. It executes the Derivation (Analysis) operation for each STN.
- **Input:** Trust logic expression (Tree) + STN Topology.
- **Output:** List of DSPGs which will be used to update STN Topology.

* **Derivation:**
- **Functionality:** For each DSPG, this function derives the SL expression tree by using DSPG analysis algorithm of the book to obtain expanded trust logic expression. The algorithm steps are as follows:
- **0.** Find all the PPS (Paralel Path Subnetworks) from the source to the target
- **1.** Calculate the nesting levels of the edges
- **2.** Find the maximum nesting level and the PPS with all the edges have the maximum nesting level to start
- **3.** Implement discount and fusion operations and then Update the tables/dictinary accordingly
- **4.** Simplify the subgraph into an edge
- **5.** Repeat 2,3,4 until there is no subgraph
- **6.** Implement the final discount and return the final expression and table
- If during the derivation fails which means that the graph is a non-DSPG, a heuristic algorithm is used to fix by deleting the edges which violate DSPG conditions. Then the DSPG Derivation steps from 1-6 run again to check if the obtained graph is DSPG. This step is repeated until we transform the non-DSPG graph to a DSPG graph.
- **Input:** Trust logic expression (Tree) + STN Topology.
- **Output:** Expanded trust logic expression (SL Tree Expression, not Meta Tree Expression)

**Trust Evaluator:**
- **Functionality:** It generates an output opinion score by using meta tree expression and the information of each direct opinion about the proposition regarding the operators of the stated theory in the mapping table.
- **Inputs:** Meta Tree Expression, Opinion Scores (from the Opinion Provider agent) and mapping table
- **Outputs:** Final opinion score values: $(b,d, u, a,e)$.

**AUXILARY :**
These are auxilary functions that are used to execute tasks in the network analysis, expression formatting and evaluation parts.
**SL Operators Set:**
- **Functionality:** The whole set of SL operators are defined here.
**Operator Mapper Table:**
- **Functionality:** It helps to map each logic operator with the corresponding Meta operator such as the Subjective Logic operators. Could be used to benefit from different versions of an operator such as fusion types. It can be also used when other types of logic operators other than Subjective Logic are going to be used.