% 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}