Skip to content

Instantly share code, notes, and snippets.

@sidaw
Last active March 14, 2018 18:26
Show Gist options
  • Save sidaw/af958c9b0f66529564e88de5b78f641a to your computer and use it in GitHub Desktop.
Save sidaw/af958c9b0f66529564e88de5b78f641a to your computer and use it in GitHub Desktop.
tree_comm

How can human communicate better with computer systems?

Simple reference game

Suppose there are a finite set of messages XXX expressing a finite set of meanings YYY.

  1. Nature picks the semantics y∈Yy \in YyY
  2. Alice produce xxx given yyy
  3. Bob produce y′y'y given xxx
  4. Receive reward if y=y′y=y'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)p(x|y)p(xy), which might be inherently ambiguous. Bob has to learn q(y∣x)q(y|x)q(yx) from samples. The regret is

∑tf(qt,xt,yt)−∑tf(q,xt,yt) \sum_t f(q_t, x_t, y_t) - \sum_t f(q, x_t, y_t) tf(qt,xt,yt)tf(q,xt,yt)
where the expected loss f(q,x,y)=Ey′∼q(⋅∣x)[1y≠y′]f(q, x, y) = E_{y' \sim q(\cdot|x)}[1_{y \neq y'}]f(q,x,y)=Eyq(x)[1yy].
Consider the method where Bob maintains an empirical estimate and play y′=arg⁡max⁡yq^(y∣x)y' = \arg\max_y\hat{q}(y|x)y=argmaxyq^(yx), where
q^(y∣x)=∑i=1t−11[y=yi∧x=xi]∑i=1t−11[x=xi]. \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]}. q^(yx)=i=1t11[x=xi]i=1t11[y=yix=xi].

Structured reference game

The game starts with a probabilistic context free grammar GGG known to Alice, but unknown to Bob. Suppose that GGG is a semantic grammar where each rule has the form
X→Y1Y2…Yn:λy1y2…yn.f(y1,y2,…,yn). 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). XY1Y2Yn:λy1y2yn.f(y1,y2,,yn).

  1. nature picks the semantics y∼S(G)y \sim S(G)yS(G)
  2. Alice produces xxx given yyy
  3. Bob produces y′y'y given xxx
  4. Receive reward if y=y′y=y'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 GGG, and thus does not know how to interpret yyy. On the other hand, Bob knows GGG but does not know how to interpret xxx.

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment