%% This LaTeX-file was created by <jl> Tue Feb  3 23:42:09 1998
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}

John Langford 2/3/98

I find the notation used in theoretical learning to learn rather ad hoc and
cumbersome. There are too many versions \emph{h}, h, \( h_{i} \), H, \emph{H, \( \widehat{H} \),} etc..(hmm..
I really don't know how to make all the different h's in latex yet). The only
consistency I can find, is that the more esoteric the 'h', the more abstract
the concept it represents. I can't see a nice way to extend this notation into
the staged learning which interests me (learning to learn to ... to learn).
I've been trying to figure out a better notation, which I'll show below. The
notation draws from elements of GR and partial function application. I would
really like your input on what you think is good or bad about the notation. 

First note: an element in a range is specified by a lower case letter i.e. \( i \),
while the range is specified by an uppercase letter i.e. \( I \). GR's implicit notation
requires some plasticity of thought about the meaning of \( i \).

I think it's easiest to specify the language I'm thinking of by example.

\begin{itemize}
\item \( z:x\rightarrow y \) a labeled example
\item \( h:z\rightarrow [0,1] \) the loss of an hypothesis on a labeled example
\item \( z_{I} \) a vector of examples
\item \( z_{i} \) an element from a vector of examples
\item \( h_{K}:z_{_{I}}\rightarrow h \) a hypothesis set. This can also be though of (implicitly) as a function which
when given a vector of examples gives produces a hypothesis which when given
an example, produces a loss. In other words: \( h_{K}:z_{I}\rightarrow z\rightarrow [0,1] \) or \( h_{K}:z_{I}\rightarrow (z\rightarrow [0,1]) \)
\item \( h_{k} \) an element of a hypothesis set.
\item \( z_{IJ}:Z^{I^{J}} \) a vector of vector of examples. 
\item \( z_{ij} \) an element from a vector of vector of examples.
\item \( h_{KL}:z_{IJ}\rightarrow h_{K} \) a set of hypothesis sets. Or a set of hypothesis spaces. Or a function from
a vector of tasks to a hypothesis space.
\item \( h_{kl} \) an element of a vector of hypothesis vectors
\end{itemize}
Make sense? The only technical note is that I chose the innermost index to be
the least abstract (always a vector of examples) and the outermost index to
be most abstract (the vector of vector of ....).

Now here's some more radical extensions. 

First, function application:

\( h_{kl}z_{ij}=h_{kl}(z_{ij}) \) for some element in \( h_{kl} \) and some element in \( z_{ij} \). There is some trickery here,
because the notation \( h_{kl}z_{ij} \) is very suggestive that \( h_{kl} \) is dual to \( z_{ij} \) in the mathematical
sense. Does this seem legitimate to you? 

Next, the \( \delta _{k} \) operator

\begin{itemize}
\item \( h_{kl}z_{ij}\delta _{j}=\frac{1}{J}\sum _{j=1}^{J}h_{kl}(z_{ij}) \) = a hypothesis from each hypothesis space applied to some example in each
task space. This should correspond to your definition of \( h_{1}\bigoplus ...\bigoplus h_{J}(\overrightarrow{z}) \) in definition 5. 
\item \( h_{kl}z_{ij}\delta _{j}\delta _{i}=\frac{1}{I}\sum _{i=1}^{I}\frac{1}{J}\sum _{j=1}^{J}h_{kl}(z_{ij}) \) = the average loss on a vector of tasks of an \( h_{1}\bigoplus ...\bigoplus h_{J}(\overrightarrow{z}) \). This should correspond to
\( \hat{e}r_{Z}(h) \) in definition 5.
\end{itemize}
In general, \( \delta _{k} \) means do an empirically weighted sum over the index. 

It's also important to consider the true underlying distribution instead of
the empirical distribution. We can do this with another operator, \( d_{k} \). which is
essentially the integral version of \( \delta _{k} \). Examples:

\begin{itemize}
\item \( h_{kl}z_{ij}\delta _{j}d_{i} \) corresponds to \( er_{P}(h) \) in definition 5.
\item \( d_{P}(h,h')=|(h_{kl}-h_{kl}')z_{ij}\delta _{j}|d_{i} \) 
\end{itemize}
The Note that it is only valid to \( \delta _{k} \) or \( d_{k} \) where k ranges over example indexes
because we make no assumptions about the distribution of the hypotheses.

Do you see problems with this notation? Ambiguities which get introduced? The
notation seems like it is more extensible, but I haven't tried writing out a
proof in it. 

\end{document}
