Debian Codegraph @

doc/iisignature.tex

raw
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