text:
\chapter{Language systems and language strategies}

Although languages around the world exhibit an overwhelming variety in
the ways they describe colours, most of the research in the domain of
colour has focussed on the use of single colour terms to describe
colour. This approach has allowed psychologists to study the nature of
categories and it is now widely accepted that colour categories are organised around a
prototype which is the colour that represents a category best
\citep{rosch73natural}. The approach has also allowed to shed light
on the ongoing nature-nurture debate in which the question is to what
degree categories are innate and to what degree they are acquired
during the development of a child \citep{berlin69basic}.

In the field of artificial language evolution, researchers try to
model the origins and evolution of artificial languages in a
controlled environment. Within this field, the domain of colour has
been intensively studied. The focus on using a single colour term to
describe a colour sample has allowed researchers to formalise models
of how a population of artificial language users can form and
coordinate their own colour-related language system
\citep{steels05coordinating, belpaeme05explaining, belpaeme07language,
  puglisi08cultural, baronchelli10modeling}.

Only a few descriptive studies reported on the domain of colour beyond
the restriction of using single terms. Some studies used an
unconstrained naming procedure in which human subjects were asked to
describe colour samples in any way they liked \citep{simpson91sex,
  lin01unconstrained}. The results of these studies seem conclusive:
only a small minority (15\% at most) of the colour samples would be
described using a single colour term. The other samples would be
described using a more elaborate expression in which modifiers or
combinations of colour terms are used. The results of
\citet{lin01unconstrained} are shown in more detail in \tabref{t:unconstrained-naming}.

\begin{table}[htbp]
  \centering
  \begin{tabular}{ld{3}d{3}}
    \lsptoprule
    category & \multicolumn{1}{c}{British (\%)} & \multicolumn{1}{c}{Chinese (\%)} \\
    \midrule
    basic & 15.70 & 10.66 \\
    modifier-basic & 23.20 & 17.36 \\
    compound & 10.32 & 18.09 \\
    qualifier-basic & 7.18 & 9.82 \\
    secondary & 42.30 & 42.42 \\
    idiosyncratic & 0.33 & 0.15 \\
    unnamed & 0.96 & 1.49 \\
    \lspbottomrule
  \end{tabular}
  \label{t:unconstrained-naming}
  \caption[Results of an unconstrained colour naming experiment for
  British and Chinese broken down by linguistic category]{Results of an unconstrained colour naming experiment for British and Chinese broken down by linguistic category \citep[after][]{lin01unconstrained}. The basic category consists of all samples that were described using a single basic colour term, such as \textit{red}. Modified basic corresponds to a basic modification of a single colour term, such as \textit{dark red}. Compounding means combining two colour categories as in \textit{bluish red}. Qualifier basic is any other combination of colour terms and modifiers (such as \textit{dark bluish red}). Secondary means that the colour is described in more detail using another object, as in \textit{blood red}. In idiosyncratic cases no clear classification could be made.}
\end{table}

Previous artificial language evolution models in which the single term
constraint has been lifted do exist, but all of these models deployed
a rather simplified view on semantics such as conjunctive combinations of
categories \citep{wellens08flexible} or predicate-argument expressions
\citep{batali02negotiation, smith03iterated, debeule08emergence}.
None of these models allow for semantics in continuous domains.

The main goal of this book is to study how the single term
restriction can be lifted in the models of artificial language
evolution for the continuous domain of colour by pushing both syntax
and semantics to a higher level of complexity.

\section{Language strategies for colour}
\label{s:strats-for-colour}

Although the domain of colour might seem fairly restricted, it is
fascinating to see how different languages around the world use
different \textsc{language strategies}\is{language strategy} to
express it. A language strategy is a particular approach to express
one subarea of meaning. An example of such a strategy could be
describing a colour using a single term which refers to a prototypical
category. A \textsc{language system}\is{language system} consists of
specific choices in how a particular language strategy is realised in
a language, like for example the exact location of the colour
categories and which terms to use to refer to these prototypes.

\subsection{Basic colour strategy}
\label{s:intro-basic-colour-strategy}

Currently, the most widely studied language strategy for colour is the
one that uses a single term to describe a colour. Most studies
restrict these terms even further to \textsc{basic colour
  terms}\is{basic colour term} which only refer to the domain of
colour and which are non-compositional \citep{berlin69basic}. The
basic colour terms for English are: \textit{white}, \textit{black}, \textit{red},
\textit{green}, \textit{yellow}, \textit{blue}, \textit{brown}, \textit{grey}, \textit{purple},
\textit{pink} and \textit{orange}, but exclude terms like \textit{sea green} or
\textit{light brown}. These terms are generally believed to refer to colour
categories. Each colour category has a \textsc{focal colour}\is{focal
  colour} which is the best example of a particular colour
category. The focal colours to which these terms refer have been
determined for a wide range of languages. These studies revealed
universal tendencies as some colours are more likely to be named by
basic colour terms than others \citep{regier05focal}.

Even though the language systems based on this strategy seem to
exhibit universal tendencies, they also show quite some
variation. In Russian, the colours that are named by the term \textit{blue}
in English are named by two terms: \textit{sinij} and \textit{goluboj}, which
could be translated as \textit{dark blue} and \textit{light blue}
\citep{safuanova07russian}. Japanese and Mandarin colour systems do
not make the distinction between green and blue, but use a single term
that covers both regions (\textit{ao} in Japanese and \textit{q\= \i ng} in
Mandarin). But the possible range of variation is even better
illustrated in Berinmo, a language spoken in some villages near the
Sepik River in Papua New Guinea, which uses only 5 basic colour terms:
\textit{mehi} which denotes red/orange/pink, \textit{nol} which covers most of
the blue and green area, \textit{wor} which roughly corresponds to
yellow/green/orange, \textit{wap} corresponds to the light colours and
\textit{kel} to the dark colours but it also includes some purple
\citep{roberson02color}. The geographic distribution of languages
around the world based on the number of basic colour categories can be
found in the World Atlas of Language Structures
Online\footnote{Available online at http://wals.info/feature/133} and
is reproduced in \figref{f:number-bcts} \citep{kay08number}.

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=\textwidth]{./intro/figures/number-bcts.pdf}
    \caption[The number of basic colour terms around the world]{The
      number of basic colour terms in languages around the world
      \citep{kay08number}.}
    \label{f:number-bcts}
  \end{center}
\end{figure}

