# Improved Inference of Human Intent by Combining Plan Recognition and
Language Feedback

Ifrah Idrees1, Tian Yun1, Naveen Sharma1, Yunxin Deng1, Nakul Gopalan2, George
Konidaris1, Stefanie Tellex1
1Brown University, USA, 2Arizona State University, USA

###### Abstract

Conversational assistive robots can aid people, especially those with
cognitive impairments, to accomplish various tasks such as cooking meals,
performing exercises, or operating machines. However, to interact with people
effectively, robots must recognize human plans and goals from noisy
observations of human actions, even when the user acts sub-optimally. Previous
works on Plan and Goal Recognition (PGR) as planning have used hierarchical
task networks (HTN) to model the actor/human. However, these techniques are
insufficient as they do not have user engagement via natural modes of
interaction such as language. Moreover, they have no mechanisms to let users,
especially those with cognitive impairments, know of a deviation from their
original plan or about any sub-optimal actions taken towards their goal. We
propose a novel framework for plan and goal recognition in partially
observable domains—Dialogue for Goal Recognition (D4GR) enabling a robot to
rectify its belief in human progress by asking clarification questions about
noisy sensor data and sub-optimal human actions. We evaluate the performance
of D4GR over two simulated domains—kitchen and blocks domain. With language
feedback and the world state information in a hierarchical task model, we show
that D4GR framework for the highest sensor noise performs 1% better than HTN
in goal accuracy in both domains. For plan accuracy, D4GR outperforms by 4% in
the kitchen domain and 2% in the blocks domain in comparison to HTN. The
ALWAYS-ASK oracle outperforms our policy by 3% in goal recognition and 7% in
plan recognition. D4GR does so by asking 68% fewer questions than an oracle
baseline. We also demonstrate a real-world robot scenario in the kitchen
domain, validating the improved plan and goal recognition of D4GR in a
realistic setting.

Figure 1: Kuri robot performing human intent (plan and goal) recognition. The
human, while making coffee, starts a new goal of washing hands. However, the
human forgets to use soap after turning on the faucet and instead turns off
the faucet. The robot (with access to the Hierarchical Task Network
representation of goals) observes that the current world observations do not
progress the previous goal and also cannot lead to a new goal completion and
hence uses D4GR to ask a clarification question. Based on language feedback,
the robot reduces its confidence in the goal wash hands and suggests the next
action as using soap to complete one of the most plausible goals of washing
hands.

##  I Introduction

People with cognitive impairments, such as dementia, often struggle with
focusing on everyday tasks and have limited attention spans. Efforts to assist
people in tracking task progress have involved various approaches, including
modeling tasks as a hierarchical task network (HTN), using a Bayesian Hidden
Markov Model, or employing a Partially Observable Markov Decision Process
(POMDP) [6, 19]. However, previous approaches focus on observing users rather
than engaging them in an interaction. Our work aims to develop a model for a
robot capable of assisting people complete tasks with language-based
interactions; even when the users perform sub-optimal actions or switch
between multiple goals. Our robot tracks the task progress using observations
and question-asking using natural language. Such a robot can also benefit an
operator building a machine, a child with autism doing their homework, or a
child learning to do chores.

Inferring the goals and intents of the human requires plan and goal
recognition (PGR) using noisy evidence from action execution that can be done
efficiently using planning techniques [11]. One key challenge in human intent
recognition as a PGR problem is that the robot has partial observability of
human intentions. This is compounded by noisy sensors that also create partial
observability of the environment. Modeling human progress during hierarchical
tasks has been done using Hierarchical Task Networks (HTNs) [19, 7]. However,
these recognition techniques again do not engage with the users and assume
that the user acts optimally. Moreover, incorporating clarification questions
and language utterance spoken by humans in PGR is challenging because of the
huge space of language observations. The existing solution to this problem is
heuristics [16, 5, 10], which are prone to fail as the tasks and environment
sensors become complex and noisy.

The main contribution of our paper is a novel formulation that combines
expressive and hierarchical task representation of HTNs to represent the human
mental states with the sequential decision-making capabilities of a Partially
Observable Markov Decision Process, in our Dialogue for Goal Recognition
(D4GR). Our method keeps track of the environment, user state and dialogue
history internally to perform PGR and guide in successful task completion.

POMDPs can model the uncertainty the robot faces as it performs intent
recognitions and enables the robot to ask information-seeking questions.
However, POMDP planners traditionally do not decide the relevance of the state
using the task network at each sequential time step. Further, the HTNs have no
notion of rewards to generate a sequence of actions to maximize the agent’s
utility. To solve these challenges, we assume that the user is a planner with
goals and subgoals that are represented hierarchically. Moreover, the robot is
a POMDP planner performing long-horizon dialogue policy planning. This enables
the robot to reason about asking meaningful questions in ambiguous settings,
such as the user switching goals during multiple concurrent tasks and also
performing sub-optimal actions. Using this information, the robot can better
recognize human intents based on the human actions estimated from noisy
sensors and their language feedback. This model also explicitly allows for
sub-optimal plans by a human user, which D4GR can detect.

We evaluate the usefulness of D4GR by measuring the improved accuracy in PGR
and comparing the planning time and number of questions asked to two state-of-
the-art baselines in the simulated domain developed by Wang and Hoey [19]. Our
system is able to more accurately infer human intents than these baselines
using information gathered from a language without asking unnecessary
questions. We run 880 trials for varying sensor noise levels where the
simulated human tries to complete a combination of tasks in two domains - the
kitchen and blocks domain. In the kitchen domain, there are three tasks -
washing hands, making a cup of tea, and making a cup of coffee while in the
blocks domain, tasks include an assortment of stacking letters to make 4-7
lettered words - $rote$, $tone$, $tune$, $hawk$, $capstone$. With language
feedback and the world state information in a hierarchical task model, we show
that our D4GR framework outperforms HTN by 4% on plan accuracy in the kitchen
domain and 2% in the blocks domain. In goal accuracy, for the highest sensor
noise, our D4GR performs 1% better than HTN in both kitchen and block domains.
We also deployed our algorithm on a social robot Kuri as a demonstration of a
socially intelligent robot helping confused users complete tasks. In this
demonstration, Kuri performs improved PGR by asking clarification questions
and reducing uncertainty for a challenging scenario where the user switches
between multiple concurrent goals (e.g., washing hands and making coffee) and
acts sub-optimally in the kitchen domain. The demo can be found here:
https://youtu.be/Om91zBiDDEY. An example sequence of the user and robot
interaction can be seen in Fig-1.

##  II Related Work

Plan and Goal Recognition as Planning: The first work on PGR as planning was
introduced by Ramírez and Geffner [15]. This research leverages classical
planning systems to solve PGR problems. Wang and Hoey [19] proposed an
algorithm for PGR based on hierarchical task network [4] that handles noisy
sensors and sub-optimality in human actions. However, their approach detects
mistakes heuristically using a manually defined threshold while performing a
one-step look ahead without long-horizon planning. Additionally, it lacks
dialog conversation to improve belief in the actor’s progress in the task.
Another relevant work that does not engage with the user is by Zhi-Xuan et al.
[22], which performs online Bayesian goal inference by modeling the agent as a
boundedly rational planning agent but is not designed and evaluated for
multiple concurrent hierarchical goals. Mirsky et al. [12] presents favorable
results for the hypothesis that feedback from the acting agent can improve
plan (goal and step) recognition, but their paper performs goal recognition as
reinforcement learning and has a fixed language policy without exploring the
observer’s strategy for asking clarification question. Höller et al. [7]
employs HTN Planning for PGR but struggles with sub-optimal actions and noisy
sensors, focusing on handling missing sensor observations instead.

Context-aware Social Robotics: In the past, research in social robotics has
focused on developing non-verbal social behaviors for robots to assist the
elderly [5, 10] during task completion. These works place less emphasis on
incorporating language feedback/observations for user intent inference.
Further, the robot dialog policy (if involved) does not account for the
environmental context, dialog context, and user modeling. Research in situated
human-robot dialog by Bohus and Horvitz [1], Thomason et al. [18], Idrees et
al. [8] grounds speech response in the environment but asks clarification
questions heuristically, using rule-based/greedy approaches and without using
a decision-theoretic framework. Such heuristics are prone to failure as the
tasks get complex and the environment sensors become complex and noisy.

POMDP-based Collaborative Dialog: Partially observable Markov decision
processes (POMDPs) provide a rich framework for planning under uncertainty.
They excel in optimizing agents’ actions over long horizons in complex
environments despite incomplete state information from noisy sensors [6].
Young et al. [21] and Doshi and Roy [3] built POMDP-based dialog systems.
However, these only use language as observations, not world observations, for
belief updates to choose actions with the highest reward accumulation. Whitney
et al. [20] fuses language and world observations for object fetching tasks
but does not model the user’s mental state during multi-step task completion.
The closest work to ours is by Hoey et al. [6], featuring an engaging
assistant that incorporates only world observations and not language
observations for multi-step tasks. They can infer human actions and
psychological states through hand and towel tracking but can not handle
multiple and concurrent tasks and backtracking and are limited to hand
washing. Research has recently focused on using reinforcement learning in a
collaborative dialog for interactive task learning Chai et al. [2]. However,
these works require an existing dataset for offline learning, while our
planning approach doesn’t necessitate data collection or learning.

##  III Technical Approach

Figure 2: Hierarchical Task Network for two of our tasks - washing hands, and
making tea

Given the sensor measurements $O_{w}$ of the world state $W$, an assistive
robot needs to infer the probabilities of the hidden user intent—the person’s
current goal $G$ and the current primitive human action $\alpha$. Partial
observability of the latent user intent and noise in the sensor observations
impact accurate inference of $G$, $W$, and $\alpha$ at every sequence of human
actions. We infer the probability distribution of the hidden states $G$, $W$,
and $\alpha$ using HTN planning to generate feasible plans for the human-given
predefined tasks similar to work of Wang and Hoey [19]. With the ability to
ask clarification questions, the robot actively improves the inference of the
latent states. The user’s response in the form of language observations,
$o_{l}$, gives the agent additional information about their task. With our
D4GR framework, the robot decides when to ask clarification questions and
which user action to inquire about, based on information gathered from both
the sensors and language. Our framework avoids asking unnecessary questions
and balances between information-gathering actions, like asking questions, and
goal-inducing actions, such as providing the correct next step.

###  III-A POMDP Definition

We model our PGR problem as a POMDP [9] planning problem, generating an
approximately optimal action policy for the robot. Formally, a POMDP is
defined as a tuple ($S,A,T,R,\Omega,O,\gamma,b_{0}$) where $S$ is the state
space, $A$ is a the action space, $T$ is the transition probability, $R$ is
the reward function, $\Omega$ is a set of observations, $O$ defines an
observation probability and $\gamma$ is the discount factor. Since $s_{t}$ is
not known exactly, the POMDP model updates, at each timestep, the probability
distribution over all possible states (belief state $b_{t}$). The POMDP agent
uses a planner to generate an optimal policy for the robot’s action, which in
this case is the communication with the human user.

###  III-B D4GR Formulation

Figure 3: Influence diagram for D4GR.

We define a novel model, Dialogue 4for Goal Recognition, a Partially
Observable Markov Decision Process (D4GR) that combines the goal and plan
recognition components as described by Wang and Hoey [19] with the POMDP
formalism to allow robots to take action in the environment through dialogue
for improved PGR. For efficient human intent recognition and estimation of
optimal action policy, our D4GR must handle the large space of the world and
language observations. Our formulation leverages the hierarchical task
structure of HTN and assumes independent assumptions between state variables
set of goals $G$, human user action $\alpha$, and world state $W$ for
efficient belief update. Our D4GR has the following components:
($S,A,T,R,\Omega,O,\gamma;b_{0}$).

State (S):  The state, $s_{t}\in S$, consists of a tuple of the user’s mental
state, $M_{t}$, and the world state, $W_{t}$, along with information needed to
track the dialog state. We represent the user mental state using HTNs. We
assume access to the HTN’s fixed knowledge graph $TaskNet$ for the tasks,
where the root node(s) represent the high-level tasks/goals $G$ that the human
can do. The internal nodes are sub-tasks that can be decomposed into leaf
nodes depicting primitive human actions. $\alpha$ denotes the current
primitive human action. We model the user’s mental state $M$ represented by
$G$ and $\alpha$. The partial $TaskNet$ for our kitchen domain is shown in
Fig-2.

The world state $W_{t}$ combines the states of world smart sensors $ss_{t}$
and the attributes of objects involved in the task $att_{t}$, such as dryness
of the hand, state of the faucet, etc. The dialog state variable $q_{t}$
stores the latest primitive human action referenced by the robot in its
clarification question. Thus, the state $s_{t}$ can be factored into the
following components:$s_{t}=(M_{t},q_{t},W_{t},)$ where $W_{t}$ =
$(ss_{t},att_{t})$, $M_{t}=(G_{t},\alpha_{t})$. Here
$G_{t},\alpha_{t},att_{t},ss_{t}$ are the hidden variables, while $q_{t}$ is
the known variables, hence making this a Mixed Observable Markov Decision
Process (MOMDP) [13]. The influence diagram can be seen in Fig-3.

Action(A) includes the actions of the agent. The robot for this research can
perform the following predefined language-based actions - 1) $Wait$: does
nothing but advances the time step. 2) $Ask\\{argmax(\alpha)\\}$: The robot
asks a clarification question about the primitive action $\alpha$ with the
highest belief. The question template used is: “I believe that you just did
action $(\alpha_{i})$, is this correct?”. 3) $inform\\_next\\_instruction$:
informs the next action that the user should perform at the current timestep
based on the current belief. This action is chosen based on a fixed policy and
is executed when the user provides a negative language response to the robot’s
clarification question.

Observations ($\Omega$) encompass both the user’s language ($o_{l}$) and
observations about the world state ($o_{w}$). $o_{w}$ includes discrete
observations of the world smart sensor’s state $ss_{t}$ and the attributes of
the task-related objects $att_{t}$ such as _hand_dry == true, faucet_on ==
false_ , etc. These observations are binary for the states in $W_{t}$, so the
faucet can only be on or off. The language observations are natural language
responses.

Observational Model ($O$):  The robot needs a model of $p(o|s)$ $=$
$p(o_{l},o_{w}|s)$ to update its belief. Most of the complexity of our model
is captured in this observation model and belief update defined in the sec-
III-C.

Transition Model ($T$) : $T(s,a,s^{\prime})\equiv p(s_{t+1}|s_{t},a_{t})$. Our
stochastic transition function is factorized as shown in Eq-1, following a
similar approach to Wang and Hoey [19]. We factor our mental model $M_{t}$
into $G_{t}$ and $\alpha_{t}$. Additionally, we assume that the last question
asked, $q_{t}$, is independent of $G$, $\alpha$, and $W$.

$\displaystyle\tiny p(s_{t+1}|s_{t},a_{t})$
$\displaystyle=p(G_{t+1}|W_{t+1},G_{t})\times
p(W_{t+1}|W_{t},\alpha_{i,t+1})\times$ $\displaystyle\qquad
p(\alpha_{t+1}|W_{t},G_{t})\times p(q_{t+1}|q_{t},a).$ (1)

In Eq-1, we assume that $q_{t}$ changes deterministically from null to
$max{(\alpha_{t})}$ after the robot asks a clarifying question. Further, $G$
is deterministically carried forward to the next time step.

$\displaystyle p(q_{i,t+1}|q_{i,t},a_{t})$ $\displaystyle\qquad=$
$\displaystyle\begin{cases}1\text{ for }\tiny{max(\alpha)}\quad else\quad
0,&\text{if }a\neq NULL\\\ 1\text{ for }q_{i,t},\quad else\quad
0&a_{t}==NULL.\end{cases}$

Reward $(R(s,a))$ We provide a positive reward (5) for asking a clarifying
question when the user is doing the wrong or suboptimal lowest primitive step.
A negative reward ($-5$) for asking a clarifying question when the human user
is doing the correct primitive step or when the agent asks a question about a
wrong primitive action. Thus, doing nothing accumulates zero rewards until the
right question is asked, while not asking a question or asking a wrong one
results in a penalty.

###  III-C Belief Update for Goal Recognition and Planning

Figure 4: Results for Top1 Goal Accuracy versus Sensor Reliability for the two
domains kitchen and block

Our belief update performs human intent recognition by maintaining a belief
over the hidden user’s mental state $M_{t}=(G_{t},\alpha_{t})$ and the world
state $W_{t}$. The actions executed by the user produce an observation of the
world state $o_{w}$ indicating the change in the world state $W_{t}$. The user
can also provide speech/language feedback $o_{l}$ in response to the
clarification question asked. We classify the intent of each sentence into
positive or negative feedback using the bag of words approach. Negative
responses $r_{n}$ include { ‘no’, ‘nope’, ‘other’, ‘not’ } while positive
responses $r_{p}$ include the words { ‘yes’, ‘yeah’, ‘sure’, ‘yup’ }. Further,
our world sensor noise model generates the correct sensor state with
probability $sr$ and the incorrect sensor state with $1-sr$. We adopt the
noise model for the sensor described by Wang and Hoey [19].

The observation model can be further expanded and approximated as follows:

$\displaystyle p(o_{t}|s_{t};a_{t-1})\propto
p(s_{t}|o_{t},a_{t-1})*p(o_{t}|a_{t-1}).$ (2)

Overall, the probability of $s_{t}$ given $o_{t}$ and $a_{t-1}$ can be
factored into the world observation model and language observation model in
Eq-3. We assume that the world observation $o_{w,t}$ solely provides
information about the $W$ and $\alpha$. Meanwhile, the language observation is
relevant to the human action $\alpha$, the last question asked $q_{t}$,
subsequently affecting the goal.

$\displaystyle
p(s_{t}|o_{t},a_{t-1})\propto\underbrace{p(G_{t}|W_{t})*p(W_{t}|o_{w,t})*p(\alpha_{t}|o_{w,t})*p(o_{w,t})\rule[-5.0pt]{0.0pt}{5.0pt}}_{\mbox{world
observational model}}$
$\displaystyle*\underbrace{p(\alpha_{t},q_{t}|o_{l,t})*p(o_{l,t})*p(q_{t}|a_{t-1})\rule[-5.0pt]{0.0pt}{5.0pt}}_{\mbox{language
observational model}}.$ (3)

For both the world and primitive action belief update in eq-3, the components
$p(W_{t}|o_{w,t})$ and $p(\alpha_{t}|o_{w,t})$ are derived from Wang and Hoey
[19]. The Bayesian update is as follows:

$\displaystyle p(\alpha_{t}|o_{w,t})\propto\sum_{w_{t-1}\in
W_{t-1}}\sum_{w_{t}\in W_{t}}p(\alpha_{t},o_{w,t},w_{t-1},w_{t}),$ (4)
$\displaystyle p(W_{t}|o_{w,t})=\sum_{w_{t-1}\in
W_{t-1}}\sum_{\alpha_{i,t}\in\alpha_{t}}p(\alpha_{i,t},o_{w,t},w_{t-1},w_{t}).$
(5)

We adopt the proposed algorithm for goal recognition, $p(G_{t}|W_{t})$ in Wang
and Hoey [19]. The algorithm maintains a goal belief distribution by
generating a probabilistic explanation set - $ExplaSet$. Each $expla\in
Explaset$ uses HTN planning to explain the observations so far. The
probability of each goal $g_{i}$ in $G$ given the world state is the sum of
probabilities of $expla\in ExplaSet$ whose $PredictedGoal$ == $g_{i}$. Our
algorithm reweighs primitive actions probabilities based on the language
observational model described below, influencing the world belief update
according to Eq-5 and, consequently, the goal recognition update.

The derivation of the language observational model is:

$\displaystyle p(\alpha_{t},q_{t}|o_{l,t})*p(o_{l,t})\propto
p(o_{l,t}|\alpha_{t},q_{t}).$ (6)

We adopt a bag-of-words approach as our POMDP’s observational model instead of
utilizing a large language model (LLM) like GPT3. LLMs are not inherently
grounded. Our model explicitly establishes a connection between sensor
information and semantics through a transition model in the POMDP. Although
LLMs could be incorporated for intent classification using the right prompt,
we did not pursue this direction as it falls outside the focus of our paper.

To estimate the effect of the language observation $o_{l}$ on $\alpha$ and
$q$, we calculate $p(o_{l,t}|\alpha_{t},q_{t})$. For this, we consider three
possibilities for the state: If the highest belief primitive action
$\alpha_{max,t}$ is the same as the question asked, then the user is likely to
respond with positive/confirmation feedback. The opposite is true if
$\alpha_{max,t}\neq q_{t}$. If $q_{t}=Null$, then no question has been asked,
so both types of responses are equally likely. The mathematical representation
of $p(o_{l,t}|\alpha_{t},q_{t})$. is governed by the following conditional
probability table:

| $p(o_{l,t}=Yes)$ | $p(o_{l,t}=No)$
---|---|---
$\alpha_{max,t}=q_{t}$ | $0.99$ | $0.01$
$\alpha_{max,t}\neq q_{t}$ | $0.01$ | $0.99$
$q_{t}=Null$ | $0.5$ | $0.5$

TABLE I: Conditional Probability for $p(o_{l,t+1}|\alpha_{t},q_{t})$

At each time step as the human performs an action, we solve the MOMDP using
the POUCT solver [17] to approximate the optimal policy for the robot’s
communication with the human. The observational model is then employed to
update the robot’s belief of user’s mental state $M=\\{G,\alpha\\}$.

##  IV Evaluation

Figure 5: Results for Top1 Plan Accuracy versus Sensor Reliability for the two
domains kitchen and block

Our evaluation aims to test the hypothesis that our hierarchical decision-
theoretic framework D4GR improves 1) the accuracy of goal recognition and plan
recognition of human activity and 2) the robot’s ability to guide the person
towards task success. We evaluate the enhanced performance of our algorithm by
measuring the accuracy of goal recognition and prediction of the next human
action, also referred to as plan recognition, at every time step. We also
measure the planning time, the cumulative expected return, and the number of
clarification questions asked for completing the tasks by D4GR and compare it
against the three presented methods in simulation. We also perform a robot
demonstration of D4GR for the scenario where the human switches between
washing hand and making tea tasks.

We use the simulation environment introduced by Wang and Hoey [19] for our
experiments. The simulator models real environment state changes that result
from the primitive actions specified in the HTN for the virtual human. In the
simulator, 44 binary virtual sensors are observing the world state. Some of
the examples include sensors for $hand\\_dry,faucet\\_on,block\\_picked\\_up$.
For our experiments, we vary sensor reliability from 99% to 80%.

