tree_comm

tree_comm.md

How can human communicate better with computer systems?

Simple reference game

Suppose there are a finite set of messages $X$ expressing a finite set of meanings $Y$.

1. Nature picks the semantics $y \in Y$
2. Alice produce $x$ given $y$
3. Bob produce $y'$ given $x$
4. Receive reward if $y=y'$

In the standard machine learning setting, Alice uses a fixed distribution, and Bob is a learning algorithm. Suppose Alice use a fixed distribution $p(x|y)$, which might be inherently ambiguous. Bob has to learn $q(y|x)$ from samples. The regret is $$ \sum_t f(y_t, x_t, q_t) - \sum_t f(y_t, x_t, q) $$

where the expected loss $f(q, x, y) = E_{y' \sum_t f(y_t, x_t, q_t) - \sum_t f(y_t, x_t, q_t)\sim q(\cdot|x)}[1_{y \neq y'}]$. Consider the method where Bob maintains an empirical estimate and play $y' = \arg\max_y\hat{q}(y|x)$, where $$ \hat{q}(y|x) = \frac{\sum_{i=1}^{t-1} 1[y=y_i \land x=x_i]}{\sum_{i=1}^{t-1} 1[x=x_i]}. $$

If Alice also adapts, meaning that Alice is allowed to play $p_t$ in each round, and $x_t$ is sampled according to $p_t$. Note that Alice is not allowed to communicate all of $p_t$ to Bob, but merely a sample $x$. $$ \sum_t f(y_t, p_t, x_t, q_t) - \sum_t f(y_t, p, x_t, q) $$

Structured reference game

The game starts with a probabilistic context free grammar $G$ known to Alice, but unknown to Bob. Suppose that $G$ is a semantic grammar where each rule has the form $$ X \rightarrow Y_1 Y_2 \ldots Y_n : \lambda y_1 y_2 \ldots y_n. f(y_1, y_2, \ldots, y_n). $$

1. nature picks the semantics $y \sim S(G)$
2. Alice produces $x$ given $y$
3. Bob produces $y'$ given $x$
4. Receive reward if $y=y'$, Bob and Alice learn.

We use this as a model of human/computer communication, where Bob plays the role of a computer system, and Alice the human user. Alice does not know $G$, and thus does not know how to interpret $y$. On the other hand, Bob knows $G$ but does not know how to interpret $x$.

Adaptation

The static approach is to consider natural language as fixed and universal. This fixed language (such as English) is already capable of expressing any meanings. To communicate between the human and computer, the computer has to understand this existing language, and map it to its own action space.

Whenever the subject matter is outside of daily life, insisting on standard English can quickly become untenable:

In right-angled triangles the square on the side subtending the right angle is equal to the squares on the sides containing the right angle

In math and computer science, communication systems like formulas and programming languages are required to refer to new concepts and achieve the desired amount of precision. In most areas, some adaptation to the domain is required to achieve efficient communication, which results in domain specific concepts and conventions glued together by natural language. Some examples:

Alice knows a clique C in the graph, and Bob knows an independent set I in the graph. They want to know whether C and I share a common vertex or not.

I picked up a charge as well, a couple of blocks, a couple of steals, just being around the court and reliable for my teammates. Being able to clean glass, get my guys good looks where they are able to catch and shoot or catch it and lay it up, makes it a lot easier for me.

A grammar can be regarded as a device that enumerates the sentences of a language. We study a sequence of restrictions that limit grammars first to Turing machines, then to two types of system from which a phrase structure description of the generated language can be drawn, and finally to finite state Markov sources (finite automata).

Functional elucidation of causal genetic variants and elements requires precise genome editing technologies. The type II prokaryotic CRISPR (clustered regularly interspaced short palindromic repeats)/Cas adaptive immune system has been shown to facilitate RNA-guided site-specific DNA cleavage.

Perhaps the goal of communicating with computers in natural English is misguided as long as the grounding of the language is different from natural English.

Language