text:
\documentclass[a4paper,10pt]{report}
\usepackage{blindtext} % for dummy texts
\usepackage[T1]{fontenc}
\usepackage[table]{xcolor}
\usepackage{titlesec}
\usepackage{graphicx}
%\usepackage[inkscapepath=../assets/svg]{svg}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{fancyvrb}
\usepackage[english]{babel}
\usepackage{csquotes}
\usepackage{hyperref}
\usepackage{adjustbox,lipsum}
\hypersetup{
   colorlinks=true,
   linkcolor=blue,
   urlcolor=cyan
}
\usepackage{tikz}
\usepackage{amssymb}
\usepackage[sc]{mathpazo}
\linespread{1.05}
\usepackage{microtype}
\usepackage{breqn}
\usepackage{caption}
\usepackage{subcaption}
\usepackage[
   backend=bibtex,%
   bibencoding=utf8,%
   language=english,%
   style=numeric-comp,%
   sorting=nyt,%
   maxbibnames=10,%
   natbib=true%
]{biblatex}
\addbibresource{references.bib}
\usepackage{siunitx}
\usepackage{booktabs}
\usepackage{longtable}
\usepackage{geometry}
\usepackage{multirow}
\graphicspath{ {../assets/img/} }

\newgeometry{hmargin={30mm,30mm}}

% Set TOC depth and sections numbering
\setcounter{tocdepth}{3}
\setcounter{secnumdepth}{3}

% Remove chapters head and reduce spacing
\titleformat{\chapter}[hang]{\Large\bfseries}{\thechapter \hspace{2ex}}{0pt}{\Large}
\titlespacing{\chapter}{0cm}{0cm}{0.5cm}
\usepackage[parfill]{parskip}

% Make quotes italic
\renewcommand{\mkbegdispquote}[2]{\itshape}