Other systems based on this strategy vary in which dimensions of the
colour domain are relevant for the basic colour terms. The basic
colour system of Hunan\'oo, a language spoken by the Mangyans in the
Philippines, consists of four colour terms: \textit{(ma)biru} (`blackness'),
\textit{(ma)lagti} (`whiteness'), \textit{(ma)rara} (`redness') and \textit{(ma)latuy}
(`greenness'). In this system only the lightness and the red-green
opponent channels are relevant to name colours whereas the yellow-blue
opponent channel is ignored \citep{conklin55hanunoo}.

\subsection{Graded membership strategy}

The fact that each colour category has a focal colour also
implies that other colour samples are worse examples of a particular
colour category. Some languages allow their users to mark how well a
particular sample represents the prototype. In English this marking is
optional and achieved through the adverb \textit{very} and the modifying
\textit{-ish} suffix, for instance in the expression \textit{greenish}. In other
languages, such as Tarahumara, which is an indigenous language spoken
in the North of Mexico, this marking is obligatory. This language has
an elaborate system of modifiers that distinguishes three levels of
membership: \textit{-kame} which could be translated as `very', \textit{-name}
which could be glossed as `somewhat' and \textit{-nanti} for the lowest
degree of membership. An example of how this system is used for the
Turahumara colour category for red: \textit{sit\'a-} is shown in \figref{f:tarahumara} \citep{burgress83tarahumara}.

\begin{figure}[htbp]
  \begin{center}
   \includegraphics[width=\textwidth]{./intro/figures/tarahumara.pdf}
   \caption[The use of modifiers in Tarahumara]{The use of modifiers
     to express graded membership in Tarahumara shown on an array of
     Munsell chips. The bigger the circle, the more it represents a
     particular colour expression. (a) aggregate of all expressions
     using the \textit{sit\'a} root (b) \textit{sit\'akame} (very red) (c)
     \textit{sit\'aname} (somewhat red) (d) \textit{sit\'ananti} (only slightly
     red). Note how each modifier specifies a region that is further
     removed from the prototypical colour of \textit{sit\'a}. Figure from
     \cite{burgress83tarahumara}.}
    \label{f:tarahumara}
  \end{center}
\end{figure}

\subsection{Compounding strategy}

Some languages also allow users to compound two colour categories into
a new one. Especially to describe a colour sample that is not a good
example of any of the basic colour categories, this might be a very
productive strategy that increases expressivity. An example in English
would be \textit{blue-green}. This compounding can also be modulated by
additional markers, like for example the \mbox{\textit{-ish}} marker as in
\textit{brownish-red} in English.

\cite{safuanova07russian} have collected data on the focal colours of
compounds in Russian. One of their main findings is that in Russian
the order in which colour terms are compounded has an influence on
the resulting focal colour: the second term seems to be more important
in the expression. This is illustrated in the upper left segment of
\figref{f:category-combination}. The colours between \textit{\v
z\"eltyj} (`yellow') and \textit{zel\"enyj} (`green') are for example named:
\textit{zelenovato-\v z\"eltyj} (`greenish-yellow'), \textit{zel\"eno-\v z\"eltyj}
(`green-yellow'), \textit{\v z\"elto-zel\"enyj} (`yellow-green') and \linebreak\textit{\v
z\"eltovato-zel\"enyj} (`yellowish-green') where the suffix \textit{-ato}
acts as a modulator.

\begin{figure}[htbp]
  \begin{center}
   \includegraphics[width=0.6\textwidth]{./intro/figures/category-combination.pdf}
   \caption[Compound chromatic terms in Russian]{Compound chromatic
     terms projected on the hue plane of the NCS colour space. The
     second term in the compound clearly has a bigger impact on the
     resulting focal colour than the first one. The colours between
     \textit{\v z\"eltyj} (`yellow') and \textit{zel\"eno} (`green') are for example
     named: (13) \textit{zelenovato-\v z\"eltyj} (`greenish-yellow'), (14)
     \textit{zel\"eno-\v z\"eltyj} (`green-yellow'), (15) \textit{\v
     z\"elto-zel\"enyj} (`yellow-green') and (16) \textit{\v
     z\"eltovato-zel\"enyj} (`yellowish-green'). Figure from
     \cite{safuanova07russian}.}
    \label{f:category-combination}
  \end{center}
\end{figure}

\subsection{Basic modification strategy}

Similarly, many language systems allow for the use of basic
modifiers which modify some aspects of a colour category. In English
for example, users can modify the brightness and the chromaticity of a
colour category through the use of modifiers (\textit{light} or \textit{dark}
for modifying the brightness and \textit{bright} or \textit{pale} for modifying
the chromaticity). This strategy has been attested for a wide range of
languages, including Vietnamese \citep{alvarado02modifying} and
Chinese \citep{lin01unconstrained}.

Although basic modifiers are quite commonly used, only a few
papers report on the exact transformation that is implied by these
modifiers. One exception is the study by \cite{safuanova07russian} of
the Russian language, in which the authors determined the focal
colours of the modified categories. An example of such an analysis in
the Natural Color Sytem (see Appendix \ref{s:NCS}) is shown in \figref{f:intro-russian-modifiers}. The modifiers \textit{t\"emno-} (`dark') and
\textit{svleto} (`light'), modify the focus of the basic category parallel to
the blackness dimension (W-S). The modifiers \textit{bledno-} (`pale') and
\textit{jarko-} (`bright') shift the chromaticity of the basic colour
category (W-C or S-C) \citep{safuanova07russian}.

\begin{figure}[htpb]
  \centering
  \includegraphics[width=.5\textwidth]{./intro/figures/russian-diagram.pdf}
  \caption[Location of modified basic colour foci in Russian]{Location
    of modified basic colour foci in Russian projected into the NCS
    blackness-chromaticity triangle. \textit{t\"emno-} (`dark', solid
    circle), \textit{jarko-} (`bright', sun), \textit{svetlo-} (`light', open circle) and  \textit{bledno-} (`pale', dashed circle). Figure
    from \cite{paramei05singing}.}
  \label{f:intro-russian-modifiers}
\end{figure}

\subsection{Other strategies}

Another strategy that is often used to name colours, is suggesting
colours by naming an object that is typical for that colour (like for
example \textit{lavender} or \textit{salmon} in English). These object names can
also be used in combination with basic colour terms (like \textit{sky blue}
or \textit{cherry red}). Even though the abundant usage of these terms has
been confirmed in unconstrained naming experiments, like for example
in English and Chinese \citep{lin01unconstrained}, the actual focal
colours of these expressions have yet to be determined. The previous
list of language strategies is not exhaustive, as other strategies to
describe colours exist (for example using comparatives like in \textit{most green}).

\section{Modelling language strategies and linguistic interaction}
\is{language strategy!modelling}

Modelling a language strategy starts with the reverse engineering of
the semantic and syntactic templates that allow language users to
conceptualise and express a particular subarea of meaning in
language. A language strategy also includes the operationalisation of
a series of learning operators, which will be discussed later.

In the \textsc{basic colour strategy}, the semantic template defines how
to select the appropriate colour category to describe a colour sample,
for example, the category that is most similar to that sample. The
syntactic template could then define a lexicon in which categories are
associated to terms. These templates can be used in both production
and interpretation.

The performance of the semantic and syntactic templates can be
evaluated in a \textsc{baseline experiment}\is{baseline experiment}.
In such an experiment, these templates are instantiated
based on a natural language system that is provided by the
experimenter. It allows to model a natural language system and to test
its simulated performance in a benchmark using simulated language
users, or agents.

%\subsection{Modelling linguistic interaction}
\label{s:intro-language-games}

In order to model the function of a language strategy, I will use the
language game paradigm \citep{steels96self}. In this paradigm,
language users are modelled as \textsc{agents}\is{agent} and a language community
as a \textsc{population of agents}. These agents constantly engage in
local interactions, or \textsc{language games}\is{language game} in
which they try to achieve \textsc{communicative goals}\is{communicative goal}, like for example drawing the
attention of another agent to one of the objects in a shared
environment or \textsc{context}\is{context}. Achieving these communicative goals is considered to be
the function of a language strategy.

A language game typically involves two agents randomly drawn from the
population. One is assigned the role of the speaker and the other the
role of the hearer. The speaker selects a private communicative goal,
for which it conceptualises a meaning. Using its current linguistic
knowledge it produces an utterance to express this meaning. The hearer
parses this utterance using its own current linguistic knowledge and
interprets the resulting meaning in his own world model. This
interpretation might lead to some actions which should allow the
speaker to verify whether the intended communicative goal was
reached. If this is not the case, the speaker reveals the
communicative goal to the hearer. Both agents update their linguistic
and conceptual knowledge in order to become more successful in future
interactions. All the processes involved in one interaction are
summarised in a \textsc{semiotic cycle}\is{semiotic cycle} which is
shown in \figref{f:intro-semiotic-cycle}
\citep{steels03reentrance}.

\begin{figure}
  \begin{center}
   \includegraphics[width=.8\textwidth]{./intro/figures/semiotic-cycle.pdf}
   \caption[The semiotic cycle of a language game]{The semiotic cycle
     of a language game. The speaker selects a communicative goal
     using its own world model, conceptualises a meaning and renders
     an utterance for this meaning. The hearer parses this utterance
     into meaning which is interpreted using its own world model. This
     interpretation might lead to some action, upon which the speaker
     provides feedback (not shown in figure).}
    \label{f:intro-semiotic-cycle}
  \end{center}
\end{figure}

\subsection{Language games for colour}
\label{s:language-games-for-colour}

The first language game in which colour could be expressed by the
agents, was the Talking Heads experiment
\citep{steels99talking}. In this experiment contexts consisted
of coloured geometrical figures on a whiteboard which were perceived
by two pan-tilt cameras. Software agents could be embodied in these
cameras. The communicative goal was to draw the attention of the other
agent to one of these figures. The agents could describe several
domains to achieve this goal, including the domain of colour. It soon
became apparent that the domain of colour was rich and complex enough
to be studied in isolation.

This observation led to the development of the \textsc{colour naming
  game}\is{language game!Colour Naming Game}\is{Colour Naming
  Game|see{language game}} \citep{steels05coordinating,
  belpaeme05explaining, belpaeme07language, puglisi08cultural,
  baronchelli10modeling} in which agents were restricted to use only
the domain of colour to achieve the communicative goal. The use of
information in other domains, for example spatial relations, was not
allowed. The Colour Naming Game has been devised to study how a
population of agents can form and align its own colour category
systems. In these studies the contexts were based on the random
selection of a number of colour samples from a large set of
colour samples. A colour sample is an abstract representation that
only contains colour information.

\newpage
In the \textsc{grounded colour naming game}\is{language
game!Grounded Colour Naming Game}\is{Grounded Colour Naming
Game|see{language game}} (see \sectref{s:experiments-grounded}),
embodied agents (ro\-bots) are placed in a closed office environment and
the contexts consisted of toy-like objects that are placed in front of
the agents. Although embodied agents could easily use different
domains to describe the objects in front of them, they are only
allowed to describe the colour information of these objects. In this
language game, the utterances are still restricted to a single term.

I introduce the \textsc{colour description game}\is{language
  game!Colour Description Game}\is{Colour Description
  Game|see{language game}} (see Chapters
\ref{s:graded-membership-strategy}--\ref{s:basic-modification-strategy})
in which the restriction of using a single colour term to describe the
colour of an object is lifted.

\subsection{Background assumptions}

The language paradigm focusses on the functional and evolutionary
aspect of languages, but this can only be achieved by making some
assumptions. It is assumed that agents are capable of giving joint
attention \citep{tomasello95jointattention}, constructing world
models, taking turns, being cooperative,\footnote{\cite{wang08self}
  show that uncooperative agents can also bootstrap a language under
  certain conditions.} and so on. These assumptions are each
interesting and far from trivial research topics by
themselves. Although it is clear that these processes are
prerequisites for studies in the language game paradigm, they are not
in the main focus of this paradigm.

\section{Self-organisation of language systems}

A language system is not a static system, but rather a living system
that is constantly evolving. In the self-organisation of language systems
based on the basic colour strategy, language systems are expanded by
the introduction of new colour categories. By studying a wide range of
contemporary language systems for colour, some researchers have even
proposed a universal evolutionary order by which colour categories are
introduced to a language \citep{berlin69basic}.

% todo: meer uitleg

\section{Modelling the self-organisation of language systems}

In order to model the self-organisation of language systems\is{language system!self-organisation of},
the implementation of a language strategy needs\enlargethispage{\baselineskip}
to be extended with a series of learning operators that specify:

\begin{enumerate}
\item how a language user can acquire a language system from other
  language users using \textsc{adoption operators}\is{learning operators!adoption operator}
\item how language users can update their knowledge of the language
  system after a linguistic interaction using \textsc{alignment
    operators}\is{learning operators!alignment operator}
\item how a language user can expand a language system using
  \textsc{invention operators}\is{learning operators!invention operator}
\end{enumerate}

For the basic colour strategy, the adoption operator allows a user to
adopt a new colour category and its associated colour term when a new
unknown term is encountered. The invention operators allow users to
introduce new colour terms that are associated to new colour
categories to the language system. Finally, the alignment operator
specifies that agents should update their colour categories to better
represent the topic when the linguistic interaction was successful.

An \textsc{acquisition experiment}\is{acquisition experiment} could be implemented in which the
adoption and alignment operators of a language strategy are
tested. Such an experiment involves two agents in which one needs to
acquire a predefined language system from another agent. By comparing
the performance of the agent that is acquiring the language system to
the performance in the baseline experiment, the performance of the
adoption and alignment operators can be evaluated.

The final step would be a \textsc{formation experiment}\is{formation experiment} in which a
population of agents needs to construct its own language system from
scratch. Such an experiment checks the performance of the invention
operators by comparing the performance of the population of agents in
this experiment to the baseline performance.

%\subsection{Language as a complex adaptive system}

Within the language game paradigm, a language system is considered to
be a \textsc{complex adaptive system} \citep{steels00language}. It is shaped
and reshaped by its users to suit their needs, even over the course of
a single dialogue \citep{garrod94conversation}, in order to become
more successful in communication while minimising cognitive effort. No
single user has a complete view of the language and no user can
control the linguistic behaviour of the complete group. Instead,
language is a self-organising system that emerges through local
interactions or language games.

\section{Evolution of language strategies}
\is{language strategy!evolution}

If one takes a historical perspective on language, one can also
detect shifts in dominance from one language strategy to another. In
the evolution of the basic colour terms in English an interesting
meaning shift occurred: at their Indo-European root most colour terms
had primarily a brightness meaning sense. Around the transition from
Old to Middle English the hue meaning sense of all basic colour terms became
more dominant than the original brightness sense
\citep{casson97shift}. Both meaning senses could be thought of as
different variations of the basic colour strategy.

This is illustrated in \figref{f:history-yellow} in which the
history of the term \textit{yellow} is shown. In Indo-European its
syntactic form was \textit{ghel} which was primarily used to refer to the
shining (of yellow metals). In Old English the term \textit{geolo} acquired
a hue sense and could be used to refer to the colour of some silk
cloth. In the transition to Middle English \textit{yelou} the hue sense
became the more dominant one and the term could also be used to refer
to for example yolk and ripe corn, although it could still be used to
refer to gold. The same is true for all other basic colour terms. Most
interestingly, all colour terms that were introduced to English after
this shift, like for example \textit{orange}, never had a brightness sense
but only a hue sense \citep{casson97shift}. Similar meaning shifts
have been reported in a wide range of languages
\citep{maclaury92brightness}.

\begin{figure}
  \begin{center}
   \includegraphics[width=.8\textwidth]{./intro/figures/history-yellow.pdf}\\[-1\baselineskip]
   \caption[The evolution of the term \textit{yellow} in English]{The
     evolution of the term \textit{yellow} in English. Like almost all
     other basic colour terms, its meaning shifted from brightness to
     hue around the transition from Old English to Middle
     English \citep{casson97shift}.}
    \label{f:history-yellow}
  \end{center}
\end{figure}

\section{Modelling evolution of language strategies}

Given the observed evolution and selection at both the level of
language strategies and the level of linguistic items that make up a
particular language system, I explore the hypothesis that linguistic
agents need explicit representations of language strategies which they
use to keep track of how successful a particular strategy has been in
communication. These explicit representations allow me to introduce an
additional layer of selection at the level of language strategies.

\section{Structure of this book}

\chapref{s:formalisms} will introduce the formalisms that will be
used to model language strategies and language systems.

\partref{s:language-strats} of this book focusses on the
reconstruction of the general semantic and syntactic structures that
allow me to run baseline experiments for several of the language
strategies identified in this chapter: the basic colour strategy, the
graded membership strategy, the compounding strategy and the
basic modification strategy.

In \partref{s:evolution-of-language-systems}, I will focus on the
self-organisation of language systems that are based on one language strategy,
namely the basic colour strategy, by introducing its adoption,
alignment and invention operators. This will allow me to study the
impact of embodiment on the performance of these operators. I will
also show results of related experiments on language systems that are
realisations of this strategy.

In \partref{s:evolution-of-language-strategies}, I
will present a model that allows to study the evolution of language
strategies based on linguistic selection. I will start by introducing
two variants of the basic colour category and show an experiment that
models the meaning shift as documented for the history of basic colour
terms. I will also explore the origins of language strategies based on
a combinatorial search process.

The concluding \partref{s:conclusion} will give an overview of
the main results that have been achieved in this book and will
outline some directions for future research.

max_stars_repo_name: langsci/Bleys

max_issues_repo_name: langsci/Bleys

max_forks_repo_name: langsci/Bleys


text:
\documentclass[twoside]{MATH77}
\usepackage[\graphtype]{mfpic}
\usepackage{multicol}
\usepackage[fleqn,reqno,centertags]{amsmath}
\begin{document}
\opengraphsfile{pl02-14}
\begmath 2.14 Sine and Cosine Integrals

\silentfootnote{$^\copyright$1997 Calif. Inst. of Technology, \thisyear \ Math \`a la Carte, Inc.}

\subsection{Purpose}

Given $x$, these subprograms compute the Sine Integral, Si$(x)$, the Cosine
Integral, Ci$(x)$, and an entire function, Cin$(x)$ related to the cosine
integral. These functions are defined as%
\begin{align*}
\text{Si}(x)&=\phantom{-}\int_0^x\frac{\sin (s)}s\,ds,\\
\text{Ci}(x)&=-\int_x^\infty \frac{\cos (s)}s\,ds,\quad \text{and}\\
\text{Cin}(x)&=\phantom{-}\int_0^x\frac{1-\cos (s)}s\,ds,
\end{align*}

Ci$(x)$ and Cin$(x)$ satisfy the relation Ci$(x)+\text{Cin}(x)=\ln x+\gamma $%
, where $\gamma $ is Euler's constant, approximately 0.57721~56649. To
calculate the related sine integral defined by si$(x)=-\int_x^\infty \frac{%
\sin (s)}s\,ds$ use the identity si$(x)=\text{Si}(x)-\pi /2.$

Reference [1] provides further discussion of the properties of the Sine and
Cosine integrals.

\subsection{Usage}

\subsubsection{Program Prototype, Single Precision}

\begin{description}
\item[REAL]  \ {\bf X, SSI, SCI, SCIN, T}
\end{description}

Assign a value to X and use one of the following function references.

To compute the Sine Integral Si$(x):$
$$
\fbox{{\bf T = SSI(X)}}
$$
To compute the Cosine Integral Ci$(x)$ for $x > 0:$
$$
\fbox{{\bf T = SCI(X)}}
$$
To compute the entire function Cin$(x)$ related to the Cosine Integral:
$$
\fbox{{\bf T = SCIN(X)}}
$$

\subsubsection{Argument Definitions}

\begin{description}
\item[X]  \ [in] Argument of function.
\end{description}

\subsubsection{Modification for Double Precision}

For double precision usage change the REAL type statement to DOUBLE
PRECISION and change the function names to DSI, DCI or DCIN respectively.
\vspace{10pt}

\hspace{5pt}\mbox{\input pl02-14 }

\subsection{Examples and Remarks}

See DRSSI and ODSSI for an example of the usage of these subprograms.

Si$(x)$ is an odd function and Cin$(x)$ is an even function. Ci$(x)$ is not
defined for $x \leq 0.$

The notations for these functions vary. We use the notation of
\cite{ams55:sin-int}.

\subsection{Functional Description}

The computer approximations for these functions use Chebyshev polynomial
expansions.

These subprograms were tested on the IBM PC/AT by comparing the results to
tables in \cite{ams55:sin-int}.

\bibliography{math77}
\bibliographystyle{math77}

\subsection{Error Procedures and Restrictions}

The subprograms SSI and SCIN detect no error conditions. The subprogram SCI
issues an error message if $x \leq 0$. The error message is issued by way of
the error message processor at level~0, and the returned function value is
0.0. See Chapter~19.2 for further description of the error message processor.

\subsection{Supporting Information}

The source language is ANSI Fortran~77.

Subprograms designed and developed by E. W. Ng, JPL, 1970. Modified by W. V.
Snyder, JPL, 1989.

\begin{tabular}{@{\bf}l@{\hspace{5pt}}l}
\bf Entry & \hspace{.35in} {\bf Required Files}\vspace{2pt} \\
DCI & \parbox[t]{2.7in}{\hyphenpenalty10000 \raggedright
DCI, DCPVAL, DERM1, DERV1, ERFIN, ERMSG\rule[-5pt]{0pt}{8pt}}\\
DCIN & \parbox[t]{2.7in}{\hyphenpenalty10000 \raggedright
DCI, DCPVAL, DERM1, DERV1, ERFIN, ERMSG\rule[-5pt]{0pt}{8pt}}\\
DSI & \parbox[t]{2.7in}{\hyphenpenalty10000 \raggedright
DCPVAL, DSI\rule[-5pt]{0pt}{8pt}}\\
\end{tabular}

\begin{tabular}{@{\bf}l@{\hspace{5pt}}l}
\bf Entry & \hspace{.35in} {\bf Required Files}\vspace{2pt} \\
SCI & \parbox[t]{2.7in}{\hyphenpenalty10000 \raggedright
ERFIN, ERMSG, SCI, SCPVAL, SERM1, SERV1\rule[-5pt]{0pt}{8pt}}\\
SCIN & \parbox[t]{2.7in}{\hyphenpenalty10000 \raggedright
ERFIN, ERMSG, SCI, SCPVAL, SERM1, SERV1\rule[-5pt]{0pt}{8pt}}\\
SSI & \parbox[t]{2.7in}{\hyphenpenalty10000 \raggedright
SCPVAL, SSI}\\
\end{tabular}

\begcode

\medskip\
\lstset{language=[77]Fortran,showstringspaces=false}
\lstset{xleftmargin=.8in}

\centerline{\bf \large DRSSI}\vspace{10pt}
\lstinputlisting{\codeloc{ssi}}

\vspace{30pt}\centerline{\bf \large ODSSI}\vspace{10pt}
\lstset{language={}}
\lstinputlisting{\outputloc{ssi}}

\closegraphsfile
\end{document}

ext: tex


text:
\documentclass{sixpage}
\title{The Demo of an Amazon 6-pager}
\subtitle{\href{https://writingcooperative.com/the-anatomy-of-an-amazon-6-pager-fc79f31a41c9}{The Anatomy of an Amazon 6-pager}}  % 一句话总结目标用户是哪些人，他们可以获得什么价值
\author{Jesse Freeman}
\date{\today}
%\imchinese % 中文文档请去除注释，进入中文风格
\begin{document}
    \maketitle
%https://writingcooperative.com/the-anatomy-of-an-amazon-6-pager-fc79f31a41c9

    \section{Introduction}
    This document aims to outline the current state of Pixel Vision 8's business and share our strategic priorities for 2020.
    Our mission is to work with developers interested in creating retro-looking 8-bit games by connecting with them from the moment they get their first idea through completing a project.
    PV8 lives in a subset of the game development tool space known as Fantasy Consoles(see appendix 7.1).
    These Fantasy Consoles are small, self-contained, dedicated game development environments with build-in tools reminiscent of old 8-bit consoles or computers.
    While we continue to execute via our website, itch.io, Twitter, and Discord (see appendix 7.2), we still need to amplify our message to reach other developers interested in using a Fantasy Console.

    Early on, PV8 gained attention from developers as an alternative to existing Fantasy Consoles due to a few key distinguishers.
    These include the ability to customize project limitations, a rich graphics UI(user interface), and the project is open source.
    Most of the competing Fantasy Consoles use come form of command-line interface for working with the underlying file system and tools.
    These Fantasy Consoles emulate early DOS and Commodore 64 style operating systems from the late 70s.
    We purposely modeled PV8 around a more user-friendly operating system akin to the first Macintosh computers of the mid-80s to increase adoption among millennials.

    Given the recent crowding of this space, we need to reduce the time it takes to get started, unblock technical hurdles, and offer a clear path to export stand-alone Windows, Mac, and Linux games from PV8 to distinguish ourselves from the competition.
    By removing developer friction, we hope to increase organic adoption and, in turn, attract developers that produce higher quality games.
    Our focus in 2020 will help establish PV8 as the number one Fantasy Console developers want to use, ensuring a healthy pipeline of completed games as we head into 2021.

    \section{Goals}
    In 2020, we plan to focus on and achieve the following goals:
    \begin{itemize}
        \item \textbf{Increase stability}: Reduce the total number of active Github issues from 100 on 12/31/2019 to 25 12/31/2020, a decrease of 75\% YoY.
        \item \textbf{Increase active users}: Grow the active developer community from 7.4k on 12/31/2019 to 20k by 12/31/2020, an increase of 63\% YoY.
        \item \textbf{Increase game release}: Create additional tutorials, documentation, and code examples that enable developers to create new games from 5 on 12/31/2019 to 20 by 12/31/2020, +75\% YoY.
    \end{itemize}

    \section{Tents}
    The following tents are guiding principles we use to evaluate and prioritize Pixel Vision 8 activities:
    \begin{itemize}
        \item \textbf{Quality over quantity}: We will not rush out updates on a set schedule. Instead, we will work towards more significant releases that fix multiple bugs and improve the overall stability of the tooling.
        \item \textbf{Keep scale in mind}: While we'd like to develop individual relationships with each user, we should focus on features and marketing programs that address the top of the funnel to increase developer adoption at scale.
        \item \textbf{Reduce developer friction}: We want to focus on educating developers through in-depth technical content and tool documentation instead of relying solely on community knowledge transfer.
        \item \textbf{Game first approach}: Developers should have a clear publishing path, and our tools need to assist in making this process as easy and intuitive as possible.
        \item \textbf{Play with developers who play with us}: We will proiritize relationships with developers who are more willing to support PV8 and collaborate. To have long-term success, we believe mutual interests will be the most sustainable.
        \item \textbf{Organic trumps paid}: Although some kind of paid promotions will be critial for building and accelerating adoption, we want to focus on driving organic demand through community building adn not on paid user acquisition.
    \end{itemize}

    \section{State of the Business}
    Pixel Vision 8 has three primary verticals that contribute to the business: the framework, Pixel Vision OS, and technical content.
    The framework represents the open-source C\# codebase that runs the Fantasy Console itself on Windows, Mac, and Linux.
    This open-source project lives on GitHub and is licensed under the Microsoft Public License (see appendix 7.3).
    Also, PV8 uses a custom-built operating system written in Lua and runs on top of the framework as a stand-alone application.
    The OS includes all of the tools that developers use to make games as well as a way to manage project files and export finished games.
    Finally, the technical content includes all of the documentation, tutorials, and code examples that not only help on board developers, but also generate the primary source of income to support the project.

    In 2019, 66\% of our total income came from itch.io, with the remaining 34\% generated from the main website through direct sales.
    These two revenue sources accounted for \$3.7k in gross revenue, thanks to the addition of 786 new paying customers (see appendix 7.4).
    While this covered operational costs (see appendix 7.5), it stunted the ability to scale up development verses the time put into supporting and building new features (see appendix 7.6).
    This data also points to a failure with the subscription business model since customers favored one time purchases instead of smaller monthly payments.
    Over time, the lack of subscriptions will impact the recurring revenue potential in 2020.
    In order to offset the lack of subscriptions, we will instead focus on ways to increase direct sales through complementary content such as tutorials and art packs to make the core product free to grow the user base.
    Finally, we look to expand alternative income opportunities such as itch.io's "pay what you want" feature and Github sponsorships to make the base product free.

    \section{2019 Lessons Learned}
    2019 was a successful year for increasing paid and non-paying customers, product stability, and reducing dependence on direct one on one customer support.
    As of December 31, 2019, we had a total of 7.4k customers.
    Our unique feature set helped contribute to this growth.
    Working with a well-known pixel artist, Christina Antoinette Neofotistou (@castpixel), also helped build additional awareness and credibility in the indie game developer community.

    One challenge we faced last year was cultivating more developers to create games.
    Although there has been a great deal of interest on Twitter, very few games have been created by the community in 2019.
    As a result, developers are not widely using Pixel Vision 8, which continued to be a problem in activating the community last year.
    To achieve the 2019 goal of adding 1k new users by EOY, we decided to focus more on features, and the type of content developers asked for, instead of directly pursuing customer acquisition.
    Since there were substantial changes between releases in 2019, this required significant rewrites and editing, which proved to be time-consuming.

    \section{Strategic Priorities}
    In 2020, our priorities are to reduce developer friction, improve stability, and encourage high-quality games to be created with Pixel Vision 8.
    To do this, we will work to enhance technical content, discoverability in the broader Fantasy Console community, and explore new marketing opportunities in a crowded space.
    However, we still control our destiny, and as such, we will leverage our channels to improve awareness around building games with PV8.
    Where we are unable to reduce friction or increase growth organically, we will work to achieve the following strategic priorities:

    \subsection{Focus on increasing stability of the product by closing 50+ open issues, -75\% YoY.}
    \underline{Finish Pixel Vision OS tools:} Currently, the Pixel Vision OS tools are in varying states of completion.
    Each one needs to be audited, overhauled, and templatized, so consistency exists across the board.
    That requires the standardization of a copy/paste and undo/redo system, easier to use UI components and a formal workflow for converting designs into actual working tools.
    Not only is this critical for our developers to have the best tools possible, but it also sets us up for success.
    As we head into 2021, we will begin to look into creating new tools to handle more advanced tasks like building meta-sprites and animations and sharing games online via the website's backend.

    \newpage

    \section{FAQ} % 1~2页，提出读者可能存在的疑问，并予以解答
% 设想读者看完正文后可能存在的疑问
% 列出读者可能提出的问题
% 按重要性排序并编号
% 准备好答案，确保答案准确且简洁
% 理想情况下，所有关键问题均已在FAQ中得到解决，会议上可以集中讨论其他未解决的问题
% 好的FAQ可帮助团队提前预知重要的问题，有助改善思维清晰度

    \newpage

    \section{附录} % 不超过10页,提供数据，以支撑正文论点
% 附录非必要，6-page正文应能独立使用
% 附录应包含支持正文论点所需的数据
% 不应包含无法放进正文的内容

\begin{lstlisting}[language=C,caption=casdcasdc code,style=diff]
@@ librabbitmq/amqp_openssl.c:180 -85,8 +85,8 @@
#include<stdio.h>
static int amqp_ssl_socket_open(void *base, const char *host, int port, struct timeval *timeout) {
	// (*@\dots@*)
+	cert = SSL_get_peer_certificate(self->ssl);
	result = SSL_get_verify_result(self->ssl);
-	if (X509_V_OK != result) {
+	if (!cert || X509_V_OK != result) {
		goto error_out3;
	}
	// (*@\dots@*)
}
\end{lstlisting}

\begin{lstlisting}[language=yaml,caption=yaml example]
---
key: value
map:
    key1: "foo:bar"
    key2: value2
list:
  - element1
  - element2
# This is a comment
listOfMaps:
  - key1: value1a
    key2: value1b
  - key1: value2a
    key2: value2b
---
\end{lstlisting}
\end{document}


text:
\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsmath}
\usepackage{caption}
\usepackage{wrapfig}
\usepackage{tikz}
\usepackage[none]{hyphenat}

\title{Pythagorean Theorem}
\author{1505080}
\date{\today}

\usepackage{natbib}
\usepackage{graphicx}

\begin{document}

\maketitle

\section{Introduction}
    In this document, we present the very famous theorem in mathematics: Pythagorean theorem, which is stated as follows.\\
    \\
    \textbf{Theorem 1.1 (Pythagorean theorem) } \textit{The square of the hypotenuse (the side opposite the right angle) is equal to the sum of the squares of the other two sides.} \\
    \par
    Numerous mathematicians proposed various proofs to the theorem. The theorem was long known even before the time of Pythagoras. Pythagoras was the first to provide with a sound proof. The proof that Pythagoras gave was by \textit{rearrangement}. Even the great Albert Einstein also proved the theorem without rearrangement, rather by using dissection. Figure \ref{fig:pythThmFig1} shows the visual representation of the theorem.

    \begin{figure}[h!]
        \centering

        \begin{tikzpicture}[scale = 0.5]
            % \draw [help lines,step = 1 cm] (-10,-10) grid (10,10);
            % \draw (-10,0) -- (10,0);
            % \draw (0,-10) -- (0,10);

            \definecolor{fillColor}{RGB}{215,235,242};
            \path [fill = fillColor] (-4.099101966,-5.854101966) -- (-4.099101966,5) -- (6.75,5) -- (6.75,-5.854101966) -- (-4.099101966,-5.854101966);

            \definecolor{aColor}{RGB}{164,117,169};
            \path [fill = aColor] (0,0) -- (1.5,0) -- (1.5,-1.5) -- (0,-1.5) -- (0,0);

            \definecolor{bColor}{RGB}{247,146,150};
            \path [fill = bColor] (1.5,0) -- (1.5,3) -- (4.5,3) -- (4.5,0) -- (1.5,0);

            \definecolor{cColor}{RGB}{30,180,220};
            \path [fill = cColor] (0,0) -- (-3,1.5) -- (-1.5,4.5) -- (1.5,3) -- (0,0);

            \draw[red] (0,0) -- (1.5,0) -- (1.5,3) -- (0,0);
            \draw[blue] (1.5,0.35) -- (1.15,0.35) -- (1.15,0);

            \definecolor{nodeColor}{RGB}{90,26,107};

            \node [below, nodeColor] at (0.75,0) {$a$};
            \node [right, nodeColor] at (1.5,1.5) {$b$};
            \node [left, nodeColor] at (0.75,1.5) {$c$};

            \path [fill = aColor] (0.75,-2.927050983) -- (2.25,-2.927050983) -- (2.25,-4.427050983) -- (0.75,-4.427050983) -- (0.75,-2.927050983);
            \node [nodeColor] at (1.5,-3.677050983) {$a^2$};

            \node [nodeColor] at (2.75,-3.677050983) {$+$};

            \path [fill = bColor] (3.25,-2.177050983) -- (6.25,-2.177050983) -- (6.25,-5.177050983) -- (3.25,-5.177050983) -- (3.25,-2.177050983);
            \node [nodeColor] at (4.75,-3.677050983) {$b^2$};

            \node [nodeColor] at (0.25,-3.677050983) {$=$};

            \path [fill = cColor] (-3.599101966,-2) -- (-.25,-2) -- (-.25,-5.354101966) -- (-3.599101966,-5.354101966) -- (-3.599101966,-2);
            \node [nodeColor] at (-1.922050983,-3.677050983) {$c^2$};

        \end{tikzpicture}

        \caption{Visual representation of the famous Pythagorean theorem.}
        \label{fig:pythThmFig1}
    \end{figure}

    \begin{figure}[h!]
        \centering

        \begin{tikzpicture}[scale = 0.67]
            %\draw [step = 1 cm, help lines] (-5,-5) grid (5,5);
            \draw [blue, ultra thin] (-3.398076211,0) -- (3.398076211,0);
            \draw [blue, ultra thin] (0,-3.398076211) -- (0,3.398076211);

            \draw [blue, ultra thick] (0,0) circle (3);

            \draw [red] (0,0) -- (2.598076211, 1.5);
            \definecolor{arcColor}{RGB}{93,134,182}

            \draw [arcColor] (1,0) arc [radius = 1, start angle =0, end angle = 30];

            \draw [arcColor] (0,1.5) -- (2.598076211, 1.5) -- ( 2.598076211,0);

            \draw[black] (2.598076211, 1.5) -- (3.398076211, 1.5);
            \draw[black] (2.598076211, 1.5) -- (2.598076211, 2.3);

            \draw[blue, thick, <->, >=latex] (0,2) -- (2.598076211, 2);
            \draw[blue, thick, <->, >=latex] ( 3.098076211,0) -- (3.098076211, 1.5);

            \node [above] at (1,2) {$\cos{\theta}$};
            \node [right] at (3.098076211,0.75) {$\sin{\theta}$};
            \node [above] at (1.1,0) {$\theta$};

            \node[rotate = 30, red, above] at (1.299038106, 0.75) {r=1};

        \end{tikzpicture}

        \caption{Alternate representation of Pythagorean theorem.}
        \label{fig:pythThmFig2}
    \end{figure}

\section{Trigonometric Forms}
    Lots of other forms of the same theorem exist. The most useful, perhaps, are expressed in trigonometric terms, as follows:

    \begin{equation}
            \sin^2\theta + \cos^2\theta = 1
            \label{eqn:pythThmEqn1}
    \end{equation}

    \begin{equation}
            \sec^2\theta - \tan^2\theta = 1
            \label{eqn:pythThmEqn2}
    \end{equation}

    \begin{equation}
            \mathrm{cosec}^2\theta - \cot^2\theta = 1
            \label{eqn:pythThmEqn3}
    \end{equation}

    \subsection{Representing the First}
        Taking \ref{eqn:pythThmEqn1}, we can show them as shown in Figure\ref{fig:pythThmFig2}. When we take a point at unit distance from the origin, the $y$ and $x$ co-ordinates become $\sin\theta$ and $\cos\theta$ respectively. Therefore, sum of the squares of the two becomes equal to the square of the unit distance, which, of course, is 1.

\end{document}


text:
\documentclass[././main.tex]{subfiles}

\begin{document}
\section{Ha'ard}
A small settlement scraping by in the ruined halls of the Harvard stop along the MBTA's Red Line. The camp is run by whoever has the people's respect -- there's not enough to go around for anything else to work.

\end{document}

max_stars_repo_name: Noah-Houghton/Eldritch-Apocalypse

max_issues_repo_name: Noah-Houghton/Eldritch-Apocalypse

max_forks_repo_name: Noah-Houghton/Eldritch-Apocalypse


text:
% !TEX program = xelatex

\documentclass{resume}
\linespread{1.04}
\begin{document}
\pagenumbering{gobble}

\name{Moyang He}

\contactInfo{iammoyang@gmail.com}{206~-~390~-~0024}{Seattle, WA, 98115}

\section{Experience}
\datedsubsection{{Facebook,~~ Software Engineer}}{2018 -- Now}
\datedsubsection{{Facebook,~~  Software Engineer Intern}}{2017}
\datedsubsection{{Amazon,~~ Software Development Engineer Intern}}{2016}

\section{Industrial Projects}

\datedsubsection{Facebook Login OAuth Dialog}{Facebook}
\begin{itemize}
    \item Improve and develop Facebook login OAuth dialog to enable 3rd party apps to use Facebook Login
    \item Create framework for other product teams to build team specific Facebook Login experience
\end{itemize}

\datedsubsection{Multiple Modern Web Application}{Facebook}
\begin{itemize}
    \item Contribute on multiple internal and external React web applications in Facebook including Facebook Ads Manager, the largest React project in the world
    \item Apply best practice of modern web app, use GraphQL and Relay to interact with backend service, add data schema support enable Flow and Lint checks
\end{itemize}

\datedsubsection{Facebook Pages API}{Facebook}
\begin{itemize}
    \item Develop new features and maintain Facebook Pages API that is used by millions of third party developers who want to leverage Facebook platform. Follow Facebook Graph API standard.
    \item Define and implement Facebook API Rate Limit system running on extremely high call volume(billions call per day) for data integrity protection and anti-scrapping. Support downstream services, products and teams.
\end{itemize}

\datedsubsection{Facebook Ads SDK CI/CD pipeline system}{Facebook}
\begin{itemize}
    \item Develop a CI/CD pipeline system to automatically generate official Facebook Ads SDK code, run regression tests, push code to GitHub and release in package management systems. Greatly expedite Facebook SDK release cycle, minimize manual work and improve develop, push and release process
\end{itemize}

\datedsubsection{Amazon Feed and Report Platform}{Amazon}
\begin{itemize}
    \item Build web application to manage Amazon merchant feed \& report platform which is used by ops team
    \item Design and implement RESTful API, build service backed by ElasticSearch and NoSQL/DynamoDB to support extremely high volume traffic in holiday season, deployed in AWS EC2
    \item Create front-end UI using AngularJS framework, refactor and migrate legacy code, introduce TypeScript support to existing codebase
\end{itemize}

\section{Open Source Community Project}
\datedsubsection{Facebook Ads API SDK}{}

\begin{itemize}
    \item Review and merge pull requests in Facebook Ads SDK Github Repo as repo member
    \item Support Facebook Platform developer's community, develop and maintain new features of Facebook Ads SDK, answer developers' questions
    \item Support SDK of five languages including Java, Python, Javascript, PHP and Ruby. Repository example: https://github.com/facebook/facebook-python-business-sdk
\end{itemize}

\section{Education}

\datedsubsection{M.S., Computer Science, Northeastern University}   {2015 -- 2017}
\datedsubsection{B.S., Applied Mathematics, Xiamen University}   {2011 -- 2015}

\end{document}


text:
\chapter{Generalised Linear Models}
\section{Examine distribution of G1, G2 and G3}
In this exercise we try to explain grades in mathematics of students by other predictive variables using linear models. First we have a look at the distribution of the dependent variables, here the first, second and third grade (G1, G2 and G3) during the year, to check whether a normal assumption is justified and we can use a standard linear model or whether we have to use a generalised linear model. Therefore we plot a histograms and QQ-Plots. Because the Poisson distribution seems suitable, too, for the data, we include a QQ-Plot for the normal distribution and the Poisson distribution (see Figure \ref{4gradedist}).
\begin{figure}[ptb]
\centering
\includegraphics[width=\textwidth, keepaspectratio]{ex7/gradedist.png}
\caption{Histogram (first row) and QQ-Plots using Normal (second row) and Poisson (third row) distribution for theoretical quantiles for G1, G2 and G3. Red line represents the density of a fitted normal distribution and blue points a Poisson distribution, each with parameters estimated from the sample.}
\label{4gradedist}
\end{figure}

Although the distributions look very similar, especially for G1 and G2, there are already some theoretical arguments that speak for the assumption of a Poisson distribution rather than a normal. First, the data is discrete, whereas the normal distribution has a density. Additionally the normal distribution allows negative numbers, too, whereas the Poisson distribution - although the values range trough $\mathbb{N}$ - only realises positive integer values. Still the data ranges only from 0 to 20, which is difficult to model reasonable with generalised linear models anyway. In the concrete data we see, that - especially for G3 - the Pisson distribution fits better to the data in the histogram. For G1 we see a rather good fit for both distributions. In the QQ-Plot we see that the sample distribution has shorter tails than the normal visible in the slightly S-curved shape of the plot, showing us that the sample quantiles at the border don't increase as fast as the theoretical at the right tail of the distribution an don't decrease that fast at the lower tail respectively. This pattern is less distinct for the Poisson distribution. Otherwise this would be a sign for underdispersion of the sample. The Fano factor $F$ is defined as the ratio of the variance over the mean of a distribution and equals 1 for a Poisson distribution. It is shown with other summary statistics in \ref{4tablegrades}.
\begin{table}[ht]
\centering
\begin{tabular}{lrrrrrrrrr}
  \hline
 timepoint & min & q25 & med & M & q75 & max & IQR & SD & F \\
  \hline
   G1 &   3 &   8 &  11 & 10.91 &  13 &  19 &   5 & 3.32 & 1.01 \\
   G2 &   0 &   9 &  11 & 10.71 &  13 &  19 &   4 & 3.76 & 1.32 \\
   G3 &   0 &   8 &  11 & 10.42 &  14 &  20 &   6 & 4.58 & 2.02 \\
   \hline
\end{tabular}
\caption{Summary statistics for the grade (G1, G2, G3) in mathematics of the data set. Here $F$ is the Fano factor.}
\label{4tablegrades}
\end{table}

In the table we see that the Fano factor is near to one for G1 indicating that is there is no underdispersion. For G2 and G3 there is the problem of the high amount of 0 in the data, visible in the histogram and in the QQ-Plots as the first quantiles are all at 0. For G2 this is not that bad and the assumption of a Poisson distribution seems still justified because the rest of the data suits quite well. But also the normal distribution seems not far from the data. In the QQ-Plot we see that the points form a steeper curve compared to the reference line. This may be caused by the many zeros that don't suit to any of the both distributions. This is even more drastically for the third time point. Because the pattern is so much distorted, I decided to include the same plots for G3 where I dropped the zeros (see Figure \ref{4gradedist2}). There we see a much better in the histogram as well as in the QQ-Plots. Now a similar pattern as for G1 is visible. An underdispersion is also visible in the QQ-Plot for the Poisson distribution. The Fano factor for the reduced sample is now 0.90 indicating a slight underdispersion compared to a Poisson distribution, too. Without dropping zeros the Fano factor was 2.02 indicating a high overdispersion, which is quite obvious from the visualisations. Also for G2 the overdispersion was confirmed by a smaller Fano factor of 1.32, which is still greater than the optimum at 1. Summing up I would conclude that a Poisson distribution is theoretical more suitable and that the data follow its shape well enough to use generalised linear models.
\begin{figure}[thb]
\centering
\includegraphics[width=\textwidth, keepaspectratio]{ex7/gradedist2.png}
\caption{Histogram and QQ-Plots for normal and Poisson distribution with sample parameters for G3 without zeros. The red line represents the fitted normal curve and blue points the Poisson distribution with sample mean.}
\label{4gradedist2}
\end{figure}

\section{Model fit for G1}
Now we try to fit a suitable model to predict he first grade G1 from other variables. Those include for example sex, age and education and job of father and mother. With the function \texttt{glm} and the argument \texttt{family='poisson'} we fit a generalised linear model with a Poisson distributed response. The design matrix is built with all available independent variables. The reduced (I dropped some not significant variable in the list) output of the \texttt{summary} for the resulting \texttt{glm} object looks as follows:
% \newpage
\begin{small}\begin{verbatim}
> summary(model1)

Call:
glm(formula = fmla, family = "poisson", data = dat)

Deviance Residuals:
     Min        1Q    Median        3Q       Max
-2.38057  -0.64611  -0.01502   0.50274   2.01602

Coefficients:
                  Estimate Std. Error z value Pr(>|z|)
(Intercept)       2.418107   0.331755   7.289 3.13e-13 ***
schoolMS          0.007157   0.058426   0.122  0.90250
sexM              0.078237   0.036434   2.147  0.03176 *
age              -0.006480   0.015983  -0.405  0.68515
addressU          0.012823   0.043630   0.294  0.76882
famsizeLE3        0.036639   0.035590   1.029  0.30325
PstatusT          0.016047   0.053050   0.302  0.76227
Medu              0.010664   0.023797   0.448  0.65405
Fedu              0.014886   0.020349   0.732  0.46446
Mjobhealth        0.078652   0.081444   0.966  0.33419
[...]
traveltime       -0.003407   0.025788  -0.132  0.89488
studytime         0.053887   0.020846   2.585  0.00974 **
failures         -0.147644   0.028151  -5.245 1.56e-07 ***
schoolsupyes     -0.211886   0.052610  -4.027 5.64e-05 ***
famsupyes        -0.093311   0.035213  -2.650  0.00805 **
paidyes          -0.008676   0.035007  -0.248  0.80426
[...]
freetime          0.023120   0.017435   1.326  0.18482
goout            -0.037487   0.016743  -2.239  0.02516 *
Dalc             -0.002047   0.025074  -0.082  0.93494
Walc             -0.004639   0.018663  -0.249  0.80371
health           -0.015492   0.011868  -1.305  0.19178
absences          0.001520   0.002185   0.696  0.48662
---
Signif. codes:  0 `***` 0.001 `**` 0.01 `*` 0.05 `.` 0.1 ` ` 1

(Dispersion parameter for poisson family taken to be 1)

    Null deviance: 402.47  on 394  degrees of freedom
Residual deviance: 263.08  on 355  degrees of freedom
AIC: 2000.2

Number of Fisher Scoring iterations: 4
\end{verbatim}\end{small}

There we see first some distributional measures for the deviance residuals. Let's have look at the coefficients. We see for each independent variable the estimate, standard error and z-value. In the last column there is the $p$ value. This indicated whether we consider the predictive value of a variable as significant or not. R indicates the usual threshold with the significance codes. Using this suggestion we see that most of the variables don't provide much predictive information about the grade. Just sex (\texttt{sexM}), weekly study time (\texttt{studytime}), number of past class failures (\texttt{failures}), extra educational support in school (\texttt{schoolsupyes}) and in the family (\texttt{famsupyes}) as well as the time a student goes out with friends (\texttt{goout}) are significant. Here a negative estimate indicates a negative influence for higher values or the level of the factor respectively. Male students (\texttt{sexM}) for example get higher grades (estimate 0.08) than female. Beneath the table for the coefficients we see the deviances. Testing the full model against the null model is quite needless here, since the full model will have a better fit to the data. Although we can check this very fast using the \texttt{anova} function in R after fitting the null model. The difference of deviances is 139.39 and thus significant ($p<.01$). A more interesting comparison to a nested model will be discussed in the next section.

\begin{figure}[!h]
\centering
\includegraphics[width=\textwidth, keepaspectratio]{ex7/residuals.png}
\caption{Scatter plot for fitted values against residuals, QQ-Plot and histogram with fitted normal curve in red for Pearson residuals (first row) and Anscombe residuals (second row).}
\label{4resid}
\end{figure}

To examine the adequacy of the model we also have to look at the distribution of the residuals. There are many different approaches. The Pearson and Anscombe residuals are shown in Figure \ref{4resid}. An appropriate model will show normally distributed residuals. The Pearson residuals have to be taken with care, since for non-normal responses they are skewed. Therefore Anscombe resdiuals use a normalising transformation. Although both residual distribution look a little bit skewed in the histogram they show no obvious deviations in the QQ-Plot. The scatter plot on the left shows no systematic dependence from the height of the fitted values. All in all we may expect our model is a good choice for the data.

\section{Reducing the model for G1}
We saw in the last section that most of our variables were not significant for the prediction in our full model. Therefore we fitted a reduced model containing the variables that were significant in the first model. Additionally we included the factor \texttt{Fedu} encoding the educational level of the father. The summary looks like follows:
\begin{small}\begin{verbatim}
> summary(model2)

Call:
glm(formula = G1 ~ sex + Fedu + studytime + failures + schoolsup +
    famsup + goout, family = "poisson", data = dat)

Deviance Residuals:
     Min        1Q    Median        3Q       Max
-2.70146  -0.70149  -0.02238   0.58681   2.55092

Coefficients:
             Estimate Std. Error z value Pr(>|z|)
(Intercept)   2.34585    0.07578  30.955  < 2e-16 ***
sexM          0.06585    0.03237   2.034  0.04193 *
Fedu          0.04281    0.01482   2.888  0.00388 **
studytime     0.05828    0.01906   3.057  0.00223 **
failures     -0.13876    0.02495  -5.561 2.69e-08 ***
schoolsupyes -0.19834    0.04978  -3.984 6.78e-05 ***
famsupyes    -0.07330    0.03240  -2.263  0.02365 *
goout        -0.03525    0.01406  -2.506  0.01220 *
---
Signif. codes:  0 `***` 0.001 `**` 0.01 `*` 0.05 `.` 0.1 ` ` 1

(Dispersion parameter for poisson family taken to be 1)

    Null deviance: 402.47  on 394  degrees of freedom
Residual deviance: 302.02  on 387  degrees of freedom
AIC: 1975.1

Number of Fisher Scoring iterations: 4
\end{verbatim}\end{small}

At first glance it may seem surprising that the variable \texttt{Fedu} is now significant. But since the whole model changes the estimates and standard errors for specific covariates change, too. Now we have a highly reduced model with only significant explaining variables. Compared to \texttt{model1} the residual deviance is of course higher. But the AIC, which is a criterion for the goodness-of-fit, which accounts for the size of the residuals as well as the number of coefficients to estimate in a model, decreased, indicating a better fit for \texttt{model2}. The residuals for \texttt{model2} follow a normal distribution, too. I omit the visualisation here since it is quite similar to the one in the last section, but it can be found in the supplementary code. Since the second model is nested in the full model we can compare them with an analysis of deviance. Like mentioned above this is easily done with the function \texttt{anova} and the argument \texttt{test='Chisq'}. With 32 degrees of freedom and a difference of 38.94 in the sum of residual deviances we get $p=.19$ indicating that the additional explaining value of the full model is not significant. Thus we can stick to the reduced model.

A third model was fitted by dropping the variable \texttt{goout} and adding the variable \texttt{Walc} again:
\begin{small}\begin{verbatim}
> summary(model3)

Call:
glm(formula = G1 ~ sex + Fedu + studytime + failures + schoolsup +
    famsup + Walc, family = "poisson", data = dat)

Deviance Residuals:
     Min        1Q    Median        3Q       Max
-2.64853  -0.69869  -0.02535   0.61090   2.51693

Coefficients:
             Estimate Std. Error z value Pr(>|z|)
(Intercept)   2.31120    0.07204  32.083  < 2e-16 ***
sexM          0.07558    0.03296   2.293  0.02183 *
Fedu          0.04067    0.01477   2.753  0.00591 **
studytime     0.05231    0.01935   2.704  0.00685 **
failures     -0.14110    0.02488  -5.671 1.42e-08 ***
schoolsupyes -0.20115    0.04985  -4.035 5.46e-05 ***
famsupyes    -0.07447    0.03239  -2.299  0.02148 *
Walc         -0.02614    0.01274  -2.052  0.04016 *
---
Signif. codes:  0 `***` 0.001 `**` 0.01 `*` 0.05 `.` 0.1 ` ` 1

(Dispersion parameter for poisson family taken to be 1)

    Null deviance: 402.47  on 394  degrees of freedom
Residual deviance: 304.07  on 387  degrees of freedom
AIC: 1977.2

Number of Fisher Scoring iterations: 4
\end{verbatim}\end{small}

There we see again that all covariates are significant and the residuals don't show serious deviations from the normal distribution (see code). Now, how can we tell, whether \texttt{model2} or \texttt{model3} is better? We can't use analysis of deviances here, since the two models are not nested. Therefore we have to keep at other measures, like penalised goodness-of-fit criteria (e.g. the AIC and BIC). Like mentioned above, a smaller AIC indicates a better fit. Since the two models estimated the same amount of coefficients, we don't need to use those but can directly look at the residual deviance or the likelihood. With a sum of 302.02 the second model is a bit better than the third one with 304.07. This is also visible in the difference of the log-likelihood. It is -979.57 for the second and -980.60 for the third model respectively. So \texttt{model2} has the higher likelihood and should hence be our choice. Still we have to keep in mind that this comparison is not inferential but descriptive.


text:
\section{Evaluation and Summary}
\label{sec:evaluation}

% This gives an evaluation of the project, including

% A description of how the project is evaluated, including
    % What criteria are used to evaluate whether the system is suceesful?
    % How these criteria are assessed?
    % Who is involved in the evaluation?
% Your critical evaluation of your project results/outcomes.
% Your critical evaluation of the strengths and weaknesses of your project as carried out.
% Where appropriate, 3rd party evaluation of the software/computer system/application developed on the project, and/or customer feedback, be obtained in strict accordance with
    % ethical use of the project 3rd party evaluation human participants
        % explicitly state if human participants were involved for the project 3rd party evaluation;
        % if human participants were involved for the project 3rd party evaluation,
            % explicitly confirm that the CS Department ethical procedure for Comp39x projects 3rd party evaluation has been followed.
            % include into appendix the 3rd party evaluator information sheet and consent forms completed and signed by the 3rd party evaluators on your project.

From the engineering aspect, the project is generally good and gives two command line application as research tools.
One can generate same scale graphs pairs with the bisimulation flag that ready to be used as data set for machine learning.
And the scale of the graph, number of pair, the rate of positive and negative, graph density can be customised.
Other can use the data generated to training a preset neural network.
In this tool, the number of training epoch, learning rate, batch size, the rate of test set and training set division can be customised.
And the training can be continued after the program ends.
The whole project was pushed as expected.
All components were tested and work well.
Nevertheless, the process of the project still needs improvement.
The most important is the test of components.
It was done by hand, which not reliable and inefficient.
Most test data from the textbook is reliable but not enough in quantity.

On the other hand, form aspect of research, the goal is generally achieved.
Whereas, it opens the next stage of research.
There are two experiments done in this project.
First is the wide experiment.
It tests the performance of the learning algorithm when feeding the data (mainly) from different parts of space (i.e. all possible same scale graphs).
The experiment shows that in most situation the performance of the algorithm is similar.
Base on it, one can say that except the extreme situation (i.e. graph density equals 0.9) the performance of the algorithm when feeds a non-extreme value, is representative respect to the graphs pair with the same scale.
Second is the deep experiment.
It is aimed at testing the capability of the preset neural network.
It will test the performance of the learning algorithm when feeding the data with different scale (i.e. node number)
Base on the conclusion of the wide experiment, only the dataset generated with one density will be used to represent the result of the whole space in this very scale.
And the result shows that when the graphs become bigger, the performance did become worse,
which indicate the limitation of the neural network.
However, when the scale keeps expanding to a certain level, the performance unexpectedly become better.
It may be because of the insufficient quantity, but there still needs more experience.

Still, there are many things need to be improved as a research project.
Firstly, the literature review needs to be more at the begin of the project.
At the start of the project, most literature reviewed is about bisimulation.
The main aim was overlooked during the development of the first part.
It caused problems when the project stepped into the second part.
Some components need to be rewritten in order to serve the second part.
Second, the experiment design should be carefully considered.
For the wide experiment, the dataset used can be better by mixing all graphs pairs generated on different density then sampling from the pool.
For the deep experiment, the criteria of the deep experiment is quite blurred.
And the result indicates that more experiments are needed.

Moreover, for further experiments a better test cases generator may need to be designed.
The generator designed and implemented in the project aimed at ``random".
In other words, the generator was designed to be as random as possible.
However, in fact, true random generated graphs are mostly like the graphs shown in Figure \ref{fig:outputg3} and Figure \ref{fig:outputg4}.
They are either very easy to be denied or very simple to be recognised (see Section \ref{sec:results}).
Concretely, it is possible that 80\% of graphs pairs belongs to the above two types.
In that situation, the network will only need to learn to distinguish these two types of graphs, the performance can reach over 80\% accuracy while lacking generalisation ability.
Thu, the better idea may be a generator that can generate all kinds of pair while decreasing the incidence of these two types.
And generative adversarial network (GAN) can be a good choice.


text:
\documentclass[bigger]{beamer}

\input{header-beam} % change to header-handout for handouts

% ====================
\title[Lecture 21]{Logic I F13 Lecture 21}
\date{November 28, 2013}
% ====================

\include{header}

\setlength{\fitchprfwidth}{14em}

\section{What is Logical Metatheory?}

\subsec{What is Logical Metatheory?}{

\bit
\item Most of Logic I is logical \emph{theory}: working \emph{in} a logical language, \emph{in} a logical proof system (Fitch), \emph{using} logical concepts like ``tautology'' and ``FO interpretation''
\item Logical \emph{meta}theory investigates language, proof system, logical concepts, and proves theorems about them
\eit

}

\subsec{Provability and Consequence}{

\bit
\item We write
\bit
\item $A_1$, \dots, $A_n \models B$ if $B$ is a conseqence of $A_1$, \dots, $A_n$ and
\item $A_1$, \dots, $A_n \vdash B$ if $B$ has a formal proof from premises $A_1$, \dots, $A_n$.
\eit
\item What is the relation between $\models$ and $\vdash$?
\eit

}

\subsec{Soundness}{

\bit
\item A proof system is \emph{sound} relative to a semantics if
\[
A_1, \dots, A_n \vdash B \Rightarrow A_1, \dots, A_n \models B
\]
\item This guarantees the proof system is \emph{safe}: you \emph{can't} prove anything that doesn't follow from the premises
\item In particular you can't prove anything that's not a tautology/FO validity from no premises
\eit

\textbf{Soundness Theorem.} Fitch is a sound proof system

}

\subsec{Completeness}{

\bit
\item A proof system is \emph{complete} relative to a semantics if
\[
A_1, \dots, A_n \models B \Rightarrow A_1, \dots, A_n \vdash B
\]
\item This guarantees the proof system is \emph{as powerful as possible}: you \emph{can} prove anything that follows from the premises
\item In particular, you can prove all tautologies/FO validities from no premises
\eit

\textbf{Completeness Theorem (G\"odel 1930).}\\ Fitch is a complete proof system

}

\subsec{Satisfiability}{

\bit
\item A set of sentences $A_1$, \dots, $A_n$ is \emph{satisfiable} if there is a FO structure that makes all of the sentences true. (Cf. TT-possible)
\item A FO structue that makes a set of sentences true is called a \emph{model} of it
\item If a set is satisfiable, what kinds of models does it have?
\bit
\item Does it have (only) finite models?
\item Does it have (only) infinite models?
\item Does it have models with a specific domain (e.g., the natural numbers)?
\eit
\eit

\textbf{L\"owenheim-Skolem Theorem.} If a set has an infinite model, it has a model with domain the natural numbers.

}

\subsec{Decidability and Complexity}{

\bit
\item A \emph{decision problem} is a yes/no question, asked about a specific (syntactic) object, e.g.,
\bit
\item Given a sequence of symbols:\\
Is it awell-formed formula?
\item Given a sentence containing only $\land$, $\lor$, $\lnot$:\\
Is it TT-possible?
\item Given a sentence of the blocks language:\\
Is it a FO validity?
\item Given a sentence of an arbitrary FO language:\\
 Does it only have infinite models?
\eit
\item A problem is \emph{decidable} if there is a computer program that will always find the correct answer to it, \emph{undecidable} otherwise.
\item Complexity of a problem: \emph{how fast} can a computer find the answer?
\eit

}

\section{Soundness}

\subsec{Soundness}{

\bit
\item Remember: Fitch is \emph{sound} if whenever there's a proof of $B$ from premises $A_1$, \dots, $A_n$, then it's guaranteed that $B$ is a conseqence of $A_1$, \dots, $A_n$
\item Fitch is, in fact, sound
\item How do you prove it?
\bit
\item We have to show this for all infinitely many possible proofs!
\item But: each proof uses only finitely many rules
\item Idea: use \emph{induction} on the number of rules used, i.e.,
\item Show that any proof that uses no rules at all is correct, and
\item Show that any proof correct to line $n$ is also correct to line $n+1$
\eit
\eit

}

\subsec{Correct Proof}{

\bit
\item A proof is \emph{correct down to line $n$} if every line which isn't a premise or an assumption of a subproof down to and including $n$ is a consequence of
\ben
\item the premises of the proof
\item all assumptions which are open at line~$n$, i.e., all assumptions of subproofs that line~$n$ is contained in
\een
\item E.g., the proof \qquad
\fitchprf{\pline[1.]{A}\\ \pline[2.]{B}}{
\pline[3.]{C}\\
\subproof{\pline[4.]{D}}{\pline[5.]{E}}}\\
is correct to line 5 if $\sf A, B \models C$ and $\sf A, B, D \models E$.
\eit

}

\subsec{Induction on Numbers of Steps in Proofs}{

\bit
\item The \emph{induction basis} is: any proof correct down to line~1\\
(trivially true, since line1 is a premise!)
\item The \emph{induction step} is:\\
If every proof is correct down to line $n$, then every proof is correct down to line $n+1$
\item In other words, if proofs are correct down to line $n$, the next step, if it is a correct application of a rule, does not break things
\eit
}

\subsec{One More Line: Reit}{

\begin{columns}
\begin{column}{3.5cm}
\hskip-2em\setlength{\fitchprfwidth}{8em}
\fitchprf{\pline[1.]{P}\\ \pline[2.]{Q}}{
\subproof{\pline[3.]{R}}{
\ellipsesline\\
\pline[$k$.]{A}\\
\ellipsesline\\
\subproof{\pline[$l$.]{S}}{
\ellipsesline\\
\pline[$(n+1)$.]{A}[\reit{$k$}]}}}
\end{column}
\begin{column}{7cm}
\vskip-2cm
\bits
\item Can only click on line $k$ if the innermost subproof that line $k$ is in has not ended before line $n+1$!
\item So: all assumptions open at line $k$ still open at line $n+1$
\item All proofs correct down to line $n$, so:
\bit
\item $\sf P, Q, R \models A$
\eit
\item But then also:
\bit
\item $\sf P, Q, R, S \models A$
\eit
\eit
\end{column}\end{columns}

}

\subsec{One More Line: $\land$Intro}{

\bit
\item Suppose we have a proof correct down to line $n$, and line $n+1$ is justified by $\land$Intro
\item If that step checks out, we know:
\bit
\item Line $n+1$ contains a conjunction, $A \land B$
\item There are exactly two support steps cited, $k$ and $l$
\item Line $k$ contains A, line $l$ contains B (or vice versa)
\item All assumptions open at line $k$ and $l$ are still open at line $n+1$ (there may be more)
\eit
\item Since the proof is correct down to line $n$, in particular
\bit
\item A is a consequence of the premises and assumptions open at line $k$
\item B is a consequence of the premises and assumptions open at line $l$
\eit
\eit

}

\subsec{One More Line: $\land$Intro}{

\begin{columns}
\begin{column}{3.5cm}
\hskip-2em\setlength{\fitchprfwidth}{8em}
\fitchprf{\pline[1.]{P}\\ \pline[2.]{Q}}{
\subproof{\pline[3.]{R}}{
\ellipsesline\\[-.5ex]
\pline[$k$.]{A}\\
\subproof{\pline[$k+1$.]{S}}{
\ellipsesline\\[-.5ex]
\pline[$l$.]{B}\\
\subproof{\pline[$l+1$.]{T}}{
\ellipsesline\\[-.5ex]
\pline[$(n+1)$.]{}\\
\pline[\quad]{A\land B}[\landi{$k, l$}]}}}}
\end{column}
\begin{column}{7cm}
\vskip-2cm
\bits
\item Correct to line $k$ and line $l$:
\bit
\item $\sf P, Q, R \models A$
\item $\sf P, Q, R, S \models B$
\eit
\item Then also:
\bit
\item $\sf P, Q, R, S, T \models A$
\item $\sf P, Q, R, S, T \models B$
\eit
\item Show: $\sf P, Q, R, S, T \models A \land B$
\item Suppose not: then there is an interpretation that makes
\bit
\item $\sf P, Q, R, S, T$ true and
\item $A \land B$ false
\eit
\item This would make either
\bit
\item $\sf P, Q, R, S, T$ true, A false, or
\item $\sf P, Q, R, S, T$ true, B false!
\eit
\eit
\end{column}\end{columns}

}

\subsec{One More Line: $\lnot$Intro}{

\begin{columns}
\begin{column}{3.5cm}
\hskip-2em\setlength{\fitchprfwidth}{8em}
\fitchprf{\pline[1.]{P}\\ \pline[2.]{Q}}{
\subproof{\pline[3.]{R}}{
\ellipsesline\\
\subproof{\pline[$k$.]{A}}{
\ellipsesline\\
\pline[$k'$.]{\bot}}
\ellipsesline\\
\pline[$(n+1).$]{\lnot A}[\lnoti{$k$--$k'$}]}}
\end{column}
\begin{column}{7cm}
\vskip-2cm
\bits
\item Correct to line $k'$:
\bit
\item $\sf P, Q, R, A \models \bot$
\eit
\item Show: $\sf P, Q, R \models \lnot A$
\item Suppose not: then there is an interpretation that makes
\bit
\item $\sf P, Q, R$ true and
\item $\sf\lnot A$ false
\eit
\item This would make
\bit
\item $\sf P, Q, R, A$ true, $\bot$ false
\eit
\eit
\end{column}\end{columns}

}

\subsec{One More Line: $\exists$Elim}{

\begin{columns}
\begin{column}{3.5cm}
\hskip-2em\setlength{\fitchprfwidth}{8em}
\fitchprf{\pline[1.]{P}\\ \pline[2.]{Q}}{
\subproof{\pline[3.]{R}}{
\ellipsesline\\
\pline[$m$.]{\exists x\, A(x)}\\
\ellipsesline\\
\boxedsubproof[$k$.]{c}{A(c)}{
\ellipsesline\\
\pline[$k'$.]{B}}
\ellipsesline\\
\pline[$(n+1).$]{B}[\lexie{$m$}{$k$--$k'$}]}}
\end{column}
\begin{column}{7cm}
\vskip-1.5cm

\bits
\item Correct to $m$: $\sf P, Q, R \models \exists x\, A(x)$
\item<.-> Correct to $k'$: $\sf P, Q, R, A(c) \models B$
\item Suppose not $\sf P, Q, R \models B$:
then there is a FO interpretation $I$ that makes
$\sf P, Q, R$ true and $B$ false
\item $\sf P, Q, R \models \exists x\,A(x)$, so at least one object $\alpha$
satisfies A(x)
\item $I^*$: just like $I$, except $c : \alpha$
\bit
\item makes A(c) true
\item makes P, Q, R true, \emph{B false} (don't contain c!)
\eit
\item Since $\sf P, Q, R, A(c) \models B$, $I^*$ also makes \emph{B true}: contradiction.
\eit
\end{column}\end{columns}

}

\section{Completeness}

\subsec{Completeness}{

\bit
\item Remember: (Completeness 1)\\
Fitch is \emph{complete} if:

\medskip
 whenever $B$ is a consequence of $A_1$, \dots, $A_n$, there's guaranteed to be a proof of $B$ from premises $A_1$, \dots, $A_n$
\medskip

\item Much harder to prove than soundness
\item Equivalent to: (Completeness 2)

\medskip
If a set of sentences is consistent, it is satisfiable

\medskip
(\emph{Consistent} means: there is no proof of $\bot$ from those sentences as premises)
\eit

}

\subsec{Completeness 2 Implies Completeness 1}{

\bit
\item Suppose any consistent set of sentences is satisfiable (Completeness 2)
\item Show: if $\sf A_1, \dots, A_n \models B$ then $\sf A_1, \dots, A_n \vdash B$ (Completeness 1)
\item Or show contrapositive:\\
if \emph{not} $\sf A_1, \dots, A_n \vdash B$ then \emph{not} $\sf A_1, \dots, A_n \models B$
\item Observe:
\bens
\item $\sf \sf A_1, \dots, A_n, \lnot B$ is satisfiable $\Rightarrow$ not: $\sf \sf A_1, \dots, A_n \models B$
\item $\sf A_1, \dots, A_n, \lnot B \vdash \bot$ $\Rightarrow$ $\sf A_1, \dots, A_n \vdash B$, so
\item not $\sf A_1, \dots, A_n \vdash B$ $\Rightarrow$ not $\sf A_1, \dots, A_n, \lnot B \vdash \bot$
\een
\eit

}

\subsec{Proof of (2)}{

\begin{columns}[t]
\begin{column}{2.5cm}
\fitchprf{\pline[1.]{A_1}\\
\ellipsesline\\
\pline[$n$.]{A_n}\\
\pline[$(n+1)$.]{\lnot B}}{
\ellipsesline\\
\pline[$m$.]{\bot}}
\end{column}
\begin{column}{7cm}\setlength{\fitchprfwidth}{8em}
$\Rightarrow$\fitchprf{\pline[1.]{A_1}\\
\ellipsesline\\
\pline[$n$.]{A_n}}{
\subproof{\pline[$(n+1)$.]{\lnot B}}{
\ellipsesline\\
\pline[$m$.]{\bot}}
\pline[$m+1$.]{\lnot\lnot B}[\lnoti{$(n+1)$--$m$}]\\
\pline[$m+2$.]{B}[\lnote{$(m+1)$}]}
\end{column}\end{columns}
}

\subsec{Completing the Proof}{

\bit
\item We're proving:\\
not $\sf A_1, \dots, A_n \vdash B$ $\Rightarrow$ not $\sf A_1, \dots, A_n \models B$
\item Assume: not $\sf A_1, \dots, A_n \vdash B$
\item We had (3), contrapositive of (2):\\
 not $\sf A_1, \dots, A_n \vdash B$ $\Rightarrow$ not $\sf A_1, \dots, A_n, \lnot B \vdash \bot$
\item So:  not $\sf A_1, \dots, A_n, \lnot B \vdash \bot$ (by MP), i.e.,\\
 $\sf A_1, \dots, A_n, \lnot B$ is consistent
\item So: $\sf A_1, \dots, A_n, \lnot B$ is satisfiable (Completeness 2)
\item We also had (1):\\
$\sf \sf A_1, \dots, A_n, \lnot B$ is satisfiable $\Rightarrow$ not $\sf \sf A_1, \dots, A_n \models B$
\item So not $\sf \sf A_1, \dots, A_n \models B$ (by MP). QED
\eit

}

\section{Decision Problems}

\subsec{Decision Problems}{

\bit
\item Given a sentence containing only $\land$, $\lor$, $\lnot$:\\
Is it true in the first line of its truth table?
\item Given a sentence containing only $\land$, $\lor$, $\lnot$:\\
Is it TT-possible?
\item Given a sentence of the blocks language:\\
Is it a FO validity?
\item Given a sentence of an arbitrary FO language:\\
 Does it only have infinite models?
\eit
}

\subsec{An Easy Decision Problem}{

\begin{block}{Instance: Sentence A containing only $\land$, $\lor$, $\lnot$\\
Problem: Is A true when all atomic sentences are true?}

\bit
\item Decidable
\item Complexity is \emph{linear}, i.e.,
\item There are programs that compute the answer after $c\cdot n$
steps, where
\bit
\item $n$ is the number of symbols in A
\item $c$ is a constant number
\eit
\eit
\end{block}

}

\subsec{SAT: An Hard Decision Problem}{

\begin{block}{Instance: Sentence A containing only $\land$, $\lor$, $\lnot$\\
Problem: Is A TT-possible?}

\bit
\item Decidable
\item Complexity is \emph{unknown}
\item There are programs that compute the answer after $c\cdot 2^n$
steps (SAT is in EXPTIME)
\item For instance: search through all lines of truth table
\item Noone has proved yet that there aren't faster programs
\item SAT is \emph{NP-complete}
\item Finding complexity of SAT would settle \emph{P vs NP} problem
\eit
\end{block}

}

\subsec{2SAT: Another Easy Decision Problem}{

\begin{block}{Instance: Sentence A: conjunction of disjunctions of at most 2 atmic or negated atomic sentences\\
Problem: Is A TT-possible?}

\bit
\item Decidable
\item Complexity is \emph{linear}
\item Non-trivial algorithm!
\item Applications in VLSI circuit design, graph theory, tomography, planning turnaments (optimal home/away games)
\eit
\end{block}

}

\subsec{Church-Turing Theorem}{

\begin{block}{Instance: Sentence A of any FO language\\
Problem: Is A a FO validity?}

\bit
\item Undecidable
\item Proved independently by Alonzo Church and Alan Turing in 1935
\item Reason we have Turing machines
\eit
\end{block}
}

\end{document}


text:
    \foldertitle{logdist}{Probability Distribution Package}{logdist/Contents}

	This package gives quick access to basic univariate distributions. Its
primary use is setting up priors in the
\href{model/estimate}{\texttt{model/estimate}} and
\href{poster/arwm}{\texttt{poster/arwm}} functions.

The logdist package is called to create function handles that have
several different modes of use. The primary use is to compute values
that are proportional to the log of the respective density. In addition,
the function handles also give you access to extra information (such as
the the proper p.d.f., the name, mean, std dev, mode, and stuctural
parameters of the distribution), and to a random number generator from
the respective distribution.

Logdist methods:

\paragraph{Getting function handles for univariate
distributions}\label{getting-function-handles-for-univariate-distributions}

\begin{itemize}
\itemsep1pt\parskip0pt\parsep0pt
\item
  \href{logdist/chisquare}{\texttt{chisquare}} - Create function
  proportional to log of Chi-Squared distribution.
\item
  \href{logdist/normal}{\texttt{normal}} - Create function proportional
  to log of Normal or Student distribution.
\item
  \href{logdist/lognormal}{\texttt{lognormal}} - Create function
  proportional to log of log-normal distribution.
\item
  \href{logdist/beta}{\texttt{beta}} - Create function proportional to
  log of beta distribution.
\item
  \href{logdist/gamma}{\texttt{gamma}} - Create function proportional to
  log of gamma distribution.
\item
  \href{logdist/invgamma}{\texttt{invgamma}} - Create function
  proportional to log of inv-gamma distribution.
\item
  {[}\texttt{t}{]} (logdist/t) - Create function proportional to log of
  Student T distribution.
\item
  \href{logdist/uniform}{\texttt{uniform}} - Create function
  proportional to log of uniform distribution.
\end{itemize}

\paragraph{Calling the logdist function
handles}\label{calling-the-logdist-function-handles}

The function handles \texttt{F} created by the logdist package functions
can be called the following ways:

\begin{itemize}
\item
  Get a value proportional to the log-density of the respective
  distribution at a particular point; this call is used within the
  \href{poster/Contents}{posterior simulator}:

  y = F(x)
\item
  Get the density of the respective distribution at a particular point:

  y = F(x,`pdf')
\item
  Get the characteristics of the distribution -- mean, std deviation,
  mode, and information (the inverse of the second derivative of the log
  density):

  m = F({[}{]},`mean') s = F({[}{]},`std') o = F({[}{]},`mode') i =
  F({[}{]},`info')
\item
  Get the underlying ``structural'' parameters of the respective
  distribution:

  a = F({[}{]},`a') b = F({[}{]},`b')
\item
  Get the name of the distribution (the names correspond to the function
  names, i.e.~can be either of \texttt{'normal'}, \texttt{'lognormal'},
  \texttt{'beta'}, \texttt{'gamma'}, \texttt{'invgamma'},
  \texttt{'uniform'}):

  name = F({[}{]},`name')
\item
  Draw a vector or matrix of random numbers from the distribution;
  drawing from beta, gamma, and inverse gamma requires the Statistics
  Toolbox:

  a = F({[}{]},`draw',1,1000);

  size(a) ans = 1 10000
\end{itemize}

\paragraph{Getting on-line help on logdist
functions}\label{getting-on-line-help-on-logdist-functions}

\begin{verbatim}
help logdist
help logdist/function_name
\end{verbatim}

max_stars_repo_name: OGResearch/IRIS-Toolbox-For-Octave

max_issues_repo_name: OGResearch/IRIS-Toolbox-For-Octave

max_forks_repo_name: OGResearch/IRIS-Toolbox-For-Octave


text:
% This is a model template for the solutions in computational science. You can find a very useful documentation for LaTeX in Finnish at ftp://ftp.funet.fi/pub/TeX/CTAN/info/lshort/finnish/ or in English at ftp://ftp.funet.fi/pub/TeX/CTAN/info/lshort/english/. The section List of mathematical symbols in Chapter 3 is especially useful for the typesetting of mathematical formulas.

% Compile the document to PDF by command 'pdflatex model.tex' in the terminal. The command must be run twice for the references in the text to be correct.

\documentclass[a4paper,11pt]{article}
\usepackage[utf8]{inputenc}
% This includes letters such as � and �
\usepackage[T1]{fontenc}
% Use here 'Finnish' for Finnish hyphenation. You may have to compile the code twice after the change.
\usepackage[english]{babel}
\usepackage{graphicx}
% Some math stuff
\usepackage{amsmath,amsfonts,amssymb,amsbsy,commath,booktabs,hyperref}
% This is just to include the urls
\usepackage{hyperref}
\usepackage[margin=2cm]{geometry}

\setlength{\parindent}{0mm}
\setlength{\parskip}{1.0\baselineskip}

\usepackage{listings}
\usepackage{color}
\usepackage{pdfpages}

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}

\lstset{frame=tb,
	language=Python,
	aboveskip=3mm,
	belowskip=3mm,
	showstringspaces=false,
	columns=flexible,
	basicstyle={\tiny\ttfamily},
	numbers=none,
	numberstyle=\tiny\color{gray},
	keywordstyle=\color{blue},
	commentstyle=\color{dkgreen},
	stringstyle=\color{mauve},
	breaklines=true,
	breakatwhitespace=true,
	tabsize=4
}

\begin{document}

\title{Becs-114.1100 Computational Science -- exercise round 5} % Replace the exercise round number
\author{Kunal Ghosh, 546247} % Replace with your name and student number
\maketitle
\section{Solution to Question 2}
\subsection{Solving linear equations using Scaled Pivoting. Weights from corresponding hilbert matrices}\label{prob2a}
\begin{figure}[ht]
	\center
	\includegraphics[scale=0.75]{figure_1.png}
    \caption{Plot showing that as n increases the RMS error of the solution of a system of linear equations, with the hilbert matrix values as its coefficients, increases.The red dots show the actual error values}
	\label{fig:err1}
\end{figure}

\begin{table}[ht]
\centering
\label{my-label}
\begin{tabular}{|c|c|c|}
\hline
 \textbf{n}&\textbf{RMS Error}&\textbf{Condition Number}  \\ \hline
 2&0.73833521&15.0167409881  \\ \hline
 5&1.02602254&282901.77002 \\ \hline
 8&1.09505307&7657562245.89 \\ \hline
 12&1.16783884&5.89342127254e+15 \\ \hline
 15&2.11656192&1.74359790918e+17 \\ \hline
\end{tabular}
\caption{Table showing the values of n and the RMS error after solving the system of linear equations with \textbf{hilbert(n)} as the coefficients.}
\end{table}
The table of n and errors appears on page 4.
The corresponding python code can be found at \ref{code:problem2a}

\subsection{Solving system of linear equations with coefficients as hilbert(n) for n=3}
\includepdf[pages=-]{NewDoc1.pdf}
\clearpage
\section{Appendix A}\label{code:problem2a}
Python source code for \ref{prob2a}.
{\footnotesize
\begin{lstlisting}

from __future__ import division
from scipy.linalg import hilbert
import numpy as np
from pprint import pprint
import pylab as pl

def new_solve(A,b):
    A = np.asarray(A, np.float)
    b = np.asarray(b, np.float)
    # Create the scale vector max(abs(ri)) of each row ri in A
    S = np.zeros(A.shape[0], np.float)
    S = np.max(np.abs(A), axis=1)
    # Create the Index vector
    I = np.asarray(range(np.max(S.shape)))
    # iterate over as many times as there are rows (r = 0 to rmax)
    for idx in range(len(I)):
        r = I[idx]
        # get the values from the idx(th) column
        rows_we_want = I[idx:]
        corresponding_column_values = A[rows_we_want, idx]
        # divide the column values by their corresponding scale and get the index of the row with max value
        div_val = np.true_divide(np.abs(corresponding_column_values),S[rows_we_want])
        I_idx = np.argmax(div_val)
        # because the above index is in I, the actual row is
        act_idx = I[idx:][I_idx]
        max_row = A[act_idx,:]
        # swap current Idx with max_row's idx
        # swap the 0th idx and the new max in the sub array of I
        I[idx:][0], I[idx:][I_idx] = I[idx:][I_idx], I[idx:][0]
        # iterate over remaining rows and update them
        for rem_rows in I[idx+1:]:
            # Get the appropriate multiple of the pivot row. to make the remaining row's idx column a zero
            multiplier = np.true_divide(A[rem_rows][idx],max_row[idx])
            A[rem_rows,idx:] -= max_row[idx:] * multiplier
            b[rem_rows] -= b[act_idx] * multiplier
    return I, A, b

def gauss(I, A, b):
    # returns the solutions to x
    x = np.zeros(I.shape)
    # because this is directly used in indexing and
    # max index of x would be len(x) -1
    len_x = len(x)-1
    # reverse I because we go in reverse I order.
    I = I[::-1]
    for count,row in enumerate(I):
        # get the row which we need to evaluate.
        weighted_sum_of_already_computed_x = 0
        for i in range(count):
            # if its the first value, we need to evaluate once.
            # for the second value, we need to evaluate twice and so on.
            col = len_x-i
            weighted_sum_of_already_computed_x += A[row, col] * x[col]
        # len(x)-count-1 because indices from 3 to 0 when len(x) = 4
        x[len_x-count] = (b[row] - weighted_sum_of_already_computed_x) / A[row,len_x-count]
    return x

def error(x,x_actual):
    diff = np.abs(x-x_actual)
    return np.sqrt(np.divide(np.sum(diff ** 2),x.shape))

if __name__ == '__main__':
    errs = []
    errors = []
    n_vals = [2,5,8,12,15]
    for n in n_vals:
        A = hilbert(n)
        b = np.sum(A,axis=1)
        I,A,b = new_solve(A,b)
        x = gauss(I,A,b)
        errors.append(error(x,b))
        print n,errors[-1]
    pl.plot(n_vals, errors,c='b')
    pl.grid()
    pl.scatter(n_vals, errors,c='r',marker="o")
    pl.xlabel("values of n")
    pl.ylabel("RMS error of partial pivot and actual solution of hilbert(n)")
    pl.show()

\end{lstlisting}
}
\end{document}


text:
\documentclass{article}[18pt]
\input{../format}
\lhead{AZ900}

\begin{document}
\begin{center}
\underline{\huge Creating an Azure Account}
\end{center}
\section{Purchasing Options}
\begin{itemize}
	\item \textbf{Azure.com} - Fastest and easiest
	\item \textbf{Microsoft Representative} - Intended for large organizations
	\item \textbf{Microsoft partner} - Partner provides access to Azure, manages billing and provides support.
\end{itemize}
\section{Azure Billing}
\subsection{Azure subscription}
\textbf{Azure subscription} - a logical container used to provision resources in Azure.\\
You might want to create additional subscriptions to separate:
\begin{itemize}
	\item \textbf{Environments} - development and testing
	\item \textbf{Organisational structures} - different departments
	\item \textbf{Billing} - manage and track costs
\end{itemize}
You may also need additional subscriptions due to subscription limits as they have hard limits, such as the max number of Express Route circuits per subscription is 10.
\begin{center}
	\includegraphics[width=15cm]{4-billing-structure-overview}
\end{center}
\section{Support options}
\subsection{Free resources}
\begin{itemize}
	\item Online documentation
	\item Community support
	\begin{itemize}
		\item Azure knowledge center
		\item Microsoft tech community
		\item Stack overflow
		\item Server fault
		\item Azure feedback forums
		\item Twitter
	\end{itemize}
	\item Demo videos
	\item Billing and subscription management support
	\item Azure quickstart center
	\item Azure service health
	\item Azure advisor
\end{itemize}
\subsection{Support plans}
{\renewcommand{\arraystretch}{2}
	\begin{tabularx}{\textwidth}{|L|L|L|L|}
		\hline
		& Developer & Standard & Professional Direct\\
		\hline
		Best for& Non-critical workloads&Production workloads & Business-critical workloads\\
		\hline
		Reactive technical support& 1 business day& 1 hour for critical& 1 hour and priority tracking for critical\\
		\hline
		Proactive technical support& N/A & N/A & Access to a pool of technical experts\\
		\hline

	\end{tabularx}
}

\end{document}

max_stars_repo_path: Module 2 - Creating an azure account/Module_2.tex