Extractable patterns

Abstract This set of notes attempts to study possibility of constructing categories with neural nets as morphism and functors. The reason for such construction comes stems from possible enriching connections between category theory and deep learning. Usually Category Theory is used to formalize abstractions of the given concrete objects. On the other hand, Deep Learning is mostly used in constructing explicit neural network based mappings between various spaces given by sampled datasets. The notes explores if it is possible to leverage on strengths of category theory and deep learning in order to represent more abstract concepts and processes. Introduction Motivation: The main motivation for development of framework if two folds. Firstly, it might shed a new light for representing more abstract objects, such as movements and processes. Secondly, we leverage on rich experience of building deep neural nets accumulated in Machine Learning community. Abs...

"You are number of languages that you know" said one of the quotes attributed to Al-Farabi, which my school teacher used to tell us. Indeed almost all languages describe the same objects: humans, animals, nature and universe in general. However, the way each language does so might differ from another one. This difference makes learning new languages fun. A somewhat similar statement can be said about programming languages. Almost all of them perform some kind of logical and computational transformations on given data, however the ways they do so might significantly differ. Having learnt some Python to play with Machine Learning (ML) algorithms, I wanted to explore other programming languages. The first language which came to mind was C++. It is one of the languages used to code massive and complex software systems. So did I explored using a website  https://www.programiz.com/cpp-programming . How it went The installation part went easy. The application XCode does a solid ...

When one reads about Machine Learning (ML) or Artificial Intelligence (AI) it is common to come across a list of approaches to AI such as: symbolic reasoning, Bayesian learning, artificial neural networks and so on. Seeing this list I was puzzled with a notion of Bayesian Learning. The only thing I knew with a name Bayes in its name was a famous Bayes's theorem which states that \[ P(H\mid E) = \frac{P(E\mid H)P(H)}{P(E)} \] where $P(H)$ and $P(H\mid E)$ denote prior and posterior probabilities of hypothesis $H$, respectively. What puzzled me is the application of such a simple looking formula to draw patterns from data. In order to learn basic principles of Bayesian learning, I decided to consult Wikipedia and few online tutorials. This post is about results of this exploration. Wikipedia says Bayesian learning (inference?) is a method of statistical inference in which Bayes's theorem is used to update the probability for a hypothesis as more evidence or informatio...

A subject of Algebraic Geometry (AG) is one of central branches of Mathematics, yet I have almost no knowledge of objects and spaces that algebraic geometers study. The mere look at the name suggests some kind of relationship between algebra and geometry. So does algebra lends its hand to solve geometric problems, or is it other way around. I did not know. Realising my ignorance of the matter, I decided to rectify situation I decided to read some Wikipedia articles along with some introductory books on the subject matter. In this post I intend to share fruits of my explorations. How AG was born? AG was born out of desire to solve systems of polynomial equations. Suppose we have a system \[ f_i(X_1,\ldots,X_n) = 0, \quad i=1,\ldots, m \] where each $f_i$ is a polynomial of $n$ variables with coefficients drawn from some field $k$, which can succinctly be written as $f_i\in k[X_1,\ldots,X_n]$. What to do next? Mostly it is pretty difficult to solve such systems. However, i...

This post continues to study relationship between definitions of Hausdorff dimension obtained through covers and gales. In the last post, we have shown how to switch from covers to gales, which allowed us to conclude that \[ \inf G(X) \le \dim_H(X) \] So now our aim should be verification of reverse inequality, i.e. $\dim_H(X)\le \inf G(X)$. In order to do this, we go back to definitions. Let us start with basics $\mathcal{C} = \{0,1\}^{\mathbb{N}}$ is Cantor space with some subset $X$. Let $d$ be an $s$-gale which succeeds on $X$, i.e. $X\subseteq S^{\infty}[d]$. This means that $\inf G(X)\le s$. Furthermore, for any given $\epsilon>0$, one could choose $s$ such that $\inf G(X)\ge s-\epsilon$. Given such $s$, we claim that $\mathcal{H}^s(X)=0$, i.e. \[ \inf\{\sum_{i=1}^{\infty}diam(C_{w_i})^s \} = 0 \] where $X\subseteq \bigcup C_{w_i}$. This would give us $\dim_H(X)\le s \le \inf G(X) + \epsilon$. By letting $\epsilon\to 0$, the desired inequality follows. So our main...

In this post we attempt to understand a relationship between Hausdorff dimension defined in a classical way and Hausdorff dimension defined using gales. Recall that classical Hausdorff dimension is defined in terms of covers. So, in order to understant that relationship, we need to be able to 'switch' back and forth from covers and gales. In this post we will try to switch from covers to gales. As before, we work in Cantor space $\mathcal{C} = \{0,1\}^{\mathbb{N}}$. We start with some subset $X\subseteq \mathcal{C}$. For any given $\varepsilon>0$, one can choose $s\ge 0$ such that $s-\varepsilon < \dim_H(X) < s$. Then we go on to show that there $s$-gale succeeding on $X$, i.e. $\inf G(X)\le s$. Combining this with above inequality, we have \[ \inf G(X)\le s < \dim_H(X) + \varepsilon \] By letting $\varepsilon \to 0$, one shows that $\inf G(X)\le \dim_H(X)$. So, we are left to show that it is indeed possible to construct $s$-gale given the fact that $\dim...