###  IV-A Domain and Experiment Test Cases

We test our algorithm in two domains: a block domain and a kitchen domain. The
Knowledge Base, $TaskNet$ of the HTN for the kitchen has three goals: wash
hands, make tea, and make coffee. and the block domain has five goals of
stacking blocks to make words with varying lengths of 4 to 7. The five goals
of our block domain are $rote$, $tone$, $tune$, $hawk$, and $capstone$.  The
two domains differ in their HTN planning structure, as the block’s domain has
higher goals (root nodes) but a shorter tree depth than the kitchen domain.
Such a setup allows us to explore the effect of HTN structure on goal and plan
recognition performance. We evaluate the performance of our algorithm over
four categories of test case scenarios:

Single Goal & Correct Steps: Captures scenarios where the human always
executes a correct action sequence for achieving a single goal.

Multiple Goals & Correct Steps: The person works on multiple goals
simultaneously by switching back and forth,

Single Goal & Wrong Steps: A human has a single goal but can execute wrong
steps affecting progress toward the goal.

Multiple Goals & Wrong Steps: The human moves back and forth between goals and
executes wrong actions.

The easiest case is Single Goal & Correct Steps, and the hardest is Multiple
Goals & Wrong Steps.

###  IV-B Baselines:

We compare D4GR’s performance in simulation with three other methods. Our
first baseline is HTN, a previous method of HTN-based goal recognition
introduced by Wang and Hoey [19]. This method passively incorporates partially
observable world observations for PGR without engaging with the user. Our
second method is ALWAYS-ASK which acts as an oracle that always asks the
correct clarification question and uses the language feedback for the belief
update of D4GR. This baseline always has the highest goal and step recognition
accuracy but receives a lower reward because it asks unnecessary questions.
Our third baseline is SIPS111The SIPS baseline is adopted from the code
repository cited in Zhi-Xuan et al. [22] and uses their default setting:
static goal transition. introduced by Zhi-Xuan et al. [22]. This algorithm is
not equipped to handle hierarchical nature of goals.

###  IV-C Metric Definitions:

We measure 1) Top 1 Accuracy for Goal recognition, 2) Accuracy for Plan
Recognition similar to Wang and Hoey [19] averaged over all timesteps. These
metrics measure the accuracy of our belief update. To evaluate our POMDP
formulation, we also measure the planning time taken: runtime averaged over
the steps, the cumulative reward for the whole human action sequence, and the
number of questions asked averaged over trials.

##  V Results

Our proposed algorithm aims to improve the capability of the robot for goal
and plan recognition. The performance of D4GR depends on how accurately our
cognitive assistive robot estimates the belief states for the human mental
model $M_{t}$: the likelihood of goals $G$ and the human actions $\alpha$ at
each simulated step. The ground truth of each human action’s $\alpha$ given
the goal $G$ can be obtained from the knowledge base.

###  V-A Exp 1 - Goal Accuracy Performance

|  |  Runtime (s) $\downarrow$ |  Cumulative Expected Return $\uparrow$ |  Question Frequency $\downarrow$ |  |  |  |  |  |  |  |
---|---|---|---|---|---|---|---|---|---|---|---|---
Domain | Method | 0.8 | 0.9 | 0.95 | 0.99 | 0.8 | 0.9 | 0.95 | 0.99 | 0.8 | 0.9 | 0.95 | 0.99 |  |  |  |  |  |  |  |
| ALWAYS-ASK | 2.085 | 1.869 | 1.563 | 1.367 | -37.253 | -62.769 | -69.323 | -73.569 | 1.000 | 1.000 | 1.000 | 1.000 |  |  |  |  |  |  |  |
| D4GR | 28.750 | 20.445 | 18.814 | 17.084 | -26.056 | -24.656 | -23.014 | -23.989 | 0.297 | 0.318 | 0.325 | 0.358 |  |  |  |  |  |  |  |
| HTN | 9.056 | 1.524 | 1.371 | 1.040 |  |  |  |  | 0.000 | 0.000 | 0.000 | 0.000 |  |  |  |  |  |  |  |
Block | SIPS | 43.173 | 41.615 | 40.654 | 40.934 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| ALWAYS-ASK | 0.484 | 0.425 | 0.407 | 0.343 | -41.848 | -55.593 | -62.342 | -73.265 | 1.000 | 1.000 | 1.000 | 1.000 |  |  |  |  |  |  |  |
| D4GR | 13.912 | 13.439 | 13.572 | 11.384 | -24.527 | -26.542 | -26.399 | -21.437 | 0.312 | 0.317 | 0.316 | 0.296 |  |  |  |  |  |  |  |
Kitchen | HTN | 0.415 | 0.380 | 0.391 | 0.349 |  |  |  |  | 0.000 | 0.000 | 0.000 | 0.000 |  |  |  |  |  |  |  |
TABLE II: Trend in Questions Asked, Rewards Accumulated and Runtime (Sensor
reliability varies from 80% to 99%)

In Fig-4, we present results for the average goal accuracies of D4GR and
compare them with the baselines over varying sensor reliability and test case
categories. The reason for choosing the sensor reliability range from [0.8 to
0.99] is because most of the deep-learned vision and human action detectors
have similar average accuracy [14]. Overall, as the sensor reliability
decreases, the accuracy performance of HTN-based methods (ALWAYS-ASK, D4GR,
HTN) suffers. The oracle baseline, ALWAYS-ASK, always has the highest goal
accuracy. Even at lower sensor reliabilities (higher sensor noise), D4GR’s
accuracy remains higher than HTN in all experiment categories by 1% on average
in both domains. This trend indicates that even when the sensor’s
observational model fails, D4GR can better predict the belief states than HTN.
The SIPS method did not generate functional plans for our kitchen domain even
when the input specification was correct. Their particle filter algorithm
could not find feasible plans for the goals. Hence, presenting the results in
the blocks domain. Compared to the SIPS baseline, our method is 30 % better in
the blocks domain. We significantly outperform the SIPS baseline in the
multiple goals scenario by almost 43% because SIPS does not handle the
hierarchical nature of goals. The problem categories with single goals
(correct steps & wrong steps) have the best performance for the lowest sensor
reliability. We see D4GR performance boost by 2.8% in the kitchen domain and
1.4% in the blocks domain as compared to HTN. The Oracle, on average, is 6.3%
more accurate than the HTN baseline in this category. Our D4GR improves
accuracy by inferring when and what to ask a question rather than always
asking.

###  V-B Exp 2 - Plan Accuracy Performance

Similar to goal accuracy, we plot the planning accuracy for D4GR and compare
it with the baselines for varying sensor noise in Fig-5. Our algorithm overall
is 3% more accurate than HTN in both domains. For the lowest sensor
reliabilities, D4GR is 4% better than HTN in the kitchen domain and 2% better
than HTN in the block domain. For the multiple goal scenarios (correct and
wrong steps), D4GR performs the best with an accuracy improvement of 2.7% in
the kitchen domain and 2.3% in the block domain.

###  V-C Exp 3 - Trend in Questions Asked, Rewards Accumulated and Runtime:

Our proposed algorithm aims to improve the PGR capabilities of the agent by
enabling the robot to engage with the users and ask for language feedback. One
performance measure is the number of helpful clarification questions asked
with varying sensor reliabilities in Table-II. When the environment and human
actions are unambiguous (sensor reliability is high and/or the human is
performing correct actions), D4GR enables the robot to intelligently infer
that it does not need to ask lots of questions. At sensor reliability 0.99,
D4GR still asks questions because users can do sub-optimal actions leading to
ambiguity. Overall the agent asks questions 32.4% and 31% of the time in the
block and kitchen domains respectively. When compared over varying sensor
noise, the change in the number of questions asked is insignificant; the
numbers lie within the same standard deviation.

Further, asking a large number of clarification questions, especially if they
are not relevant to the current progress of the task, takes more computing
resources since planning will have to be done at every timestep. This effect
is measured by the runtime and the reward accumulated by D4GR. Our reward
function penalizes asking a lot of questions, especially when they reference
an irrelevant human action. Our results show that D4GR takes more planning
time per step as compared to ALWAYS-ASK and HTN but is 48% faster than SIPS.
All these measurements are done on a machine with 31 GB RAM, Intel® Core™
i7-9750H CPU @ 2.60GHz × 12. The code was run single-threaded. D4GR takes more
time than HTN but enables accuracy performance boost as noted in previous
sections, Sec-V-A and Section-V-B. Further, D4GR accumulates a higher
reward/lower penalty as compared to ALWAYS-ASK by 58% in both domains
highlighting that D4GR does not ask unnecessary questions.

###  V-D Robot Demonstration

We performed a robot demonstration to highlight the feasibility of D4GR in the
real world. The Kuri robot was used primarily for the demo due to its audio
transcription capability. The demonstration consisted of a human performing
two interleaving tasks in a kitchen while the Kuri robot observed the actions
performed and engaged with the user using the D4GR algorithm. The human begins
with making coffee and then moves to wash their hands. Unlike HTN, which
struggled to recognize the change in goal, D4GR correctly identified both
goals. The demonstration simulated sensor reliability at 0.8 using an oracle
and sensor noise model. Kuri used D4GR to intelligently infer when to ask a
question and what to ask and is able to perform goal recognition and planning
correctly. In the case of negative feedback from humans, Kuri offers its
predicted correct step to the human.

##  VI Discussion and Future Work

Our deployed algorithm D4GR shows improved accuracy for goal and plan
recognition than the baseline $HTN$ and $SIPS$. It does so while asking fewer
questions than the ALWAYS-ASK oracle policy. Our deployed robot with D4GR
performs real-time communication, as demonstrated. The time taken for online
planning is influenced by two critical parameters of the POMDP solver: 1) $d$,
representing the finite depth of the probabilistic decision tree constructed
with state-action pairs, and 2) $n$, the finite number of observations sampled
from each node. Increasing $d$ and $n$ enhances the solver’s accuracy and
increases runtime. To achieve real-time communication, we conducted empirical
experiments and determined that setting $d=19$ and $n=6$ provided appropriate
action choices within a reasonable time.

Our algorithm shows promising improvements in PGR accuracy, although it comes
with increased runtime compared to HTN. Our algorithm is designed to assist
users with cognitive impairment in their daily tasks, focusing on non-time-
critical activities. By providing delayed feedback, our social assistive robot
increases the likelihood of users learning from mistakes and avoiding
continuous repetition of errors compared to using HTN. We can reduce runtime
further by retaining only the highest probable explanation sets, denoted as
$ExplaSet$ in HTN planning. However, this impacts the PGR accuracy since
$ExplaSet$ with multiple goals during initial steps can get pruned due to
their lower probabilities. In the multi-goal and low sensor reliability
setting, D4GR shows slightly lower PGR accuracy than HTN. This is due to
D4GR’s reliance on noisy beliefs and user switching goals, leading to a higher
probability of asking questions about irrelevant actions. The rational
language feedback also adversely affects the update of the explaset,
potentially diminishing its utility in later timesteps of the episode.

Our work is also limited by the type of clarification questions the robot can
ask. We have a fixed template for the question. It will be interesting to see
how humans respond to various clarification strategies and how the robot can
plan over a space of such categories. This will increase the action space
requiring more exploration by the POMDP solver. Further, our language
observational model is a bag of words model. It can be more expressive by
incorporating inference from LLMs.

