| 1 |
% NOTE: The canonical version of this documentation is now doc.md in the repository root. |
| 2 |
% This LaTeX file is retained for reference and PDF generation. |
| 3 |
\documentclass[a4paper]{extarticle} |
| 4 |
%\documentclass[a4paper,8pt]{extarticle} |
| 5 |
%landscape, twocolumn |
| 6 |
\usepackage[utf8]{inputenc} |
| 7 |
\usepackage[T1]{fontenc} |
| 8 |
\usepackage[backend=biber,backref=true]{biblatex} |
| 9 |
%\usepackage[backend=biber]{biblatex} |
| 10 |
\addbibresource{iisig.bib} |
| 11 |
\usepackage{parskip} %or set \parindent to 0pt |
| 12 |
\usepackage{graphicx} |
| 13 |
\usepackage{fullpage} |
| 14 |
\usepackage{color} |
| 15 |
%review 8pt and fullpage |
| 16 |
\usepackage{amsmath} |
| 17 |
%\usepackage{amssymb} |
| 18 |
%\usepackage{amslatex} |
| 19 |
\usepackage{siunitx} |
| 20 |
\usepackage{comment} |
| 21 |
\usepackage[section]{placeins} |
| 22 |
\usepackage{listings} |
| 23 |
\lstset{breaklines=true,basicstyle=\ttfamily,language=Python} |
| 24 |
\usepackage{arrayjobx} |
| 25 |
\usepackage{enumitem} |
| 26 |
\usepackage{tocloft} |
| 27 |
\setlength{\cftbeforesecskip}{0pt} |
| 28 |
\renewcommand{\contentsname}{} |
| 29 |
|
| 30 |
%nonewpage seems to have problems: |
| 31 |
%-you lose the index entries for functions on the same page as the index |
| 32 |
%-you have to run makeindex manually |
| 33 |
%\usepackage[nonewpage]{imakeidx} |
| 34 |
\usepackage{imakeidx} |
| 35 |
\DeclareFieldFormat{url}{{\small \url{#1}}} |
| 36 |
\makeindex[intoc,title=Index of functions] |
| 37 |
|
| 38 |
\usepackage{hyperref} %load this late |
| 39 |
|
| 40 |
\usepackage{changepage} % for adjustwidth |
| 41 |
\newenvironment{defn}{\begin{adjustwidth}{1cm}{}\ignorespaces}{\end{adjustwidth}\ignorespacesafterend} |
| 42 |
%\newenvironment{defn}[2]{\begin{adjustwidth}{1cm}{}}{\end{adjustwidth}} |
| 43 |
|
| 44 |
%\newtheorem{theorem}{Theorem} |
| 45 |
%uncomment this to get borders round floats |
| 46 |
%\usepackage{float}\floatstyle{boxed}\restylefloat{figure} |
| 47 |
\begin{document} |
| 48 |
\title{iisignature (version 0.24)} |
| 49 |
\author{Jeremy Reizenstein %\thanks{Department of Statistics and Centre for Complexity Science, University of Warwick (Supported by the Engineering and Physical Sciences Research Council). Facebook AI Research} |
| 50 |
and |
| 51 |
Ben Graham\thanks{University of Warwick and Facebook AI Research. Jeremy was supported by the Engineering and Physical Sciences Research Council.}} |
| 52 |
\date{June 2016 -- December 2019} |
| 53 |
\maketitle |
| 54 |
|
| 55 |
\def\ii{{\texttt{iisignature}}} |
| 56 |
\def\pypi{{\texttt{PyPI}}} |
| 57 |
\def\numpy{{\texttt{numpy}}} |
| 58 |
\def\scipy{{\texttt{scipy}}} |
| 59 |
\def\i#1{\index{#1@\texttt{#1}}} |
| 60 |
\def \hilite#1{\underline{\color{blue}\textbf{#1}}} |
| 61 |
|
| 62 |
\begin{abstract} |
| 63 |
The \ii\ Python package is designed to provide an easy-to-use reasonably efficient implementation of iterated-integral signatures and log-signatures of piecewise linear paths. Some motivation as to the usefulness of these things in machine learning may be found in \cite{OxSigIntro}. |
| 64 |
This software is described in the paper \cite{iisigPaper}, which users may wish to cite. |
| 65 |
\end{abstract} |
| 66 |
%\section{Introduction} |
| 67 |
%This |
| 68 |
\begin{minipage}{0.6\textwidth} |
| 69 |
\tableofcontents |
| 70 |
\end{minipage} |
| 71 |
\section{Installation into Python} |
| 72 |
First ensure you have \verb|numpy| installed and available, version 1.17 or later. You will need to be able to build \verb|C++| python extensions. |
| 73 |
On a Mac, this means you will need to have installed Xcode and the Xcode command line tools first. |
| 74 |
%Then you can install from \pypi with \verb|pip install iisignature|. |
| 75 |
Then \verb|pip install iisignature| will install it from \pypi. Python 3.8 or later is required. |
| 76 |
|
| 77 |
{\small (You can also run \verb|pip install --user iisignature| to install for your user only. On Windows, this doesn't need administrator rights, but you can't install for both 64 bit and 32 bit builds of the same version of Python in this way as doing one breaks the other.)} |
| 78 |
|
| 79 |
%For Python 2.7 and older on Windows, the build is not working perfectly and you might want to get in touch if you want to use this combination.\footnote{I find it basically works building with \texttt{python setup.py build -c mingw32}, where the compiler is (MinGW from \url{https://nuwen.net/mingw.html} for 64 bit Python and standard MinGW for 32 bit Python). However, there are problems with running the tests, at least when you have no debugger attached. } |
| 80 |
%For example, |
| 81 |
%\begin{quotation} |
| 82 |
%\begin{lstlisting} |
| 83 |
%set Path=%Path%;c:\mingw\bin |
| 84 |
%c:\python27-32\python.exe setup.py build --compiler=mingw32 |
| 85 |
%\end{lstlisting} |
| 86 |
%\end{quotation} |
| 87 |
|
| 88 |
%You may need |
| 89 |
%\verb|MACOSX_DEPLOYMENT_TARGET=10.9 pip install iisignature| depending on your python version, if the bare \verb|pip| command produces compiler errors. |
| 90 |
|
| 91 |
%https://stackoverflow.com/questions/25352389/difference-between-macosx-deployment-target-and-mmacosx-version-min-compiler-op |
| 92 |
%https://stackoverflow.com/questions/36960587/cython-build-cant-find-c11-stl-files-but-only-when-called-from-setup-py |
| 93 |
%https://stackoverflow.com/questions/33738885/python-setuptools-not-including-c-standard-library-headers |
| 94 |
\newpage |
| 95 |
\section{Quick example} |
| 96 |
To generate a random 3 dimensional path made up of 20 points and get its signature and log signature up to level 4 do this: |
| 97 |
\begin{quotation} |
| 98 |
\begin{lstlisting}[frame=single,language=Python,keywordstyle=\bf] |
| 99 |
import iisignature |
| 100 |
import numpy as np |
| 101 |
|
| 102 |
path = np.random.uniform(size=(20,3)) |
| 103 |
signature = iisignature.sig(path,4) |
| 104 |
s = iisignature.prepare(3,4) |
| 105 |
logsignature = iisignature.logsig(path,s) |
| 106 |
\end{lstlisting} |
| 107 |
\end{quotation} |
| 108 |
\section{Usage} |
| 109 |
|
| 110 |
Many of the functions require a path as input. A path in $d$ dimensions which is specified as a series of $n$ points should be given as a \verb|numpy| array of either \verb|float32| or (preferably) \verb|float64| with shape \verb|(n,d)|, or anything (like a list) which can be converted to one. |
| 111 |
|
| 112 |
\textbf{Batching:} Many of the functions which accept arrays can do the same operation multiple times in a single call by stacking the inputs, i.e. adding extra initial dimensions. This is supported on any of the functions where this document shows an ellipsis (\verb|...|) in a shape. If there are multiple array inputs to a function, their extra dimensions must match each other (broadcasting is not done). The result will have all the initial dimensions in it. Having any of these extra dimensions is always optional. A few of the functions are assumed to be most useful in the case where batching is in use. %Broadcasting is not supported. |
| 113 |
|
| 114 |
\verb!version()! \i{version} |
| 115 |
|
| 116 |
\begin{defn} |
| 117 |
\nopagebreak Return the version number of \ii. |
| 118 |
\end{defn} |
| 119 |
|
| 120 |
|
| 121 |
\subsection{Signatures} |
| 122 |
For the purposes of \ii, a signature up to level $m$ is the concatenation of levels 1 to $m$ as a single one dimensional array. The constant 1 which is always level 0 of a signature is never included. |
| 123 |
|
| 124 |
%\begin{minipage}{1\textwidth} |
| 125 |
\verb!siglength(d, m)! \i{siglength} |
| 126 |
\begin{defn} |
| 127 |
\nopagebreak The length of the signature up to level $m$ of a $d$-dimensional path. This has the value |
| 128 |
%\begin{align*} |
| 129 |
\[\sum_{i=1}^m d^i = \frac{d(d^m-1)}{d-1}.\] |
| 130 |
%\end{align*} |
| 131 |
\end{defn} |
| 132 |
%\end{minipage} |
| 133 |
|
| 134 |
\verb!sig(path, m, format=0)!\i{sig} |
| 135 |
|
| 136 |
\begin{defn} |
| 137 |
\nopagebreak The signature of the $d$-dimensional path \verb|path| up to level m is returned. The output is a \numpy\ array of shape \verb!(...,siglength(d,m))!. |
| 138 |
(If \verb|format| is supplied as \verb!1!, then the output for a single path is given as a list of \numpy\ arrays, one for each level, for the moment.) |
| 139 |
(If \verb|format| is supplied as \verb|2|, then we return not just the signature of the whole path, but the signature of all the partial paths from the start to each point of the path. |
| 140 |
If \verb|path| has shape \verb|(...,n,d)| then the result has shape \verb|(...,n-1,siglength(d,m))|.) |
| 141 |
\end{defn} |
| 142 |
\newpage |
| 143 |
\verb!sigjacobian(path, m)!\i{sigjacobian} |
| 144 |
\begin{defn} |
| 145 |
\nopagebreak This function provides the Jacobian matrix of the \verb|sig| function with respect to \verb|path|. If \verb|path| has shape \verb|(n,d)| then an array of shape \verb!(n,d,siglength(d,m))! is returned. |
| 146 |
\[\verb|sigjacobian(path,m)[a,b,c]| |
| 147 |
\approx |
| 148 |
{\partial\,(\verb|sig(path,m)[c]|) \over |
| 149 |
\partial\,(\verb|path[a,b]|)} |
| 150 |
\] |
| 151 |
%\verb cannot live in the argument of a function, which is why I use \[ and \over instead of e.g. align* and frac |
| 152 |
\end{defn} |
| 153 |
\verb!sigbackprop(s, path, m)!\i{sigbackprop} |
| 154 |
|
| 155 |
\begin{defn} |
| 156 |
\nopagebreak This function does the basic calculation necessary to backpropagate derivatives through the \verb|sig| function. If \verb|path| has shape \verb|(...,n,d)| and we are trying to calculate the derivatives of a scalar function $F$, and we have its derivatives with respect to \verb|sig(X,m)| stored in an array \verb|s| of shape \verb|(...,siglength(d,m))|, then this function returns its derivatives with respect to \verb|path| as an array of shape \verb|(...,n,d)|. |
| 157 |
\[\verb|sigbackprop(s,path,m)| |
| 158 |
\approx |
| 159 |
\verb|numpy.dot(sigjacobian(path,m),s)| |
| 160 |
\] |
| 161 |
\[\verb|sigbackprop(array(|{\partial F \over \partial \verb|sig(path,m)|}\verb|),path,m)[a,b]| \approx {\partial F \over \partial \verb|path[a,b]|} |
| 162 |
\] |
| 163 |
\end{defn} |
| 164 |
\verb!sigjoin(sigs, segments, m, fixedLast=float("nan"))!\i{sigjoin} |
| 165 |
|
| 166 |
\begin{defn} |
| 167 |
\nopagebreak Given the signatures of paths in dimension $d$ up to level $m$ in a shape \verb|(...,siglength(d,m))| array and an extra displacement for each path, stored as an array of shape \verb|(...,d)|, returns the signatures of each of the paths concatenated with the extra displacement as an array of shape \verb|(...,siglength(d,m))|. If the optional last argument \verb|fixedLast| is provided, then it provides a common value for the last element of each of the displacements, and \verb|segments| should have shape \verb|(...,d-1)| -- this is a way to create a time dimension automatically. |
| 168 |
\end{defn} |
| 169 |
\verb!sigjoinbackprop(derivs, sigs, segments, m, fixedLast=float("nan"))!\i{sigjoinbackprop} |
| 170 |
|
| 171 |
\begin{defn} |
| 172 |
\nopagebreak Returns the derivatives of some scalar function $F$ with respect to both \verb|sigs| and \verb|segments| as a tuple, given %that \verb|derivs| is |
| 173 |
the derivatives of $F$ with respect to \verb!sigjoin(sigs, segments, m, fixedLast)!. Returns both an array of the same shape as \verb|sigs| and an array of the same shape as \verb|segments|. If \verb|fixedLast| is provided, also returns the derivative with respect to it in the same tuple. |
| 174 |
\end{defn} |
| 175 |
\verb!sigcombine(sigs1, sigs2, d, m)!\i{sigcombine} |
| 176 |
|
| 177 |
\begin{defn} |
| 178 |
\nopagebreak Given the signature of two paths in dimension $d$ up to level $m$, return the signature of the two paths concatenated. This is the Chen multiplication of two signatures. Both \verb|sigs1| and \verb|sigs2| must have the same shape \verb|(...,siglength(d,m))|. |
| 179 |
\end{defn} |
| 180 |
\verb!sigcombinebackprop(derivs, sigs1, sigs2, d, m)!\i{sigcombinebackprop} |
| 181 |
|
| 182 |
\begin{defn} |
| 183 |
\nopagebreak Returns the derivatives of some scalar function $F$ with respect to both \verb|sigs1| and \verb|sigs2| as a tuple, given %that \verb|derivs| is |
| 184 |
the derivatives of $F$ with respect to \verb!sigcombine(sigs1, sigs2, d, m)!. Returns two arrays of the same shape as \verb|sigs1|. |
| 185 |
\end{defn} |
| 186 |
\verb!sigscale(sigs, scales, m)!\i{sigscale} |
| 187 |
\begin{defn} |
| 188 |
\nopagebreak Given the signatures of paths in dimension $d$ up to level $m$ in a shape \verb|(...,siglength(d,m))| array and a scaling factor for each dimension for each path, stored as an array of shape \verb|(...,d)|, returns the signatures of each of the paths scaled in each dimension by the relevant scaling factor as an array of shape \verb|(...,siglength(d,m))|. |
| 189 |
\end{defn} |
| 190 |
\verb!sigscalebackprop(derivs, sigs, segments, m)!\i{sigscalebackprop} |
| 191 |
|
| 192 |
\begin{defn} |
| 193 |
\nopagebreak Returns the derivatives of some scalar function $F$ with respect to both \verb|sigs| and \verb|scales| as a tuple, given %that \verb|derivs| is |
| 194 |
the derivatives of $F$ with respect to \verb!sigscale(sigs, scales, m, fixedLast)!. Returns both an array of the same shape as \verb|sigs| and an array of the same shape as \verb|scales|. |
| 195 |
\end{defn} |
| 196 |
\iffalse |
| 197 |
\verb!sigjoinbackprop1(sigs, segments, m, derivs)!\i{sigjoinbackprop1} |
| 198 |
|
| 199 |
\begin{defn} |
| 200 |
\nopagebreak Returns the derivatives of $F$ with respect to \verb|sigs| as an array of shape \verb|(n,siglength(d,m))| given that \verb|derivs| is the derivatives of $F$ with respect to \verb!sigjoin(sigs, segments, m)!. |
| 201 |
\end{defn} |
| 202 |
\verb!sigjoinbackprop2(sigs, segments, m, derivs)!\i{sigjoinbackprop2} |
| 203 |
|
| 204 |
\begin{defn} |
| 205 |
\nopagebreak Returns the derivatives of $F$ with respect to \verb|segments| as an array of shape \verb|(n, d))| given that \verb|derivs| is the derivatives of $F$ with respect to \verb!sigjoin(sigs, segments, m)!. |
| 206 |
\end{defn} |
| 207 |
\fi |
| 208 |
\newpage |
| 209 |
\subsection{Log signatures} |
| 210 |
\begin{center} |
| 211 |
\begin{minipage}{0.7\textwidth} |
| 212 |
\noindent\textbf{Quick summary:} To get the log signature of a \verb!d!-dimensional path \verb!p! up to level \verb!m!, there are two steps, as follows. |
| 213 |
\begin{quotation} |
| 214 |
\begin{lstlisting}[language=Python,keywordstyle=\bf] |
| 215 |
s=iisignature.prepare(d,m) |
| 216 |
logsignature=iisignature.logsig(p,s) |
| 217 |
\end{lstlisting} |
| 218 |
\end{quotation} |
| 219 |
The rest of this section gives more details. |
| 220 |
\end{minipage} |
| 221 |
\end{center} |
| 222 |
The algebra for calculating log signatures is explained in \cite{LOGSIG}. Several methods are available for calculating the log signature, which are identified by a letter. |
| 223 |
|
| 224 |
%good explanation http://tex.stackexchange.com/questions/56809/multiline-item-indent |
| 225 |
\begin{description}[leftmargin=1in,itemindent=0in,labelwidth=0.3in, |
| 226 |
labelsep=0.3in,labelindent=0.4in] |
| 227 |
\item[D] The \hilite{d}efault method, which is one of the methods A, C or S below, chosen automatically depending on the dimension and level requested. |
| 228 |
\item[C] The \hilite{c}ompiled method, under which machine code is generated to calculate the BCH formula explicitly. Currently, the generated code is designed for both \verb|x86| and \verb|x86-64| on both Linux (System V, Mac etc.) and Windows systems. I don't know anyone using other systems, but the result is likely to be a crash. |
| 229 |
\item[O] The BCH formula is expanded explicitly, but stored simply as a normal \hilite{o}bject. The object's instructions are followed to calculate the log signature. No code is written. This is simpler and potentially slower than the default method. It makes no particular assumptions about the platform, and so may be more broadly applicable. |
| 230 |
\item[S] The log signature is calculated by first calculating the \hilite{s}ignature of the path, then explicitly evaluating its logarithm, and then projecting on to the basis.% using linear algebra functionality of \numpy. |
| 231 |
%\footnote{For the Lyndon basis, the calculation exploits the fact that if $w$ is a Lyndon word then the corresponding basis element of the free Lie algebra $\rho(\sigma(w))$ in tensor space is a linear combination of words which are all anagrams of $w$. The full projection matrix is thus quite sparse, and we only need solve smaller systems, one for each anagram class.} |
| 232 |
This is observed to be faster than using the BCH formula when the log signature is large (for example level 10 with dimension 3 or higher dimension). It may be more generally faster when the path has very many steps. |
| 233 |
\item[A] The signed \hilite{a}rea is calculated explicitly by adding up the areas of triangles. This very simple method only works for level 1 and 2 of the signature, but works efficiently when the dimension of the path is large. |
| 234 |
\item[X] The log signature is calculated by first calculating the signature of the path, then explicitly evaluating its logarithm. This logarithm is returned e\hilite{x}panded in tensor space. This is used for testing purposes. |
| 235 |
\end{description} |
| 236 |
%Lyndon signature, pickling |
| 237 |
|
| 238 |
Log signatures are by default reported in the Lyndon basis in ascending order of level, with alphabetical ordering of Lyndon words within each level. A version of the standard or classical Hall basis is available instead by requesting it in the \verb|prepare| function. |
| 239 |
|
| 240 |
The C, O and S methods only work when the dimension of the path is below 256. The C and O methods only work up to 20 levels of signature. The A method only works up to 2 levels of signature. |
| 241 |
|
| 242 |
%\vbox{ |
| 243 |
\verb!logsiglength(d, m)!\i{logsiglength} |
| 244 |
\begin{defn} |
| 245 |
The length of the log signature up to level $m$ of a $d$-dimensional path. This value can be calculated using Witt's formula (see \cite{wikinecklace}). It is |
| 246 |
%\begin{align*} |
| 247 |
\[\sum_{l=1}^m \frac1l\sum_{x|l}\mu\left(\frac{l}{x}\right)d^x\] |
| 248 |
%\end{align*} |
| 249 |
where $\mu$ is the M\"obius function. |
| 250 |
\end{defn} |
| 251 |
%} |
| 252 |
|
| 253 |
\verb!prepare(d, m, methods=None)! \i{prepare} |
| 254 |
\nopagebreak \begin{defn}\nopagebreak |
| 255 |
This does preliminary calculations and produces an object which is used for calculating log signatures of $d$-dimensional paths up to level $m$. The object produced is opaque. It is only used as an input to the \verb|basis|, \verb|info| and \verb|logsig| functions. |
| 256 |
|
| 257 |
It is a capsule. It cannot be pickled. This means that if you are using \verb|multiprocessing|, you cannot pass it between ``threads''. You can run the function before creating the ``threads'', and use it in any thread - this works because it is fork-safe on non Windows platforms. On Windows, the function will be run separately in each background ``thread''. |
| 258 |
|
| 259 |
The calculation can take a long time when $d$ or $m$ is large. The Global Interpreter Lock is not held during most of the calculation, so you can profitably do it in the background of a slow unrelated part of the initialization of your program. For example: |
| 260 |
\begin{quotation} |
| 261 |
\begin{lstlisting}[language=Python,keywordstyle=\bf] |
| 262 |
import iisignature, threading |
| 263 |
def f(): |
| 264 |
global s |
| 265 |
s=iisignature.prepare(2,10,"CS") |
| 266 |
t = threading.Thread(target=f) |
| 267 |
t.start() |
| 268 |
#slow activity: theano.function, another prepare(), |
| 269 |
# keras compile, ... |
| 270 |
t.join() |
| 271 |
\end{lstlisting} |
| 272 |
\end{quotation} |
| 273 |
|
| 274 |
This function by default prepares to use only the default method. You can change this by supplying a string containing the letters of the methods you wish to use. For example, for $d=3$ and $m=10$, if you really wanted all methods to be available, you might run \verb|prepare(3,10,"COSX")| -- this takes a long time, because the BCH calculation is big. |
| 275 |
|
| 276 |
If you want results in the standard Hall basis instead of in the Lyndon word basis, add an H anywhere into the method string. For example \verb|prepare(2,4,"DH")|. When this is done, the result should be directly comparable to the output from the CoRoPa library \cite{coropa}. |
| 277 |
|
| 278 |
If you want to prepare the ability to convert log signatures to signatures, |
| 279 |
i.e.~the functions \texttt{logsigtosig} and \texttt{logsigtosigbackprop}, |
| 280 |
add the digit \verb!2! anywhere into the method string. |
| 281 |
|
| 282 |
The object returned never changes once it is created, except that \verb!logsigbackprop! can add the preparation for the \textbf{S} method later. |
| 283 |
|
| 284 |
\end{defn} |
| 285 |
\verb!logsig(path, s, methods=None)! \i{logsig} |
| 286 |
|
| 287 |
\begin{defn} |
| 288 |
\nopagebreak The log signature of the $d$-dimensional path \verb|path| up to level $m$, returned as a \numpy\ array of shape \verb!(...,logsiglength(d,m))!, where \verb!s! is the result of calling \verb!prepare(d,m[,...])!. |
| 289 |
|
| 290 |
By default, this uses the calculation method (\textbf{C}, \textbf{O}, \textbf{S} or \textbf{A}) which is supported by \verb|s| and comes first in the table above. You can restrict this by supplying as the final argument a string containing the letters of the methods you wish to be considered, this will probably be a one-letter string. |
| 291 |
|
| 292 |
If you wish to use the \textbf{X} method, you have to ask for it here, and the output will have shape \verb!(...,siglength(d,m))!. |
| 293 |
\end{defn} |
| 294 |
\verb!logsigbackprop(derivs, path, s, methods=None)!\i{logsigbackprop} |
| 295 |
|
| 296 |
\begin{defn} |
| 297 |
\nopagebreak Returns the derivatives of some scalar function $F$ with respect to \verb|path|, given %that \verb|derivs| is |
| 298 |
the derivatives of $F$ with respect to \verb!logsig(path, s, methods)!. Returns an array of the same shape as \verb|path|. The only methods supported are \textbf{S} and \textbf{A} (the defaults) and \textbf{X} (which is only used if \verb|methods| is \verb|'X'|). If the \verb|'X'| method is not requested, the \textbf{A} method is inapplicable, and \verb|s| does not support the \textbf{S} method, then \verb|s| is modified so it \emph{does} support the \textbf{S} method. |
| 299 |
\end{defn} |
| 300 |
|
| 301 |
\verb!basis(s)! \i{basis} |
| 302 |
|
| 303 |
\begin{defn} |
| 304 |
\nopagebreak The basis of bracketed expressions given as a tuple of unicode strings, for words of length no more than $m$ on $d$ letters, where \verb!s! is the result of calling \verb!prepare(d,m[,...])!. These are the bracketed expressions which the coefficients returned by \verb|logsig| refer to. |
| 305 |
|
| 306 |
If $d>9$, the output of this function is not yet fixed. An example of how to parse the output of this function can be seen in the tests. |
| 307 |
\end{defn} |
| 308 |
|
| 309 |
\verb!info(s)! \i{info} |
| 310 |
|
| 311 |
\begin{defn} |
| 312 |
\nopagebreak If \verb!s! is the result of calling \verb!prepare(d,m[,...])!, then this returns a dictionary of properties of \verb|s|, including a list of methods which it supports. This may be a useful diagnostic. |
| 313 |
\end{defn} |
| 314 |
|
| 315 |
\verb!logsigtosig(logsig, s)! \i{logsigtosig} |
| 316 |
|
| 317 |
\begin{defn} |
| 318 |
\nopagebreak If \verb!s! is the result of calling \verb!prepare(d,m,methods)!, |
| 319 |
and \texttt{logsig} (shape \verb|(...,logsiglength(d,m))|) is a logsignature, |
| 320 |
then returns the corresponding signature with shape \verb|(...,siglength(d,m))|. |
| 321 |
The digit \texttt{2} must be included in \texttt{methods}. |
| 322 |
\end{defn} |
| 323 |
|
| 324 |
\verb!logsigtosigbackprop(derivs, logsig, s)!\i{logsigtosigbackprop} |
| 325 |
|
| 326 |
\begin{defn} |
| 327 |
\nopagebreak Returns the derivatives of some scalar function $F$ with respect to \verb|logsig|, given |
| 328 |
the derivatives of $F$ with respect to \verb!logsigtosig(logsig, s)!. |
| 329 |
Returns an array of the same shape as \verb|logsig|. |
| 330 |
\end{defn} |
| 331 |
|
| 332 |
\verb!logsigjoin(sigs, segments, s)!\i{logsigjoin} |
| 333 |
|
| 334 |
\begin{defn} |
| 335 |
\nopagebreak Given the log signatures of paths in dimension $d$ up to level $m$ in a shape \verb|(...,siglength(d,m))| array and an extra displacement for each path, stored as an array of shape \verb|(...,d)|, and \verb!s! the result of calling \verb!prepare(d,m,methods), returns the log signatures of each of the paths concatenated with the extra displacement as an array of shape \verb|(...,logsiglength(d,m))|. |
| 336 |
\end{defn} |
| 337 |
\verb!logsigjoinbackprop(derivs, sigs, segments, s)!\i{logsigjoinbackprop} |
| 338 |
|
| 339 |
\begin{defn} |
| 340 |
\nopagebreak Returns the derivatives of some scalar function $F$ with respect to both \verb|sigs| and \verb|segments| as a tuple, given %that \verb|derivs| is |
| 341 |
the derivatives of $F$ with respect to \verb!logsigjoin(sigs, segments, s)!. Returns both an array of the same shape as \verb|sigs| and an array of the same shape as \verb|segments|. |
| 342 |
\end{defn} |
| 343 |
|
| 344 |
|
| 345 |
\subsection{Linear rotational invariants} |
| 346 |
\begin{center} |
| 347 |
\begin{minipage}{0.7\textwidth} |
| 348 |
\noindent\textbf{Quick summary:} To get all the linear rotational invariants of a two dimensional path \verb!p! up to level \verb!m!, there are two steps, as follows. |
| 349 |
\begin{quotation} |
| 350 |
\begin{lstlisting}[language=Python,keywordstyle=\bf] |
| 351 |
s=iisignature.rotinv2dprepare(m,"a") |
| 352 |
invariants=iisignature.rotinv2d(p,s) |
| 353 |
\end{lstlisting} |
| 354 |
\end{quotation} |
| 355 |
The rest of this section gives more details. |
| 356 |
\end{minipage} |
| 357 |
\end{center} |
| 358 |
|
| 359 |
The paper \cite{JD} explains how to find the linear subspace of signature space of two dimensional paths which is invariant under rotations of the path. The subspace is spanned by a set of vectors each of which lives in a single signature level, and all those levels are even. The functions in this section calculate them, and are a bit experimental. You may need to rescale them in a deep learning context. |
| 360 |
|
| 361 |
\verb!rotinv2dprepare(m,type)! \i{rotinv2dprepare} |
| 362 |
\begin{defn} |
| 363 |
\nopagebreak This prepares the way to find linear rotational invariants of signatures up to level \verb|m| of 2d paths. The returned opaque object is used (but not modified) by the other functions in this section. \verb|m| should be a small even number. \verb|type| should be \verb|"a"| if you want to return \textbf{a}ll the invariants. |
| 364 |
|
| 365 |
Some invariants do not add information, because their values are products of other invariants. Set \verb|type| to \verb|"s"| if you want to exclude them. Internally, at each level, a basis for the invariant subspace with the known elements quotiented out is found using \textbf{s}ingular value decomposition from \numpy. The exact result in this case is not guaranteed to be stable between versions. (An alternative, potentially faster, method of doing the same calculation uses the \textbf{Q}R decomposition as provided by \scipy. You can get this by setting \verb|type| to \verb|"q"|. This will only work if you have \scipy\ available, and may generate a strange but harmless warning message.\footnote{I have observed this only on Python 3.6 on Windows, and do not understand it.\url{https://stackoverflow.com/questions/45054949/calling-scipy-from-c-extension}}) (In addition, setting \verb|type| to \verb|"k"| means that \emph{only} the invariants which are already \textbf{k}nown based on lower levels will be returned. This is used for testing.) |
| 366 |
|
| 367 |
If $m$ exceeds 10 this function can take a lot of time and memory. |
| 368 |
\end{defn} |
| 369 |
\verb!rotinv2d(path, s)! \i{rotinv2d} |
| 370 |
|
| 371 |
\begin{defn} |
| 372 |
\nopagebreak The rotational invariants of the signature of the 2-dimensional path \verb|path| up to level $m$, where \verb!s! comes from \verb!rotinv2dprepare(m,...)!. The result is returned as a \numpy\ array of shape \verb!(...,rotinv2dlength(s))!. |
| 373 |
\end{defn} |
| 374 |
\verb!rotinv2dlength(s)! \i{rotinv2dlength} |
| 375 |
|
| 376 |
\begin{defn} |
| 377 |
\nopagebreak The number of rotational invariants which are found by the calculation defined by \verb!s!, where \verb!s! is the result of calling \verb!rotinv2dprepare(m,type)!. When the type is \verb|"a"|, this is just \[\sum_{i=1}^{m/2}\binom{2i}{i}.\] |
| 378 |
In common cases, the result is given in this table: |
| 379 |
\end{defn} |
| 380 |
|
| 381 |
|
| 382 |
\begin{center} |
| 383 |
\begin{tabular}{r|rrr} |
| 384 |
\verb|m|&\verb|"a"|&\verb|"s"|&\verb|"k"|\\\hline |
| 385 |
2&2&2&0\\ |
| 386 |
4&8&5&3\\ |
| 387 |
6&28&15&15\\ |
| 388 |
8&98&46&76\\ |
| 389 |
10&350&154&336\\ |
| 390 |
12&1274&522&1470\\ |
| 391 |
14&4706&1838&6230\\%took 42 mins |
| 392 |
\end{tabular} |
| 393 |
\end{center} |
| 394 |
|
| 395 |
%\newpage |
| 396 |
\verb!rotinv2dcoeffs(s)! \i{rotinv2dcoeffs} |
| 397 |
\begin{defn} |
| 398 |
\nopagebreak The basis of rotational invariants which are found by the calculation defined by \verb!s!, where \verb!s! is the result of calling \verb!rotinv2dprepare(...)!. The result is given as a tuple of 2d \numpy\ arrays, where each row of element \verb|i| is an element of the basis within level $(2i+2)$ of the signature. |
| 399 |
\end{defn} |
| 400 |
|
| 401 |
\section{Implementation notes} |
| 402 |
The source code is easily found at \url{https://github.com/bottler/iisignature}. The extension module is defined in a single translation unit, \verb|src/pythonsigs.cpp|. Here I explain the structure of the implementation which is located in various header files in the same directory. If you want to use the functionality of the library from \verb!C++!, it should be easy just to include these header files. |
| 403 |
|
| 404 |
\begin{description} |
| 405 |
\item{\verb|calcSignature.hpp|} implements the functions \verb|sig|, \verb|sigbackprop|, \verb|sigjacobian|, \verb|sigjoin| and \\ \verb|sigjoinbackprop|, and \verb|sigscale| and \verb|sigscalebackprop|. |
| 406 |
|
| 407 |
\item{\verb|logSigLength.hpp|} implements the function \verb|siglength| and \verb|logsiglength|. |
| 408 |
\item{\verb|iisignature_data/bchLyndon20.dat|} is the file of Baker-Campbell-Hausdorff coefficients from Fernando Casas and Ander Murua available from \cite{bchinfo}. It was calculated using their method described in \cite{bch}. You need to open this file and point the global variable \verb|g_bchLyndon20_dat| to its entire contents. |
| 409 |
\item{\verb|readBCHCoeffs.hpp|} has facilities for reading the coefficients in \verb|bchLyndon20.dat|. |
| 410 |
\item{\verb|bch.hpp|} implements calculations which manipulate elements of the Free Lie Algebra with generic coefficient objects. This uses \verb|readBCHCoeffs.hpp|. The procedures are as explained in \cite{LOGSIG}, and the design is similar to the python code \verb|logsignature.py|. |
| 411 |
\item{\verb|makeCompiledFunction.hpp|} defines a structure \verb|FunctionData| which describes a function which does some arithmetic on two arrays which is generic enough to concatenate log signatures. It has the ability to run such a function (\verb|slowExplicitFunction|) and the ability to create an object \verb|FunctionRunner| which represents a compiled version of the function. Currently no particular recent CPU capability is assumed - SSE2 is being used. |
| 412 |
\item{\verb|logsig.hpp|} uses \verb|bch.hpp| and \verb|makeCompiledFunction.hpp| to implement the \verb|prepare| function. |
| 413 |
|
| 414 |
The code required to solve the linear systems to convert a signature to a log signature (for the \textbf{S} method) is not provided. The addin relies on \numpy\ to do this. |
| 415 |
|
| 416 |
If you want to call this from your own \verb|C++| code, you will need to provide a value for \verb|interrupt|. A function which does nothing is fine. The idea is that it should be a function which returns if the calculation should continue and throws an exception if it wants the calculation to abort. None of these header files catch any exceptions - you can safely catch it in the calling code. |
| 417 |
|
| 418 |
\item{\verb|rotationalInvariants.hpp|} has functions to identify linear rotational invariants and their shuffle products. |
| 419 |
\end{description} |
| 420 |
|
| 421 |
\section{Example code, Theano, Tensorflow, Torch and Keras} |
| 422 |
%http://tex.stackexchange.com/questions/181118/how-to-escape-curly-braces-within-texttt - \string |
| 423 |
\def\Th{\texttt{Theano}} |
| 424 |
\def\Te{\texttt{tensorflow}} |
| 425 |
\def\K{\texttt{Keras}} |
| 426 |
Simple examples of using many of the functions are in the test file at \url{https://github.com/bottler/iisignature/blob/master/tests/test_sig.py}. |
| 427 |
|
| 428 |
\Th\ and \Te\ are Python frameworks for constructing calculation graphs, of the sort which is useful for deep learning. \K\ is a Python framework for deep learning which uses either of them for its calculations. \ii\ does not depend on these libraries. Pure Python code using \ii\ inside \Te, \Th\ and \K\ can be found in the source repository at \url{https://github.com/bottler/iisignature/tree/master/examples}. |
| 429 |
|
| 430 |
\begin{itemize} |
| 431 |
\def\pytorch{\texttt{PyTorch}} |
| 432 |
\item The modules \verb!iisignature_theano!, \verb!iisignature_tensorflow! and \verb|iisignature_torch| provide operations \verb!Sig!, \verb|LogSig|, \verb|SigJoin| and \verb!SigScale! in \Th, \Te\ and \pytorch\ respectively which mirror the functions \verb!sig!, \verb|logsig|, \verb!sigjoin! and \verb!sigscale! in \ii. The calculations are done via \ii, and therefore always on the CPU. |
| 433 |
\item \verb!iisignature_recurrent_keras! is a module which provides a recurrent layer in \K\ using the \Th\ and \Te\ operations. There are variants of this file for compatibility with older versions of \K. A similar module for \pytorch\ is given in \verb!iisignature_recurrent_torch!. |
| 434 |
\end{itemize} |
| 435 |
Other files with names beginning with \verb|demo| in the same directory provide demonstrations of this functionality. |
| 436 |
\section{Version history} |
| 437 |
\begin{tabular}{rcp{0.75\textwidth}} |
| 438 |
Revision&Date&Highlights\\[2mm] |
| 439 |
0.24&2019-12-01&FIX longstanding BUG giving incorrect result in \verb|logsigbackprop| for Lyndon basis when \texttt{m>=6} or (\texttt{d>=3} and \texttt{m>=4}). |
| 440 |
New: \verb|sigcombine|, \verb|logsigtosig|, area \verb|'A'| method for \verb|logsig|. Python 3.8 build for windows.\\ |
| 441 |
0.23&2018-08-21&\verb|2| option for \verb|sig| for partial signatures, return 64 bit floats from \verb|sig|, Python 3.7 and Numpy 1.15 support\\ |
| 442 |
0.22&2017-10-02&mac installation fix, fix issues with 0.21 release\\ %such as 0.21 doc never existed, README malformatted on PyPI |
| 443 |
0.21&2017-09-20&\verb|logsigbackprop|, %batching for rotinv, |
| 444 |
speedups: Horner method for \verb|'S'|, store \verb|BasisElt| in order\\ |
| 445 |
0.20&2017-08-09&Batching, triangle optimised \verb|'S'|, Mac install fix, \verb|sigjoinbackprop| to \verb|fixedLast|, \verb|logsig| bug for paths of one point, \verb|QR| method\\ |
| 446 |
0.19&2017-06-27&Rotational invariants, 32bit linux \verb|'C'|, inputs don't have to be numpy arrays\\ |
| 447 |
0.18&2017-03-28&Hall basis, \verb|info|, fix memory leak in \verb|sigjoinbackprop| and \verb|sigscalebackprop|, fix \verb|sigscalebackprop|\\%, examples updated to Keras2\\ |
| 448 |
0.17&2017-01-22&\verb|sigscale|, fix \verb|sigjoinbackprop| on Windows (code was miscompiled)\\%level-by-level output, sigmultcount %can use \newline within a cell in the p{} column |
| 449 |
0.16&2016-08-23&Derivatives of signature%, Theano examples |
| 450 |
\\ |
| 451 |
0.15&2016-06-20&Windows build\\ |
| 452 |
\end{tabular} |
| 453 |
Improvements to the example code are not listed here, they can be seen on \verb|github|. |
| 454 |
\printindex |
| 455 |
|
| 456 |
\printbibliography[heading=bibintoc] |
| 457 |
\end{document} |
| 458 |
|
| 459 |
%NB - Ctrl-C seems to work, but you can get spurious SVD errors |