% Gemini theme
% https://github.com/anishathalye/gemini
%
% We try to keep this Overleaf template in sync with the canonical source on
% GitHub, but it's recommended that you obtain the template directly from
% GitHub to ensure that you are using the latest version.

\documentclass[a4paper]{article}

% ====================
% Packages
% ====================

\usepackage[slovene]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath} 
\usepackage{amsthm}  
\usepackage{amssymb} 
\usepackage{amsfonts}
\usepackage{lmodern}
\usepackage{graphicx}
\usepackage{url}
\usepackage{pgfplots}
\usepackage{xcolor, soul}
\pgfplotsset{compat=1.14}

% ====================
% Lengths
% ====================

% If you have N columns, choose \sepwidth and \colwidth such that
% (N+1)*\sepwidth + N*\colwidth = \paperwidth
\newlength{\sepwidth}
\newlength{\colwidth}
\setlength{\sepwidth}{0.025\paperwidth}
\setlength{\colwidth}{0.3\paperwidth}

\newcommand{\separatorcolumn}{\begin{column}{\sepwidth}\end{column}}
% za številske množice uporabite naslednje simbole
\newcommand{\R}{\mathbb R}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\C}{\mathbb C}
\newcommand{\Q}{\mathbb Q}
\newcommand{\F}{\mathbb F}