Further, our work assumes access to a pre-defined knowledge base for the
tasks. One thing that we will be exploring in the future is how to make the
knowledge base adaptive to a layman user’s needs and preferences as the task
progresses through interactive dialogue. Our research opens venues for
language grounding and human intent recognition in other collaborative tasks
like building machines/complex furniture together by humans and robots. This
is an encouraging step toward enhancing the sensory capabilities of home-
service robots that can assist people in completing tasks with language-based
interactions.

##  VII Conclusion

We propose a novel algorithm for robots to interactively keep track of
people’s ongoing progress in a task using questions. Moreover, our D4GR
framework can suggest plan improvements to users in solving a task if
required. Our work shows that: 1) modeling the user as an HTN and
incorporating language feedback improves robots’ belief of human’s progress in
simulation; 2) POMDPs are effective methods for tracking a task’s progress and
asking clarification questions. Our D4GR formulation has a similar goal and
step recognition accuracy as the best baseline ALWAYS-ASK method while asking
68% fewer questions. In future work, we aim to conduct a user study with the
targeted population to measure our approach’s usefulness during the
interaction. D4GR’s ability to intelligently balance between clarifying
uncertainty with a lesser number of questions allows for realistic
interactions between a social robot and a human. This ability in the future
can allow for realistic interactions with human users during collaborations
over tasks between humans and robots.

##  VIII Acknowledgement

We thank our labmates at Brown and Rutgers for their valuable insights. This
work was supported by NSF under award number IIS-1652561, ONR under award
numbers N00014-21-1-2584 and N00014-22-1-2592, and with funding from Echo
Labs.

## References

  * Bohus and Horvitz [2010] Dan Bohus and Eric Horvitz.  Facilitating multiparty dialog with gaze, gesture, and speech.  In _ICMI-MLMI_ , ICMI-MLMI ’10, New York, NY, USA, 2010. Association for Computing Machinery.  ISBN 9781450304146.  doi: 10.1145/1891903.1891910.
  * Chai et al. [2018] Joyce Y Chai, Qiaozi Gao, Lanbo She, Shaohua Yang, Sari Saba-Sadiya, and Guangyue Xu.  Language to action: Towards interactive task learning with physical agents.  In _IJCAI_ , pages 2–9, 2018.
  * Doshi and Roy [2007] Finale Doshi and Nicholas Roy.  Efficient model learning for dialog management.  In _HRI_ , pages 65–72, 2007.
  * Erol [1994] Kutluhan et al Erol.  Htn planning: Complexity and expressivity.  In _AAAI_ , volume 94, pages 1123–1128, 1994.
  * Fasola and Matarić [2013] Juan Fasola and Maja J Matarić.  A socially assistive robot exercise coach for the elderly.  _Journal of Human-Robot Interaction_ , 2(2):3–32, 2013.
  * Hoey et al. [2010] Jesse Hoey, Pascal Poupart, Axel von Bertoldi, Tammy Craig, Craig Boutilier, and Alex Mihailidis.  Automated handwashing assistance for persons with dementia using video and a partially observable markov decision process.  _Computer Vision and Image Understanding_ , 114(5):503–519, 2010.
  * Höller et al. [2018] Daniel Höller, Gregor Behnke, Pascal Bercher, and Susanne Biundo.  Plan and goal recognition as htn planning.  In _2018 IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI)_ , pages 466–473. IEEE, 2018.
  * Idrees et al. [2020] Ifrah Idrees, Stefanie Tellex, and Momotaz Begum.  Grounding human-robot dialogue in environment sensors to help elderly in activities of daily living.  _Robodial Workshop - SigDial_ , 2020.
  * Kaelbling et al. [1998] Leslie Pack Kaelbling, Michael L Littman, and Anthony R Cassandra.  Planning and acting in partially observable stochastic domains.  _Artificial intelligence_ , 101(1-2):99–134, 1998.
  * Kidd and Breazeal [2008] Cory D Kidd and Cynthia Breazeal.  Robots at home: Understanding long-term human-robot interaction.  In _2008 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pages 3230–3235. IEEE, 2008.
  * Meneguzzi and Pereira [2021] Felipe Rech Meneguzzi and Ramon Fraga Pereira.  A survey on goal recognition as planning.  In _Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), 2021, Canadá._ , 2021.
  * Mirsky et al. [2017] Reuth Mirsky, Roni Stern, Meir Kalech, et al.  Sequential plan recognition.  _arXiv preprint arXiv:1703.01083_ , 2017.
  * Ong et al. [2009] Sylvie CW Ong, Shao Wei Png, David Hsu, and Wee Sun Lee.  Pomdps for robotic tasks with mixed observability.  In _Robotics: Science and Systems_ , volume 5, page 4, 2009.
  * Pareek and Thakkar [2021] Preksha Pareek and Ankit Thakkar.  A survey on video-based human action recognition: recent updates, datasets, challenges, and applications.  _Artificial Intelligence Review_ , 54(3):2259–2322, 2021.
  * Ramírez and Geffner [2009] Miquel Ramírez and Hector Geffner.  Plan recognition as planning.  In _Twenty-First IJCAI_ , 2009.
  * Razzaq et al. [2017] Muhammad Asif Razzaq, Wajahat Ali Khan, and Sungyoung Lee.  Intent-context fusioning in healthcare dialogue-based systems using jdl model.  In _ICOST_ , pages 61–72. Springer, 2017.  doi: 10.1007/978-3-319-66188-9˙6.
  * Silver and Veness [2010] David Silver and Joel Veness.  Monte-carlo planning in large pomdps.  _Advances in neural information processing systems_ , 23, 2010.
  * Thomason et al. [2019] Jesse Thomason, Aishwarya Padmakumar, and et al.  Improving grounded natural language understanding through human-robot dialog.  In _(ICRA)_ , pages 6934–6941. IEEE, 2019.
  * Wang and Hoey [2017] Dan Wang and Jesse Hoey.  Hierarchical task recognition and planning in smart homes with partial observability.  In _International Conference on Ubiquitous Computing and Ambient Intelligence_ , pages 439–452. Springer, 2017.
  * Whitney et al. [2017] David Whitney, Eric Rosen, James MacGlashan, Lawson LS Wong, and Stefanie Tellex.  Reducing errors in object-fetching interactions through social feedback.  In _2017 (ICRA)_ , pages 1006–1013. IEEE, 2017.
  * Young et al. [2013] Steve Young, Milica Gašić, Blaise Thomson, and Jason D Williams.  Pomdp-based statistical spoken dialog systems: A review.  _Proceedings of the IEEE_ , 101(5):1160–1179, 2013.
  * Zhi-Xuan et al. [2020] Tan Zhi-Xuan, Jordyn Mann, Tom Silver, Josh Tenenbaum, and Vikash Mansinghka.  Online bayesian goal inference for boundedly rational planning agents.  _NEURIPS_ , 33:19238–19250, 2020.


# A Logarithmic Decomposition for Information

Keenan J. A. Down12 and Pedro A. M. Mediano3  1Queen Mary, University of
London<EMAIL_ADDRESS>2University of Cambridge<EMAIL_ADDRESS>3Imperial College London<EMAIL_ADDRESS>
###### Abstract

The Shannon entropy of a random variable $X$ has much behaviour analogous to a
signed measure. Previous work has concretized this connection by defining a
signed measure $\mu$ on an abstract information space $\tilde{X}$, which is
taken to represent the information that $X$ contains. This construction is
sufficient to derive many measure-theoretical counterparts to information
quantities such as the mutual information
$I(X;Y)=\mu(\tilde{X}\cap\tilde{Y})$, the joint entropy
$H(X,Y)=\mu(\tilde{X}\cup\tilde{Y})$, and the conditional entropy
$H(X|Y)=\mu(\tilde{X}\,\setminus\,\tilde{Y})$. We demonstrate that there
exists a much finer decomposition with intuitive properties which we call the
logarithmic decomposition (LD). We show that this signed measure space has the
useful property that its logarithmic atoms are easily characterised with
negative or positive entropy, while also being coherent with Yeung’s
$I$-measure [14]. We present the usability of our approach by re-examining the
Gács-Körner common information from this new geometric perspective and
characterising it in terms of our logarithmic atoms. We then highlight that
our geometric refinement can account for an entire class of information
quantities, which we call logarithmically decomposable quantities.

##  I Introduction

For all first-order information-theoretical quantities derived from the
classical Shannon entropy on a series of random variables
$X_{1},\ldots,X_{r}$, Yeung demonstrated that there exists a representative
set in a corresponding $\sigma$-algebra $\mathcal{F}$ and, moreover, that for
any set in the $\sigma$-algebra there is a sensible measure of information
[14]. This correspondence, built on earlier work by Hu Kuo Ting in [9], offers
a firm foundation for the measure-theoretical perspective of entropy.

The $\sigma$-algebra $\mathcal{F}$ of Yeung is coarse in that it is generated
by the unions, intersections, and complements of abstract information spaces
$\tilde{X}_{1},\ldots,\tilde{X}_{r}$. This symbolic connection, while
mechanically useable and consistent, offers little insight into the
constituent elements of these information spaces. Our geometric perspective on
a refinement provides both a quantitative and qualitative foundation for this
measure.

Decomposing these information spaces is of great interest across multiple
domains. What kind information is transmitted across a network of neurons, and
with what qualitative structure? How can we disentangle the complex interplay
between confounding variables, such as gender and pay, or race and arrest
rate? It is known that the mutual information cannot generally be encoded [5],
but can we develop alternative language to explain these interactions? In this
work we describe these abstract information spaces in greater detail than, to
the best of our knowledge, has previously been seen. Given a series of random
variables $X_{1},\ldots,X_{r}$ we present a theoretically maximal refinement
of the corresponding $\sigma$-algebra. We will construct a measure $L^{\circ}$
on this abstract information space, and this measure shall represent the
informational content of its subsets. In doing so we also decompose the
$\sigma$-algebra of Yeung [14] into logarithmic atoms, whose contribution to
the entropy is particularly easy to characterise, in a process we call
logarithmic decomposition.

We will make the utility of our new vocabulary clear by also expressing the
common information of Gács and Körner [5] in terms of our logarithmic
decomposition. We will see that both mutual information and common information
reside in a class of information quantities we call logarithmically
decomposable quantities, which we believe to contain many standard measures.

##  II Refinement of Abstract Information Spaces

Let $X_{1},\ldots,X_{r}$ be discrete random variables on a corresponding
finite sample space $\Omega$ with the natural $\sigma$-algebra $\mathcal{F}$
generated by all possible combinations of outcomes on each variable. Using the
probability space $(\Omega,\mathcal{F},P)$, we will define a corresponding
space for information.

######  Definition 1.

Let $(\Omega,\mathcal{F},P)$ be a probability space as above. Then define the
complex of $\Omega$ as the simplicial complex on all outcomes
$\omega\in\Omega$:

$\Delta(\Omega)=\bigcup_{k=1}^{N}\Omega_{k}\cong\mathcal{P}(\Omega)\setminus\\{\varnothing\\}.$
(1)