% Change texttt line breaks
\renewcommand{\texttt}[1]{%
  \begingroup
  \ttfamily
  \begingroup\lccode`~=`.\lowercase{\endgroup\def~}{.\discretionary{}{}{}}%
  \catcode`/=\active\catcode`[=\active\catcode`.=\active
  \scantokens{#1\noexpand}%
  \endgroup
}

\titlespacing{\chapter}{0pt}{20pt}{0pt}

\begin{document}
\frenchspacing

%----------------------------------------------------------------------------------------
%	FIRST PAGE
%----------------------------------------------------------------------------------------
\title{
  {{\large{\textsc{Alma Mater Studiorum $\cdot$ University of Bologna}}}}
  \rule{\textwidth}{0.4pt}\vspace{3mm}
  \textbf{FantaBayesianNet\footnote{The code for the project is publicly available on \href{https://github.com/giuseppeboezio/FantaBayesianNet}{GitHub}}}
  \begin{figure}[!htb]
    \centering
    \includegraphics[width = 100pt]{fantacalcio-icon}
  \end{figure} \\
  Fundamentals of Artificial Intelligence and Knowledge Representation (Module 3)
}

\author{ Giuseppe Murro (\href{mailto:giuseppe.murro@studio.unibo.it}{giuseppe.murro@studio.unibo.it}) \\ Giuseppe Boezio (\href{mailto:giuseppe.boezio@studio.unibo.it}{giuseppe.boezio@studio.unibo.it}) \\ Salvatore Pisciotta (\href{mailto:salvatore.pisciotta2@studio.unibo.it}{salvatore.pisciotta2@studio.unibo.it})}
\date{\today}
\maketitle
\newpage
\tableofcontents
\setcounter{tocdepth}{1}
%\listoffigures
%\listoftables
\newpage
%----------------------------------------------------------------------------------------

%----------------------------------------------------------------------------------------
%	INTRODUCTION
%----------------------------------------------------------------------------------------
\chapter{Introduction}\label{chap:introduction}

The task of predicting the performance of football players is gaining increasing attention in the sports and statistical communities. In this work, we used a Bayesian Network to model relevant factors of player performance in the presence of noisy data. We apply our analysis to the 2020–2021 season in the top Italian league, Serie A, and use the player ratings provided by a popular Italian fantasy football game, the so-called Fantacalcio.
Actually in literature there is a lack of published research on modeling this kind of data
within a Bayesian framework. The only work done on this field is \cite{bayesian_edigi_gabry} which propose various hierarchical models for predicting player ratings.

Instead in this project we are focused to explore the causal relations that allow to predict if a football player can be deployed or not in a fantasy football lineup. Different kind of reasoning are done to exploit the flow of influence between variables and possible independences. The implementation of the model and the methods used for inference are based on the pgmpy \cite{pgmpy} python library.

%----------------------------------------------------------------------------------------

%----------------------------------------------------------------------------------------
%	BACKGROUND
%----------------------------------------------------------------------------------------
{\let\clearpage\relax\par \chapter{Background}\label{chap:background}}

Fantasy sports games typically involve roster selection and match-by-match challenges against other participants with the results determined by the collective performance of the players on the fantasy rosters. In Italy, fantasy football was popularized by the brand \emph{Fantacalcio} \cite{fantacalcio} edited by Riccardo Albini in the 1990s and in the rest of the report we use the original denomination for referring at the Italian game.

Each player in the Italian Serie A league has an associated price determined by various factors including past performance and forecasts for the upcoming season.
At the beginning of the season, the virtual managers are allocated a limited amount of virtual money with which to buy the players that will comprise their roster.
Each roster will consist of 3 goalkeepers, 8 defenders, 8 midfielders and 6 forwards.

For every matchday in Serie A, virtual managers must \textit{deploy} a fantasy team formed by 11 players divided into their respective roles according to the modules (often  4-3-3 or 3-4-3).
After every match, the prominent Italian sports periodicals assign each player a rating,
a so-called \textit{grade}, on a scale from 1 to 10. In practice there is not much variability in these grades; they typically range 4 four to 8, with the majority between 5 and 6. These grades are very general and largely subjective performance ratings that do not account for significant individual events (goals, assists, yellow and red cards, etc.) in a consistent way.

As a means of systematically including specific in-game events in the ratings, Fantacalcio provides the so-called \textit{point scoring system}. Points are added or deducted from a player’s initial grade for specific positive or negative events during the match. The point scores are more variable than the grades, especially across positions (e.g. when comparing defending and attacking players). Goalkeepers suffer the most from the point scoring system, as they are deducted a point for every goal conceded. On the other extreme,
forwards (attacking players) typically receive the highest point scores because every goal scored is worth three points.

For player \(i\) in match \(t\) the total score \(y_{i,t}\) is
\[y_{i,t} = G_{i,t} + P_{i,t}\]
where G is the grade and P is the point score. Table \ref{table:points} lists the game features that contribute to a player’s point score \(P_{i,t}\) for a given match.

\begin{longtable}{m{0.3\linewidth}|m{0.3\linewidth}}
  \textbf{Event} & \textbf{Points} \\ \hline \endhead
    Goal             & +3       \\
    Assist           & +1       \\
    Penalty saved*  & +3       \\ \hline
    Yellow card      & -0.5     \\
    Red card         & -1       \\
    Goal conceded*   & -1       \\
    Own goal         & -2       \\
    Missed penalty  & -3       \\ \hline

  \caption{Bonus/Malus points in Fantacalcio. The symbol * denotes an event only applicable to goalkeepers.}
  \label{table:points}
\end{longtable}

Since it is very rare for a player to participate in all matches, some  \(y_{i,t}\) are missing, and this may be due to different reasons:
\begin{itemize}
\item the player does not play in the match because of injury, disqualification, coach’s decision, or some other
reason;
\item the player does not participate in the match for long enough for their impact to
be judged by those tasked with assigning the subjective grade
\end{itemize}
For all these, the score is marked with the initials «sv».

%----------------------------------------------------------------------------------------

%----------------------------------------------------------------------------------------
%	CHAPTER 3
%----------------------------------------------------------------------------------------
{\let\clearpage\relax\par \chapter{Dataset}\label{chap:chapter-3}}

\section{Data acquisition}\label{sec:sec-31}
The first step consists in load data, merge different data frames to get a single data frame of players and process feature in order to work with them.

Since statistics of single football players of Serie A in each mach are not directly accessible and they are distributed on different web sites, we have developed a web scraping script (accessible from the \href{https://github.com/giuseppeboezio/FantaBayesianNet/tree/main/src}{repository} of this project) able to collect data from \href{https://www.fantacalcio.it/statistiche-serie-a}{Fantacalcio.it} \cite{fantacalcio} and \href{https://www.transfermarkt.it/serie-a/startseite/wettbewerb/IT1}{Transfermarket.it} \cite{transfermarket} and merge them in order to obtain a single dataset.

We decided to select only forwards players, since their statistics are the most interesting from the view point of the Fantacalcio, and we picked an average of 2 players per team for a total amount of 40 players.
These data are about the first 30 rounds of the 2020–2021 Serie A season.

\section{Data preprocessing}\label{sec:sec-32}
In the initial dataset we had a lot of data, but only some of them were useful for our model.
So starting from the raw dataset we applied three preprocessing operations:
\begin{itemize}
\item Data cleaning from useless columns and rows that refers to "postponed"  matches that did not have information about players, since the game was not played.
\item Data discretization since pgmpy does not support learning from continuous variable, and so all numerical values are mapped into bins
\item Data transformation of the missing values in the "score" attribute into the category "sv" (meaning without a score), which is the symbolic convention in Fantacalcio that indicates the absence of score for a player.
\end{itemize}

%----------------------------------------------------------------------------------------

%----------------------------------------------------------------------------------------
%	CHAPTER 4
%----------------------------------------------------------------------------------------
{\let\clearpage\relax\par \chapter{Bayesian network}\label{chap:chapter-4}}

\section{Structure}\label{sec:section-41}
\subsection{Variables}\label{subsec:subsection-411}
\begin{itemize}

    \item \textbf{goal} = Goal: represents whether, at the correspondent matchday, the player has made a goal and obtained the correspondent bonus (+3)
    \begin{itemize}
        \item True: the player has scored at least one goal
        \item False:The player didn't even score one goal
    \end{itemize}

    \item \textbf{assist} = Assist: represents whether, at the correspondent matchday, the player has made an assist and obtained the correspondent bonus (+3)
    \begin{itemize}
        \item True: The player has made at least one assist
        \item False:The player didn't even make one assist
    \end{itemize}

    \item \textbf{time_range} = Range of minutes: minutes played by the player in the correspondent match
    \begin{itemize}
        \item 0-15: The player played no more than 15 minutes
        \item 16-45:The player has played more than 15 minutes but less than 45 minutes
        \item 46-90:The player has played more than 45 minutes
    \end{itemize}

    \item \textbf{score_range} = Range of "fantasy score": fantasy score obtained by the player at the correspondent matchday, with appropriate bonus and malus included
    \begin{itemize}
        \item s.v. :The player has not played or has played too little time to have a vote
        \item <=5 :the player had a bad game with some possible malus
        \item 5.5-6.5 :the player did not play a great game or at most a sufficient game
        \item 7-9.5 :the player played a great game and may have taken some bonuses as well
        \item >=10 :the player played an excellent game and also took some bonuses
    \end{itemize}

    \item \textbf{difficulty_match}= Difficulty of the match calculated in crescent order through a formula
    \begin{itemize}
        \item 1 :easy match generally played at home
        \item 2 :easy match generally played away
        \item 3 :balanced match
        \item 4 :difficult match generally played at home
        \item 5 :difficult match generally played away
    \end{itemize}

    \item \textbf{penalty_kicker}= Kicker of the team for penalties: represents whether the player (if at the correspondent matchday was available) is the one designed to kick the penalties
    \begin{itemize}
        \item True: The player is the penalty kicker
        \item False:The player isn't the penalty kicker
    \end{itemize}

    \item \textbf{home_match}= : represents whether, at the correspondent matchday, the player's team played at home or away
    \begin{itemize}
        \item True: the team played the match at home
        \item False: the team played the match away from home
     \end{itemize}

    \item \textbf{yellow_card}= Admonition: represents whether, at the correspondent matchday, the player the player got a yellow card with correspondent malus(-0.5)
    \begin{itemize}
        \item True: the player received a yellow card
        \item False: the player didn't receive a yellow card
    \end{itemize}

    \item \textbf{red_card}= Expulsion: represents whether, at the correspondent matchday, the player the player got a red card with correspondent malus(-1)
    \begin{itemize}
        \item True: the player received a red card
        \item False: the player didn't receive a red card
    \end{itemize}

    \item \textbf{available}= Availability: represent whether the player at the corresponding matchday was available for his team or not (e.g. for an injury or a disqualification)
    \begin{itemize}
        \item True: the player was available
        \item False: the player wasn't available
    \end{itemize}

    \item \textbf{deployability}=Deployability: represents whether the player for the corresponding matchday will be a good choice for the fantasy team of the fantasy manager
    \begin{itemize}
        \item True: deploy the player is a good choice
        \item False: it is better, if possible, not to deploy the player
    \end{itemize}

\end{itemize}

\newpage
\subsection{Network}\label{subsec:subsection-412}
The building step of the model started with the realization of the first network based only on the domain's knowledge. Move forward the structure was improved and developed using correlation matrix analysis that lead us to the final network presented in Figure \ref{fig:bayesianNet}.

\begin{figure}[h]
    \centering
    \includegraphics[width=0.5\textwidth]{assets/img/Network.png}
    \caption{Bayesian Network}
    \label{fig:bayesianNet}
\end{figure}

\section{Active Trails}\label{sec:section-42}
We have done some examples of reasoning patterns, namely causal reasoning and evidential reasoning, and possibile active-trails in the directed graph. A trail $X \leftrightharpoons Z \leftrightharpoons Y$ is active if influence can flow from $X$ to $Y$ via $Z$.

The first example consists in showing how \textbf{P(deployability)} is influenced by \textbf{available} because there is an active trail between the two variables and there is no evidence or V structure that can break it.

Then, it can be shown that \textbf{starter} in the evidence behaves as a blocking node breaking an active trail between the two aforementioned variables.

In both cases there is a flow of influence because the graph is \textbf{multiply connected} i.e. there is more than one trail which connects two nodes.\newline

Active trails are shown in figure \ref{fig:first_active_trail}

\begin{figure}[h]
    \centering
    \includegraphics[width=0.45\textwidth]{assets/img/active_trail_1-1.PNG}
    \includegraphics[width=0.45\textwidth]{assets/img/active_trail_1-2.PNG}
    \caption{Active trails between available and deployability}
    \label{fig:first_active_trail}
\end{figure}
\newpage

The second example consists in showing conditional independencies between variables: \textbf{starter} and \textbf{penalty_kicker} break the two possible active trails between \textbf{available} and \textbf{deployability}. This is compliant with the \textbf{d-separation principle}, that allows us to determine whether a set X of variables is independent of another set Y, given a third set Z: if there is no active trail between two variables X and Y, then X and Y are d-separated. Thus:

\begin{center}
    \[P \models (available \perp deployability|starter,penalty\_kicker)\]
\end{center}

This means that adding \textbf{available} to the evidence gives no additional information to the query. This can be proved also comparing the two probability distributions and showing that for all combinations of values they provide the same results.
Comparison is shown in figure \ref{fig:broken_trails}

\begin{figure}[h]
    \centering
    \includegraphics[width=0.45\textwidth]{assets/img/active_trail_2-1.PNG}
    \includegraphics[width=0.45\textwidth]{assets/img/active_trail_2-2.PNG}
    \caption{Broken active trails}
    \label{fig:broken_trails}
\end{figure}

In the third example we are trying to understand whether a \textbf{score range} between 7-9.5 could be due to the fact that the player made a goal or not.

It can be shown also in this case that there is a \textbf{direct cause} from \textbf{goal} to \textbf{score_range}. This means that exists an active trail between the two variables.

Looking at the probability distribution, it can be understood how the goal could be a possible explanation to the received score with a probability around 58 \%.

The next step is to understand whether the goal could be a good explanation even if the player got a yellow card. In this case we put in the evidence also the \textbf{yellow card} and this variable influences the goal because \textbf{score_range} allows the activation of a V-structure, thus there is an active trail between \textbf{goal} and \textbf{yellow_card}.

An interesting thing is to highlight how the probability to have made a goal increases, probably because it is very difficult that a player can get a good score with a yellow card without a goal.
Active trail is shown in figure \ref{fig:active_with_V_structure}

\begin{figure}[h]
    \centering
    \includegraphics[width=0.70\textwidth]{assets/img/active_trail_3.PNG}
    \caption{Active trail with V structure}
    \label{fig:active_with_V_structure}
\end{figure}

\section{Independencies}\label{sec:section-43}

The V-structure between score_range and difficulty match allows to understand the independence between goal and difficulty match because this kind of structure breaks the only possible active trail between the two variables. In our domain this is quite reasonable becouse a good player can score a goal indipendetly by the opposing team. It has been shown in two different ways:
\begin{center}
    $P \models (goal \perp difficulty\_match)$
\end{center}

It has been shown in two different ways:
\begin{enumerate}
    \item Showing that \textbf{P(difficulty_match|goal) = P(difficulty_match)} as shown in figure \ref{fig:prob_distributions}
    \item Showing that there is no \textbf{active trail} in the graph between the two variables as showed in figure \ref{fig:independence}
\end{enumerate}

\begin{figure}[h]
  \centering\begin{minipage}[b]{0.45\textwidth}
    \includegraphics[width=\textwidth]{assets/img/prob_distributions.PNG}
\caption{Comparison between probability distributions}
\label{fig:prob_distributions}
  \end{minipage}
  \hfill\begin{minipage}[b]{0.45\textwidth}
    \includegraphics[width=\textwidth]{assets/img/Independence.PNG}
    \caption{Independence between goal and difficulty match}
\label{fig:independence}
  \end{minipage}
\end{figure}

%----------------------------------------------------------------------------------------

%----------------------------------------------------------------------------------------
%	CHAPTER 5
%----------------------------------------------------------------------------------------
\chapter{Inference}\label{chap:chapter-5}

\section{Exact Inference}\label{sec:section-51}

The query considered for a deeper analysis with exact inference is the probability of the player to be deployed given that he is a starter, more formally

\[ P(Deployability|starter) \]

There are different ways to solve with exact inference this query.
The first method, which is not the best one, consists of using marginalization property and global semantics to decompose the probability as the product of different probabilities iterating over the variables which are neither query variables nor evidence ones. This method is called inference by enumeration.
For previous query write the whole decomposition would be too chaotic and dispersive, thus it will be provided a sketch of the steps to follow

\[ \alpha P(Deployability,starter) \]

\[ \alpha \sum_{hidden} P(Deployability,starter, hidden) \]

\[ \alpha \sum_{hidden} P(Deployability|difficulty \,match, score\, range) P(starter|available)P(hidden|parents(hidden)) \]

The query is solved using a depth first search which turns out to be not so efficient because same terms appearing in different branches are computed several times.

Better results can be obtained using a sort of dynamic programming which allows to store intermediate results avoiding repeated calculations. There are different methods in this category, the one that has been used to execute the query is called variable elimination and consists of the following steps:

\begin{itemize}
    \item substituting each probability in the first formula with a factor which is a matrix built considering variables over which there is the summation. For example:

    \[ P(Deployability|difficulty\,match,score\,range) \]

    will become $f_n(Deployability, Difficulty\,match, Score\,range)$

    \item Then, in right-to-left order factors are multiplied (element-wise) getting new simplified factors which allow to get an intermediate result and saving time and space for computations.

\end{itemize}

Different ordering of the variables can be tried but as heuristic a good one consists of eliminating whichever variable minimizes the size of the next factor to be constructed.
It means to eliminate all variables which are ancestors neither the query variable nor evidence ones nor d-separated from both of them.\newline\newline
In our query there are not variables that can be eliminated because starting from deployability it is possible to reach all ancestors.
\newline

Variable elimination algorithm can be executed using different heuristics to order elimination variables. Heuristics adopted in pgmpy are the followings:

\begin{itemize}
    \item MinFill: the number of edges that need to be added to the graph due to its elimination.
    \item MinNeighbors: the number of neighbors it has in the current graph.
    \item MinWeight: the product of weights, domain cardinality, of its neighbors.
    \item WeightedMinFill: the sum of weights of the edges that need to be added to the graph due to its elimination, where a weight of an edge is the product of the weights, domain cardinality, of its constituent vertices.
\end{itemize}

Considering the query:

\begin{center}
    $P(deployability|starter=True)$
\end{center}

it can be shown that query results using previously mentioned heuristics are the same but we have better time performance using MinWeight.

Following table shows different results and orderings.\newline

\adjustbox{max width=\columnwidth}{
 \begin{tabular}{||c c c ||}
 \hline
 Heuristic & Ordering & Time \\ [0.5ex]
 \hline\hline
 MinFill & [red_card, score_range, home_match, difficulty_match, goal, yellow_card, time_range, penalty_kicker, available, assist] & 0.068 s \\
 \hline
 MinNeighbors & [home_match, available, difficulty_match, penalty_kicker, red_card, time_range, goal, yellow_card, assist, score_range] & 0.035 s \\
 \hline
 MinWeight & [available, home_match, penalty_kicker, difficulty_match, time_range, score_range, red_card, goal, yellow_card, assist]	 & 0.031 s\\
 \hline
 WeightedMinFill & [home_match, available, penalty_kicker, difficulty_match, time_range, score_range, red_card, goal, yellow_card, assist] & 0.034 s \\ [1ex]
 \hline
\end{tabular}
}

A problem of exact inference with variable elimination is that it is NP-hard in the case of multiply connected networks (i.e. there are multiple trails to connect two variables) as the network of this project.

\section{Approximate Inference}\label{sec:section-52}
Starting from the results provided by the exact inference, using the variable elimination method, it is possible to analyze and compare the behavior of three approximate inference methods: the rejection sampling, the likelihood weighting and the Gibbs sampling all of them implemented using the pgmpy library.

To observe how these inference methods behave in different situations, we tested 4 interesting queries:

\begin{enumerate}
    \item$P(goal|assist )$
    \newline
    The result of this query (see Fig. \ref{fig:query1results}) highlights that a player has a probability of around 30\% of make goal when he has already done an assist. Starting from the fact that the probability of a player to score a goal, without any evidence, is around 25\% we can deduce that the probability increase due to the more comfortable approach of the forward into the match.

    \item $P(penalty\_kicker\ | available, goal,\neg starter)$
    \newline
    This query shows (see Fig. \ref{fig:query2results}) that whether a player scored a goal starting the match from the bench, there is a probability of 53\% that he is the penalty kicker of the team. This result highlights that it is quite probable that the goal is the consequence of a marked penalty.
\end{enumerate}
    \textbf{Analysis of sampling methods:}
        \newline
        As we can see from \ref{fig:query1results} and \ref{fig:query2results} since the second query has more evidence of the first one the time of the rejection sampling dramatically increase. On the contrary, likelihood weighting and Gibbs sampling maintain the same sampling times. Indeed, the method of rejection sampling is implemented by generating samples from forward sampling and rejects those that do not match our evidence and keep doing until it has as sample as the sample size.
        Moreover, Gibbs sampling appears poorly when the sample sizes are not big. This is due to the implementation of the sampling method in pgmpy library since it does not allow to explicit the evidence variables. For this reason, a lot of samples that are not compatible with evidence are rejected.

    \begin{figure}[h]
      \centering\begin{minipage}[b]{0.45\textwidth}
        \includegraphics[width=\textwidth]{assets/img/query1prob.png}
      \end{minipage}
      \hfill\begin{minipage}[b]{0.45\textwidth}
        \includegraphics[width=\textwidth]{assets/img/query1time.png}
      \end{minipage}
    \caption{Probability values and sampling times of $P(goal|assist )$}
    \label{fig:query1results}
    \end{figure}

    \begin{figure}[h]
      \centering\begin{minipage}[b]{0.45\textwidth}
        \includegraphics[width=\textwidth]{assets/img/query2prob.png}
      \end{minipage}
      \hfill\begin{minipage}[b]{0.45\textwidth}
        \includegraphics[width=\textwidth]{assets/img/query2time.png}
      \end{minipage}
    \caption{Probability values and sampling times of $P(penalty\_kicker | available, goal,\neg starter)$}
    \label{fig:query2results}
    \end{figure}

\begin{enumerate}
\addtocounter{enumi}{2}
    \item$P(deployability | yellow\_card, assist)$
    \newline
  The result of the query it is quite interesting because the malus of the yellow card (-0.5) doesn't influence the deployability. This happens because, nevertheless the player has received an admonition he played a good game with an assist (bonus +1), so it is a good choice to deploy him in lineup.

    \item $P(goal | time\_range = 0-15)$
    \newline
    The result of this query is quite obvious, a player need more minutes to score a goal, so if you are looking for a high score in your Fantacalcio team and you know that the forward could play only few minutes, it is better not to deploy him.
\end{enumerate}

\textbf{Analysis of sampling methods:}
    \newline
    As we can see from \ref{fig:query3results} and \ref{fig:query4results} the errors of likelihood weighting and Gibbs sampling are higher in these two queries with respect to previous two. This happens because they converge really slow with probabilities close to 0 (like in the forth query) and 1 (like in the third query)

\begin{figure}[h]
  \centering\begin{minipage}[b]{0.45\textwidth}
    \includegraphics[width=\textwidth]{assets/img/query3prob.png}
  \end{minipage}
  \hfill\begin{minipage}[b]{0.45\textwidth}
    \includegraphics[width=\textwidth]{assets/img/query3error.png}
  \end{minipage}
\caption{Probability values and absolute error trend of $P(deployability | yellow\_card, assist)$}
\label{fig:query3results}
\end{figure}

\begin{figure}[h]
  \centering\begin{minipage}[b]{0.45\textwidth}
    \includegraphics[width=\textwidth]{assets/img/query4prob.png}
  \end{minipage}
  \hfill\begin{minipage}[b]{0.45\textwidth}
    \includegraphics[width=\textwidth]{assets/img/query4error.png}
  \end{minipage}
\caption{Probability values absolute error trend of $P(goal | time\_range = 0-15)$}
\label{fig:query4results}
\end{figure}

%----------------------------------------------------------------------------------------

%----------------------------------------------------------------------------------------
%	CHAPTER 6
%----------------------------------------------------------------------------------------
\chapter{Conclusion and future works}\label{chap:chapter}
The results provided in this paper are reasonable admissible but since we tried to make inference about a complete stochastic domain, it found out to be really difficult to obtain good results because it was not always possible to take into account the enormous amount of variables that effectively affect the domain of our analysis and construct a model on it.
A possible different analysis based on our model could be to extend the dataset of players, considering not only forwards but also midfielders and defenders in order to prove whether the model could be a good base to develop a real software that helps fantasy managers to solve their doubts in line up their fantasy football formation.

%----------------------------------------------------------------------------------------

%----------------------------------------------------------------------------------------
%	REFERENCES
%----------------------------------------------------------------------------------------
{\let\clearpage\relax\par \printbibliography}

\end{document}

max_stars_repo_name: SalvoPisciotta/FantaBayesianNet

max_issues_repo_name: SalvoPisciotta/FantaBayesianNet

max_forks_repo_name: SalvoPisciotta/FantaBayesianNet


text:
% !TEX TS-program = pdflatexmk
\documentclass{article}

\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage[a4paper, total={5.5in, 8in}]{geometry}
\usepackage{amsthm}
\usepackage{natbib}

\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}[definition]
\newtheorem{remark}{Remark}

\newtheorem{theorem}[definition]{Theorem}
%\newtheorem{theorem}{Theorem} %This is the example presented in the introduction but it has the additional parameter [section] that restarts the theorem counter at every new section.
\newtheorem{corollary}{Corollary}[definition] %A environment called corollary is created, the counter of this new environment will be reset every time a new definition environment is used.
\newtheorem{lemma}[definition]{Lemma} %In this case, even though a new environment called lemma is created, it will use the same counter as the definition environment.

\title{Exchangeable Array and Random Graph}
\date{\today}
\author{Dongwoo Kim\\ANU}

\begin{document}

\maketitle

\section{Exchangeable array for graph}
\begin{definition}[Jointly exchangeable array] A random 2-array $(X_{ij})_{i,j\in \mathbb{N}}$
is jointly exchangeable if
\begin{align}
(X_{ij}) \stackrel{d}{=} (X_{\pi(i)\pi(j)}) \quad \text{for } i,j \in \mathbb{N}^2
\end{align}
for any permutation $\pi$ of $\mathbb{N}$.
\end{definition}

\begin{theorem}[\label{aldous_hoover}Aldous, Hoover Theorem \citep{aldous1981representations,hoover1979relations}] A random 2-array $(X_{ij})_{i,j\in \mathbb{N}}$
is jointly exchangeable if and only if there exists a random measurable function $f:[0,1]^3 \rightarrow \mathcal{X}$ such that
\begin{align}
(X_{ij}) \stackrel{d}{=} (f(U_i, U_j, U_{ij})),
\end{align}
where $(U_{i})_{i \in \mathbb{N}}$ and $(U_{ij})_{ij\in\mathbb{N}^2}$ with $U_{ij} = U_{ij}$ are a sequence and matrix of i.i.d. Uniform[0,1] random variables.
\end{theorem}
If the function $f$ is a symmetric in its first two argument, then the matrix $X$ is symmetric. In general, however, it does not need to be a symmetric (e.g. directed graph).

For the undirected graph case $\mathcal{X} = \{0,1\}$, the theorem can be simplified further through a random function called \textit{graphon} $W:[0,1]^2 \rightarrow [0,1]$, symmetric in its arguments, where
\[ f(U_i, U_j, U_{ij}) =
  \begin{cases}
    1       & \quad U_{ij} < W(U_i, U_j)\\
    0  & \quad \mathrm{otherwise}\\
  \end{cases}
\]

\begin{example}[Random function prior on function $f$ \citep{Lloyd2013}] Lloyd et al. use a Gaussian process prior to define function $f$ for an undirected graph. They define $W(U_i, U_j) = \phi(\Theta(U_i,U_j))$ where $\phi$ is a logistic function, and $\Theta(\cdot, \cdot)$ is a continuous function with a Gaussian process prior. Thus, the probability of edge between node $i$ and $j$ is equal to Bernoulli$(\phi(\Theta(U_i,U_j)))$.
\end{example}

\begin{example}[Stochastic block model] The stochastic block model is another generative model for random graphs. The model assumes that each node belongs to a community and there is a edge probability between communities. Then the probability of edge between two different nodes are determined by the edge probability between communities where the two nodes belong. In stochastic block model with Aldous, Hoover Theorem, $U_i$ and $U_j$ determine the communities of node $i$ and $j$, respectively, and $U_{ij}$ determines the existence of edge between node $i$ and $j$ as done in graphon. The stick breaking process is one way to partition unit length interval into an infinite number of communities \citep{sethuraman1994constructive}.
\end{example}

\begin{definition}[Sparse Graph]
Let the number of nodes in a graph be $n$. The graph is sparse if the number of edges are $o(n^2)$ or dense if the number of edges are $\Theta(n^2)$.
\end{definition}

\begin{remark}[Graphon is trivially dense]
Every graph represented by graphon $W$ are either empty or dense. The asymptotic proportion of edges is $p = \frac{1}{2}\int W(x, y) dxdy$ and the graph is hence either empty $(p=0)$ or dense (since $O(pn^2) = O(n^2)$).
\end{remark}

In \citep{Lloyd2013}, the authors place a Gaussian process prior over graphon $W:[0,1]^2 \rightarrow \mathbb{R}$ and transform the output through the logistic function to model the edge probability between nodes.

For the undirected graph case where $X_{ij} = X_{ji}$, one can sample upper triangle of the adjacency matrix, and use the same result for the lower triangle. For the directed graph case, however, the adjacency matrix is no longer symmetric, also, by the theorem, both $X_{ij}$ and $X_{ji}$ rely on single parameter $U_{ij}$. Therefore, one should jointly sample ($X_{ij}$, $X_{ji}$) together from three parameters $U_{i}, U_{j}, U_{ij}$, which means $X_{ij}$ and $X_{ji}$ are not conditionally independent. In addition, asymmetric graphon $W$ could be employed for directed random graph. However, \citep{Cai2015} show that assymetric graphon is inappropriate to impose certain structures on a graph such as the partial ordering and propose a class of priors for directed graphs.

\section{Exchangeable array for matrix factorisation}
Jointly exchangeable array assume that both rows and columns index the same entities. However, the assumption does not hold for the general matrix where rows and columns represent different entities (e.g. users and items in recommendation system).

\begin{definition}[Separately exchangeable array]A random 2-array $(X_{ij})_{i,j\in \mathbb{N}}$ is separately exchangeable if
\begin{align}
(X_{ij}) \stackrel{d}{=} (X_{\pi(i)\sigma(j)}) \quad \text{for } i,j \in \mathbb{N}^2
\end{align}
for any permutation $\pi$ and $\sigma$ of $\mathbb{N}$.
\end{definition}

\begin{corollary}[\label{sea}Separately exchangeable array] A random 2-array $(X_{ij})$ is separately exchangeable if and only if there exists a random measurable function $f:[0,1]^3 \rightarrow \mathcal{X}$ such that
\begin{align}
(X_{ij})  \stackrel{d}{=} (f(U_i, U_j, U_{ij})),
\end{align}
where $(U_i)_{i\in \mathbb{N}}$, $(U_j)_{j\in \mathbb{N}}$, and $(U_{ij})_{ij\in \mathbb{N}^2}$ are i.i.d. Uniform[0,1] random variables.
\end{corollary}
In the separately exchangeable array case, function $f$ is not a symmetric in its first two arguments.

\begin{example}[Probabilistic matrix factorisation (PMF) \citep{Salakhutdinov2008}]
PMF is one instantiation of Corollary \ref{sea}. Let the generative process of PMF be
\begin{align}
U_i &\sim \mathcal{MN}_d(0, \Sigma_U)\\
V_j &\sim \mathcal{MN}_d(0, \Sigma_V)\\
X_{ij} &\sim \mathcal{N}(U_i^\top V_j, \sigma_x)
\end{align}
where $\mathcal{MN}_d$ is a $d$-dimensional zero-mean multivariate normal distribution with covariance $\Sigma$. This corresponds to random measurable function
$f(U_i, U_j, U_{ij}) = \Phi_1(U_{ij}; \Phi_d(U_i;0, \Sigma_{U})^\top \Phi_d(U_j;0, \Sigma_{U}), \sigma^2_x)$, where $\Phi_d(\cdot;\mu, \sigma^2)$ is an inverse-CDF of $d$-dimensional multivariate function with mean $\mu$ and variance $\sigma^2$. Note that $\sigma$ here differs from the permutation notation.
\end{example}

\section{Exchangeable array for knowledge graph}

A knowledge graph can be represented as a 3-array tensor $X_{ijk}$, where the first two dimensions represent entities, and the third dimension represent relations. Therefore, $X_{ijk}$ is jointly exchangeable in its first two dimensions, and the third dimension is separately exchangeable to the first two dimensions.

\begin{definition}[$\pi$-exchangeable array for knowledge graph \citep{Orbanz2015}]A random 3-array $(X_{ijk})_{i,j,k\in \mathbb{N}}$ is jointly exchangeable in its first two dimensions and separately exchangeable with the third dimension if
\begin{align}
(X_{ijk}) \stackrel{d}{=} (X_{\pi(i)\pi(j)\sigma(k)}) \quad \text{for } i,j,k \in \mathbb{N}^3
\end{align}
for any permutation $\pi$ and $\sigma$ of $\mathbb{N}$.
\end{definition}

\begin{corollary}[$\pi$-exchangeable array for knowledge graph]
A random 3-array $X_{ijk}$ is jointly exchangeable in its first two dimension and separately exchangeable for the third dimension if and only if there exists a random measurable function $f:[0,1]^7 \rightarrow \mathcal{X}$ such that
\begin{align}
(X_{ijk})  \stackrel{d}{=} (f(U_i, U_j, U_k, U_{ij}, U_{ik}, U_{jk}, U_{ijk})),
\end{align}
where $(U_i)_{i\in \mathbb{N}}$, $(U_k)_{k\in \mathbb{N}}$, $(U_{ij})_{ij\in \mathbb{N}^2}$, $(U_{ik})_{ik\in \mathbb{N}^2}$, and $(U_{ijk})_{ijk\in \mathbb{N}^3}$  are i.i.d. Uniform[0,1] random variables.
\end{corollary}

\begin{remark}[Compositional model \citep{gu2015traversing}] Compositional vector space models cannot be modelled through the exchangeable array theorem because the dependency between triples breaks the exchangeability.
\end{remark}

\begin{example}[Bayesian RESCAL (BRESCAL)] The generative process of BRESCAL with normally distributed output variable $X_{ijk}$ is as follows:
\begin{align}
e_i, e_j &\sim \mathcal{MN}_d(0, \sigma_e^2 I_d)\\
R_k &\sim \mathcal{MN}_{d^2}(0, \sigma_r^2 I_{d^2})\\
X_{ijk} &\sim \mathcal{N}(R_k^\top (e_i \otimes e_j), \sigma_x^2).
\end{align}
Again, we can transform uniform random variables $U_i, U_j, U_k$ to $e_i, e_j, R_k$ via the inverse-CDF of zero-mean multivariate normal distribution. Then $X_{ijk}$ is determined by $U_{ijk}$ via the inverse-CDF of normal distribution with mean $R_k^\top (e_i \otimes e_j)$ and variance $\sigma_x^2$, i.e. $X_{ijk} = \Phi_1(U_{ijk};R_k^\top (e_i \otimes e_j), \sigma_x^2)$. The model is invariant w.r.t the changes in the other uniform variables $U_{ij}, U_{ik}$, and $U_{jk}$.
\end{example}

\section{Sparse exchangeable graph}
\citet{Caron2015} propose a symmetric simple point process on $\mathbb{R}^2_+$ as the edge set of a random graph, and \citet{Veitch2015} formalise the probabilistic symmetry as joint exchangeability of the point process.
\begin{definition}[Jointly exchangeable random measure on $\mathbb{R}^2$] A random measure $\xi$ on $\mathbb{R}^2$ is jointly exchangeable if for every measure preserving transformation $f$ on $\mathbb{R}_+$, we have
\begin{align}
\xi \circ (f \otimes f)^{-1} \stackrel{d}{=} \xi
\end{align}
\end{definition}
\begin{theorem}[\label{thm:kallenjoint}Kallenberg's jointly exchangeable theorem \citep{Kallenberg1990,kallenberg2005probabilistic}] A random measure $\xi$ on $\mathbb{R}^2$ is jointly exchangeable iff it has an almost surely representation
\begin{align}
\xi &= \sum_{i,j} f(\alpha, \vartheta_i, \vartheta_j, \zeta_{i,j})\delta_{\theta_i, \theta_j} \label{eqn:kallenjoint}\\
&+ \sum_{j,k}\{g(\alpha, \vartheta_j, \chi_{jk})\delta_{\theta_j,\sigma_{jk}} + g'(\alpha, \vartheta_j, \chi_{jk})\delta_{\sigma_{jk},\theta_j}\}\\
&+ \sum_{k}\{l(\alpha, \eta_k)\delta_{\nu_k,\nu'_k} + l'(\alpha, \eta_k)\delta_{\nu'_k, \nu}\}\\
&+\sum_j\{h(\alpha, \vartheta_j)(\delta_{\theta_j} \otimes \Lambda) + h'(\alpha, \vartheta_j)(\Lambda \otimes \delta_{\theta_j})\} + \beta\Lambda_D + \gamma \Lambda^2,
\end{align}
for some measurable function $f:\mathbb{R}_+^4 \rightarrow \mathbb{R}_+$, $g,g':\mathbb{R}_+^3 \rightarrow \mathbb{R}_+$, and $l, l', h, h': \mathbb{R}_+^2\rightarrow\mathbb{R}_+$, some collection of independent uniformly distributed random variables $(\zeta_{i,j})$ on $[0,1]$, some independent unit rate Poisson processes $\{(\theta_j, \vartheta_j)\}$ and $\{(\sigma_{ij}, \chi_{ij})\}$ on $\mathbb{R}_+^2$ and $\{(\nu, \nu'_j, \eta_j)\}$ on $\mathbb{R}^3$, and some independent set of random variables $\alpha, \beta, \gamma \geq 0$. $\Lambda$ is Lebesgue measure on $\mathbb{R}_+$, and $\Lambda_D$ is Lebesgue measure on the diagonal of $\mathbb{R}_+^2$.
\end{theorem}

If we only focus on an atomic measure, all terms with the Lebesgue measure have measure zero. The atomic measure will be symmetric if $f$ is symmetric in its the second and third arguments, $g = g'$, and $l=l'$. The atomic measure will be simple if $f, g, g', l,$ and $l'$ are $\{0,1\}$-valued. This random measure is locally finite under certain conditions, and a truncated measure is defined as a Kallenberg exchangeable graph by \cite{Veitch2015}.

Each atomic term in Theorem \ref{thm:kallenjoint} uniquely contributes to a structure of the random measure.

\begin{example}[\label{caron2015}Caron and Fox model]
\cite{Caron2015} propose a simple point process on $\mathbb{R}^2$ as a product measure of a complete random measure. They propose a hierarchical model
\begin{align}
G_0 &= \sum_{i=1}^{\infty} w_i \delta_{\theta_i} & &G_0 \sim \text{CRM}(\rho, \lambda)\\
G &= \sum_{i,j} n_{ij} \delta_{\theta_i, \theta_j} & &G|G_0 \sim \text{PP}(G_0 \otimes G_0)\\
Z &=\sum_{i,j} \min(n_{ij} + n_{ji}, 1)\delta_{\theta_i, \theta_j}, &&
\end{align}
for L\'{e}vy intensity measure $\rho$ and $\lambda$ where $\rho$ is a jump part of the measure.
$Z$ can be directly specified as
\[ p(z_{ij}=1|w) =
  \begin{cases}
    1 - \exp(-2w_iw_j)       & \quad i \neq j\\
    1 - \exp(-w_i^2) & \quad i = j\\
  \end{cases}
\]
This model can be reformulated in the Kallenberg's exchangeable theorem. The CRM $G_0$ can be constructed from a two-dimensional unit-rate Poisson process on $\mathbb{R}_+^2$ by the inverse L\'{e}vy method \cite{ferguson1972representation}. Let $(\theta_i, \vartheta_i)$ be a unit rate Poisson process on $\mathbb{R}_+^2$, and $\rho^{-1}$ be the inverse L\'{e}vy intensity of $\rho$, where $w_i = \rho^{-1}(\vartheta_i)$. The model can be formulated under the representation of Equation \ref{eqn:kallenjoint} as
\[ f(\alpha, \vartheta_i, \vartheta_j, \zeta_{i,j}) =
	\begin{cases}
	1- \exp(-2\rho^{-1}(\vartheta_i)\rho^{-1}(\vartheta_j)) & \quad i \neq j\\
    1 - \exp( \rho^{-1}(\vartheta_i)^2) & \quad i = j\\
	\end{cases}
\]
and $g,g',l,l'=0$.

They show that the resulting graph is sparse if intensity measure $\rho$ is infinite activity, i.e. $\int_{0}^{\infty} \rho(w)dw = \infty$ and dense if the intensity measure is finite activity, i.e. $\int_{0}^{\infty} \rho(w)dw < \infty$.
\end{example}

\begin{example}[Sparse block structured graphs \citep{Herlau2015}]
\end{example}

\begin{example}[Sparse graphs with overlapping communities \citep{Todeschini2016}]
\end{example}

Like \textit{graphon} in exchangeable random array, \citep{Veitch2015} also characterise the space of exchangeable atomic measure in terms of \textit{graphex}.

\begin{theorem}[Graphex \citep{Veitch2015}] Let $\xi$ be a random adjacency atomic measure. Then $\xi$ is jointly exchangeable iff it has a.s. representation
\begin{align}
\xi &= \sum_{i,j}\mathbf{1} [W_\alpha(\vartheta_i, \vartheta_j) \leq \zeta_{i,j}]\delta_{\theta_i, \theta_j} \\
&+\sum_{j,k} \mathbf{1} [\chi_{jk} \leq S(\alpha, \vartheta_j)](\delta_{\theta_j,\sigma_{jk}} +  \delta_{\sigma_{jk},\theta_j}) \\
&+\sum_{k} \mathbf{1} [\eta_{k} \leq I(\alpha)](\delta_{\nu_k,\nu'_k} + \delta_{\nu'_k, \nu_k}),
\end{align}
where $W:\mathbb{R}^3 \rightarrow [0,1]$, $S:\mathbb{R}^2 \rightarrow \mathbb{R}$, and $I:\mathbb{R}\rightarrow\mathbb{R}$, $(\zeta_{i,j})$ are collection of uniform random variable in [0,1], $\{(\theta_i, \vartheta_i)\}$, $\{(\sigma_{jk}, \chi_{jk})\}$, and $\{(\nu_k, \nu'_k, \eta_{k})\}$ are independent unit rate Poisson processes on $\mathbb{R}^2_+$ and $\mathbb{R}^3_+$, and $\alpha$ is an independent random variable on $\mathbb{R}_+$.
\end{theorem}

\begin{example}[Caron and Fox model with graphex] The model in Example \ref{caron2015} can be represented in terms of graphex notation.
\[ W_\alpha(\vartheta_i, \vartheta_j) =
	\begin{cases}
	1- \exp(-2\rho^{-1}(\vartheta_i)\rho^{-1}(\vartheta_j)) & \quad i \neq j\\
    1 - \exp( \rho^{-1}(\vartheta_i)^2) & \quad i = j\\
	\end{cases}
\]

\end{example}

\section{Sparse exchangeable bipartite graph}

\begin{theorem}[Kallenberg's separately exchangeable theorem \citep{Kallenberg1990}] A random measure $\xi$ on $\mathbb{R}^2$ is separately exchangeable iff it has an almost surely representation
\begin{align}
\xi &= \sum_{i,j} f(\alpha, \vartheta_i, \vartheta'_j, \zeta_{i,j})\delta_{\theta_i, \theta'_j} \\
&+ \sum_{j,k}\{g(\alpha, \vartheta_j, \chi_{jk})\delta_{\theta_j,\sigma_{jk}} + g'(\alpha, \vartheta'_j, \chi'_{jk})\delta_{\sigma'_{jk},\theta'_j}\}\\
&+ \sum_{k}l(\alpha, \eta_k)\delta_{\rho_k,\rho'_k} \\
&+\sum_j\{h(\alpha, \vartheta_j)(\delta_{\theta_j} \otimes \Lambda) + h'(\alpha, \vartheta'_j)(\Lambda \otimes \delta_{\theta'_j})\} + \gamma \Lambda^2
\end{align}
for some measurable function $f:\mathbb{R}_+^4 \rightarrow \mathbb{R}_+$, $g,g':\mathbb{R}_+^3 \rightarrow \mathbb{R}_+$, and $l, l', h, h': \mathbb{R}_+^2\rightarrow\mathbb{R}_+$, some collection of independent uniformly distributed random variables $(\zeta_{i,j})$ on $[0,1]$, some independent unit rate Poisson processes $\{(\theta_i, \vartheta_i)\}$, $\{(\theta'_j, \vartheta'_j)\}$, $\{(\sigma_{ij}, \chi_{ij})\}$ and $\{(\sigma'_{ij}, \chi'_{ij})\}$ on $\mathbb{R}_+^2$ and $\{(\rho_j, \rho'_j, \eta_j)\}$ on $\mathbb{R}^3$, and some independent set of random variables $\alpha, \gamma \geq 0$. $\Lambda$ is Lebesgue measure on $\mathbb{R}_+$.
\end{theorem}

\begin{example}[\citep{Caron2012}]
Matrix factorisation for the sparse bipartite graph has been partially discussed in \citep{Caron2012}, although the formal proof of the sparsity is lacking.
\end{example}

\bibliographystyle{apalike}
\bibliography{ref}

\end{document}

ext: tex

max_stars_repo_name: arongdari/sparse-graph-prior

max_issues_repo_name: dongwookim-ml/sparse-graph-prior

max_forks_repo_name: dongwookim-ml/sparse-graph-prior


text:
% corrected LN 83

\subsubsection{FR02: Luxembourgish dataset collection}\label{datasetlux}~\\

To collect the Luxembourgish dataset, the \textit{Teachable
Machine}\cite{teachablemachine} was used. It contains a recorder to create a
dataset consisting of audio files. The recording of the audio files can be set
to $1s$. However, the recorder saves the files in the \textit{.webm} file type.
Therefore, the audio files have to be converted to \textit{.wav} files before
the features can be extracted. The following bash script using the
\textit{ffmpeg} command converts the audio files in a file directory to the
desired file format:

\newpage

\lstset{
  language = Bash,
  literate = {\#\#}{{{\#\#}}}2,
  columns  = fullflexible,
  keepspaces,
}

% \newpage

\lstinputlisting[language=Bash]{sections/technical/fr2/ffmpeg.sh}


text:
\section{Related Work}

This work builds on the idea behind delta-debugging \cite{DD}: test
cases should not contain extraneous information that is not needed to
reproduce failure (or some other behavior, as in more recent work
\cite{icst2014,stvrcausereduce}).  Delta-debugging and slicing
\cite{TCminim} are limited, generally, to producing subsets of the
original test case, not modifying parts of the test to obtain further
simplicity.  We extend this concept by also allowing modification or
re-ordering of actions in a test.  In some cases these changes
allows further reduction of the length of the test case as well.  Some
earlier work in bounded model checking modified counterexamples to use
numerically smaller values \cite{MakeMost} but otherwise did not aim
to simplify or normalize failures.

Normalization is in part motivated by the fuzzer taming \cite{PLDI13}
problem: determining how many distinct faults are present in a large
set of failing test cases.  This is a key problem in practical
application of automated testing.  Previous work on fuzzer taming
\cite{PLDI13} used delta-debugging to reduce some test cases to
syntactic duplicates.

Zhang \cite{SaiSimple} proposed an alternative approach to semantic
test simplification that, like our approach, is able to modify, rather
than simply remove, portions of a test.  However, because Zhang
operates directly over a fragment of the Java language, rather than
using an abstraction of test actions allowed, the set of rewrite
operations performed is highly restricted: no new methods can be
invoked, statements cannot be re-ordered, and no new values are used.
These restrictions limit the approach's ability to simplify tests and
make it inappropriate for  normalization, as opposed to simplification.  The approach also performs little
syntactic normalization: e.g., it does not even force a test to use
fixed variable names when variable name is irrelevant.  CReduce
\cite{CReduce} performs some simple normalization as part of a complex
test-case reduction scheme for C code, and the peephole-rewrite scheme
used in CReduce is also an inspiration for the approach taken by our
normalizer.

Work on producing readable tests \cite{Guava,Readable} is also
related, in that it aims to ``simplify'' tests in a way that goes
beyond measuring test length.  Work on readable tests is primarily
intended to assist debugging in  terms of human-factors, while our
normalization and generalization aims to increase the information
density of a test (potentially increasing readability as well), and to address the fuzzer taming problem.  The approaches are
completely orthogonal: our normalized tests could be altered to
improve readability by these methods.

The most closely related work to our generalization efforts is Pike's
SmartCheck \cite{SmartCheck}.  SmartCheck targets algebraic data in
Haskell, and offers an interesting alternative approach to reduction
and generalization.  Test case generalization is also akin to dynamic invariant generation,
in that it informs the user of invariants over a series of test
executions \cite{Daikon}.  The only other work we are aware of that is
similar to generalization concerns essential and accidental aspects of
model checking counterexamples \cite{FreeWill,MakeMost,SPIN03}.


text:
%!Mode:: "TeX:UTF-8"

\section{Socket Error Handling}

\href{http://my.oschina.net/costaxu/blog/127394}{几种TCP连接中出现RST的情况}

\href{http://russelltao.iteye.com/blog/1405349}{从TCP协议的原理来谈谈rst复位攻击}

\subsection{graceful shutdown of sockets}

 It is important to distinguish the difference between \emph{shutting down a
 socket connection} and \emph{closing a socket}.

Shutting down a socket connection involves an exchange of protocol messages between the two endpoints,
hereafter referred to as a shutdown sequence.
Two general classes of shutdown sequences are defined: graceful and abortive (also called hard).
In a graceful shutdown sequence, any data that has been queued, but not yet transmitted can be sent prior to the connection being closed.
In an abortive shutdown, any unsent data is lost.
The occurrence of a shutdown sequence (graceful or abortive) can also be used to provide an FD_CLOSE indication to the associated applications signifying that a shutdown is in progress.

Closing a socket, on the other hand, causes the socket handle to become
deallocated so that the application can no longer reference or use the socket in any manner.

When you have finished using a socket, you can simply close its file descriptor with close.
If there is still data waiting to be transmitted over the connection, normally close tries to complete this transmission.
You can control this behavior using the SO\_LINGER socket option to specify a timeout period.
You can also shut down only reception or transmission on a connection by calling shutdown

max_stars_repo_name: truckli/technotes

max_issues_repo_name: truckli/technotes

max_forks_repo_name: truckli/technotes


text:
\subsection{Evaluation Procedures}

One of the go-to~\cite{szegedy2014intriguing, kannan2018adversarial} datasets when it comes to
testing defenses is MNIST~\cite{lecun}. Modern papers~\cite{kannan2018adversarial,
tramèr2020ensemble} use ImageNet~\cite{ILSVRC15} as a training/assessment database. However we did
not get to considering ImageNet due to deadlines. So, we kept our evaluation to MNIST\footnote{MNIST
was suggested by Ali Varamesh as well; he was inspired by \cite{szegedy2014intriguing} and
\cite{goodfellow2015explaining}}. This dataset involves 70,000 images, 60,000 of which are meant for
training, and 10,000 for testing. We chose 4,200 of the 60k as validation images (used for early
stopping), and 55,800 used for the optimization procedure. The validation dataset was not subject to
an adversary. Moving on, each image is 28 pixels wide and tall, with a single channel that
represents grayscale data. The maximum value of a pixel is 255 (with the minimum at 0); however,
unlike what is common in imagery, 255 represents black, and decreasing values cause increasing
whiteness. This is an important point: \cite{szegedy2014intriguing}, for example, understandably,
has 0 and 255 be the black and white, respectively. In order to be consistent with testing, we
followed their assumption and did this same. Following \cite{szegedy2014intriguing}, in which they
claim to have trained their networks for perfect \textit{training set} classification, we
unsuccessfully tried to do the same, but got close\footnote{We had seen a reference that did not
achieve this either, implying that we are not alone and this might be normal, but have lost track of
the reference}.

We chose the ``FC-100-100-10'' network from \cite{szegedy2014intriguing} as our test network.
However, it was necessary in some cases to modify the network as Pairwise Difference and Angular are
not standard neurons. Further, in the latter case, we didn't use an activation at all; this is due
to cosine having curvature and putting out values between -1 and 1 (note that these values are
actually scaled depending on the value of its denominator constant). For Pairwise Difference, we
used sigmoid as the final output of the layer. Because FC-100-100-10 is fully-connected, this meant
that both Pairwise Difference and Angular took as input the output of the last layer or the image
itself. Finally, the Pairwise Difference (which was only used for the first layer due to its
pixel-oriented nature) and Angular-based networks used Batch Renormalization~\cite{ioffe2017batch},
and we trained a normal FC-100-100-10 network with Batch Renormalization for the purposes of an
ablation study (as we had found in the past that Batch Normalization~\cite{ioffe2015batch} acted as
a defense itself). In fact, the results for the network outside of ablation are interesting from an
adversarial standpoint, so we include them for that reason as well.

Our complete implementation, found at \cite{mycode}[Friendly], used Chainer~\cite{tokui2019chainer,
language, 2020NumPy-Array, cupy_learningsys2017}. The training procedures outside of what has been
described were very straightforward. We used momentum-based Stochastic Gradient Descent, and
learning rates varied to fit the model more appropriately; momentum was kept the same for all
models, as well as the batch size (20). The main reason for such a small number is that Pairwise
Difference can use up a lot of memory, and we thought it fair that all networks use the same batch
size for proper comparison. Early stopping was also employed, but none of our networks ever hit its
20 epoch limit (based on validation set performance) during the 100 epoch hard ``deadline'', so to
speak. Prediction loss was based on mean squared error, and it was formulated as
\[
    \frac{1}{s} \sum_{i=1}^{s} (\mathbf{c}_i - \mathbf{o}_i)^T (\mathbf{c}_i - \mathbf{o}_i)
\]
where $s$ is the number of samples in the batch, $\mathbf{c}$ is the correct confidence vector
(a.k.a.\ one-hot), and $\mathbf{o}$ is the outputs of the network for sample $i$. In the case of the
network whose derivative is penalized, that penalty is given a weight of 0.5, while the mean squared
error term has weight 1.0. See table \ref{settings} for the full list of hyperparameter settings
that vary between networks. Note that we tried only to follow through mostly with point 2 and
partially with point 1 in \ref{oggafsoscdtae}; time prevented us from exhausing all three points.
Specific to point 1, we do not achieve the properties ``any compelling threat model should at the
very least grant knowledge of the model architecture, training algorithm, and allow query
access''~\cite{athalye2018obfuscated}[§ 6.1] and ``[it] is not meaningful to restrict the
computational power of an adversary artificially (e.g., to fewer than several thousand attack
iterations)''~\cite{athalye2018obfuscated}[§ 6.1].
\begin{table}[th]
    \begin{center}
        \begin{tabular}{| c | c | c | c | c | c | c |}
            \hline
                                  &     S       &     RS      &   A     &     GMR     &      GMRES        &   PD     \\
            \hline
            Batch Renormalization &     no      &     yes     &   yes   &     no      &        no         &  yes     \\
            Activation function   &   sigmoid   &   sigmoid   &   N/A   &   sigmoid   &  Elastic Sigmoid  & sigmoid  \\
            Learning rate         &    0.002    &    0.002    & 0.0002  &    0.0009   &      0.002        &  0.002   \\
            \hline
        \end{tabular}
    \end{center}
    \caption{``S'' stands for ``Standard'', ``RS'' for ``Renormalized Standard'', ``A'' for
             ``Angular'', ``GMR'' for GMR, ``GMRES'' for the addition of Elastic Sigmoid to GMR, and
             ``PD'' for ``Pairwise Difference''}
    \label{settings}
\end{table}
As is stated in \cite{athalye2018obfuscated}, it is important to conduct tests using a separate
network for generating adversarial examples due to ``gradient masking'' (as a reminder, this is an
effect where the trained network can handle attacks that use the network's gradient, while not being
able to handle other kinds of attacks; this author only knows of gradient-based attacks which use a
different network, but there may be something he is missing). As a result, they recommend black-box
attacks, where attacks are performed not using any internal values (such as the gradient) from the
network being tested. As a result, we also show black-box results where we train
another\footnote{~\cite{madry2019deep, szegedy2014intriguing} are the inspirations for ``another''}
original, non-protected network provides the adversarial examples to each of the defended networks.
The results on the MNIST test set can be found in table \ref{defensiveproficiency}. We followed
\cite{madry2019deep} and used the $[0, 255]$ equivalent (77) of the 0.3 (out of 1.0) $L_\infty$
noise that they chose. We use $L_{\infty}$ as it is used throughout the literature
(\cite{goodfellow2015explaining, madry2019deep, tramèr2020ensemble}, etc) and is the easiest to
program for. To disclose discrepancies in performance under normal circumstances, we present table
\ref{clean}. All testing was performed \textit{not} using the values Batch Renormalization learned
(which turns it into Batch Normalization~\cite{ioffe2015batch}, according to \cite{ioffe2017batch}[§
3]) as we had very strange (at least from the perspective of our knowledge of Batch Renormalization)
performance issues otherwise; this issue may be the author's fault, but we did not get to resolving
it.

\begin{table}
    \begin{center}
        \begin{tabular}{| c | c | c | c | c | c | c |}
            \hline
                             &      S      &    RS     &    A     &   GMR     &   GMRES   &   PD     \\
            \hline
            White-box (FGSM) &  46.16\%    &  43.30\%  &  0.53\%  &  37.67\%  &  36.98\%  &  32.20\% \\
            Black-box (FGSM) &  45.28\%    &  45.27\%  &  56.35\% &  43.24\%  &  44.70\%  &  49.87   \\
            \hline
        \end{tabular}
    \end{center}
    \caption{Performance of each network when it comes to black-box and white-box attacks.
             Table \ref{settings}'s caption has the meaning of the top-row acronyms.}
    \label{defensiveproficiency}
\end{table}

\begin{table}
    \begin{center}
        \begin{tabular}{| c | c | c | c | c | c |}
            \hline
            S        &     RS    &     A     &   GMR    &   GMRES   &   PD     \\
            \hline
            95.86\%  &  97.80\%  &  85.40\%  &  96.09\% &  96.72\%  &  95.91\% \\
            \hline
        \end{tabular}
    \end{center}
    \caption{Same layout as table \ref{defensiveproficiency}, but the networks were not attacked.}
    \label{clean}
\end{table}

\subsection{Outcomes}

The results turned out to be poor. It is questionable whether or not we can make any claims
whatsoever. Angular's adversarial performance was just bad (even relative to a normal network
without defenses) when up against a white-box attack, a surprising find. It did do pretty well for
the black-box equivalent, but, again, its performance in table \ref{clean} makes this network nearly
useless considering that most scenarios in real life will not be adversarial. Further, such
comparisons are not fair because Angular is not in the same performance ``state'' as the other
networks; this is why ~\cite{szegedy2014intriguing} tries to keep performance across networks the
same. If we were to actually get the angular network's accuracy up enough, it could be that the
black-box benefits would disappear. It also turned out that there was no point to ablation because
there were no benefits of using Batch (Re)normalization. Speculation about the results can be found
in \ref{analysis}.

\subsection{Analysis}
\label{analysis}

The performance of an Angular-based network is simultaneously surprising and possibly easy to
explain. The first rationale could be that we did not pick an adequate constant to nullify the
aforementioned issue of many of zero-length vectors. None of these vectors actually ended up a zero
because each of them contained the whole image (a vector with all-zero values would contain no
number pixels), but the constant may cause issues regardless if not chosen properly. However, a more
likely scenario is that the scaling of the gradient with the addition of more elements is not as
good as hoped. As stated previously, ideally the gradient of each element in the input vector of an
Angular neuron contributes a normalized amount such that all partial derivatives in the vector add
up to, roughly speaking, the same value as when using a small patch as input. Such a neuron would
not be too dissimilar from Angular, but coming up with the formulation that we would want probably
entails integrating from the derivative that we want. We may even be able to drop normalizing the
weight vector by dividing it by $\left\| \mathbf{w} \right\|$ entirely, seeing as it is held
constant at time of attack. Though hardly fleshed-out, we would need to integrate something similar
to $\frac{\mathbf{a}}{\left\| \mathbf{a} \right\|_1}$ (this does not involve the weight vector, so
this integration is more complicated than what is shown).

As far as Pairwise Difference, the most likely explanation is that most pairs involve a comparison
between two zero-value pixels, which puts each subtraction squarely in the middle of the sigmoid
used for comparison. As a result, even FGSM using a max-norm of just 10 has a reduced 34.50\%
accuracy. It is possible that treating each comparison as a miniature neuron with two weights (or
even a bias) could be a fix for this issue because, as previously stated, this would still attempt
to address the issue of large vectors in dot products.

Renormalization appears to have been worse for the original network, which actually checks out. This
is due to the fact that \cite{ioffe2015batch} states that Batch Normalization~\cite{ioffe2015batch}
(Renormalization's predecessor) aims to keep the input to the activation function centered near, and
tight around, the origin (at least in the case of the sigmoid function) which is where the strongest
gradients lie. While this is a blessing for optimization during training, it's also a blessing for
any attacker who uses gradients in their attacks. It is possible that one conclusion that should be
drawn from this is that a Batch Renormalization-trained network in Batch Normalization mode appears
to be detrimental from a defensive standpoint.

Gradient Magnitude Reduction's lack of usefulness is concerning. The theory behind GMR, at least
intuitively, makes sense, and this may just come down to using the wrong weight in the loss term
involving the gradient w.r.t.\ the image. However, an important point to raise is that GMR does not
make any guarantees about reducing the gradient in any location other than at the point at which the
gradient is calculated. It may help to penalize even the second derivative (as it has a hand in
determining the first derivative in other locations), but the Universal Approximation
Theorem\cite{HORNIK1989359} makes it possible that even the second derivative may not be enough
seeing as there may be a valid third derivative, fourth derivative, etc. It is relevant to note that
adversarial training side steps this issue by essentially reducing the gradient at points far
(relatively speaking) from the normal datapoint, forcing (according to the evidence) all derivatives
(not just the first) to be close to zero. Elastic Sigmoid paired with GMR was ineffective as well,
for the same reasons.

Clearly, we have good reason to look further into all the defenses proposed; future work will need
to be responsible for doing so. We also need to consider Projected Gradient
Descent~\cite{madry2019deep} as an attack, as recommended by \cite{athalye2018obfuscated} because of
its effectiveness.

max_stars_repo_name: benvcutilli/CountingPlusFriendly

max_issues_repo_name: benvcutilli/CountingPlusFriendly

max_forks_repo_name: benvcutilli/CountingPlusFriendly


text:
\section{\module{stringprep} ---
         Internet String Preparation}

\declaremodule{standard}{stringprep}
\modulesynopsis{String preparation, as per RFC 3453}
\moduleauthor{Martin v. L\"owis}{martin@v.loewis.de}
\sectionauthor{Martin v. L\"owis}{martin@v.loewis.de}

When identifying things (such as host names) in the internet, it is
often necessary to compare such identifications for
``equality''. Exactly how this comparison is executed may depend on
the application domain, e.g. whether it should be case-insensitive or
not. It may be also necessary to restrict the possible
identifications, to allow only identifications consisting of
``printable'' characters.

\rfc{3454} defines a procedure for ``preparing'' Unicode strings in
internet protocols. Before passing strings onto the wire, they are
processed with the preparation procedure, after which they have a
certain normalized form. The RFC defines a set of tables, which can be
combined into profiles. Each profile must define which tables it uses,
and what other optional parts of the \code{stringprep} procedure are
part of the profile. One example of a \code{stringprep} profile is
\code{nameprep}, which is used for internationalized domain names.

The module \module{stringprep} only exposes the tables from RFC
3454. As these tables would be very large to represent them as
dictionaries or lists, the module uses the Unicode character database
internally. The module source code itself was generated using the
\code{mkstringprep.py} utility.

As a result, these tables are exposed as functions, not as data
structures. There are two kinds of tables in the RFC: sets and
mappings. For a set, \module{stringprep} provides the ``characteristic
function'', i.e. a function that returns true if the parameter is part
of the set. For mappings, it provides the mapping function: given the
key, it returns the associated value. Below is a list of all functions
available in the module.

\begin{funcdesc}{in_table_a1}{code}
Determine whether \var{code} is in table{A.1} (Unassigned code points
in Unicode 3.2).
\end{funcdesc}

\begin{funcdesc}{in_table_b1}{code}
Determine whether \var{code} is in table{B.1} (Commonly mapped to
nothing).
\end{funcdesc}

\begin{funcdesc}{map_table_b2}{code}
Return the mapped value for \var{code} according to table{B.2}
(Mapping for case-folding used with NFKC).
\end{funcdesc}

\begin{funcdesc}{map_table_b3}{code}
Return the mapped value for \var{code} according to table{B.3}
(Mapping for case-folding used with no normalization).
\end{funcdesc}

\begin{funcdesc}{in_table_c11}{code}
Determine whether \var{code} is in table{C.1.1}
(ASCII space characters).
\end{funcdesc}

\begin{funcdesc}{in_table_c12}{code}
Determine whether \var{code} is in table{C.1.2}
(Non-ASCII space characters).
\end{funcdesc}

\begin{funcdesc}{in_table_c11_c12}{code}
Determine whether \var{code} is in table{C.1}
(Space characters, union of C.1.1 and C.1.2).
\end{funcdesc}

\begin{funcdesc}{in_table_c21}{code}
Determine whether \var{code} is in table{C.2.1}
(ASCII control characters).
\end{funcdesc}

\begin{funcdesc}{in_table_c22}{code}
Determine whether \var{code} is in table{C.2.2}
(Non-ASCII control characters).
\end{funcdesc}

\begin{funcdesc}{in_table_c21_c22}{code}
Determine whether \var{code} is in table{C.2}
(Control characters, union of C.2.1 and C.2.2).
\end{funcdesc}

\begin{funcdesc}{in_table_c3}{code}
Determine whether \var{code} is in table{C.3}
(Private use).
\end{funcdesc}

\begin{funcdesc}{in_table_c4}{code}
Determine whether \var{code} is in table{C.4}
(Non-character code points).
\end{funcdesc}

\begin{funcdesc}{in_table_c5}{code}
Determine whether \var{code} is in table{C.5}
(Surrogate codes).
\end{funcdesc}

\begin{funcdesc}{in_table_c6}{code}
Determine whether \var{code} is in table{C.6}
(Inappropriate for plain text).
\end{funcdesc}

\begin{funcdesc}{in_table_c7}{code}
Determine whether \var{code} is in table{C.7}
(Inappropriate for canonical representation).
\end{funcdesc}

\begin{funcdesc}{in_table_c8}{code}
Determine whether \var{code} is in table{C.8}
(Change display properties or are deprecated).
\end{funcdesc}

\begin{funcdesc}{in_table_c9}{code}
Determine whether \var{code} is in table{C.9}
(Tagging characters).
\end{funcdesc}

\begin{funcdesc}{in_table_d1}{code}
Determine whether \var{code} is in table{D.1}
(Characters with bidirectional property ``R'' or ``AL'').
\end{funcdesc}

\begin{funcdesc}{in_table_d2}{code}
Determine whether \var{code} is in table{D.2}
(Characters with bidirectional property ``L'').
\end{funcdesc}


text:
% DO NOT COMPILE THIS FILE DIRECTLY!
% This is included by the other .tex files.

\begin{frame}[t,plain]
\titlepage
\end{frame}

\begin{frame}
    \frametitle{Outline of the presentation}
    \begin{itemize}
        \item Present the components used in MISP to expire IOCs
        \item Present the current state of Indicators life-cycle management in MISP
    \end{itemize}
\end{frame}

\section{Expiring IOCs: Why and How?}
\begin{frame}[fragile]
\frametitle{Indicators lifecycle - Problem Statement}
    \begin{itemize}
        \item {\bf Sharing information} about threats {\bf is crucial}
        \item Organisations are sharing more and more
    \end{itemize}
    \vspace{1em}

    Contribution by {\bf unique organisation} (\texttt{Orgc.name}) on MISPPriv:\\
    \vspace{1em}
    \begin{minipage}{0.45\textwidth}
        \begin{tabular}{ll}
            \hline
            Date  & Unique Org \\
            \hline
            2013  & 17 \\
            2014  & 43 \\
            2015  & 82 \\
            2016  & 105 \\
            2017  & 118 \\
            2018  & 125 \\
            2019-10 & 135 \\
            \hline
        \end{tabular}
        \vspace{0.5em}
    \end{minipage}
    \begin{minipage}{0.5\textwidth}
        \begin{lstlisting}
{
    "distribution": [1, 2, 3]
}\end{lstlisting}
    \end{minipage}

\end{frame}

\begin{frame}
\frametitle{Indicators lifecycle - Problem Statement}
    \begin{itemize}
        \item Various users and organisations can share data via MISP, multiple parties can be involved
        \begin{itemize}
            \item \textbf{Trust}, \textbf{data quality} and \textbf{relevance} issues
            \item Each user/organisation have \textbf{different use-cases} and interests
                \begin{itemize}
                    \item Conflicting interests: Operational security VS attribution
                \end{itemize}
        \end{itemize}
        \item[] $\rightarrow$ Can be partially solved with \textit{Taxonomies}
        \pause
        \vspace{0.5cm}
    \item Attributes can be shared in large quantities \small{(more than 12M on \texttt{MISPPRIV} - Sept. 2020)}
        \begin{itemize}
            \item Partial info about their \textbf{freshness} (\textit{Sightings})
            \item Partial info about their \textbf{validity} (\textit{last\_seen})
        \end{itemize}
        \item[] $\rightarrow$ Can be partially solved with our \textit{Data model}
    \end{itemize}
    \begin{center}
        MISP's \textit{Decaying model} combines the two
    \end{center}
\end{frame}

\begin{frame}
\frametitle{Requirements to enjoy the decaying feature in MISP}
    \begin{itemize}
        \item Starting from \textbf{MISP 2.4.116}, the decaying feature is available
        \item \textbf{Update} decay models and \textbf{enable} some
        \item MISP Decaying strongly relies on \textit{Taxonomies} and \textit{Sightings}, don't forget to review their configuration
    \end{itemize}
    \vspace{0.7cm}
     Note: The decaying feature has no impact on the information stored in MISP, it's just an \textbf{overlay} to be used in the user-interface and API
\end{frame}

\begin{frame}
    \frametitle{\textit{Sightings} - Refresher (1)}
    \textit{Sightings} add a \textbf{temporal context} to indicators.
    \begin{itemize}
        \item \textit{Sightings} can be used to represent that you saw the IoC
        \item \textbf{Usecase:} Continuous feedback loop MISP $\leftrightarrow$ IDS
    \end{itemize}

    \begin{center}
        \includegraphics[scale=1.00]{pics/sightings.png}
    \end{center}
\end{frame}

\begin{frame}
    \frametitle{\textit{Sightings} - Refresher (2)}
    \textit{Sightings} add a \textbf{temporal context} to indicators.
    \begin{itemize}
        \item \textit{Sightings} give more credibility/visibility to indicators
        \item This information can be used to {\bf prioritise and decay indicators}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Taxonomies - Refresher (1)}
    \includegraphics[width=1.00\linewidth]{pics/taxonomies.png}
    \begin{itemize}
        \item \textit{Taxonomies} are a simple way to attach a classification to an \textit{Event} or an \textit{Attribute}
        \item Classification must be globally used to be efficient (or agreed on beforehand)
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Taxonomies - Refresher (2)}
    \includegraphics[width=1.00\linewidth]{pics/taxonomy-admiralty-scale.png}
    \begin{center}
        $\rightarrow$ Cherry-pick allowed \textit{Tags}
    \end{center}
\end{frame}

\begin{frame}
    \frametitle{Taxonomies - Refresher (3)}
    \begin{itemize}
        \item Some taxonomies have a \texttt{numerical\_value}
        \item Allows concepts to be used in an mathematical expression
        \begin{itemize}
            \item[$\rightarrow$] Can be used to prioritise IoCs
        \end{itemize}
    \end{itemize}
    \vspace{0.5cm}

    \begin{footnotesize}
    \texttt{admirality-scale} taxonomy\footnote{\url{https://github.com/MISP/misp-taxonomies/blob/master/admiralty-scale/machinetag.json}}
    \begin{columns}[T] % align columns
    \begin{column}{.40\textwidth}
        \begin{tabular}{|ll|}
            \hline
            \textbf{Description} & \textbf{Value}\\
            \hline
            Completely reliable & 100\\
            Usually reliable & 75\\
            Fairly reliable & 50\\
            Not usually reliable & 25\\
            Unreliable & 0\\
            Reliability cannot be judged & 50\\
            Deliberatly deceptive & 0\\
            \hline
        \end{tabular}
    \end{column}%
    \hfill%
    \begin{column}{.48\textwidth}
        \begin{tabular}{|ll|}
            \hline
            \textbf{Description} & \textbf{Value}\\
            \hline
            Confirmed by other sources & 100\\
            Probably true & 75\\
            Possibly true & 50\\
            Doubtful & 25\\
            Improbable & 0\\
            Truth cannot be judged & 50\\
            \hline
        \end{tabular}
    \end{column}%
    \end{columns}
    \end{footnotesize}

\end{frame}

\begin{frame}
    \frametitle{Taxonomies - Refresher (3)}
    \begin{footnotesize}
    \texttt{admirality-scale} taxonomy\footnote{\url{https://github.com/MISP/misp-taxonomies/blob/master/admiralty-scale/machinetag.json}}
    \begin{columns}[T] % align columns
    \begin{column}{.40\textwidth}
        \begin{tabular}{|ll|}
            \hline
            \textbf{Description} & \textbf{Value}\\
            \hline
            Completely reliable & 100\\
            Usually reliable & 75\\
            Fairly reliable & 50\\
            Not usually reliable & 25\\
            Unreliable & 0\\
            Reliability cannot be judged & 50 \textbf{\color{red}?}\\
            Deliberatly deceptive & 0 \textbf{\color{red}?}\\
            \hline
        \end{tabular}
    \end{column}%
    \hfill%
    \begin{column}{.48\textwidth}
        \begin{tabular}{|ll|}
            \hline
            \textbf{Description} & \textbf{Value}\\
            \hline
            Confirmed by other sources & 100\\
            Probably true & 75\\
            Possibly true & 50\\
            Doubtful & 25\\
            Improbable & 0\\
            Truth cannot be judged & 50 \textbf{\color{red}?}\\
            \hline
        \end{tabular}
    \end{column}%
    \end{columns}
    \end{footnotesize}

    \vspace{0.5cm}
    $\rightarrow$ Users can override tag \texttt{numerical\_value}
\end{frame}

\begin{frame}
    \frametitle{Scoring Indicators: Our solution}
    $$ \texttt{score}(\texttt{\tiny Attribute}) = \texttt{base\_score}(\texttt{\tiny Attribute, Model}) \;\;\bullet\;\; \texttt{decay}(\texttt{\tiny Model, time}) $$
    \begin{itemize}
        \item \texttt{base\_score}(\texttt{\tiny Attribute, Model})
            \begin{itemize}
                \item Initial score of the \textit{Attribute} only considering the context (\textit{Attribute's type}, \textit{Tags})
            \end{itemize}
        \vspace{1cm}
        \item \texttt{decay}(\texttt{\tiny Model, time})
            \begin{itemize}
                \item Function composed of the \textbf{lifetime} and \textbf{decay speed}
                \item Decreases the \texttt{base\_score} over time
            \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Scoring Indicators: Our solution}
    $$ \texttt{score}(\texttt{\tiny Attribute}) = \texttt{base\_score}(\texttt{\tiny Attribute, Model}) \;\;\bullet\;\; \texttt{decay}(\texttt{\tiny Model, time}) $$
    \begin{center}
    \begin{tikzpicture}
        \draw[->] (-1, 0) -- (4.5, 0) node[right] {$time$};
        \draw[->] (0, -1) -- (0, 4.2) node[left] {$score$};
        \node at (-1, 2.6) {\footnotesize base\_score};
        \draw[scale=0.5, domain=0:8, smooth, variable=\y, blue]  plot ({\y}, {5 * (1 - (\y/8)^(3.5))});
    \end{tikzpicture}
    \end{center}
\end{frame}

\section{Current implementation in MISP}
\begin{frame}
    \frametitle{Implementation in MISP: \texttt{Event/view}}
    \includegraphics[width=1.00\linewidth]{pics/decaying-event.png}
    \begin{itemize}
        \item \texttt{Decay score} toggle button
        \begin{itemize}
            \item Shows Score for each \textit{Models} associated to the \textit{Attribute} type
        \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}[fragile]
    \frametitle{Implementation in MISP: API result}
    \texttt{/attributes/restSearch}
    \begin{lstlisting}
"Attribute": [
  {
    "category": "Network activity",
    "type": "ip-src",
    "to_ids": true,
    "timestamp": "1565703507",
    [...]
    "value": "8.8.8.8",
    "decay_score": [
      {
        "score": 54.475223849544456,
        "decayed": false,
        "DecayingModel": {
          "id": "85",
          "name": "NIDS Simple Decaying Model"
        }
      }
    ],
[...]
    \end{lstlisting}
\end{frame}

\begin{frame}
\frametitle{Implementation in MISP: Objectives}
    \begin{itemize}
        \item \textbf{Automatic scoring} based on default values
        \item \textbf{User-friendly UI} to manually set \textit{Model} configuration (lifetime, decay, etc.)
        \item \textbf{Simulation} tool
        \item Interaction through the \textbf{API}
        \item Opportunity to create your \textbf{own} formula or algorithm
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Implementation in MISP: Models definition}
        \hspace{190pt}
        \raisebox{-1.0ex}{\Large $\Rsh$} {\tiny $score = base\_score \cdot \left( 1 - \left( \frac{t}{\tau} \right)^{\frac{1}{\delta}} \right) $}
    \textit{Models} are an instanciation of the formula with configurable parameters:
    \begin{itemize}
        \item Parameters: \texttt{lifetime, decay\_rate, threshold}
        \item \texttt{base\_score} computation
        \item \texttt{default base\_score}
        \item associate \textit{Attribute} types
        \item formula
        \item creator organisation
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Implementation in MISP: Models Types}
    Two types of model are available
    \begin{itemize}
        \item \textbf{Default Models}: Created and shared by the community. Coming from \texttt{misp-decaying-models} repository\footnote{\url{https://github.com/MISP/misp-decaying-models.git}}.
        \begin{itemize}
            \item[$\rightarrow$] Not editable
        \end{itemize}
    \vspace{0.5cm}
    \item \textbf{Organisation Models}: Created by a user on MISP
        \begin{itemize}
            \item Can be hidden or shared to other organisation
            \item[$\rightarrow$] Editable
        \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Implementation in MISP: Index}
    \includegraphics[width=1.00\linewidth]{pics/decaying-index.png}
    Standard CRUD operations: View, update, add, create, delete, enable, export, import
\end{frame}

\begin{frame}
    \frametitle{Implementation in MISP: Fine tuning tool}
    \includegraphics[width=1.00\linewidth]{pics/decaying-tool.png}
    Configure models: Create, modify, visualise, perform mapping
\end{frame}

\begin{frame}
    \frametitle{Implementation in MISP: \texttt{base\_score} tool}
    \includegraphics[width=1.00\linewidth]{pics/decaying-basescore.png}
    Adjust Taxonomies relative weights
\end{frame}

\begin{frame}
    \frametitle{Implementation in MISP: simulation tool}
    \includegraphics[width=1.00\linewidth]{pics/decaying-simulation.png}
    Simulate decay on \textit{Attributes} with different \textit{Models}
\end{frame}

\begin{frame}[fragile]
    \frametitle{Implementation in MISP: API query body}
    \texttt{/attributes/restSearch}
    \begin{lstlisting}
{
    "includeDecayScore": 1,
    "includeFullModel": 0,
    "excludeDecayed": 0,
    "decayingModel": [85],
    "modelOverrides": {
        "threshold": 30
    }
    "score": 30,
}
    \end{lstlisting}
\end{frame}

\lstset{language=PHP}
\begin{frame}[fragile]
    \frametitle{Creating a new decay algorithm}
    \lstset{basicstyle=\scriptsize}
    \begin{lstlisting}
<?php
include_once 'Base.php';

class Polynomial extends DecayingModelBase
{
    public const DESCRIPTION = 'The description of your new decaying algorithm';

    public function computeScore($model, $attribute, $base_score, $elapsed_time)
    {
       // algorithm returning a numerical score
    }

    public function isDecayed($model, $attribute, $score)
    {
        // algorithm returning a boolean stating
        // if the attribute is expired or not
    }
}
?>
    \end{lstlisting}
\end{frame}

\begin{frame}
    \frametitle{Decaying Models 2.0}
    \begin{itemize}
        \item Improved support of \textit{Sightings}
        \begin{itemize}
            \item \texttt{False positive} \textit{Sightings} should somehow reduce the score
            \item \texttt{Expiration} \textit{Sightings} should mark the attribute as decayed
        \end{itemize}
        \item Potential \textit{Model} improvements
        \begin{itemize}
            \item Instead of resetting the score to \texttt{base\_score} once a \textit{Sighting} is set, the score should be increased additively (based on a defined coefficient); thus \textbf{prioritizing surges} rather than infrequent \textit{Sightings}
            \item Take into account related \textit{Tags} or \textit{Correlations} when computing score
        \end{itemize}
        \item Increase \textit{Taxonomy} coverage
        \begin{itemize}
            \item Users should be able to manually override the \texttt{numerical\_value} of \textit{Tags}
        \end{itemize}
    \end{itemize}
\end{frame}

max_stars_repo_name: cudeso/misp-training

max_issues_repo_name: cudeso/misp-training

max_forks_repo_name: cudeso/misp-training


text:
%-------------------------------Collapse Ratio---------------------------------
\section{Collapse Ratio}

The collapse ratio is a dimensionless number defined as the smallest ratio of the
height of a vertex above its opposing triangle to the longest edge of that opposing
triangle across all vertices of the tetrahedron. Figure~\ref{f:tet-height} shows
how the ratio is computed for a single vertex (vertex $3$). Assuming that edge $0-2$
is the longest edge of triangle $0-1-2$, the collapse ratio for vertex $3$ becomes:
\[
  q_{ex} = \frac{h_3}{\normvec{ L_{02}}}.
\]
In general, take $(i,j,k,\ell)$ to be a permutation of $\{0,1,2,3\}$
(i.e., $(i,j,k,\ell)\in\Sf$) and $\normvec{ L_{ab}}$ to be the length of the edge
connecting vertices $a$ and $b$.
Then the collapse ratio may be written
\[
  q = \min_i\left\{\frac{h_i}{\max\left\{\normvec{ L_{jk}},\normvec{ L_{k\ell}},\normvec{ L_{\ell j}}\right\}}\right\}.
\]

The collapse ratio is intended to identify tetrahedra whose vertices are nearly planar (slivers).
Note that $q$ approaches zero as vertex $3$ in
Figure~\ref{f:tet-height} approaches the plane defined by $0-1-2$.
However, this metric can be misleading when the vertex with the smallest projected height
(say $3$ without loss of generality) is not projected interior to triangle $0-1-2$.
In this case, it is possible for $0-1-2$ to have a small area (which increases $q$) but
for edges $0-3$, $1-3$, and $2-3$ to be very long compared to those of triangle $0-1-2$.
Thus slivers can have arbitrarily high collapse ratios.

\tetmetrictable{collapse ratio}%
{$1$}%                                                Dimension
{$[0.1,DBL\_MAX]$}%                                   Acceptable range
{$(0,DBL\_MAX]$}%                                     Normal range
{$[0,DBL\_MAX]$}%                                     Full range
{$\frac{\sqrt{6}}{3}$}%                               Equilateral tet
{\cite{patran:03}}%                                   Citation
{v\_tet\_collapse\_ratio}%                            Verdict function name