In this post we aim to provide characterization of Hausdorff Dimension in Cantor space in terms of special function called gales. Our presentation mainly follows that of Mayordomo [1], while the notion itself is from Lutz [2]. Gales Let us first go through definitions of supergales and gales. Take $s\in [0, \infty)$. An $s$-supergale is a function $d:\{0,1\}^*\to [0,\infty)$ such that: \[ d(w) \ge 2^{-s}\left[ d(w0) + d(w1) \right] \] for all $w\in \{0,1\}^*$. A definition $s$-gale is similar to the above, except for the equality sign in place of the inequality sign for each $w\in \{0,1\}^*$. A supermartingale is $1$-supergale, while a martingale is an $1$-gale. As for names, they seem to derive from a notion of martingale from probability theory. A parameter $s$ describes fairness of the betting game. Observe that the condition for $s$-gale can be rewritten as: \[ E[d(wb)] = \frac{1}{2}d(w0) + \frac{1}{2}d(w1) = 2^{s-1}d(w) \] Depending on the value of $s$, the game ca...

In some of previous posts we have discussed regular languages and automatic relations from automata theory. This discussion were meant to lead to the upcoming discussion of automatic groups. Groups are one of the most fundamental algebraic structures arising almost everywhere in mathematics. Why to study automatic group? Well this kind of research arouse around sixties when Rabin and others asked what would happen if we impose some kind of algorithmic conditions on mathematical structures. First people studied heavily so called computable structures, i.e. structures recognized by computable functions. These days people study structures under all sorts of algorithmic constraints. Some study in computable constraints, some go beyond and look at Turing machines which work with reals, while some people, like me, study structures with automata-theoretic constraints. One of the first people who have done that are Hodgson, Khoussainov and Nerode. There are several variants of studying...

Introduction People like to measure things. In mathematical analysis there is a notion of measure studied in Measure theory . In Topology we have a notion of topological dimension . In Information Theory we have a notion of entropy . In Computational Complexity Theory we have notions of time and space complexities . So the general idea is to quantify size or complexity of the given object. Then we can talk about whether this object is somehow bigger/more complex than the other object. In this post I would like to say few things about Hausdorff dimension . Motivation Why do we need Hausdorff dimension? There are many reasons. One of the reasons people talk most is its fineness. In other words Hausdorff measure can provide some meaningful information when Lebesgue measure gives none. To see that, observe that there are many sets of measure $0$. A single point is of measure $0$ and a Cantor space is of measure $0$. However, it is clear that those two are completely different objec...

Several posts ago, we have talked about SVMs. In particular how it is possible to formulate SVM objective as optimization technique. In this post we are going to learn about Lagrange Duality, an optimization method, which is going to help us to solve the optimization problem we ended up with last time. Let us start with a simpler optimization problem given as: \[ \min_w\, f(w) \] subject to constraints: \[ h_i(w) = 0, \quad i=1,\ldots, l. \] The classical way to solve such a problem is to write a Lagrangian function: \[ L(w,\beta) = f(w) + \sum_{i=1}^l \beta_i h_i(w) \] and set \[ \frac{\partial L}{\partial w_i} = 0, \quad \frac{\partial L}{\partial \beta_i}=0 \] This works because at critical points of $L(w,\beta)$ we must have $h_i(w)=0$ for all $i$. Now let us consider a more complex optimization problem: \[ \min f(w) \] subject to constraints: \[ g_i(w) \le 0, \quad i = 1,\ldots,k \] and \[ h_j(w) = 0,\quad j = 1,\ldots,l \] Let us call the above pr...

In one of the previous posts we have gone through a concept of  regular languages. These languages are quite convenient to work with and have a great deal of good properties, which might be the topic for another post. In this post I would like to focus on automatic relations. This notion tries to extend regularity from unary relation to $k$-ary relations. So instead of asking if $x\in L$ for a given regular language $L$, we ask $(x_1,x_2,\ldots,x_n)\in R$ for a some relation $R$. Suppose $R\subseteq (\Sigma^*)^n$ be some $n$-ary relation. Our aim is to check a membership of the tuple $(x_1,x_2, \ldots, x_n)$ in $R$. For this we stack or \emph{convolute} these words, so that it might look like this in the case of $n=4$: \[ \begin{bmatrix} 1 & 0 & 0 & 1 & 1\\ 0 & 1 & 1 & & \\ 1 & & & &\\ 1 & 0 & 0 & & \end{bmatrix} \] Observe that above block is nonuniform in length, so it cannot be generated by the tuple...