where $\Omega_{k}$ is the set of subsets $S\subseteq\Omega$ with $|S|=k$ and
$N=|\Omega|$. For a collection of $n$ outcomes $\omega_{1},\ldots,\omega_{n}$,
we label the corresponding simplex for $n\geq 2$ as
$B^{\circ}(\omega_{1},\ldots,\omega_{n})\in\Omega^{n}$, which, viewing
$\Delta(\Omega)$ geometrically, corresponds to a face, volume, or edge without
its boundaries. For additional consistency, we let
$B(\varnothing)=B^{\circ}(\varnothing)=\emptyset$. Note that we write
$B^{\circ}$ to signify that the boundaries of the simplex are not included.

We occasionally write $\Delta\Omega$ instead of $\Delta(\Omega)$ to simplify
the notation.

######  Example 2.

Consider a space of outcomes $\Omega=\\{1,2,3,4\\}$. The complex consists of
the following elements

$\displaystyle\begin{split}\Delta(\Omega)=\\{&B(1),B(2),B(3),B(4),\\\
&B^{\circ}(1,2),B^{\circ}(1,3),B^{\circ}(1,4),\\\
&B^{\circ}(2,3),B^{\circ}(2,4),B^{\circ}(3,4),\\\
&B^{\circ}(1,2,3),B^{\circ}(1,2,4),B^{\circ}(1,3,4),B^{\circ}(2,3,4),\\\
&B^{\circ}(1,2,3,4)\\}\end{split}$ (2)

4321 Figure 1: The highlighted triangle along with its boundary corresponds to
the subset
$B(1,2,4)=\\{B(1),B(2),B(4),B^{\circ}(1,2),B^{\circ}(1,4),B^{\circ}(2,4),B^{\circ}(1,2,4)\\}$.

######  Remark 3.

The points of the simplex (of the form $B(\omega)$) are relatively
inconsequential and we will make use of them only when advantageous, but
otherwise we will not mention them further. We will see in section III that
the points will be associated with zero entropy in our constructed measure
space.

##  III Construction of a signed measure

Having endowed $\Delta(\Omega)$ with a geometric interpretation, we would like
to equip it now with a signed measure. Doing this completes the construction
of the abstract information space $\tilde{X}$ of a random variable $X$, which
has appeared previously in the form of a set-variable correspondence [14, 9].
We will use the entropy loss to assign an entropy to each atom in our
decomposition [1].

We will define here two measures of entropy loss: The total entropy loss $L$,
which will represent the total entropy lost when merging a select group of
regions in a partition; and the interior loss $L^{\circ}$, which we will later
use to measure the elements of our geometric space $\Delta(\Omega)$. We will
see that $L$ measures entire simplices with their boundaries, and $L^{\circ}$
will push the construction further to measure the interiors of these
simplices. The purpose of this distinction is that the $L$ measure alone
offers enough behaviour to deduce the measure of Campbell [3], but becomes
insufficient to study non-orthogonal partitions of $\Omega$. The interior loss
measure $L^{\circ}$ will refine this measure to resolve this orthogonality
issue.

From the perspective of entropy loss, a variable will lose entropy when
boundaries between events are deleted [1]. To see this, let $X$ be a random
variable corresponding to a partition $\bm{Q}_{X}=\\{Q_{1},\ldots,Q_{t}\\}$ of
the outcome space $\Omega$ where $\mathbb{P}(Q_{i})=\sum_{\omega\in
Q_{i}}\mathbb{P}(\omega)$. If we create a new random variable $X^{\prime}$ by
merging two of the partitions $Q_{1}$ and $Q_{2}$ so that
$\bm{Q}_{X^{\prime}}=\\{Q_{1}\cup Q_{2},Q_{3},\ldots,Q_{t}\\}$ becomes the new
partition, then the new variable $X^{\prime}$ will have a reduced entropy.
Clearly, removing all boundaries will correspond to an entropy loss equivalent
to the total entropy of the variable $X$.

######  Definition 4.

Let $X$ be a random variable with corresponding partition
$\bm{Q}_{X}=\\{Q_{1},\ldots,Q_{t}\\}$, and let $X^{\prime}$ be the random
variable with corresponding partition

$\bm{Q}_{X^{\prime}}=\left\\{\bigcup_{\alpha\in
A}Q_{\alpha}\right\\}\cup\left\\{Q_{\beta}:\beta\notin A\right\\},$ (3)

where $A$ is a subset of events which we intend to merge. What we recover is
$\bm{Q}_{X}$ with all parts indexed in $A$ merged together. Then we define the
total loss

$L(A)=H(X)-H(X^{\prime}).$ (4)

We may simplify the situation by writing $L(p_{1},\ldots,p_{n})$ instead of
$L(P_{1},\ldots,P_{n})$ or writing $L(S)$ for $S=\\{p_{1},\ldots,p_{n}\\}$ to
signify that $L$ can also be viewed as a function on $\mathbb{R}^{n}$.
Expanding the above expression we find

$\displaystyle\begin{split}L(p_{1},\ldots,p_{n})=&\,H(X)-H(X^{\prime})\\\
=&\,p_{1}\log\left(\frac{1}{p_{1}}\right)+\cdots+p_{n}\log\left(\frac{1}{p_{n}}\right)\\\
&\,-(p_{1}+\cdots+p_{n})\log\left(\frac{1}{p_{1}+\cdots+p_{n}}\right)\\\
=&\,\log\left[\frac{(p_{1}+\cdots+p_{n})^{(p_{1}+\cdots+p_{n})}}{p_{1}^{p_{1}}\ldots
p_{n}^{p_{n}}}\right].\end{split}$ (5)

We note that for any partition $P_{1},\ldots,P_{n}$ of $\Omega$ we must have
that $L(P_{1},\ldots,P_{n})\geq 0$. Moreover, using equation (4), it is
immediately clear that for a random variable $X$ with outcomes of associated
probabilities $p_{1},\ldots,p_{n}$ with $\sum p_{i}=1$, we have

$H(X)=L(p_{1},\ldots,p_{n})$ (6)

Trivially we also see that $L(p)=0$ for any $p\in[0,1]$.

We now extend the definition of the total loss using Möbius inversion to
produce the interior loss, $L^{\circ}$. For maximum strength, we will now
treat $\Omega$ as a partition of singletons $\omega_{i}\in\Omega$, as we will
see this is sufficient to describe all other possible partitions.

######  Definition 5.

We will define the interior loss function
$L^{\circ}(\omega_{1},\ldots,\omega_{n})$ recursively. For $n=1$ let
$L^{\circ}(\omega)=0$. For $n\geq 1$ we then recursively define $L^{\circ}$ by

$L^{\circ}(\omega_{1},\ldots,\omega_{n})=L(\omega_{1},\ldots,\omega_{n})-\sum_{\begin{subarray}{c}S\subset\\{\omega_{1},\ldots,\omega_{n}\\}\\\
|S|\leq n-1\end{subarray}}L^{\circ}(S).$ (7)

Again, as with the total loss, we will often abuse this notation and write
$L^{\circ}(p_{1},\ldots,p_{n})$ where the probabilities reflect individual
outcomes or regions in the partition.

Geometrically, we will see that the interior loss will measure entropies in
interior regions of the complex $\Delta(\Omega)$.

######  Remark 6.

The total loss can be expressed as a sum of the interior losses by virtue of
their construction:

$L(\omega_{1},\ldots,\omega_{n})=\sum_{S\subseteq\\{\omega_{1},\ldots,\omega_{n}\\}}L^{\circ}(S),$
(8)

and hence the interior loss function can also be expressed in terms of the
loss function by virtue of the inclusion-exclusion principle:

$L^{\circ}(\omega_{1},\ldots,\omega_{n})=\sum_{S\subseteq\\{\omega_{1},\ldots,\omega_{n}\\}}(-1)^{n-|S|}L(S).$
(9)

The interior loss corresponds to the Möbius inversion of the total loss on the
partially ordered set defined by containment of simplices.

As an aside, and while meaningless within probability theory, we note that the
functions $L$ and $L^{\circ}$ can both be extended to domains where the
probabilities $p_{i}$ are greater than one, and many of the following results
hold for any $p_{i}\in\mathbb{R}^{+}$.

We now show that $L^{\circ}$ can be used as a measure of entropy. We will
later demonstrate that $L^{\circ}$ provides a refinement of the $I$-measure of
Yeung [14].

######  Theorem 7.

Let $\Omega$ be a finite set of outcomes and let $\Sigma$ be the
$\sigma$-algebra generated by all of the elements $b\in\Delta(\Omega)$. For
$S\subseteq\Delta(\Omega)$ define $L^{\circ}(S)=\sum_{b\in S}L^{\circ}(b)$.
Then $(\Delta(\Omega),\Sigma,L^{\circ})$ is a finite signed measure space.

###### Proof.

Setting $L^{\circ}(\varnothing)=0$, and using the definition of $L^{\circ}(S)$
we see that $L^{\circ}$ is at least countably additive across disjoint sets in
$\Sigma$. Hence $(\Delta\Omega,\Sigma,L^{\circ})$ is a signed measure space. ∎

We will see in section IV-A that this measure is a refinement of the the
$I$-measure of Yeung [14]. For now, we shall state a series of further results
which are useful for calculations with $L^{\circ}$.

######  Lemma 8 (Interior loss identity).

Let $T=\\{p_{1},\ldots,p_{k}\\}$ for some collection of probabilities. For
notational clarity we will write

$\sigma(T)=\sigma(p_{1},\ldots,p_{k})=(p_{1}+\cdots+p_{k})^{(p_{1}+\cdots+p_{k})}.$
(10)

Further still we shall write

$A_{k}=\prod_{\begin{subarray}{c}S\subseteq\\{p_{1},\ldots,p_{n}\\}\\\
|S|=k\end{subarray}}\sigma(S).$ (11)

Then we have that

$L^{\circ}(p_{1},\ldots,p_{n})=\sum_{k=1}^{n}(-1)^{n-k}\log(A_{k})$ (12)

This lemma demonstrates that our atoms are measured by alternating sums of
logarithms, justifying the name logarithmic decomposition. Our next lemma
allows the confident inclusion of $0$ in our domain.

######  Lemma 9 (Interior loss at 0).

For $p_{1},\ldots,p_{n},x\in\mathbb{R}^{+}$ where $n\geq 0$, we have

$\lim_{x\to 0}L^{\circ}(p_{1},\ldots,p_{n},x)=0$ (13)

######  Lemma 10.

Let $p_{1},\ldots,p_{n-1},x\in\mathbb{R}^{+}$ and let $x$ vary. Then

$\lim_{x\to\infty}|L^{\circ}(p_{1},\ldots,p_{n-1},x)|=|L^{\circ}(p_{1},\ldots,p_{n-1})|$
(14)

The result of this lemma will be useful for a corollary which follows from the
next result. The following theorem demonstrates the useful property that
logarithmic atoms have an intrinsic sign.

######  Theorem 11.

Let $p_{2},\ldots,p_{n}\in\mathbb{R}^{+}$ be a sequence of nonzero arguments
for $n\geq 2$ and $m\geq 0$. Then

$(-1)^{m+n}\frac{\partial^{m}L^{\circ}}{\partial
x^{m}}(x,p_{2},\ldots,p_{n})\geq 0.$ (15)

Setting $m=0$ we immediately see that the sign of logarithmic atoms alternates
solely on the number of outcomes they contain; a property which standard co-
informations do not have.

