\documentclass[twocolumn,global]{svjour}
\usepackage{lastpage,url,alltt,graphicx,cite,url,fancyheadings,bar,fancyvrb}
\usepackage{rotating,wrapfig,stfloats}

\usepackage{eso-pic}
\usepackage{color}
\usepackage{type1cm}

\newenvironment{ccode}{\scriptsize\begin{alltt}}{\end{alltt}\normalsize}

   \newcommand{\code}[3]{
     \begin{figure}[!t]
        \fvset{  samepage=true,
                 fontsize=\scriptsize,
                 commandchars=\\\{\},
                 framesep=2mm,
                 label={\small{\textit{#1}}},
                 labelposition=topline,
                 frame=single
                 }
            {\bf \VerbatimInput{#1}}
    \caption[#2]{#3}\label{fig:#1}
    \end{figure}
}

\usepackage{amssymb,times}
\DeclareFontShape{OT1}{cmtt}{bx}{n}{
  <5><6><7><8><9><10><10.95><12><14.4><17.28><20.74><24.88>cmttb9}{}

\newcommand{\mytitle}{
Improving IV\&V Techniques Through the Analysis of Project Anomalies:\\
LINKER: final report
}
\footrulewidth 0.0pt\headrulewidth 0.1pt
\lhead{}\rhead{}\chead{}\rfoot{}\lfoot{}\cfoot{}
\rhead{{\scriptsize 
\date{\today}\\
Download this paper at: \url{http://unbox.org/wisp/var/timm/var/07/07linker2.pdf}\\
WP reference: \url{http://unbox.org/wisp/var/omid/papers/ivvReport/my.tex}}}
\lhead{\includegraphics[width=6cm]{wvulogo.pdf}}

\newenvironment{smallitem}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{itemize}
   \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{itemize}}

\newenvironment{smallenum}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{enumerate}
  \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{enumerate}}

 \newtheorem{recommend}{Recommendation}

 \newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
 \newcommand{\bi}{\begin{smallitem}}
\newcommand{\ei}{\end{smallitem}}
 \newcommand{\be}{\begin{smallenum}}
\newcommand{\ee}{\end{smallenum}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}

\begin{document}
\title{
\mytitle
\author{Tim Menzies, Omid Jalali}
\institute{Lane Department of Computer Science and Electrical Engineering, West Virginia University, USA
\newline
\url{tim@menzies.us}, 
(\url{http://menzies.us})\newline
\url{jalali.omid@gmail.com}
}}
\maketitle \thispagestyle{fancy}
\pagestyle{fancy}

\vspace{-1cm}\begin{abstract}
The original plan for this project is in two parts.
The {\em second part} intended to combine two (or more) of the IV\&V data sources
 into an active monitoring
framework where data collected during an active IV\&V project will trigger an
alert if a project becomes unusual (and defining ``unusual'' is one of the goals of this project).

Before we can generalize between sources, we studied each source in isolation
to determine its strengths and weaknesses.
Hence, the {\em first part} of this project aims to gain experience with the various IV\&V data sources
available to researchers like ourselves; e.g.
{\em SILAP}, from
the IV\&V planning and scoping team; 
James Dabney's {\em Bayes networks} that
describe the IV\&V business practices of the L3
IV\&V contractor; 
the {\em PITS} issue tracking data; 
the {\em LINKER} database
project that intends to
join PITS to other data sources.
%To date, this project has resulted in:
%\bi
%\item
%A preliminary report described what had been learned from the
%SILAP data. 
%A ranking was offered on the most common IV\&V work-breakdown structure (WBS) activities.
%This ranking can be used for (e.g.) identifying what WBS tasks would benefit most from optimization.
%\item
%Two  reports on text mining from the
%PITS issues tracking database that 
%generated an expert system
%which audited a test engineer's proposed severity level.
%\item
%A preliminary report
%Dabney's Bayes networks. On a limited case study, it was shown that Bayes nets
%and treatment learning could generate parsimonious explanations 
%for project events.
%\ei

This report was meant to have been about the LINKER system that was to have collected
data from multiple NASA projects at IV\&V. However, at the time of this writing, LINKER is an inactive project.
Therefore, this report returns to the Dabney Bayes net study described earlier in this project.
Dabney et.al. did not offer an automatic update facility for their belief distributions. We implemented such
a facility and, on experimentation, found an interesting property- the more data given to a Bayes net, the
worse its error. That is, Bayes nets work best in domains with low levels of data.
This is an important property for managing projects in an environment where
data sources are constantly changing, and may not always be totally reliable.

%This report describes LINKER, a new database at IV\&V that combines data from different sources.
%LINKER is still under-development. Hence, unlike the prior reports, this report 
%does not report experimental results. Rather, it discusses the benefits and drawbacks of LINKER.

\end{abstract}
\noindent
{\bf Credits:}
This work would have been impossible without James Dabney's thorough modeling of IV\&V processes
in belied networks. 
This research was conducted at
West Virginia University under NASA sub-contract project 100005549, task 5e, award 1002193r.

\noindent
{\bf Cautions}
Reference herein to
any specific commercial product, process, or service by trade name,
trademark, manufacturer, or otherwise, does not constitute or imply
its endorsement by the United States 
Government.

\tableofcontents
\listoffigures
\newpage
\rhead{\thepage\ of \pageref{LastPage}}
\lhead{Menzies, Jalali: Linker - final report}

\section{Introduction}

This report was meant to have been about data collection and anomaly detection within the framework of IV\&V's LINKER
system.
LINKER's aim was to combines data from different sources and act as a 
centralized query system
for IV\&V data.  
LINKER was designed to overcome certain limitations with the NASA IV\&V \underline{p}roject \underline{i}ssue 
\underline{t}racking \underline{s}ystem (PITS).
 The
current interface of PITS can only run queries against a single
project. There is no way  to select multiple projects or to save a
query generated on one screen for one project and to use it on
another project.

The intent was that 
LINKER would have read-only access to the other
IV\&V databases and offer a centralized query facility that can
reach into the other databases.  Internally, LINKER was to have worked by first
importing data from other IV\&V databases.
Initially, LINKER was  only targeting PITS but, when other databases
become available, the intent was to integrate them as well.
Once imported, LINKER was to have become an environment within which analysts
could  explore data from multiple projects.

However, at the the time of this writing, LINKER is no longer an active project. Like many data collection
projects at NASA, the funding, personnel, and other resources available to LINKER has been reallocated.
Therefore, just like with the SILAP databases studied previously by this project, we can't use this data source

What is the lesson here? Perhaps it is that any large organization has numerous competing demands on their data
collection and analysis resources. In such an environment, it is prudent to ask ``what can be done with the
least amount of data?''. Elsewhere we have studied general software process models from USC's COCOMO family of tools~\cite{boehm00b}.
Those tools require tuning to local data and, as was the case with LINKER and many other projects~\cite{me06d}, 
that data is often not available. 
However, for those models, we found a loophole. While the exact local tuning is unavailable {\em the space of
possible tunings is well known}. By sampling from the space of all possible models, and restraining the factors
that lead to the greatest uncertainty, it is possible to find stable conclusions~\cite{me07f}.

While an exciting result, it would be preferable if  something similar could be shown using models developed
for IV\&V. 
Dabney ~\cite{dabney06} built such models while
exploring  methods to improve the defect removal efficiency at NASA's IV\&V center. 
Dabney'  Bayes nets are a natural tool for anomaly detection~\cite{coo04}, which the stated aim of this project. Anomalous
project situations that require more investigation could be detected if we can't squeeze new ideas into old beliefs.
In that case, something is not what was expected (i.e. either  the old ideas or the new data). 

This report extends Dabney's work in several ways:
\bi
\item His method uses proprietary software while BELIEF is an open source tool and can be
modified to provide support for any future requirement.
\item Dabney did not provide a mechanism for automatic update for the nodes of 
Bayesian network suggested in his study. On the other hand, our BELIEF tool has a constant feedback
mechanism that reflects the ongoing changes in the nodes.
\item Dabney's method uses a single numeric value for each node. BELIEF allows for any 
distribution (which could be a single numeric value) for each node
that can be more descriptive in the Bayesian network.
\ei
BELIEF is a better tool than the QNET tool described in previous reports from this project since it integrates
both belief propagation and belief updates into one package. QNET only performed belief propagation and left
belief updates to the TAR3 learner. 

One advantage of BELIEF is that it simplifies experimentation.
QNET+TAR3 tool minutes to run while QNET takes seconds.
Hence, for this study, we could
perform hundreds of experiments in a very small amount of time. The results have a  
interesting property:
\begin{quote}{\em 
updates to internal beliefs get more complicated and more error prone,
the more project data is supplied to the tool.}
\end{quote}
 This is not a bug in our tool; rather it is a fundamental property
of any tool that tries to squeeze old ideas into new constraints. As
the greater the number of new ideas increases, it becomes harder
and harder to fit the old ideas into the new.

This is an important property since, to say it another way, Bayes nets work best when there is limited information.
Since this is often the case at NASA, it strongly suggests that Bayes nets are worth much more exploration.


\begin{figure*}
\begin{center}
\includegraphics[width=7in]{bayesall.png}
\end{center}
\caption[A Bayes network of IV\&V practices]{Dabney's 
Bayes net describing IV\&V practices. The red square, top left, is expanded in \fig{bayes1}.
}\label{fig:bayes}
\end{figure*}
\section{Belief Networks}

A belief network (also known as a Bayesian network)
is a directed acyclic graph of 
\bi
\item
nodes representing variables (nodes can represent any kind of 
variable, be it a measured parameter, a latent variable or an hypothesis);
\item
arcs representing probabilistic dependency relations among the variables 
and local probability distributions for each variable given values of its parents.
\ei

If there is an arc from node $A$ to another node  $B$, then variable $B$ 
depends directly on variable $A$, and $A$ is called a $parent$ of $B$. 
If there are $n$ variables, then
for each variable $X_i$ ($1 \le i \le n$),
the set of parent variables is denoted by $parents(X_i)$ 
then the joint distribution of the variables is product of the local distributions
\[
Pr(X_1, \ldots, X_n) = \prod_{i=1}^n Pr(X_i \mid parents(X_i))
\]
If $X_i$ has no parents, its local probability distribution is said to be $unconditional$, 
otherwise it is $conditional$. If the variable represented by a node is $observed$, 
then the node is said to be an $evidence$ node. 
In order to handle arbitrary distributions, we approximate $Pr(X_i)$ with
a histogram of ``N'' bins.



\begin{figure}
\begin{center}
\includegraphics[width=3.5in]{bayes1.png}
\end{center}
\caption[Defect introduction]{The ``defect 
introduction'' Bayes sub-net shown in a red box, top-left of \fig{bayes}.}
\label{fig:bayes1}
\end{figure} 


For example, \fig{bayes1} shows a part of Dabney's belief networks for IV\&V (and
the whole network is shown in \fig{bayes}).  Note that \fig{bayes} has three rows:
\bi
\item Row 1 (top) models defect introduction at the developer's site;
\item Row 2 (middle) models defect detection and removal at the developer's site;
\item Row 3 (bottom) models defect detection and removal at the IV\&V site;
\ei
The figure also has five columns representing, from left to right,
\bi
\item Requirements
\item Analysis
\item Coding
\item Testing
\item Integration
\ei
This  leads to 15 sub-graphs, one of which is shown \fig{bayes1}, another in \fig{ReqDev}.

\section{The BELIEF Tool}

BELIEF is a tool with a relatively simple approach to reduce the error in any given node of a 
belief net.
It finds all tree-like subgraphs of a graph and traverses them. For each subgraph, it propagates 
the distributions from leaves all the way to the root of that subgraph.

There are many belief network systems algorithms available~\cite{gurp99,fenton00b,fenton02}, 
so it is a reasonable question to ask ``why build another''? There were two reasons:

\bi
\item Previously, we have performed Monte Carlo analysis methods~\cite{me00e} on these kinds of models, augmented by a data mining
post-processor. We wanted to try building a Monte Carlo device with a built in data miner,
thus avoiding all the tedium of interfacing two systems with very different data structures.
\item
We have had much recent success
with stochastic analysis of software process models. Hence, we used this as an opportunity to
study stochastic updates for Bayes nets~\cite{me07f}.
\ei

\subsection{Input Structure}

The tree structure used in this tool must have several properties:
\bi
\item
Each node can have one or more of the three types of distributions, which are given distributions, goal distributions, and predicted distributions.
\item
A leaf node may have a {\em fixed} or {\em optional} given distribution.
If it is fixed, the given distribution must be used in the process any time this node is referenced.
If it is optional, the given distribution is only used once to initialize the tool.
No non-leaf node can have a given distribution.
\item
An arbitrary number of nodes can have goal distributions. Each such node is called a {\em goal node}.
\item
The tool generates a predicted distribution for each node as it traverses through the tree. Predicted distributions are only internal to the tool.
\item
If a node is a {\em goal node}, it has an error value assigned to it, which is essentially the difference between its goal and predicted distributions.
This error value is defined later.
\item
Each node has a {\em priority}, which determines how important it is to reach its goal distribution with as small an error as possible.
\item
A non-leaf node can apply one of the four operands \{OR, AND, NOT, NULL\} to its child nodes. 
These operands are defined later.
\ei

The simplest way to describe a tree structure is through a parent-child relation description; i.e. each parent node is described using its child nodes.
For simplicity purposes, comma-separated-value (csv) format is chosen. Each node is described by its identifier (name), followed by
number of child nodes, followed by its child nodes' identifiers (names).
For instance, the tree in \fig{SampleTree} is described in \fig{SampleTreeCSVSimple}.

\begin{figure}
\begin{center}
\includegraphics[width=3.5in]{SampleTree.jpg}
\end{center}
\caption[Sample Tree]{A sample tree.}
\label{fig:SampleTree}
\end{figure}

\begin{figure}
\begin{center}
\scriptsize
\begin{tabular}{|c|c|c|}
\hline
node name & child count & children \\\hline
D         & 0           &          \\\hline 
E         & 0           &          \\\hline 
F         & 0           &          \\\hline 
G         & 0           &          \\\hline 
H         & 0           &          \\\hline 
B         & 2           & D,E      \\\hline 
C         & 3           & F,G,H    \\\hline
A         & 2           & B,C      \\\hline
\end{tabular}
\end{center}
\caption[Relations in Sample Tree]{Description of tree in \fig{SampleTree} 
in csv format. Each node is followed by number of child nodes it has and their names.}
\label{fig:SampleTreeCSVSimple}
\end{figure}

A complete description of a tree requires several other fields as well.
Each node has an operand, a priority value, two range descriptors for
minimum and maximum values for the distributions of that node, a flag for the given distribution which
describes it as {\em fixed} or {\em optional}, as well as given and goal distributions and their flags.
\fig{SampleTreeCSVComplete} illustrates how these values are ordered.

\begin{figure*}
\begin{center}
\scriptsize
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
node & operand & priority & min & max & optional & given & goal & child & children & given distribution & goal distribution \\ 
name &         &          &     &     & or fixed & flag  & flag & count & names    & (if flag = yes)    & (if flag = yes)   \\\hline
D    & null    & 0        & 10  & 40  & optional & yes   & no   & 0     &          & 1,5,5,5,6,5,4,1    &                   \\\hline
E    & null    & 0        & 20  & 30  & optional & no    & no   & 0     &          &                    &                   \\\hline
F    & null    & 0        & 10  & 25  & fixed    & yes   & no   & 0     &          & 4,6,4,2,1,4,5,6    &                   \\\hline
G    & null    & 0        & 10  & 30  & optional & no    & no   & 0     &          &                    &                   \\\hline
H    & null    & 0        & 50  & 80  & optional & no    & no   & 0     &          &                    &                   \\\hline
B    & or      & 0        & 10  & 40  & optional & no    & no   & 2     & D,E      &                    &                   \\\hline
C    & or      & 10       & 25  & 45  & optional & no    & yes  & 3     & F,G,H    &                    & 1,4,4,6,6,4,4,1   \\\hline
A    & or      & 60       & 15  & 50  & optional & no    & yes  & 2     & B,C      &                    & 2,2,4,5,5,4,2,2   \\\hline
\end{tabular}
\end{center}
\caption[More Details of Sample Tree]{More detailed description of tree in \fig{SampleTree} in csv format.}
\label{fig:SampleTreeCSVComplete}
\end{figure*}

In \fig{SampleTreeCSVComplete}, node {F} has its flag set to {\em fixed}.
This means that its given distribution must be used in every traversal of the tree.
All other nodes have {\em optional} distributions, meaning that if their given 
distributions are provided, they are only used once for initialization.
Also, note that once a distribution flag is set, such distribution must be provided.
All distribution are discretized into a fixed number of bins (in our example 8 bins). Each bin
represents has a frequency count representing the number of instances that fall in that bin's range.

\subsection{Operands}

The four possible operands for each node are \{OR, AND, NOT, NULL\}. All operations are performed on
distributions. However, each distribution is normalized before and after the operation.
\bi
\item
OR operates on two or more distributions of child nodes.
It finds the maximum value of each bin among all child nodes'
distributions and assigns it the corresponding bin in parent's predicted distribution.
\item
AND operates on two or more distributions of child nodes as well.
It finds the minimum value of each bin among all child nodes'
distributions and assigns it the corresponding bin in parent's predicted distribution.
\item
NOT operates on a single distribution.
It inverts the distribution of the child node
by subtracting the normalized value of each bin from 1.

\item
NULL operates on zero or one distribution.
If a node is a leaf node, it ignores the operation, operating on zero distributions.
If a node is a non-leaf node, it simply passes the child node's distribution to its parent without modification.
\ei

As an example, three normalized distributions are given below.
\begin{center}
{
\scriptsize
\begin{tabular}{l|c|c|c|c|c|c|c|c}
Name & Bin1 & Bin2 & Bin3 & Bin4 & Bin5 & Bin6 & Bin7 & Bin8 \\\hline
A    & 0.10 & 0.10 & 0.05 & 0.10 & 0.15 & 0.25 & 0.10 & 0.15 \\
B    & 0.05 & 0.20 & 0.05 & 0.20 & 0.10 & 0.15 & 0.25 & 0.00 \\
C    & 0.15 & 0.00 & 0.10 & 0.25 & 0.10 & 0.05 & 0.10 & 0.25 \\
\end{tabular}
}
\end{center}

Four operations on some of these distributions are given below. Note that the
distribution generated after each operation is not normalized for simplicity.
However, they must be normalized for the operations to work properly.

\begin{center}
{
\scriptsize
\begin{tabular}{l|c|c|c|c|c|c|c|c}
Operation & Bin1 & Bin2 & Bin3 & Bin4 & Bin5 & Bin6 & Bin7 & Bin8 \\\hline
OR(A,B,C) & 0.15 & 0.20 & 0.10 & 0.25 & 0.15 & 0.25 & 0.25 & 0.25 \\
AND(A,C)  & 0.10 & 0.00 & 0.05 & 0.10 & 0.10 & 0.05 & 0.10 & 0.15 \\
NOT(B)    & 0.95 & 0.80 & 0.95 & 0.80 & 0.90 & 0.85 & 0.75 & 1.00 \\
NULL(A)   & 0.10 & 0.10 & 0.05 & 0.10 & 0.15 & 0.25 & 0.10 & 0.15 \\
\end{tabular}
}
\end{center}

\subsection{Definition of Error}

The algorithm relies on assessments made on how good a predicted distribution is
comparing to the goal distribution for each node. Comparing these two distributions
for each node is done through finding the error for each bin in the distributions.
For a given node, each bin has an associated error value defined as: $Error[bin] = | Goal[bin] - Predicted[bin] |$.
Note that {\em Goal} and {\em Predicted} are distributions for the given node.
It is important to measure the error for each bin separate from other bins since bins cannot
influence each other and are essentially independent.
Later in the algorithm, we will see how to use these independent error values for each bin 
to measure the overall performance of the algorithm in a given run.

\subsection{Algorithm}

The overall algorithm is described in the appendix.
It is helpful to break down the entire
algorithm in separate parts to understand it better.

\fig{algorithmInit} shows the initialization steps:
\bi
\item MaxDistort determines the upper bound of the range of distributions.
\item 100 runs are used for perfecting the predicted distributions.
\item Each distribution consists of 20 bins.
\ei
After data is read, it is stored into an array. For instance, node A of the tree described in
\fig{SampleTreeCSVComplete} is stored as illustrated in \fig{algorithmStore}.


\begin{figure}
{
\scriptsize\begin{alltt}\sffamily
\#CONSTANTS AND INITIALIZATION
MaxDistort = 2
Runs = 100
Bins = 20

\#READ AND STORE THE INPUT
\textbf{FOR} node \textbf{IN} Nodes
    read and store node's information
\ldots
\end{alltt}}
\caption[BELIEF's Algorithm: Initialization]{Initialization steps in BELIEF tool.}
\label{fig:algorithmInit}
\end{figure}

\begin{figure}
{
\scriptsize
Nodes[8].Name = A\newline
Nodes[8].Operand = OR\newline
Nodes[8].GoalPriority = 60\newline
Nodes[8].MinRange = 15\newline
Nodes[8].MaxRange = 50\newline
Nodes[8].GivenDistributionStatus = optional\newline
Nodes[8].GivenFlag = 0\newline
Nodes[8].GoalFlag = 1\newline
Nodes[8].GivenDistribution = EMPTY\newline
Nodes[8].GoalDistribution = \{2,2,4,5,5,4,2,2\}\newline
Nodes[8].ChildCount = 2\newline
Nodes[8].Child[1] = B\newline
Nodes[8].Child[2] = C\newline
}
\caption[BELIEF's Algorithm: Input Data Structure]{Storing node A (8th node) from the sample input in \fig{SampleTreeCSVComplete} in a simple data structure.}
\label{fig:algorithmStore}
\end{figure}

\begin{figure}
{
\scriptsize\begin{alltt}\sffamily
\ldots

find all Roots in the input graph

\textbf{FOR} root \textbf{IN} Roots
\{
    find subgraph[root]

    \textbf{FOR} bin \textbf{IN} Bins
        initialize MinError[bin]

     MaxPriorityNode = node with maximum priority in subgraph[root]
                                (or closest to root in case of ties)
     
     \#START PREDICTING DISTRIBUTIONS
     \textbf{FOR} run \textbf{IN} Runs
     \{
         \#INITIALIZE PREDICTED DISTRIBUTION FOR EACH NODE
         \textbf{FOR} node \textbf{IN} Nodes of subgraph[root]
             \textbf{FOR} bin \textbf{IN} Bins
                 initialize node.PredictedDistribution[bin]
\ldots
\end{alltt}}
\caption[BELIEF's Algorithm: Preparation]{Preparing to produce predicted distributions in each subgraph.}
\label{fig:algorithmPrepare}
\end{figure}

\fig{algorithmPrepare} shows the how the algorithm prepares for generating predictions.
It first finds the subgraphs of the overall graph. Then, for each
subgraph, it produces predictions.
MaxPriorityNode is the node with the maximum priority which is used later in processing leaf nodes.
In each run, the predicted distribution is initialized again. The minimum error in all the runs is stored in MinError which is initialized for each subgraph.

\begin{figure}
{
\scriptsize\begin{alltt}\sffamily
\ldots

      \#PROCESS LEAF NODES
         \textbf{FOR} node \textbf{IN} leaf nodes of subgraph[root]
         \{
             \textbf{IF} (run == 1)
                 \textbf{IF} (node.GivenFlag == 1)
                     \textbf{FOR} each bin \textbf{IN} Bins
                         node.PredictedDistribution[bin] = node.GivenDistribution[bin]
                 \textbf{ELSE} 
                     \textbf{FOR} each bin \textbf{IN} Bins
                         value1 = a random number between 0 and 
                                       MaxPriorityNode.GoalDistribution[bin] * MaxDistort
                         node.PredictedDistribution[bin] = value1
             \textbf{ELSE}
                 \textbf{IF} (node.GivenFlag == 1 AND node.GivenDistributionStatus == fixed)
                     \textbf{FOR} each bin \textbf{IN} Bins
                         node.PredictedDistribution[bin] = node.GivenDistribution[bin]
                 \textbf{ELSE} 
                     \textbf{FOR} each bin \textbf{IN} Bins
                         value1 = a random number between 0 and 
                                       MaxPriorityNode.GoalDistribution[bin] * MaxDistort
                         value2 = BestDistribution[node][bin]
                         node.PredictedDistribution[bin] = randomSelect(value1,value2)
         \}
     
         \#PROCESS ALL OTHER NODES
         \textbf{FOR} node \textbf{IN} non-leaf nodes of subgraph[root]
             node.PredictedDistribution = apply node.Operand on all its child nodes
\ldots
\end{alltt}}
\caption[BELIEF's Algorithm: Processing Nodes]{Processing leaf nodes followed by non-leaf nodes, all in the same subgraph.}
\label{fig:algorithmProcessNodes}
\end{figure}
\begin{figure}
{
\scriptsize\begin{alltt}\sffamily
\ldots
         \#SCORING
         \textbf{FOR} bin \textbf{IN} Bins
             initialize error[bin]
         \textbf{FOR} node \textbf{IN} Nodes of subgraph[root]
             \textbf{IF} (node.GoalFlag == 1)
                 \textbf{FOR} bin \textbf{IN} Bins
                     error[bin] = error[bin] + abs(node.PredictedDistribution[bin] - 
                                       node.GoalDistribution[bin]) * node.GoalPriority
     
         \#FINDING THE BEST
         \textbf{FOR} bin \textbf{IN} Bins
             \textbf{IF} (error[bin] \textless MinError[bin])
                 MinError[bin] = error[bin]
                 \textbf{FOR} (node \textbf{IN} leaf nodes of subgraph[root])
                     BestDistribution[node][bin] = node.PredictedDistribution[bin]
     \}
\}

\end{alltt}}
\caption[BELIEF's Algorithm: Scoring the Best]{Scoring the predicted distributions and keeping the best distributions seen so far for the subgraph.}
\label{fig:algorithmFinish}
\end{figure}


The algorithm then continues to process the leaf nodes, as illustrated in \fig{algorithmProcessNodes}.
For each leaf node, there are two possible choices depending on the run.

In the first run,
\bi
\item if the leaf node has a given distribution,
this distribution is used for the predicted distribution of this node.
\item Otherwise the distribution is generated bin by bin using a random
number in the range of 0 to twice the value of the corresponding bin of the node with the maximum priority.
\ei

\noindent
In other runs,
\bi
\item if the leaf node has a given distribution and its flag is set to {\em fixed},
this distribution is used for the predicted distribution of this node.
\item Otherwise, for each bin, a random number is generated in
the range of 0 to twice the value of the corresponding bin of the node with the maximum priority.
Then, using a random choice, either this random number or the best value for this bin seen so far is used.
This best value is update after each run and is kept per node per bin.
\ei 

Once all leaf nodes are processed, the algorithm starts processing the non-leaf nodes until
they are all processed and predicted distributions are generated for all non-leaf nodes.
Each non-leaf node has at least one child node and usually more. Once all these child nodes
are processed, the parent node can be processed by applying one of the operands discussed before.
The distribution generated can then be stored in node's predicted distribution.

Once the processing of all nodes have finished, the predicted distributions must be scored
as illustrated in \fig{algorithmFinish}. This is done using the error values defined before.
For each node that has a goal distribution, the error is calculated for all its bins 
and multiplied by that node's priority. This value is added to the overall error seen so far.
By using the node's priority, we make sure that the error values are weighted, meaning that
a node with lower priority does not have as much control over the distributions as a node with
higher priority. As we will see later, this allows us to reduce the errors seen in the results.

Since each bin is independent from other bins, scores are kept separate for each bin.
Therefore, we can find the bin with minimum overall error in the graph. If a new run gives rise
to a new minimum error for any specific bin, that bin's values replace any older value in the array
designed to keep the best distributions seen so far for each node. This array is used
to process leaf nodes after the first run as described before.

Once the algorithm terminates, the array {\em BestDistribution} will contain each node's distribution
that gave rise to the minimum overall error.

%\subsection{A Real Example}
%
%\begin{figure}
%\begin{center}
%\includegraphics[width=3.5in]{LargeTree.jpg}
%\end{center}
%\caption[An Actual Example]{An actual tree example.}
%\label{fig:LargeTree}
%\end{figure}
%
%\fig{LargeTree} shows an example of a graph that was used as the input to BELIEF.
%It uses a Guassian distribution as the goal distribution for the root. It also uses
%a second ditribution as the {\em fixed} given distribution for node K.
%This given distribution does not conform to (and actually opposes) the root's goal distribution which complicates the
%process of predicting distributions.
%However, in several runs the predicted distributions using BELIEF have errors less than 8\%.
%Once K's flag changes to {\em optional} the error drops to 0.1\%.
%This is predictable since the {\em fixed} flag adds a constraint that is not easily met due to its
%non-conforming distribution. The {\em optional} flag removes such a constraint.
%
%Another study using this graph was done. We used randomly generated
%given distributions assigned to a fixed number of nodes at random.
%The results show error values in the range of 0.1\% to 7\% for the highest priority goal
%and increasing accordingly for nodes with lower priority.
%Since these goals are not necessarily conforming to each other, it is predictable that
%the error seen from high priority nodes are weighted higher 
%(as seen in scoring method illustrated in \fig{algorithmFinish}) and hence the algorithm
%tries to find better distributions for nodes with higher priorities.

\section{Using Bayes Nets}
We illustrate the use of Bayes Nets with our BELIEF tool using the following three
case studies. For full details on the BELIEF algorithm, see the appendix.
\begin{figure}
\begin{center}
\includegraphics[width=3.5in]{ReqDev.pdf}
\end{center}
\caption[Defect Removal]{Dabney's ``Developer Requirements Defect 
Removal'' Bayes sub-net}
\label{fig:ReqDev}
\end{figure} 



\subsection{Case 1: A Small Example of Bayes Networks}

In a software developing environment, the first step is to prepare the requirements documentation.
Defect can be introduced while preparing the requirements and developers usually take steps to
remove such defects. However, many control factors such as ''cost/schedule pressure``, ''presentations``, 
''review quality``, and ''requirements quality`` can affect the defect removal efficiency. 
Dabney provides a graph representation of these and many other factors in \fig{ReqDev}.

Some of these factors are inherently contradictory (i.e. improving one hurts another). 
For example, the higher the ''cost/schedule pressure`` is, the lower the number of ''presentations`` will be.
Hence, it is not a straight forward approach to optimize for some goals (here, increase the defect removal efficiency 
shown as the root in \fig{ReqDev}).

For example, imagine a scenario where the developers are considering 
the values of UML ''presentations`` and ''requirements quality`` under ''cost/schedule pressure``.
The developers want to optimize their defect removal efficiency by fixing these three nodes 
in the graph and allowing other nodes to take any distribution that can help the overall optimization.

Using BELIEF, we can provide these three nodes with different (opposing) given distributions 
and find the best possible results. It is clear that the goal is to maximize the distribution in the root node.
When all three distributions are {\em fixed}, the error is in the range of 7\% to 9\%. Corresponding results are shown in \fig{ReqDevResults}.

Looking at the distributions in \fig{ReqDevResults}, we note
some distributions are more biased that others. In particular,
''cost/ schedule pressure`` influences the
final distribution in the root more than the ''requirements quality`` and ''presentations`` combined. 

\begin{figure}
\begin{center}
\includegraphics[width=3.5in]{CaseStudy1out.png}
\end{center}
\caption[Defect Removal Results]{Results of defect removal optimization with 3 fixed nodes.
The top three forward arrows show the nodes with fixed distributions and the bottom forward arrow shows the root 
node's predicted distribution using BELIEF. Compare this with the backward arrow which shows the provided goal distribution for the root node.
}
\label{fig:ReqDevResults}
\end{figure}

In the sequel, the following concept will be important.
The bottom row of \fig{ReqDevResults} shows two distributions
for the goal node of \fig{ReqDev} (fewest defects, highest
requirements quality).  Initially, BELIEF was given the
``goal'' 
distribution (bottom right) and asked to change everything needed
to achieve that distribution. The resulting distributions are
shown elsewhere in \fig{ReqDevResults}. 
Note that the ``goal'' distribution was not exactly achieved;
the ``predicted'' distribution is slightly different to the
``goal'' one.
By summing the deltas in the histograms of \fig{ReqDevResults}
we can computer the error between goal and predicted.

In this case, 
BELIEF gave an 8\% error. This
is relatively good taking into account the
opposing input constraints.
Subsequent studies in this report will explore how closely
we can make predicted approach desired.


\subsection{Case 2: The Complete Study}

As it can be seen from \fig{bayes}, Dabney's Bayesian network has 15 different sub-nets. Overall, there are
10 different root nodes that can be detected from layers 2 and 3 of this network. Layer 2 represents developer's defect
removal and layer 3 represents IV\&V's defect removal efficiency sub-nets. Layer 1's sub-nets are used as input
to sub-nets of other layers and therefore they do not contribute a root to any subgraph.

When running a graph in BELIEF, each root along with all its child nodes is considered a {\em subgraph}. Hence, when 
this network is used as the input to BELIEF, 10 subgraphs are detected. Following the arrows in \fig{bayes} for each
sub-net in layers 2 and 3 demonstrates a simple way of finding these 10 subgraphs.
BELIEF creates predictions for each of these subgraphs and their roots. The predictions have errors less than 0.1\% which is
predictable since there are no constraints (e.g. {\em fixed} distributions). Constraints are discussed in the next case study.

For each layer, BELIEF combines the error values of all the goal nodes in each subgraph corresponding to that layer and reports
the average error value for that layer. The overall error values that BELIEF reports for each layer (without constraints) are around 0.1\%.

\subsection{Case 3: Number of Constraints}

\begin{figure}
\begin{center}
\includegraphics[width=3.5in]{constraint.pdf}
\end{center}
\caption[Constraints Study]{Error values found with varying number of nodes with fixed distributions in layers 2 and 3.}
\label{fig:constraint}
\end{figure}

As it was discussed in case 2, and shown in case 1, the number of constraints in each subgraph can change the errors in predicted
distributions. In this study, we provided random constraints ({\em fixed} distributions) to leaf nodes at random and measured the error
in each layer.

To do this, we chose X\% (\mbox{$X \in \{1,2,4,8,16,32\}$}) of the nodes of the graph to receive a 
random given distribution. We then randomly chose whether the given
distribution is {\em fixed} or {\em optional}. (It should be noted that only the 
leaf nodes can have a given distribution.)
Since these constraints are assigned at random, they could be opposing other constraints.
As it is shown in \fig{constraint}, the error values increase dramatically (from less than 0.2\% to around 14\%) as the number of 
{\em fixed} distributions increase (from 0 to 47).

\newpage
\section{Conclusion}

This report has offered a missing piece of Dabney's prior studies-
for IV\&V models, BELIEF can not just predict, but work backwards
to propose changes that most let new knowledge update old knowledge.

The main effect reported here is \fig{constraint}: the more
ideas we try to squeeze into old knowledge, the harder it becomes.
This is not a bug in our tool; rather it is a fundamental property
of any tool that just to squeeze old ideas into new constraints. As
the greater the number of new ideas increases, it becomes harder
and harder to fit the old ideas into the new ones.
Bayes nets work best when general background information is 
augmented with small amounts of new knowledge. 

In this regard, Bayes nets are an excellent tool for NASA since one
way to characterize this organization is a loosely coupled
federation of teams with general, but not specific, knowledge
of what each other is doing. Sometimes (rarely) a specific
data point is transferred from Center X to Center Y, at which time
it is vital that managers extract the most information they can
from that datum.

Finally, Bayes nets are a natural tool for anomaly detection (i.e. the stated aim of this project). Anomalous
project situations that require more investigation could be detected if we can't squeeze new ideas into old beliefs.
In that case, something is not what was expected (i.e. either  the old ideas or the new data). In the framework
of this paper, such anomalies would be 
seen as large errors between predicted and goals. Note that such anomaly detection is only possible if the error was not caused by the inherent difficulty
of squeezing new ideas onto old constraints (i.e. only on the left-hand-side of  \fig{constraint}.


In summary, we recommend continuing this work, in the context of anomaly detection of Bayes net. In that case, 
the delivered system would not have automatic hooks into NASA databases since, as shown with the LINKER and
SILAP case studies, such links are hard to achieve and maintain over time. Instead, the delivered system would
be a manager's tool that, a few times a month, they would use to enter in new project beliefs or their observations
of project progress. In that scenario, only limited information would be available to our tool set but, as shown in this report,
these kinds of tools thrive when on limited information is available.
 
%
%\subsection{Bigger Picture}
%
%validation:\footnote{THIS needs lots of work. I just put the outline in here if you want it.}
%	if one is closer to goal than the other (models)
%diagnosis:
%	minimal assumptions that explain most goals
%planning:
%	least cost assumptions that achieve goal
%	considering the fact that we minimize delta from goal leaf to prediction leaf
%explanation:
%	planning + user model
%tutoring:
%	explanation + planning
%anomaly detection:
%	simple (just compare stuff)
%monitoring:
%	anomaly detection
%repair:
%	planning after anomaly detection
%
\newpage
\bibliographystyle{abbrv}
\bibliography{refs}
\newpage
\appendix
\section*{The BELIEF Algorithm}
{
\scriptsize\begin{alltt}\sffamily
\#CONSTANTS AND INITIALIZATION
MaxDistort = 2
Runs = 100
Bins = 20

\#READ AND STORE THE INPUT
\textbf{FOR} node \textbf{IN} Nodes read and store node's information
find all Roots in the input graph

\textbf{FOR} root \textbf{IN} Roots
\{
    find subgraph[root]
    \textbf{FOR} bin \textbf{IN} Bins
        initialize MinError[bin]
     MaxPriorityNode = node with maximum priority in subgraph[root]
                                (or closest to root in case of ties)
     \#START PREDICTING DISTRIBUTIONS
     \textbf{FOR} run \textbf{IN} Runs
     \{
         \#INITIALIZE PREDICTED DISTRIBUTION FOR EACH NODE
         \textbf{FOR} node \textbf{IN} Nodes of subgraph[root]
             \textbf{FOR} bin \textbf{IN} Bins
                 initialize node.PredictedDistribution[bin]
     
         \#PROCESS LEAF NODES
         \textbf{FOR} node \textbf{IN} leaf nodes of subgraph[root]
         \{
             \textbf{IF} (run == 1)
                 \textbf{IF} (node.GivenFlag == 1)
                     \textbf{FOR} each bin \textbf{IN} Bins
                         node.PredictedDistribution[bin] = node.GivenDistribution[bin]
                 \textbf{ELSE} 
                     \textbf{FOR} each bin \textbf{IN} Bins
                         value1 = a random number between 0 and 
                                       MaxPriorityNode.GoalDistribution[bin] * MaxDistort
                         node.PredictedDistribution[bin] = value1
             \textbf{ELSE}
                 \textbf{IF} (node.GivenFlag == 1 AND node.GivenDistributionStatus == fixed)
                     \textbf{FOR} each bin \textbf{IN} Bins
                         node.PredictedDistribution[bin] = node.GivenDistribution[bin]
                 \textbf{ELSE} 
                     \textbf{FOR} each bin \textbf{IN} Bins
                         value1 = a random number between 0 and 
                                       MaxPriorityNode.GoalDistribution[bin] * MaxDistort
                         value2 = BestDistribution[node][bin]
                         node.PredictedDistribution[bin] = randomSelect(value1,value2) \}
     
         \#PROCESS ALL OTHER NODES
         \textbf{FOR} node \textbf{IN} non-leaf nodes of subgraph[root]
             node.PredictedDistribution = apply node.Operand on all its child nodes
     
         \#SCORING
         \textbf{FOR} bin \textbf{IN} Bins
             initialize error[bin]
         \textbf{FOR} node \textbf{IN} Nodes of subgraph[root]
             \textbf{IF} (node.GoalFlag == 1)
                 \textbf{FOR} bin \textbf{IN} Bins
                     error[bin] = error[bin] + abs(node.PredictedDistribution[bin] - 
                                       node.GoalDistribution[bin]) * node.GoalPriority
     
         \#FINDING THE BEST
         \textbf{FOR} bin \textbf{IN} Bins
             \textbf{IF} (error[bin] \textless MinError[bin])
                 MinError[bin] = error[bin]
                 \textbf{FOR} (node \textbf{IN} leaf nodes of subgraph[root])
                     BestDistribution[node][bin] = node.PredictedDistribution[bin]\}\}
\end{alltt}}

\end{document}
