decision_notes.lyx

#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass article
\use_default_options true
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize a4paper
\use_geometry true
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation landscape
\suppress_date false
\justification true
\use_refstyle 1
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\leftmargin 2cm
\topmargin 2cm
\rightmargin 2cm
\bottommargin 2cm
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 2
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
pagenumbering{gobble}
\end_layout

\end_inset


\end_layout

\begin_layout Itemize
The decision tree represents a single-class Tsetlin Machine (TM) for Boolean
 input vector of size 
\begin_inset Formula $m$
\end_inset

 and consisting of 
\begin_inset Formula $n$
\end_inset

 clauses.
\end_layout

\begin_layout Itemize
The decision is calculated for a given input vector 
\begin_inset Formula $X=\left(x_{0},\ldots,x_{m-1}\right)$
\end_inset

 and the expected output 
\begin_inset Formula $y$
\end_inset

; 
\begin_inset Formula $y=1$
\end_inset

 if the input vector 
\begin_inset Formula $X$
\end_inset

 matches the class, and 
\begin_inset Formula $y=0$
\end_inset

 if it does not.
\end_layout

\begin_layout Itemize
Each clause 
\begin_inset Formula $C_{j}$
\end_inset

 for 
\begin_inset Formula $0\leq j<n$
\end_inset

 has either positive or negative voting defined by the function 
\begin_inset Formula $\mathrm{sgn}\left(C_{j}\right)$
\end_inset

.
 Usually, even clauses vote
\begin_inset space ~
\end_inset


\begin_inset Formula $\left(+1\right)$
\end_inset

, and odd clauses vote
\begin_inset space ~
\end_inset


\begin_inset Formula $\left(-1\right)$
\end_inset

.
\end_layout

\begin_layout Itemize

\emph on
Class confidence
\emph default
 
\begin_inset Formula $v$
\end_inset

 is the sum of all clause votes respecting their signs:
\begin_inset Formula 
\[
v=\sum_{j=0}^{n-1}C_{j}\left(X\right)\cdot\mathrm{sgn}\left(C_{j}\right).
\]

\end_inset


\end_layout

\begin_layout Itemize
Yellow diamonds represent probabilistic choices, such that a uniformly distribut
ed random variable 
\begin_inset Formula $\mathcal{U}_{\left[0,1\right)}$
\end_inset

, denoted as 
\begin_inset Quotes eld
\end_inset

rand
\begin_inset Quotes erd
\end_inset

, is less than the given probability 
\begin_inset Formula $P$
\end_inset

, displayed in the diamond.
 Therefore, the 
\begin_inset Quotes eld
\end_inset

yes
\begin_inset Quotes erd
\end_inset

 branch is triggered with an indicated probability 
\begin_inset Formula $P$
\end_inset

, and 
\begin_inset Quotes eld
\end_inset

no
\begin_inset Quotes erd
\end_inset

 is triggered with the probability 
\begin_inset Formula $\left(1-P\right)$
\end_inset

.
\end_layout

\begin_layout Itemize
The clause feedback probability is calculated once for the entire clause
 
\begin_inset Formula $C_{j}$
\end_inset

 and is based on the class confidence 
\begin_inset Formula $v$
\end_inset

 and the 
\emph on
learning threshold
\emph default
 
\begin_inset Formula $T$
\end_inset

.
\end_layout

\begin_layout Itemize
Each clause activation 
\begin_inset Formula $C_{j}\left(X\right)$
\end_inset

 is calculated as a conjunction of 
\begin_inset Formula $2m$
\end_inset

 literals, one positive and one negative for each of 
\begin_inset Formula $m$
\end_inset

 inputs; i.e., 
\begin_inset Formula $x_{k/2}$
\end_inset

 and 
\begin_inset Formula $\overline{x}_{k/2}$
\end_inset

 for 
\begin_inset Formula $0\leq k<2m$
\end_inset

: 
\begin_inset Formula 
\[
C_{j}\left(X\right)=\bigwedge_{k=0}^{2m}\left(x_{k/2}\wedge\overline{x}_{k/2}\right).
\]

\end_inset


\end_layout

\begin_layout Itemize
Positive or negative 
\begin_inset Formula $k$
\end_inset

-th literal can be expressed as 
\begin_inset Formula $x_{k/2}\oplus\mathrm{pol}\left(k\right)$
\end_inset

, where 
\begin_inset Formula $\mathrm{pol}\left(k\right)$
\end_inset

 is a literal 
\emph on
polarity
\emph default
 function defined as: 
\begin_inset Formula 
\[
\mathrm{pol}\left(k\right)=\begin{cases}
0 & \text{if }k\text{ is even (positive literal)}\\
1 & \text{if }k\text{ is odd (negative literal)}
\end{cases}
\]

\end_inset

therefore, the clause activation 
\begin_inset Formula $C_{j}\left(X\right)$
\end_inset

 can also be written as: 
\begin_inset Formula 
\[
C_{j}\left(X\right)=\bigwedge_{k=0}^{2m}x_{k/2}\oplus\mathrm{pol}\left(k\right).
\]

\end_inset


\end_layout

\begin_layout Itemize
The state of a single Tsetlin automaton 
\begin_inset Formula $\mathit{TA}_{jk}$
\end_inset

 drives the decision to include or exclude 
\begin_inset Formula $k$
\end_inset

-th literal in the clause 
\begin_inset Formula $C_{j}$
\end_inset

.
\end_layout

\begin_layout Itemize
The probability of issuing a per-literal feedback action depends on the
 
\emph on
learning rate
\emph default
 
\begin_inset Formula $s>1$
\end_inset

.
\end_layout

\end_body
\end_document