######  Corollary 12 (Interior magnitude can only decrease).

Let $p_{1},\ldots,p_{n-1},\tau\in\mathbb{R}^{+}\cup\\{0\\}$ for $n\geq 3$.
Then

$|L^{\circ}(p_{1},\ldots,p_{n-1},\tau)|<|L^{\circ}(p_{1},\ldots,p_{n-1})|$
(16)

This result is quite powerful in that it works for
$p_{1},\ldots,p_{n-1},\tau\in[0,\infty)$. For our information-theoretical
purposes, we will naturally require that $p_{i}\in[0,1]$, so the measure of
successively higher-order volumes in $\Delta(\Omega)$ will strictly decrease,
with the slowest descent for $p_{1}=\cdots=p_{n}$.

##  IV Quantities of information

Having constructed the measurable space $\Delta(\Omega)$ we will now
demonstrate its utility in characterising various variable-level information
quantities.

Firstly we will show how mutual information and co-information can be
reinterpreted using the logarithmic decomposition, and we show that the
information measure $L^{\circ}$ is consistent with the prevailing measure of
Yeung [14].

###  IV-A Mutual and Co-information

Suppose we have two variables $X$ and $Y$ defined on the same outcome space
$\Omega$. This outcome space can be taken to be the meet of the two partitions
corresponding to $X$ and $Y$ if necessary.

The degree to which the two variables interact can be quantified in terms of
their entropies via their mutual information, $I(X;Y)$, which is naturally
derived as $I(X;Y):=H(X)+H(Y)-H(X,Y)$. This expression can be derived from
multiple perspectives, including homologically, as shown by Baudot and
Bennequin [2]. Alternatively, it is given by the Kullback-Leibler divergence
between the joint distribution and the product of the marginal distributions
$D_{KL}(P(X,Y)||P(X)P(Y))$ [4], that is, it captures the degree to which the
joint distribution diverges from independence.

One possible generalisation of the mutual information for multiple variables
(although others exist, for example the total correlation [11] or the dual
total correlation [8]) is the interaction information or co-information [17,
16]. This can be defined recursively using

$I(X_{1};\ldots;X_{r})=I(X_{1};\ldots;X_{r-1})-I(X_{1};\ldots;X_{r-1}|X_{r}).$
(17)

The co-information can be taken as representing the information that is common
to several variables. The next definition will give us the connection between
a random variable and its logarithmic decomposition. Doing this will enable us
to discuss the co-information in terms of logarithmic atoms.

######  Definition 13.

Given a random variable $X$, we define the content
$\operatorname{\mathcal{C}}(X)$ inside of $\Delta(\Omega)$ to be the set of
all boundaries crossed by $X$. That is, if $X$ corresponds to a partition
$P_{1},\ldots,P_{n}$, then

$\mathcal{C}(X)=\\{\text{$B^{\circ}(S):S\subseteq\Omega,\exists\,\omega_{i},\omega_{j}\in
S$}\\\ \text{with $\omega_{i}\in P_{k}$, $\omega_{j}\in P_{l}$ such that
$k\neq l$ }\\}.$ (18)

Intuitively, this means that at least two of the outcomes in
$B^{\circ}(\omega_{1},\ldots,\omega_{n})$ correspond to distinct events in
$X$. We will in general make use of $\mathcal{C}$ to represent the logarithmic
decomposition functor from random variables to their corresponding sets in
$\Delta\Omega$.

######  Example 14.

To demonstrate our refinement, we consider the space $\Omega=\\{1,2,3,4\\}$.
Let the partitions be given by $X=\\{\\{1,3\\},\\{2,4\\}\\}$ and
$Y=\\{\\{1,2\\},\\{3,4\\}\\}$, as in figure 2.

Taking the intersection of the contents $\mathcal{C}(X)\cap\mathcal{C}(Y)$
gives the logarithmic content mutual to both variables. These logarithmic
atoms are given in figure 3.

$(1)$$(2)$$(3)$$(4)$$(X,Y)$$0.1$$0.2$$0.3$$0.4$$(X,Y)$$0.4$$0.6$$X$$0.3$$0.7$$Y$

Figure 2: Two random variables on the set $\Omega=\\{1,2,3,4\\}$ with some
illustrative probabilities.
$X$$Y$$B^{\circ}(1,2)$$B^{\circ}(3,4)$$B^{\circ}(1,3)$$B^{\circ}(2,4)$$B^{\circ}(1,4)$$B^{\circ}(2,3)$$B^{\circ}(1,2,3)$$B^{\circ}(1,2,4)$$B^{\circ}(1,3,4)$$B^{\circ}(2,3,4)$$B^{\circ}(1,2,3,4)$
Figure 3: Logarithmic atoms of $\Omega=\\{1,2,3,4\\}$ in the space
$\Delta(\Omega)$.

The next theorem is the main result of this paper, demonstrating that
Logarithmic Decomposition is at least consistent with the standard atomic
decomposition of Yeung [14].

######  Theorem 15.

Let $R$ be a region on an $I$-diagram of variables $X_{1},\ldots,X_{r}$ with
Yeung’s $I$-measure. Then

$I(R)=\sum_{B\in\operatorname{\mathcal{C}}(R)}L^{\circ}(B).$ (19)

That is, the interior loss measure is consistent with Yeung’s $I$-measure.

We note also that all inclusion-exclusion expressions such as that in equation
(42) can be naturally extended to the formal sum used in the proof. Provided
all of the coefficients in the formal sum are either 0 or 1, we can assign the
informational quantity with a content, i.e. a subset of $\Delta(\Omega)$. For
example, the O-information of Rosas et al. [7] satisfies this property and
hence has an associated content.

###  IV-B Common Information

An intrinsic problem in the study of random variables is that interactions
between variables often cannot be encoded with a third variable [5]. The Gács-
Körner formulation of this common information has, for instance, been shown to
have little relation to the mutual information in most scenarios.

We have seen in section IV-A that mutual information can be completely
described by the intersection of variable contents in logarithmic
decomposition. We will demonstrate that the logarithmic decomposition can also
describe the common information of Gács and Körner.

To do this, we will demonstrate that the common information shared between a
finite collection of variables $X_{1},\ldots,X_{r}$ corresponds to a subset of
$\operatorname{\mathcal{C}}(X_{1})\cap\cdots\cap\operatorname{\mathcal{C}}(X_{r})$.

######  Definition 16 (Gács-Körner Common Information).

The Gács-Körner common information on a finite set of random variables
$X_{1},\ldots,X_{r}$ [5] is given by

$C_{GK}(X_{1};\ldots;X_{r})=\max_{Z}H(Z)\\\ \text{such that
$f_{1}(X_{1})=\cdots=f_{r}(X_{r})=Z$ for some $f_{i}$.}$ (20)

This common information encodes interactions between variables which can be
extracted and represented by another variable [15]. The common information is
known to be usually far less than the mutual information [5]. We now
demonstrate that common information can be represented as a subset in
$\Delta(\Omega)$.

######  Theorem 17.

The Gács-Körner common information of a finite set of variables $X_{i}$
corresponds to the maximal subset $C$ of
$\bigcap_{i}\operatorname{\mathcal{C}}(X_{i})$ such that there exists some
random variable $Z$ with $\operatorname{\mathcal{C}}(Z)=C$.

It will perhaps be useful to discuss variables which are contained in
arbitrary subsets of $\Delta(\Omega)$. For this purpose, we give the following
definitions.

######  Definition 18.

Given a subset $R\subseteq\Delta(\Omega)$, we say that $R$ is discernible if
it corresponds to the content of any random variable $Z$.

Moreover, given any subset $S\subseteq\Delta(\Omega)$, let
$\operatorname{Dis}(S)\subseteq S$ be the largest discernible subset of $S$.
We will call this the maximally discernible subset of $S$.

Note that $\operatorname{Dis}(S)$ is well defined as the trivial random
variable is always discernible in $S$, and we also have uniqueness. To see
this, note that if two such non-isomorphic variables $Z_{1}$ and $Z_{2}$ were
to exist, then $\operatorname{\mathcal{C}}(Z_{1}Z_{2})\subseteq S$ would be a
larger subset, contradicting their maximality.

######  Remark 19.

As seen in theorem 17,
$L^{\circ}[\operatorname{Dis}(\bigcap_{i}\operatorname{\mathcal{C}}(X_{i}))]=C_{GK}(X_{1};\ldots;X_{r})$,
the Gács-Körner common information.

For an example illustrating this result geometrically, see figure 4.

1234$X$1234$Y$

4321a) $\operatorname{\mathcal{C}}(X)$4321b)
$\operatorname{\mathcal{C}}(Y)$4321c)
$\operatorname{\mathcal{C}}(X)\cap\operatorname{\mathcal{C}}(Y)$4321d)
$\operatorname{Dis}(\operatorname{\mathcal{C}}(X)\cap\operatorname{\mathcal{C}}(Y))$
Figure 4: The 1-dimensional atomic contents of $X$ and $Y$ and their (c)
intersection and (d) maximally discernible subset.

###  IV-C Logarithmically decomposable quantities

Having expressed the mutual information and the common information in terms of
subsets of $\Delta(\Omega)$, we are inclined to expect that other kinds of
information quantities can also be captured by the logarithmic decomposition.
To that end, we give two definitions.

######  Definition 20.

Given a collection of random variables $\\{X_{\alpha}:\alpha\in A\\}$ for some
index set $A$ on a common outcome space $\Omega$, we let
$\mathcal{A}=\mathcal{P}(A)$ be the powerset of $A$, and we define a variable
quantity to be any map $f:\mathcal{A}\to\mathbb{C}$.

This notion of variable quantity encapsulates any kind of computation on any
set of random variables and hence certainly contains information quantities.
Note that we might allow $f$ to only be defined for finite or countable
domains if necessary.

######  Definition 21.

Let $f:\mathcal{A}\to\mathbb{C}$ be a variable quantity defined on an outcome
space $\Omega$. We say that $f$ is logarithmically decomposable if there
exists a mapping $f^{*}$, defined whenever $f$ is defined, sending sets of
variable contents in $\operatorname{\mathcal{C}}\mathcal{A}$ to corresponding
subsets of $\Delta\Omega$ such that the diagram commutes.

${\mathcal{A}}$ ${\mathbb{C}}$${\mathcal{CA}}$
${\mathcal{P}(\Delta\Omega)}$$\scriptstyle{f}$$\scriptstyle{\operatorname{\mathcal{C}}}$$\scriptstyle{f*}$$\scriptstyle{L^{\circ}}$
(21)

We denote the set of logarithmically decomposable variable quantities by
$\mathcal{L}(A)$ or just $\mathcal{L}$.

This definition captures the idea that the function $f$ can be evaluated by
computing a logarithmic decomposition in some form and then applying the
measure $L^{\circ}$.

We have seen that all mutual and co-informations are logarithmically
decomposable. Moreover, in the previous subsection we also saw that the Gács-
Körner common information is also logarithmically decomposable.

##  V Conclusion

In this paper we demonstrated that there exists a signed measure space for
information which is finer than the $I$-measure of Yeung [14]. To our
knowledge, this signed measure space is the finest such space treated in the
literature, although we expect it can be rederived from many perspectives.