Though a term support vector machines sounds pretty fancy, the basic idea behind them is pretty easy. For simplicity, let us assume that we have a binary classification problem with a dataset $\mathcal{D} = \{(x^{(i)},y^{(i)}\}$ where $x^{(i)}\in \mathbb{R}^n$ and $y^{(i)}\in \pm1$. Our aim is to find somehow 'optimal' hyperplane, high-dimensional version of plane, that separates positive and negative datapoints sufficiently well. To understand how do we find that optimal hyperplane let us transform our setting to $n$-dimensional Euclidean space.\\ Here we can define an operation of dot product between any two vectors, $\cdot:\mathbb{R}^n\times \mathbb{R}^n\to \mathbb{R}$. This dot product is defined as follows: \[ x\cdot y = \sum_{i=1}^n x_iy_i \] where $x = (x_1,x_2,\ldots,x_n)$ and $y=(y_1,y_2,\ldots,y_n)$. Let us fix some vector $w$ and look at the dot product of the type: \[ w\cdot x, \text{ where } \Vert x \Vert =1 \] One might ask when is such product is m...

In this series of posts, I wish to introduce a notion of automatic groups, i.e. groups which has an automatic presentation. To do so, we need to revise notions of regularity and that of automatic relation. Let us start with a notion of regularity. Regular Languages The concept of regularity for formal languages can be approached from several sides. We are going to define regulaity using finite state machines. We start with a finite set $\Sigma$ called an \emph{alphabet}. By concatenating elements of this alphabet, we can form \emph{words} or \emph{strings}. For example, if $\Sigma = \{0,1\}$, then possible words are $01$ and $00111$. Let us denote a collection of all possible words in the given alphabet $\Sigma$ as $\Sigma^*$. We refer to subsets of $\Sigma^*$ as \emph{formal languages} or \emph{languages} for short. There are might be different kinds of languages, in fact $\vert 2^{\mathbb{N}}\vert \}$ many, some of them easy to describe, while others extremely complicated...

In the previous post, we were left with the construction of graph $\Gamma$ from group $G$ with a promise to transform the graph into a metric space. A metric space consists of vertices together with edges. Each edge is assumed to have a length of $1$.  Let's denote the given space $X$. As for metric, we first define a distance between two vertices. A distance between two vertices $h,k$ corresponds to the length of the shortest path between them. Formally: \[ d(g,h) = \min\{n\mid g^{-1}h = s_1s_2\ldots s_n \},\quad s_i\in S \] As for points on the edges, the distance defined similarly with consideration that each point should first travel to one of its two neighboring vertices. With this metric, $X$ or $Cay(G,S)$ becomes a metric space and referred to as Cayley graph of $G$ with respect to $S$. We can say few things about $X$ immediately. Firstly, $X$ is a proper metric space, i.e. its closed balls are compact. Secondly, $X$ is a geodesic metric space, i.e. there is a short...

From earliest of times, people have been using tools which simplified and enriched their lives. At first humans used natural tool such as stones to manufacture necessary items, and animals as a source of food, transportation and clothing. Then people learned to design more sophisticated tools such as engines, planes and cars. So the tools were progressing from the simplest to more advanced by the means on human intellect. In twentieth century people invented computers which could perform millions of  operations in a fractions of second, this allowed people to scale things up in an unprecedented levels. Currently, people are trying to use these computers to produce the intelligence, a mighty feat if it is to be accomplished. But the new tool has a potential of altering our very lifestyle. If earlier tools were intended to quicken thing up, the tool of artificial intelligence has a potential of turning things upside down. For this reason, I believe, we need to be aware of general de...

A Cayley graph can be considered as an attempt to geometrize or visualize groups . Algebraically, a group is just a bunch of letters some of them having an inverse script. By visualizing groups, we may observe some patterns in their structure. So let's see how can we construct Cayley graphs. Take an arbitrary group $G$ with a set of generators $S\subset G$. In other words, every element of $G$ can be written as: \begin{equation} g = s_1^{\epsilon_1}s_2^{\epsilon_2}\ldots s_n^{\epsilon_n},\quad \epsilon_i\in\{\pm1 \} \end{equation} As for $S$, we assume that $S^{-1} = S$, i.e. $s\in S$ implies $s^{-1}\in S$, and $1\not\in S$. In fact these assumptions are not necessary, but tend to make life a bit easier. Let us construct a Cayley graph $\Gamma=(V,E)$ as follows: $V=G$ $(g,h)\in E$ if $gs = h$ for some $s\in S$, or equivalently $g^{-1}h\in S$ We can observe few things straight away about $\Gamma$. It is undirected as $gs = h$ happens when $g = hs^{-1}$. Any two vert...

In this post I would like to relate some of the reasons why I decided to study automatic groups near the end of my PhD term. I have always been fascinated about patterns occurring in universe. I marvel at the objects of ever-increasing complexities populating our universe. Probably, that is the reason why I chose to study mathematics. For me mathematics is a study of patterns. But these patterns are not limited to our physical universe. Most of the time, they live in some abstract universes. In those universes, patterns live in different continents which can interpreted as fields like Algebra, Analysis, Geometry, Topology, Mathematical Logic and much more. Some patterns occur at different continents and travel back and forth along some bridges. One of the most famous among such bridges is Langlands program. Pondering on such bridges gives me a deep sense of wonder. In my third year, I mainly focused on a notion of algorithmic randomness. A randomness occurs when some patterns are no...