\newcommand{\opcija}[2]{#1\;\; [#2]}


%\renewcommand*{\footnotesize}{\fontsize{8}{10}\selectfont}
% ====================
% Title
% ====================

\title{P(izraz|gramatika)}

\author{Urh Primožič}


\begin{document}

% \maketitle
   \begin{center}
      \Large\textbf{P(izraz|gramatika)}\\
      \large\textit{Urh Primožič}
   \end{center}


    Simbolna regresija je področje strojnega učenja, ki se ukvarja z iskanjem funkcij, ki se prilegajo danim podatkom in imajo čim bolj preprost predpis. Novi algoritmi simbolne regresije za tvorjenje predpisov uporabljajo verjetnostne gramatike. Računamo lahko, s kakšno verjetnostjo dana gramatika tvori izbrano enačbo.
    % Na tvorjenje enačbe z verjetnostno gramatiko lahko gledamo kot slučajni proces in računamo, s kakšno verjetnostjo dana gramatika tvori izbrano enačbo.
    Izkaže se, da je računanje verjetnosti neizračunljiv problem, za nekatere družine gramatik pa obstajajo matematično zanimive rešitve. 


\section*{Verjetnostne gramatike}
Naj bosta $N$ in $T$ poljubni disjunktni, neprazni, končni množici simbolov in naj bo v množici $N$ odlikovan začetni simbol $S \in N$. Naj bo $R \subseteq N \times (N\cup T)^*$  celovita relacija, ki vsakemu simbolu iz $N$ priredi vsaj eno besedo, sestavljeno iz simbolov v $N\cup T$. Tedaj četvercu $G = (N, T, S, R)$ rečemo kontekstno neodvisna gramatika. Simbolom iz  $N$ rečemo ne-končni, iz $T$ pa končni simboli.  Urejene pare iz $R$ imenujemo prepisovalna pravila. Par $(A, w) \in R$ pišemo kot ${A \to w \in R}$ in rečemo, da se $A$ prepiše v $w$. 

Z uporabo prepisovalnih pravil iz $R$ lahko v končnem številu korakov začetni simbol $S$ prepišemo v  besedo $w \in T^*$, sestavljeno le iz končnih simbolov. V tem primeru rečemo, da gramatika $G$ tvori $w$. Množico vseh besed, ki jih tvori gramatika $G$, označimo z $L(G)$.

            Verjetnostna gramatika je gramatika skupaj s  porazdelitvijo ${ P \colon R \to (0,1] }$, da za fiksen $A \in N$ velja  
             % Prepisovalnemu pravilu $A \to w$ pripada verjetnost $P(A \to w)$, da za fiksen $A$ velja 
            $
            \sum \limits_{A \to w \in R} P(A \to w) = 1
            $. Na tvorbo besed z verjetnostno gramatiko lahko gledamo kot na markovski proces in računamo verjetnost tvorbe. 
            % Na tvorbo besed lahko gledamo kot markovski proces. 
% Relacijo $\to$  razširimo na $(N\cup T)^*$. Za vsako besedo oblike $vAu \in (N\cup T)^*$ in prepisovalno pravilo $A \to w$ definiramo $vAu \to vwu$ in rečemo, da smo besedo $vAu$ s prepisovalnim pravilom $A \to w$ prepisali v $vwu$. Iz relacije $R$ tvorimo izpeljevalne verige oblike 
% $$
% S \to w_1 \to \dotsb \to w_n,
% $$
% kjer je $w_n \in T^*$ in na vsakem koraku uporabimo prepisovalno pravilo na prvem simbolu iz leve, ki je v $N$. Zaporedni členi izpeljevalne verige so torej oblike $w_i = v A u, w_{i+1} = vwu$, kjer smo besedo $w_i$ prepisali v $w_{i+1}$ s pravilom $A \to w$ in v besedi $v$ ni znakov iz $N$. Definiramo jezik gramatike $L(G) = \{w \in T^*\mid \text{obstaja izpeljevalna veriga oblike} S \to \dotsb \to w\}$. Rečemo, da gramatika $G$ tvori besede iz $L(G)$.



            
            % Na besedi $vAu \in (N\cup T)^*$ lahko uporabimo prepisovalno pravilo $A \to w$ in prepišemo $vAw \to vwu$ ter $P(vAu \to vwu) = P(A\to w)$.
            
            % $G$ \textbf{tvori} besedo $w \in T^*$, če $w$ dobimo z uporabo končno mnogo prepisovalnih pravil z začetkom na $S$.
            % Preslikavo $P$ razširimo na relacijo na besedah s predpisom $P(vAu \to vwu) = P(A \to w) $. Verjetnost verige tvorbe 
            % $$\tau \colon S=w_0 \to w_1 \to \dotsb \to w_m = w$$
            % definiramo kot  $P(\tau) = \prod 
            % \limits_{i=0}^{m-1}P(w_i \to w_{i+1})$. Besedo $w$ tvorimo z verjetnostjo 
            % $
            % P(w) = \sum \limits_{\tau \text{ izpeljevalna veriga } w}P(\tau).
            % $
            
            Množico $ \{A \to w_1, \dotsc , A \to w_n\}$  prepisovalnih pravil za $A$ ob dani porazdelitvi $P$ običajno podamo kot 
            $
            A \to \opcija{w_1}{P(A \to w_1)} \mid \dotsb \mid \opcija{w_n}{P(A \to w_n)}.
            $
            \paragraph{Primer}
            %
            %
            %\large{\textbf{Primer}}
            %\normalsize
            $G = (\{S\}, \{x, +\}, S, R)$ s prepisovalnima praviloma $S \to \opcija{S+x}{p}\mid \opcija{x}{1-p}$ tvori množico besed $L(G) = \{x, x+x, x+x+x, \dotsc \}$. Besedo $\underbrace{x + \dotsb + x}_{n \text{-krat}}$ krajše pišemo kot $nx$.
            Verjetnost, da tvorimo besedo  $nx$, je $P(nx) = (1-p)p^{n-1}$.
        \section*{Uporaba v simbolni regresiji}
            Algoritem za odkrivanje enačb ProGED \cite{proged} z gramatikami tvori različne oblike predpisov za izraze oblike $f(x_1, \dotsc, x_n, c)$, nato pa vsako pojavitev simbola $c$ v predpisu  z numerično optimizacijo nadomesti s tako konstanto, da se izraz čim bolj prilega podatkom. 
            %
% Omejimo se na gramatike, ki tvorijo matematične izraze s prostimi konstantami (ki jih zapišemo s simbolom $c$). V praksi nato vsak simbol $c$ posebej zamenjamo z nekim številom.
\paragraph{Primer}
                        $$
\begin{array}{rcl}
    E & \to & cV + E \mid c\\
    V & \to & xV \mid x
\end{array}
$$
Zgornja gramatika tvori polinome s konstantami oblike $cx^{r_1} + \dotsb + cx^{r_m} + c$. Algoritem izmed množice funkcij $ \{c_0x^{r_1} + \dotsb + c_{m-1}x^{r_m} + c_m \mid c_i \in \C\} $ izbere tisto, ki se podatkom najbolj prilega. Z vidika simbolne regresije lahko predpis, tvorjen z gramatiko, enačimo z množicami vseh funkcij, ki jih dobimo iz predpisa, če simbole $c$ nadomestimo s števili.

\subsection*{Formalizacija predpisa}
            % Posamezen izraz s konstantami zajema množico vseh funkcij, ki jih lahko predstavimo z izrazom, če simbole $c$ zamenjamo za števila.
            Zgornjo intuicijo povzamemo v formalni definiciji izraza.
            Naj bo $\F$ poljubna množica dovoljenih vrednosti konstant $c$, $D$ pa poljubna domena za spremenljivke $x_1, \dotsc, x_n$. Naj bo $G$  verjetnostna gramatika, ki tvori le besede oblike 
            $w =  w_1 c w_2 c \dotsm c w_{m+1}$ (kjer v členih $w_i$ ni znaka $c$) in za vsako izbiro konstant 
            $c_1, \dotsc , c_m \in \F$ beseda $ w_1 c_1 w_2 c_2 \dotsm c_m w_{m+1}$ predstavlja predpis za funkcijo 
            \begin{align*}
            \phi_w(c_1, \dotsc, c_m) \colon U & \longrightarrow D\\[-1ex]
            (x_1, \dotsc , x_n) & \longmapsto w_1 c_1 w_2 c_2 \dotsm c_m w_{m+1},
\end{align*}
kjer je $U \subseteq D^n$ maksimalna domena, da je $ \phi_w(c_1, \dotsc, c_m)$ še dobro definirana. Če je $D \in \{\R, \C\}$ dodatno privzamemo, da $ \phi_w(c_1, \dotsc, c_m)$ zvezno razširimo na vse robne točke domene $U$, kjer je to mogoče.


Na množici besed gramatike $G$ definiramo preslikavo 
                $$
    \Phi(w) = \{\phi_w(c_1, \dotsc, c_m) \mid c_1, \dotsc, c_m \in \F \}.
    $$  
    % kjer je $\F$ prej izbran prostor prostih konstant, funkcije pa so definirane na največji možni podmnožici izbrane domene (običajno gledamo funkcije nad $\R$).
    Na  $L(G)$ uvedemo ekvivalenčno relacijo    
    $$
    w \sim v \iff \Phi(w) = \Phi(v).
    $$ in preko nje definiramo  \textbf{prostor formalnih izrazov}  kot kvocient $L(G) /_\sim$.
    % Za poljubno gramatiko $G$, ki tvori matematične izraze s prostimi konstantami, definiramo \textbf{prostor formalnih izrazov} kot kvocient $L(G) /_\sim$ za relacijo na besedah 
    % $$
    % w \sim v \iff \Phi(w) = \Phi(v).
    % $$
            % \heading{\color{teal}Problem izračuna verjetnosti}
            \subsection*{Izračun verjetnosti}
            Iščemo algoritem, ki bi za poljubno gramatiko $G$ kot zgoraj in poljubno besedo $w \in L(G) $ izračunal $P([w]):= \sum \limits_{v \sim w} P(v)$. Izkaže se, da je splošen problem neizračunljiv \cite{pastetakekec}, obstajajo pa rešitve za manjše družine gramatik.
            % \subsection{Neizračunljivost}
            % Algoritem, ki bi rešil splošen problem izračuna verjetnosti, ne obstaja. Če bi, bi iz izračuna $P([v])$ za gramatiko $S  \to f [0.5]\mid 0 [0.5]$ za poljubno elementarno funkcijo $f$ preverili, če je povsod enaka $0$. Tak algoritem pa ne obstaja \cite{richardson}.        
Osnovna gramatika, ki jo uporablja ProGED, je podana s pravili 
            $$
\begin{array}{rcl}
    E & \to & \opcija{E+cV}{p} \mid \opcija{c}{1 -p}\\
    V & \to & \opcija{x_1}{q_1} \mid \dotsb \mid \opcija{x_n}{q_n}
\end{array}
$$
 in 
tvori linearne izraze oblike $w = c +cx_{r_1} + \dotsb + cx_{r_k} $. Velja enakost

\begin{align*}
    P([w]) &= \sum \limits_{I \subseteq \{1, \dotsc, k\}} (-1)^{|I|} \displaystyle \frac{1-p}{1-p\sum \limits_{i \in \{1, \dotsc, k\} \setminus I}q_{r_i}}
   \\
   &= \sum \limits_{i=k}^\infty (1-p)p^i  \left ( \sum_{\substack{l_1 + \dotsb + l_k = i \\ l_j \geq 1}}\binom{i}{l_1, \dotsc, l_k} q_{r_1}^{l_1} \dotsm q_{r_k}^{l_k} \right ).
\end{align*}

\renewcommand{\section}[2]{}%
\bibliographystyle{plain}
%\bibliographystyle{IEEEtran}
\bibliography{viri}

\end{document}