To complete this refinement we utilised a Möbius inversion on the lattice of
all possible outcomes $\Delta(\Omega)$. To demonstrate that this approach
indeed reflects a more fundamental description of entropy, we showed that the
sign of the logarithmic atoms $B^{\circ}(\omega_{1},\ldots,\omega_{n})$ is
intrinsic to their structure. Our proof was analytic, but we expect a proof
using convexity is possible. We demonstrated that this approach can capture
both mutual information and common information, and we noted that there is a
larger class of information quantities which can be logarithmically
decomposed. We expect many standard information quantities are also
logarithmically decomposable, but for space we have not treated others.

This work opens a new combinatorical framework for use in studying
logarithmically decomposable information quantities. While the work presented
here takes a geometric perspective, entropy on an inter-variable scale has
been shown to have much homological behaviour [2, 10], and we hope that our
tools might be incorporated into the more general topological study of
information in the future.

Lastly, we hope that these atoms might be applied to the problem of partial
information decomposition [13] and extensions such as $\Phi$ID [6], as the
result of theorem 11 demonstrates a potential new avenue for the
characterisation of synergistic interactions in complex systems.

#### Acknowledgements

The authors would like to thank Dan Bor, Fernando Rosas, Robin Ince and Juho
Äijälä for interesting discussions on this work and its future directions.

## References

  * [1] John C Baez, Tobias Fritz, and Tom Leinster.  A characterization of entropy in terms of information loss.  Entropy, 13(11):1945–1957, 2011.
  * [2] Pierre Baudot and Daniel Bennequin.  The homological nature of entropy.  Entropy, 17(5):3253–3318, 2015.
  * [3] L Campbell.  Entropy as a measure.  IEEE Transactions on Information Theory, 11(1):112–114, 1965.
  * [4] T. M. Cover and J. A. Thomas, _Elements of Information Theory_ , 1991.
  * [5] Peter Gács and János Körner.  Common information is far less than mutual information.  Problems of Control and Information Theory, 2(2):149–162, 1973\.
  * [6] Pedro AM Mediano, Fernando E Rosas, Andrea I Luppi, Robin L Carhart-Harris, Daniel Bor, Anil K Seth, and Adam B Barrett.  Towards an extended taxonomy of information dynamics via integrated information decomposition.  arXiv preprint arXiv:2109.13186, 2021.
  * [7] Fernando E Rosas, Pedro AM Mediano, Michael Gastpar, and Henrik J Jensen.  Quantifying high-order interdependencies via multivariate extensions of the mutual information.  Physical Review E, 100(3):032305, 2019.
  * [8] Han Te Sun.  Nonnegative entropy measures of multivariate symmetric correlations.  Information and Control, 36:133–156, 1978.
  * [9] Hu Kuo Ting.  On the amount of information.  Theory of Probability & Its Applications, 7(4):439–447, 1962.
  * [10] Juan Pablo Vigneaux.  Information structures and their cohomology.  arXiv preprint arXiv:1709.07807, 2017.
  * [11] Satosi Watanabe.  Information theoretical analysis of multivariate correlation.  IBM Journal of Research and Development, 4(1):66–82, 1960.
  * [12] Stephen Willard.  General topology.  Courier Corporation, 2012.
  * [13] Paul L Williams and Randall D Beer.  Nonnegative decomposition of multivariate information.  arXiv preprint arXiv:1004.2515, 2010.
  * [14] Raymond W Yeung.  A new outlook on shannon’s information measures.  IEEE Transactions on Information Theory, 37(3):466–474, 1991.
  * [15] Lei Yu, Houqiang Li, and Chang Wen Chen.  Generalized common informations: Measuring commonness by the conditional maximal correlation.  arXiv preprint arXiv:1610.09289, 2016.
  * [16] A. J. Bell, “The co-information lattice,” in _Proceedings of the Fifth International Workshop on Independent Component Analysis and Blind Signal Separation: ICA_ , vol. 2003, 2003.
  * [17] W. McGill, “Multivariate information transmission,” _Transactions of the IRE Professional Group on Information Theory_ , vol. 4, no. 4, pp. 93–111, 1954\.

## Proofs for results

### Proof of lemma 8

###### Proof.

To simplify we shall also write $f_{k}=\begin{pmatrix}n-1\\\
k-1\end{pmatrix}$. This is the number of subsets
$S\subseteq\\{p_{1},\ldots,p_{n}\\}$ of size $k$ which contain a given
$p_{i}$. As we ask for subsets which already contain $p_{i}$, this is
equivalent to asking how many subsets there are of size $k-1$ in
$\\{p_{1},\ldots,p_{n}\\}\setminus\\{p_{i}\\}$.

Taking equation (9) and using the definition of the total loss function we
have

$L^{\circ}(p_{1},\ldots,p_{n})\\\
=\log\left[\frac{A_{n}}{\sigma(p_{1})\ldots\sigma(p_{n})}\cdot\frac{\sigma(p_{1})^{f_{n-1}}\ldots\sigma(p_{n})^{f_{n-1}}}{A_{n-1}}\cdots\right.\\\
\left.\cdots\left(\frac{A_{1}}{\sigma(p_{1})^{f_{1}}\ldots\sigma(p_{n})^{f_{1}}}\right)^{(-1)^{n-1}}\right]\\\
=\sum_{k=1}^{n}{(-1)^{n-k}}\log\left[\frac{A_{k}}{\sigma(p_{1})^{f_{k}}\ldots\sigma(p_{n})^{f_{k}}}\right]\\\
$ (22)

Notice that $f_{1}=1$ so that the final term in this sequence with $k=1$ is
equal to $\log(1)=0$. Counting the powers of $\sigma(p_{i})$ shows that in the
final expression the power of $\sigma(p_{i})$ will be
$f_{n}-f_{n-1}+f_{n-2}+\cdots\pm f_{2}$ (as the $k=1$ term is cancelled by
$A_{1}$). It is a standard result that

$\displaystyle\begin{split}\sum_{k=1}^{n}(-1)^{(n-k)}f_{k}&=0\quad\text{and
hence}\\\ \sum_{k=2}^{n}(-1)^{(n-k)}f_{k}&=(-1)^{n}\end{split}$ (23)

Hence in the final expression the power of $\sigma(p_{i})$ is $(-1)^{n}$.
Rewriting $\sigma(p_{1})\cdots\sigma(p_{n})=A_{1}$ gives us the result of
equation (12). ∎

### Proof of lemma 9

###### Proof.

We are augmenting $p_{1},\ldots,p_{n}$ with the additional argument $x$, where
we will allow $x$ to vary. Let us now write

$B_{k}=\prod_{\begin{subarray}{c}S\subseteq\\{p_{1},\ldots,p_{n},x\\}\\\ x\in
S\\\ |S|=k\end{subarray}}\sigma(S).$ (24)

Then equation (12) becomes

$L^{\circ}(p_{1},\ldots,p_{n},x)=\sum_{k=1}^{n+1}(-1)^{n+1-k}\log(B_{k}(x))\\\
+\sum_{k=1}^{n}(-1)^{n+1-k}\log(A_{k})$ (25)

Here we take $A_{k}$ to be a product of all terms not containing the argument
$x$ as per lemma 9. We notice that the sign of all terms $A_{k}$ have now
flipped, but are otherwise identical. We want to show that as $x\to 0$ that
these two sums will cancel. Recall that $B_{k}(x)$ is a product of terms of
the form
$\sigma(p_{1},\ldots,p_{n},x)=(p_{1}+\cdots+p_{n}+x)^{(p_{1}+\ldots+p_{n}+x)}$
for subsets of size $k$. We see that

$\lim_{x\to 0}\sigma(p_{1},\ldots,p_{n},x)=\sigma(p_{1},\ldots,p_{n})$ (26)

By the product and quotient rules for limits, we hence also have that

$\lim_{x\to 0}B_{k}=A_{k-1}$ (27)

Inserting this into equation (25) we see that both sides immediately cancel to
give zero as $x\to 0$. ∎

### Proof of lemma 10

###### Proof.

Using the expression of lemma 8 and the notation for $B_{k}(x)$ from lemma 9
we can write

$L^{\circ}(p_{1},\ldots,p_{n-1},x)=\sum_{k=1}^{n}(-1)^{n-k}\log(B_{k}(x))+\\\
\sum_{k=1}^{n-1}(-1)^{n-k}\log(A_{k})$ (28)

Where we have omitted the term in $A_{n}$ because any subset of
$\\{p_{1},\ldots,p_{n-1},x\\}$ of size $n$ is certain to contain $x$. We
immediately see that the second expression is equal to
$-L^{\circ}(p_{1},\ldots,p_{n-1})$. It therefore suffices to show that the
first expression in the $B_{k}(x)$ tends to 0 as $x\to\infty$

Writing the logarithm of $B_{k}(x)$ as a single fraction, we know by the
standard binomial result in equation (23) that the number of factors on the
top and the bottom of the fraction containing $x$ is equal. Let the number of
factors be $m$. Then, expanding the expression in $B_{k}(x)$, we see it is
dominated on the top and the bottom by an $x^{m}$ term. This term will
dominate as $x\to\infty$, so that the fraction tends to 1 and the logarithm in
$x$ will tend to 0, leaving us with

$\lim_{x\to\infty}L^{\circ}(p_{1},\ldots,p_{n-1},x)=-L^{\circ}(p_{1},\ldots,p_{n-1}),$
(29)

giving the result immediately. ∎

### Proof of theorem 11

###### Proof.

We will prove this by induction on $n$. To start, we demonstrate that the
derivative of $L^{\circ}$ has some useful properties. Using standard results
and utilising the notation of lemma 8, we have that

$\frac{\partial}{\partial
x}\,\sigma(x,p_{2},\ldots,p_{k})=\sigma(x,p_{2},\ldots,p_{k})\\\
\cdot\left[\log(x+p_{2}+\cdots+p_{k})+1\right]$ (30)

We restate the identity in equation (25) for $n-1$ fixed probabilities:

$L^{\circ}(p_{1},\ldots,p_{n-1},x)=\sum_{k=1}^{n}(-1)^{n-k}\log(B_{k}(x))\\\
+\sum_{k=1}^{n-1}(-1)^{n-k}\log(A_{k})$

The second sum does not depend on $x$. Differentiating with respect to $x$ we
obtain

$\displaystyle\begin{split}&\frac{\partial L^{\circ}}{\partial
x}(p_{1},\ldots,p_{n-1},x)\\\
=&\sum_{\begin{subarray}{c}S\subseteq\\{p_{1},\ldots,p_{n-1},x\\}\\\ x\in
S\end{subarray}}(-1)^{n-|S|}\frac{\partial}{\partial x}\,\log(\sigma(S))\\\
=&\sum_{\begin{subarray}{c}S\subseteq\\{p_{1},\ldots,p_{n-1},x\\}\\\ x\in
S\end{subarray}}(-1)^{n-|S|}\frac{\sigma^{\prime}(S)}{\sigma(S)}\\\
=&\sum_{\begin{subarray}{c}S\subseteq\\{p_{1},\ldots,p_{n-1},x\\}\\\ x\in
S\end{subarray}}(-1)^{n-|S|}\left[\log\left(\sum_{s\in S}s\right)+1\right]\\\
\end{split}$ (31)

The total number of subsets $S\subseteq\\{p_{1},\ldots,p_{n-1}\\}$ of size $k$
is $\begin{pmatrix}n-1\\\ k\end{pmatrix}$, so by the standard result in
equation (23) the $+1$ terms will cancel leaving only an alternating sum of
logarithms.

To simplify we shall write

$E_{n}(x)=\left((-1)^{n}\frac{\partial L^{\circ}}{\partial
x}(x,p_{2},\ldots,p_{n})\right)$ (32)

for $n\in\mathbb{N}$. Doing this gives us a sequence
$(E_{n}(x))_{n\in\mathbb{N}}$ removes the alternating factor $(-1)^{n}$,
allowing us to focus on the alternating sign over $m$.

For example

$E_{3}(x)=\log\frac{(p_{1}+x)(p_{2}+x)}{(p_{1}+p_{2}+x)(x)}.$

Note that all of the even subsets will now appear on the top of the fraction
and the odd subsets will appear on the bottom.

For the first case with $n=2$ we have

$\displaystyle\begin{split}\frac{\partial L^{\circ}}{\partial
x}(x,p_{2})&=E_{2}(x)\\\ &=\log\frac{x+p_{2}}{x}\end{split}$ (33)

which is clearly greater than 0 for all $x\in\mathbb{R}^{+}$. The successive
derivatives of $E_{2}(x)$ will continue to alternate in sign for
$x\in\mathbb{R}^{+}$ using the standard power rule.

As we also know that $L^{\circ}(x,p_{2})=L(x,p_{2})>0$, the result holds for
$n=2$. We now suppose that the statement is true for $n-1$.

We notice that

$E_{n}(x)=E_{n-1}(x)-E_{n-1}(x+p_{n})$ (34)

Hence

$\displaystyle\begin{split}&(-1)^{n}\frac{\partial^{m}L^{\circ}}{\partial
x^{m}}(x,p_{2},\ldots,p_{n})\\\ &=\frac{\partial^{m-1}}{\partial
x^{m-1}}E_{n}(x,p_{2},\ldots,p_{n})\\\ &=\frac{\partial^{m-1}}{\partial
x^{m-1}}E_{n-1}(x)-\frac{\partial^{m-1}}{\partial
x^{m-1}}E_{n-1}(x+p_{n})\end{split}$ (35)

However by assumption we have that

$(-1)^{m-2}\frac{\partial^{m-2}}{\partial x^{m-2}}E_{n-1}(x)>0$

Hence as the $m-2$-th partial derivative of $E_{n-1}$ has a given sign, we
have that the difference between the terms of equation (35) has the opposite
sign. That is,

$(-1)^{m-1}\frac{\partial^{m-1}}{\partial
x^{m-1}}E_{n}(x,p_{2},\ldots,p_{n})>0$ (36)

Now, using lemma 9 characterizing the interior loss at 0, and using that
$E_{n}$ is strictly positive (negative) for all $x\in\mathbb{R}^{+}$, the sign
of $L^{\circ}$ will be strictly negative (positive) for $x\in\mathbb{R}^{+}$.
Hence we have

$(-1)^{n}(-1)^{m}\frac{\partial^{m}L^{\circ}}{\partial
x^{m}}(x,p_{2}\ldots,p_{n})>0.$ (37)

This completes the inductive argument.

∎

### Proof of corollary 12

###### Proof.

We saw in lemma 9 that it is sensible to extend $L^{\circ}$ to
$\mathbb{R}^{+}\cup\\{0\\}$ with $L^{\circ}(p_{1},\ldots,p_{n})=0$ when any
$p_{i}=0$. Moreover, as $L^{\circ}$ is continuous as a function of $\tau$,
varies strictly monotonically by lemma 11, and is bounded at infinity by lemma
10, we must have that
$|L^{\circ}(p_{1},\ldots,p_{n-1},\tau)|\in[0,|L^{\circ}(p_{1},\ldots,p_{n-1})|)$.
∎

### Proof of theorem 15

We first state a small lemma which is a standard property of entropy. We will
make use of it to demonstrate that our measure is consistent with Yeung’s
$I$-measure.

######  Lemma 22.

Let $P_{1},\ldots,P_{k}$ be disjoint subsets forming a partition of $\Omega$
consisting of individual outcomes $\omega$ of probability $p_{\omega}$. Then

$L\left(\sum_{\omega\in P_{1}}p_{\omega},\ldots,\sum_{\omega\in
P_{k}}p_{\omega}\right)=L(\Omega)-\sum_{i=1}^{k}L(P_{i}).$ (38)

In particular, the expression of the left-hand side is equal to the measure of
the subset $\Delta(\Omega)\setminus\left(\bigcup_{i=1}^{k}B(P_{k})\right).$

###### Proof.

We first demonstrate the simple identity

$L(p_{1}+p_{2},p_{3},\ldots,p_{n})=L(p_{1},p_{2},\ldots,p_{n})-L(p_{1},p_{2}).$
(39)

Let $\Omega=\\{\omega_{1},\ldots,\omega_{N}\\}$. Then let $X$ be the random
variable with partition
$\\{\\{\omega_{1},\omega_{2}\\},\\{\omega_{3}\\},\ldots,\\{\omega_{N}\\}\\}$.
By definition we have

$L(p_{1},p_{2})=H(\Omega)-H(X)\\\
=L(p_{1},\ldots,p_{n})-L(p_{1}+p_{2},\ldots,p_{n}),$ (40)

giving the identity. The full result then follows by symmetry on the arguments
of $L$ and an inductive argument, sequentially decomposing sums into pairs. ∎

This result essentially states that the total loss of a certain variable
defined by the partition $\\{P_{1},\ldots,P_{k}\\}$ can be computed by
calculating the total loss of the entire outcome space and subtracting
boundaries internal to parts $P_{i}$.

We now proceed with the proof of the theorem.

###### Proof.

We will show that our definition of content agrees with i.) the entropy of
individual variables and ii.) the mutual information between two variables.
The case for $n$ variables follows inductively.

We will now show that for a variable $X$ with an event space with associated
probabilities $p_{1},\ldots,p_{n}$, that
$H(X)=L(p_{1},\ldots,p_{n})=L^{\circ}(\operatorname{\mathcal{C}}(X))$, the
measure of the content in $X$ (see equation (6)).

Inside of a possibly more refined partition given by outcomes in $\Omega$, we
can compute the entropy of $X$ by treating it as a partition
$P_{1},\ldots,P_{k}$ of the entire outcome space. In this case it is
equivalent to the expression in lemma 22. As mentioned after the lemma, this
corresponds to the measure of the set

$\Delta(\Omega)\,\setminus\,\left(\,\bigcup_{i=1}^{k}\,\left\\{B^{\circ}(S):S\subseteq
P_{i}\right\\}\right)=\operatorname{\mathcal{C}}(X).$ (41)

It can be seen that this is equivalent to the construction of
$\operatorname{\mathcal{C}}(X)$ in definition 13, as the only elements
remaining in $\Delta(\Omega)$ must contain outcomes spanning across
partitions. This completes i.).

The mutual information between two variables $X,Y$ is given by

$I(X;Y)=H(X)+H(Y)-H(X,Y)$ (42)

We have seen that $H(V)=L^{\circ}(\operatorname{\mathcal{C}}(V))$ for a random
variable $V$ inside of a refined space $\Omega$. Given two partitions $P$ and
$Q$ corresponding to $X$ and $Y$ respectively, the collection generated by
their intersections, $P_{i}\cap P_{j}$, is also a partition of $\Omega$,
corresponding to the joint random variable $(X,Y)$. This is a refinement of
the partitions of $X$ and $Y$.

In particular we have that $b\in\operatorname{\mathcal{C}}(X)$ implies
$b\in\operatorname{\mathcal{C}}(X,Y)$. Constructing a formal sum of elements
$b\in\operatorname{\mathcal{C}}(X,Y)$, we can extend the measure $L^{\circ}$
onto this formal sum to obtain

$I(X;Y)=L^{\circ}(\operatorname{\mathcal{C}}(X)+\operatorname{\mathcal{C}}(Y)-\operatorname{\mathcal{C}}(X,Y))=L^{\circ}(I)$
(43)

Where the formal sum
$I=\operatorname{\mathcal{C}}(X)+\operatorname{\mathcal{C}}(Y)-\operatorname{\mathcal{C}}(X,Y)$
will reflect the mutual information. We see that an atom
$b\in\operatorname{\mathcal{C}}(X,Y)$ does not appear in the formal sum $I$
unless $b\in\operatorname{\mathcal{C}}(X)\cap\operatorname{\mathcal{C}}(Y)$,
in which case it appears with coefficient $1$. As all terms in the formal sum
have coefficient $1$ or $0$, this formal sum also corresponds to the set of
atoms in $\operatorname{\mathcal{C}}(X)\cap\operatorname{\mathcal{C}}(Y)$.
Hence

$I(X;Y)=L^{\circ}(\operatorname{\mathcal{C}}(X)\cap\operatorname{\mathcal{C}}(Y)).$
(44)

That is, our logarithmic decomposition is consistent with standard Shannon
mutual information and, by extension, all higher co-informations. It is hence
a refinement of the $I$-measure of Yeung [14]. ∎

### Proof of theorem 17

###### Proof.

The common information variable $Z$ is unique up to isomorphism, so it
suffices to demonstrate that this variable $Z$ has its content
$\operatorname{\mathcal{C}}(Z)\subseteq\bigcap_{i}\operatorname{\mathcal{C}}(X_{i})$.

Given an outcome $\omega\in\Omega$, let $\omega$ be contained in the event
$X_{i}(\omega)$ in $X_{i}$. That is, $\omega$ is contained in one of the parts
$X_{i}(\omega)$ in the partition of $X_{i}$. By virtue of the definition of
the common information, we must have

$f_{i}(X_{i}(\omega))=f_{j}(X_{j}(\omega))\text{ for all
$i,j\in\\{1,\ldots,n\\}$}.$ (45)

We will now show the result in two steps. Firstly we show that the common
information variable induces a content in $\Delta(\Omega)$. Then we show that
this is contained in the intersection $C$.

Viewing the random variables as partitions of $\Omega$ and using the ordering
$A\leq B$ if $A$ is coarser than $B$, we obtain a lattice. Using the
restriction in equation (45), we can see that to compute the partition of $Z$
we must take the meet $X_{1}\land\cdots\land X_{r}$ of all variable partitions
$X_{i}$ in the lattice. In particular, the partition of $Z$ has the property
that $Z\leq\Omega$, and hence
$\operatorname{\mathcal{C}}(Z)\subseteq\Delta(\Omega)$, that is, we have the
atoms needed to describe $Z$ in $\Delta(\Omega)$. Note that
$\operatorname{\mathcal{C}}(Z)$ might be empty, in which case it corresponds
to the trivial random variable.

To show that $\operatorname{\mathcal{C}}(Z)$ is contained in the intersection
$C=\bigcap_{i}\operatorname{\mathcal{C}}(X_{i})$, let
$B^{\circ}(S)\in\operatorname{\mathcal{C}}(Z)$. By definition, $S$ crosses a
boundary in $Z$. As $Z$ is the finest partition which is coarser than
$X_{1},\ldots,X_{r}$, $S$ must cross a boundary in all $X_{i}$. That is,
$B^{\circ}(S)\in\bigcap_{i}\operatorname{\mathcal{C}}(X_{i})$. Hence
$\operatorname{\mathcal{C}}(Z)\subseteq C$.

Note that as the partition of $Z$ is unique, the content is also necessarily
unique, giving the result. ∎