# Privacy Leakage over Dependent Attributes in One-Sided Differential Privacy

This material is based on research sponsored by DARPA under agreement number
FA8750-16-2-0021. The U.S. Government is authorized to reproduce and
distribute reprints for Governmental purposes notwithstanding any copyright
notation thereon. The views and conclusions contained herein are those of the
authors and should not be interpreted as necessarily representing the official
policies or endorsements, either expressed or implied, of DARPA or the U.S.
Government. Phillip Lee, Kevin Smith P. Lee is with Honeywell.
<EMAIL_ADDRESS>Smith is with Tridium<EMAIL_ADDRESS>
###### Abstract

Providing a provable privacy guarantees while maintaining the utility of data
is a challenging task in many real-world applications. Recently, a new
framework called One-Sided Differential Privacy (OSDP) was introduced that
extends existing differential privacy approaches. OSDP increases the utility
of the data by taking advantage of the fact that not all records are
sensitive. However, the previous work assumed that all records are
statistically independent from each other. Motivated by occupancy data in
building management systems, this paper extends the existing one-sided
differential privacy framework. In this paper, we quantify the overall privacy
leakage when the adversary is given dependency information between the
records. In addition, we show how an optimization problem can be constructed
that efficiently trades off between the utility and privacy.

##  I Introduction

Integration of communication and sensing capabilities into an ever-increasing
array of physical systems enables intelligent automation services in many
applications including energy, building management and transportation [1].
However, the ubiquitous nature of connected sensors also increases the risk of
privacy breaches of individuals [2]. Maximizing the utility of the sensed data
while providing privacy guarantees to individuals has been an active area of
research in both academia and industry [3, 4].

In particular, privacy-driven access control [5] and differential privacy [6]
have been two promising areas of research. In general, the two approaches are
complimentary to each other. Access control mechanisms regulate who can access
potentially sensitive information according to pre-defined privacy rules. On
the other hand, differential privacy is designed for a query-response model
where randomized response algorithms are implemented in such a way that
responses are statistically indistinguishable independent of the individual’s
presence in the data set.

Differential privacy provides provable privacy guarantees based on the tunable
parameter $\epsilon\geq 0$, where smaller $\epsilon$ implies more privacy-
sensitive response. However, maintaining the utility of the released data even
for a relatively large value of $\epsilon$ is a challenging task [7]. The
steep decline of utility even for a small increase of $\epsilon$ is largely
due to the over-pessimistic assumption of differential privacy. In
differential privacy, the randomized response is designed such that inclusion
or exclusion of _any_ individual in the database should preserve statistical
similarity of the response. In addition, every record in the database is
treated as equally sensitive, resulting in decreased utility even when
$\epsilon$ is relatively large.

Recently, a new framework called one-sided differential privacy (OSDP) [8] has
been proposed to overcome this challenge. Unlike the existing differential
privacy, OSDP assumes that not all records are equally sensitive and increases
the utility of the released data by exploiting the release of non-sensitive
records.

In this paper, we study the privacy guarantees of OSDP in the context of
building management system. Specifically, we examine privacy implications of
occupancy data, use cases of occupancy data in the building management system,
and the effectiveness of OSDP in this context. We generalize the privacy
guarantees provided by OSDP to the case when records are statistically
dependent, which would enable more informed parameter tuning of OSDP by taking
into account the dependencies of records. We make the following specific
contributions:

  * •

We quantify the privacy leakage under OSDP when the records are statistically
dependent. We generalize the previous privacy guarantee in [8] against the
exclusion attack when the adversary is assumed to have dependency information
in the form of conditional probabilities between the records.

  * •

We present composition rules for the case of multiple queries as well as the
case when two applications that utilize different attributes are actively
exchanging obtained query responses. In both cases, we show that
multiplicative composition rules can be used to compute the privacy leakage.

  * •

Using the results obtained from the previous contributions, we show that the
total information leakage from the query responses under OSDP can be expressed
explicitly as a function of the privacy parameters. Using information-
theoretic metrics, we set up an optimization problem that efficiently trades
off between utility and privacy.

The paper is organized as follows. We review the related work in Section II.
Section III provides a summary of one-sided differential privacy and the
exclusion attack. The problem statement and motivation for this research are
given in Section IV. Our main results are presented in Section V. Section VI
concludes the paper.

##  II Related Work

Analysis of potential privacy leakage and mitigation strategies have been
active areas of research [9, 10]. Access control mechanisms for private data
have been studied in [5, 11]. In [5], the existing role-based access control
model is extended to incorporate complex privacy policies including purposes
and obligations while detecting potential conflicts in privacy policies.
Similarly in [11], a privacy-preserving access control mechanisms for a
relational database has been proposed by associating purpose information for
each data element.

Differential privacy [6] has gained attraction from the research community as
a promising framework that provides provable privacy guarantees. In
differential privacy, the query response is randomized in such a way that any
query response would be statistically similar in the presence or absence of
presence of any individual in the database. In addition to the rigorous
theoretical privacy guarantees, differential privacy allows the user to tune
the privacy parameter $\epsilon$ to trade-off between utility and privacy.

Differential privacy has been applied to building applications in [12, 3, 7]
in the context of streaming occupancy data. In [7], utility of the occupancy
data has been studied when varying values of $\epsilon$ have been applied to
the data. While [7] finds that information at the aggregated level are mainly
preserved under differential privacy, preserving the utility of data at the
individual level remains a challenge.

Recently, OSDP [8] has been proposed to overcome this challenge. However, the
privacy guarantee when the records in the database are statistically dependent
remains an open problem as noted in [8].

##  III Model and Preliminaries

###  III-A One-Sided Differential Privacy (OSDP) and the Exclusion Attack

One main drawback of differential privacy [6] is that it treats every record
to be sensitive. Such over-pessimistic assumption will lead to severe
degradation of the utility of the released data. Often, not all records in the
database would be sensitive. For simplicity, it is assumed that there exists a
policy function ${P}$ which classifies each record as either sensitive
($P(r)=0$) or non-sensitive ($P(r)=1$).

One approach is to not release a sensitive record as a query answer by
returning nothing or rejecting the query [13] and by releasing only the non-
sensitive records as responses to queries. However, such an approach will
immediately result in the adversary inferring that the non-released record is
sensitive, which results in privacy leakage for the owner of the non-released
record.

Such a privacy breach resulting from not releasing certain records is referred
to as the _exclusion attack_ [8]. One quantification of measuring the
robustness of a query answering mechanism $\mathcal{M}$ against the exclusion
attack is defined in [8]. Range of a mechanism $\mathcal{M}$ is the set of all
possible outcomes of query responses.

###### Definition 1

($\epsilon$-Freedom from exclusion attacks) A mechanism $\mathcal{M}$
satisfies $\epsilon$-freedom from exclusion attacks for policy $P$ and and
parameter $\epsilon$ if:

$\displaystyle\forall x:P(x)=0\mbox{ and
}\mathcal{O}\subseteq\mbox{range}(\mathcal{M})$
$\displaystyle\frac{\mathbb{P}(r=x|\mathcal{M}(D)\in\mathcal{O})}{\mathbb{P}(r=y|\mathcal{M}(D)\in\mathcal{O})}\leq
e^{\epsilon}\frac{\mathbb{P}(r=x)}{\mathbb{P}(r=y)}$

where $r$ is the target record in the database $D$, $x$ is the value that
makes the record sensitive, $y$ is another value in the domain.

Definition 1 states that even after observing the query answer, the ratio of
the posterior probabilities of whether the target record was sensitive or some
other value should remain _similar_ to that of the ratio of prior
probabilities given to the adversary.

In this paper, we focus on one specific mechanism of achieving OSDP called
One-Sided Differential Privacy Randomized Response (OSDPRR). OSDPRR is an
algorithm to release true data [8] while preserving privacy. The following
definition describes the OSDPRR.

###### Definition 2

(ODSPRR) For a record $r$, release the record with probability
$1-e^{-\epsilon}$ where $\epsilon>0$ if it is non-sensitive. If the record is
sensitive, then do not release the record.

It is easy to see why OSDPRR would provide mitigation against the exclusion
attack. The fact that a record has not been released does not automatically
implicate that the record was sensitive since there is a non-zero probability
of $e^{-\epsilon}$ that a non-sensitive record would not be released as well.

In [8], it was proved that OSDPRR with parameter $\epsilon$ satisfies
$\epsilon$-freedom from exclusion attacks under the assumption that _records
in the database are statistically independent from each other_. In this paper,
we are interested in the case when this assumption does not hold, as often is
the case in many applications.

##  IV Problem Statement and Motivation

OSDP is an attractive solution for many practical applications due to its ease
of implementation and provable privacy guarantees it provides. One application
we studied is a building management system as part of the TIPPERS project [3].

Figure 1 shows an example of an occupancy pattern for a space in an office
building generated by the Building Analytics App [7]. Occupancy level 1
indicates that the particular space was occupied and 0 indicates otherwise. A
quick inspection of the plot reveals that one can infer many attributes
regarding the occupant of the space. For example, one can infer the starting
time of the employee by examining when the occupancy level turns to 1 at the
beginning of the day as well as when the employee leaves the office. In
addition, one can also infer how many times the employee leaves the space and
how long it takes for the employee to come back to the space on average.

Figure 1: Occupancy pattern of an office space generated using Building
Analytics App [7]. Occupancy level 1 indicates that the space is occupied and
level 0 indicates the space is not occupied.

Such attributes can be useful in many building applications including energy
as well as space optimization. For example, a commercial building typically
has a default work hours setting (ex: 8:00 am to 5:00 pm) when all lights are
turned on. However, a lighting control coupled with occupancy sensors would
enable more energy efficient lighting control [14]. This could be done by
looking at average start time per space, and if the space does not become
occupied after the default starting hour on average (ex: 9:00 am), then the
lighting control can customize the lighting schedule to either match the
average starting time of the space or only turn on the light based on the
detected occupancy data.

Such lighting control will require average starting times of spaces occupancy
to customize its schedule. However, the lighting control would not require the
average occupancy level of spaces during the default work hours. On the other
hand, the average occupancy level (fraction of times when the space is
occupied during the work hour) information would be required for other types
of applications including space optimization [15].

While the occupancy data and the attributes that pertain to the data can
enable more efficient operation of buildings, many of these attributes are
also potentially sensitive information for the occupants. One potential
solution to provide privacy to the occupants while enabling these applications
is OSDPRR. Given that different applications require different sets of
attributes to perform their respective functionalities, OSDPRR can be
implemented per attribute. However, as often is the case, there is no
guarantee that the records from different attributes are statistically
independent from each other. Moreover, it is also possible that two or more
applications are colluding and actively exchanging information obtained from
queries.

Figure 2: Illustration of an use case of occupancy data for building
management. The dashed lines indicate queries and responses from multiple
applications, and the red solid lines indicate additional information
including the dependency information between the attributes as well as the
exchanged queries responses between colluding applications.

This implies that when releasing the data under OSDP, the query response
mechanisms needs to take into account additional privacy leakage through
statistical dependency as well as potential colluding scenarios. Figure 2
illustrates an example of occupancy driven building applications where each
application will be given the query response as well as additional information
from statistical dependency of records and other query responses from
exchanging information with other applications.

In the following Section, we will show how to quantify privacy leakage from
such additional information under OSDPRR.

##  V Privacy Leakage over Dependent Attributes

In OSDPRR, there are only two possible outcomes: the record is either released
or not. Throughout this paper, we denote

$M_{i}=\left\\{\begin{array}[]{cl}1,&\mbox{if $r_{i}$ is released.}\\\
0,&\mbox{if $r_{i}$ is suppressed.}\end{array}\right.$

In addition, we define a Bernoulli random variable to indicate whether a given
record $r_{i}$ is sensitive or not.

$X_{i}=\left\\{\begin{array}[]{cl}1,&\mbox{if $r_{i}$ takes value that makes
$r_{i}$ not sensitive.}\\\ 0,&\mbox{else.}\end{array}\right.$

For the later results, we first quantify the robustness of the OSDPRR against
the exclusion attack on record $r_{i}$ when the record is not released.

###### Theorem 1

The posterior probability ratio of $X_{i}$ given that $\mathcal{M}_{i}=0$ is
given as

$\frac{\mathbb{P}(X_{i}=0|\mathcal{M}_{i}=0)}{\mathbb{P}(X_{i}=1|\mathcal{M}_{i}=0)}=e^{\epsilon_{i}}\frac{\mathbb{P}(X_{i}=0)}{\mathbb{P}(X_{i}=1)}$
(1)

Moreover, the posterior probability ratio of $X_{i}$ after $r_{i}$ is not
released after $n$ independent consecutive queries is given as

$\frac{\mathbb{P}(X_{i}=0|\mathcal{M}_{i}^{n}=0)}{\mathbb{P}(X_{i}=1|\mathcal{M}_{i}^{n}=0)}=e^{n\epsilon_{i}}\frac{\mathbb{P}(X_{i}=0)}{\mathbb{P}(X_{i}=1)}$
(2)

where $\epsilon_{i}$ is the parameter chosen for record $r_{i}$ under OSDPRR.
In other words, $r_{i}$ will be released with probability $1-e^{\epsilon_{i}}$
if $r_{i}$ is not sensitive.

###### Proof:

The proof can be found in [8]. ∎

We are interested in how much information the adversary obtains regarding the
sensitivity of $r_{j}$ drawn from another attribute when the statistically
dependent record $r_{i}$ is not released or released.

###  V-A One Application with Dependency Information

First, we consider the case when one application obtains $\mathcal{M}_{i}$ and
wants to infer the sensitivity of $X_{j}$ where record $r_{j}$ is used by
another application.

###### Lemma 1

$X_{j}$ is conditionally independent to $\mathcal{M}_{i}$ given $X_{i}$

###### Proof:

It is obvious that

$\mathbb{P}(\mathcal{M}_{i}|X_{i},X_{j})=\mathbb{P}(\mathcal{M}_{i}|X_{i})$

since $\mathcal{M}_{i}$ is a function that is determined only by $X_{i}$.
Rewriting the above equation, we obtain

$\frac{\mathbb{P}(\mathcal{M}_{i},X_{i},X_{j})}{\mathbb{P}(X_{i},X_{j})}=\frac{\mathbb{P}(X_{j}|\mathcal{M}_{i},X_{i})\mathbb{P}(\mathcal{M}_{i},X_{i})}{\mathbb{P}(X_{i},X_{j})}=\frac{\mathbb{P}(\mathcal{M}_{i},X_{i})}{\mathbb{P}(X_{i})}$

Rearranging the last equality and applying Bayes’ theorem, we obtain

$\mathbb{P}(X_{j}|\mathcal{M}_{i},X_{i})=\mathbb{P}(X_{j}|X_{i})$ (3)

∎

The intuition is that given $X_{i}$, there is no additional information that
can be obtained from $\mathcal{M}_{i}$ regarding $X_{j}$. The following
theorem quantifies the privacy leakage on $X_{j}$ when the record $r_{i}$ is
not released.

###### Theorem 2

Let $\delta_{1}^{(ij)}=\mathbb{P}(X_{i}=0|X_{j}=0)$ and
$\delta_{2}^{(ij)}=\mathbb{P}(X_{i}=0|X_{j}=1)$, then the information leakage
on $X_{j}$ from not releasing record $r_{i}$ can be quantified as

$\displaystyle\frac{\mathbb{P}(X_{j}=0|\mathcal{M}_{i}=0)}{\mathbb{P}(X_{j}=1|\mathcal{M}_{i}=0)}=\frac{\delta_{1}^{(ij)}(e^{\epsilon_{i}}-1)+1}{\delta_{2}^{(ij)}(e^{\epsilon_{i}}-1)+1}\cdot\frac{\mathbb{P}(X_{j}=0)}{\mathbb{P}(X_{j}=1)}$
(4)

where $\epsilon_{i}$ is the parameter for the OSDPRR for record $r_{i}$.

###### Proof:

Posterior probability ratio of $X_{j}$ given $\mathcal{M}_{i}=0$ can be
written as the following.

$\displaystyle\frac{\mathbb{P}(X_{j}=0|\mathcal{M}_{i}=0)}{\mathbb{P}(X_{j}=1|\mathcal{M}_{i}=0)}$
(5) $\displaystyle=$
$\displaystyle\frac{\sum_{x_{i}}\mathbb{P}(X_{i}=x_{i}|\mathcal{M}_{i}=0)\mathbb{P}(X_{j}=0|X_{i}=x_{i})}{\sum_{x_{i}}\mathbb{P}(X_{i}=x_{i}|\mathcal{M}_{i}=0)\mathbb{P}(X_{j}=1|X_{i}=x_{i})}$
(6)

This is because $\mathbb{P}(X_{j}=x_{j}|\mathcal{M}_{i}=0)$ can be decomposed
as

$\displaystyle\mathbb{P}(X_{j}=x_{j}|\mathcal{M}_{i}=0)$ $\displaystyle=$
$\displaystyle\mathbb{P}(X_{j}=x_{j},X_{i}=1|\mathcal{M}_{i}=0)$
$\displaystyle+$
$\displaystyle\mathbb{P}(X_{j}=x_{j},X_{i}=0|\mathcal{M}_{i}=0)$

and
$\mathbb{P}(X_{j}=x_{j},X_{i}=x_{i}|\mathcal{M}_{i}=0)=\mathbb{P}(X_{i}=x_{i}|\mathcal{M}_{i}=0)\cdot\mathbb{P}(X_{j}=x_{j}|X_{i}=x_{i},\mathcal{M}_{i}=0)$.
Moreover, from Lemma 1, we have
$\mathbb{P}(X_{j}=x_{j}|X_{i}=x_{i},\mathcal{M}_{i}=0)=\mathbb{P}(X_{j}=x_{j}|X_{i}=x_{i})$.

Dividing both the numerator and denominator of expression (6) by
$\mathbb{P}(X_{i}=1|\mathcal{M}_{i}=0)$, and applying equation (1), we obtain

$\displaystyle\frac{\mathbb{P}(X_{j}=0|\mathcal{M}_{i}=0)}{\mathbb{P}(X_{j}=1|\mathcal{M}_{i}=0)}=$
(7)
$\displaystyle\frac{e^{\epsilon_{i}}\frac{\mathbb{P}(X_{i}=0)}{\mathbb{P}(X_{i}=1)}\mathbb{P}(X_{j}=0|X_{i}=0)+\mathbb{P}(X_{j}=0|X_{i}=1)}{e^{\epsilon_{i}}\frac{\mathbb{P}(X_{i}=0)}{\mathbb{P}(X_{i}=1)}\mathbb{P}(X_{j}=1|X_{i}=0)+\mathbb{P}(X_{j}=1|X_{i}=1)}$
(8)

However, the first terms in both numerator and denominator can be expressed as

$\displaystyle
e^{\epsilon_{i}}\frac{\mathbb{P}(X_{i}=0)}{\mathbb{P}(X_{i}=1)}\cdot\mathbb{P}(X_{j}=x_{j}|X_{i}=0)$
(9) $\displaystyle=$ $\displaystyle
e^{\epsilon_{i}}\frac{\mathbb{P}(X_{i}=0)}{\mathbb{P}(X_{i}=1)}\frac{\mathbb{P}(X_{i}=0|X_{j}=x_{j})\mathbb{P}(X_{j}=x_{j})}{\mathbb{P}(X_{i}=0)}$
(10) $\displaystyle=$ $\displaystyle
e^{\epsilon_{i}}\frac{\mathbb{P}(X_{i}=0|X_{j}=x_{j})}{\mathbb{P}(X_{i}=1)}\mathbb{P}(X_{j}=x_{j})$
(11)

Replacing the first term of both the numerator and the denominator of (8) with
the expression (11), we obtain the desired result. ∎

Here are some observations from Theorem 2. If $\epsilon_{i}=0$, then the
record $r_{i}$ is not released even if it is not sensitive. This results in
$\frac{\delta_{1}^{(ij)}(e^{\epsilon_{i}}-1)+1}{\delta_{2}^{(ij)}(e^{\epsilon_{i}}-1)+1}=1$.
Therefore, no information is obtained regarding $X_{j}$, Also, if $X_{i}$ and
$X_{j}$ are independent, then $\delta_{1}^{(ij)}=\delta_{2}^{(ij)}$, which
yields the same result. On other other hand, as $\epsilon_{i}\to\infty$
($r_{i}$ is released with probability 1 if it is not sensitive), then
$\lim_{\epsilon_{i}\to\infty}\frac{\delta_{1}^{(ij)}(e^{\epsilon_{i}}-1)+1}{\delta_{2}^{(ij)}(e^{\epsilon_{i}}-1)+1}\to\frac{\delta_{1}^{(ij)}}{\delta_{2}^{(ij)}}$.
Therefore, privacy guarantees regarding $X_{j}$ is completely determined by
the statistical relationship between $X_{i}$ and $X_{j}$.

The following Corollary quantifies the information leakage of $X_{j}$ when
$r_{i}$ is not released for $n$ consecutive queries under OSDPRR with
parameter $\epsilon_{i}$.

###### Corollary 1

Posterior probability ratio of $X_{j}$ given $\mathcal{M}_{i}^{n}=0$ is given
as

$\displaystyle\frac{\mathbb{P}(X_{j}=0|\mathcal{M}_{i}^{n}=0)}{\mathbb{P}(X_{j}=1|\mathcal{M}_{i}^{n}=0)}=\frac{\delta_{1}^{(ij)}(e^{n\epsilon_{i}}-1)+1}{\delta_{2}^{(ij)}(e^{n\epsilon_{i}}-1)+1}\cdot\frac{\mathbb{P}(X_{j}=0)}{\mathbb{P}(X_{j}=1)}$
(12)

where $\delta_{1}^{(ij)}$ and $\delta_{2}^{(ij)}$ are defined in Theorem 2.

###### Proof:

The proof is straightforward from the proof of Theorem 2 by replacing
$\mathcal{M}_{i}$ with $\mathcal{M}_{i}^{n}$ and by applying equation (2)
instead of equation (1). ∎

For completeness, we now derive the posterior probability ratio when
$\mathcal{M}_{i}=1$.

###### Theorem 3

The posterior probability ratio of $X_{j}$ given that record $r_{i}$ is
released is given as

$\frac{\mathbb{P}(X_{j}=0|\mathcal{M}_{i}=1)}{\mathbb{P}(X_{j}=1|\mathcal{M}_{i}=1)}=\frac{1-\delta_{1}^{(ij)}}{1-\delta_{2}^{(ij)}}\cdot\frac{\mathbb{P}(X_{j}=0)}{\mathbb{P}(X_{j}=1)}$
(13)

###### Proof:

The posterior probability ratio of $X_{j}$ can be written as

$\displaystyle\frac{\mathbb{P}(X_{j}=0|\mathcal{M}_{i}=1)}{\mathbb{P}(X_{j}=1|\mathcal{M}_{i}=1)}$
(14) $\displaystyle=$
$\displaystyle\frac{\mathbb{P}(X_{j}=0,X_{i}=1,\mathcal{M}_{i}=1)}{\mathbb{P}(X_{j}=1,X_{i}=1,\mathcal{M}_{i}=1)}$
(15) $\displaystyle=$
$\displaystyle\frac{\mathbb{P}(X_{i}=1|X_{j}=0)}{\mathbb{P}(X_{i}=1|X_{j}=1)}\cdot\frac{\mathbb{P}(X_{j}=0)}{\mathbb{P}(X_{j}=1)}$
(16)

where the first equality is from the fact that the probability of joint event
of $X_{i}=0$ and $\mathcal{M}_{i}=1$ is zero, and the second inequality is due
to the fact that $\mathcal{M}_{i}$ is conditionally independent of $X_{j}$
given $X_{i}$. ∎

Theorems 2, 3 and Corollary 1 imply that the application that utilizes record
$r_{i}$ can infer the likely sensitivity of $r_{j}$ from another attribute
given additional information in the form of conditional probabilities between
$X_{i}$ and $X_{j}$.

###  V-B Colluding Applications with Dependency Information

We now consider the case when colluding applications are actively exchanging
information. In this case, an application will not only have $\mathcal{M}_{i}$
that it has obtained from a query but also $\mathcal{M}_{j}$ which is obtained
from another application along with the dependency information.

###### Theorem 4

The posterior probability ratio of $X_{j}$ given $\mathcal{M}_{i}=0$ and
$\mathcal{M}_{j}=0$ is given as

$\frac{\mathbb{P}(X_{j}=0|\mathcal{M}_{i}=0,\mathcal{M}_{j}=0)}{\mathbb{P}(X_{j}=1|\mathcal{M}_{i}=0,\mathcal{M}_{j}=0)}=f_{1}^{(ij)}(\epsilon_{i})e^{\epsilon_{j}}\frac{\mathbb{P}(X_{j}=0)}{\mathbb{P}(X_{j}=1)}$

and

$\frac{\mathbb{P}(X_{j}=0|\mathcal{M}_{i}=1,\mathcal{M}_{j}=0)}{\mathbb{P}(X_{j}=1|\mathcal{M}_{i}=1,\mathcal{M}_{j}=0)}=f_{2}e^{\epsilon_{j}}\frac{\mathbb{P}(X_{j}=0)}{\mathbb{P}(X_{j}=1)}$

where $f_{1}^{(ij)}(\epsilon_{i})$ and $f_{2}^{(ij)}$ are defined as

$f_{1}^{(ij)}(\epsilon_{i})=\frac{\delta_{1}^{(ij)}(e^{\epsilon_{i}}-1)+1}{\delta_{2}^{(ij)}(e^{\epsilon_{i}}-1)+1},f_{2}^{(ij)}=\frac{1-\delta_{1}^{(ij)}}{1-\delta_{2}^{(ij)}}$
(17)

and $\epsilon_{i}$ and $\epsilon_{j}$ are parameters of OSDPRR for records
$r_{i}$ and $r_{j}$ respectively.

###### Proof:

In general, the posterior probability ratio can be written as

$\displaystyle\frac{\mathbb{P}(X_{j}=0|\mathcal{M}_{i}=m_{i},\mathcal{M}_{j}=m_{j})}{\mathbb{P}(X_{j}=1|\mathcal{M}_{i}=m_{i},\mathcal{M}_{j}=m_{j})}$
(18) $\displaystyle=$
$\displaystyle\frac{\mathbb{P}(X_{j}=0,\mathcal{M}_{i}=m_{i},\mathcal{M}_{j}=m_{j})}{\mathbb{P}(X_{j}=1,\mathcal{M}_{i}=m_{i},\mathcal{M}_{j}=m_{j})}$
(19) $\displaystyle=$
$\displaystyle\frac{\mathbb{P}(X_{j}=0|\mathcal{M}_{i}=m_{i})}{\mathbb{P}(X_{j}=1|\mathcal{M}_{i}=m_{i})}\cdot\frac{\mathbb{P}(M_{j}=m_{j}|X_{j}=0)}{\mathbb{P}(M_{j}=m_{j}|X_{j}=1)}$
(20)

where the second equality is from the chain rule and the fact that
$\mathcal{M}_{j}$ is conditionally independent to $\mathcal{M}_{i}$ given
$X_{j}$. The first term of equation (20) is derived from Theorem 2 for
$m_{i}=0$ and the second term is $e^{\epsilon_{j}}$ from the definition of
OSDPRR for the case of $m_{j}=0$. Similarly the case when $\mathcal{M}_{i}=1$
is derived in Theorem 3. ∎

Theorem 4 shows that similar to the case of multiple queries shown in (2), the
same multiplicative composition rule holds for the case of two colluding
applications.

It is interesting to note that $f_{1}^{(ij)}(\epsilon_{i})$ or $f_{2}^{(ij)}$
defined in Theorem 4 is not necessarily greater than or equal to 1 unlike the
multiplicative term $e^{\epsilon_{i}}$ in basic OSDP shown in (1). For the
case when $\delta_{1}^{(ij)}<\delta_{2}^{(ij)}$,
$f_{1}^{(ij)}(\epsilon_{i})<1$ for all $\epsilon_{i}\geq 0$. This implies that
when given two pieces of information $\mathcal{M}_{i}=0,\mathcal{M}_{j}=0$, it
is possible to construct cases where the term
$f_{1}^{(ij)}(\epsilon_{i})e^{\epsilon_{j}}$ is approximately equal to 1. At a
high level, $\mathcal{M}_{j}=0$ increases the likelihood of $X_{j}$ being 0.
At the same time, having $\mathcal{M}_{i}=0$ will increase the likelihood of
$X_{i}=0$, but $X_{i}$ being 0 may increase the likelihood of $X_{j}=0$. In
other words, the two pieces of information $\mathcal{M}_{i}$ and
$\mathcal{M}_{j}$ may cancel each other’s effect on the inference of $X_{j}$.
Similarly, the same argument can be made when
$\delta_{1}^{(ij)}<\delta_{2}^{(ij)}$ for the term
$f_{2}^{(ij)}e^{\epsilon_{j}}$.

On the other hand, for the case when $\delta_{1}^{(ij)}>\delta_{2}^{(ij)}$,
the two pieces of information $\mathcal{M}_{i}=\mathcal{M}_{j}=0$ reinforces
each other and result in higher likelihood of $X_{j}=0$.

###  V-C Choosing Privacy Parameters

Having higher values of $\epsilon_{i}$s will increase the utility of the data
since non-sensitive records will be released with higher probabilities.
However, when choosing a value of $\epsilon_{i}$, one needs to consider not
only the information leakage of $X_{i}$ but also overall information leakage
of $X_{j}$ through $\mathcal{M}_{i}$.

One established metric to quantify the average information leakage is mutual
information [16]. We define the overall information leakage from
$\mathcal{M}_{i}$ as $I_{i}$, mathematically defined as

$I_{i}(\epsilon_{i})=I(X_{i};\mathcal{M}_{i})+\sum_{j}I(X_{j};\mathcal{M}_{i})$
(21)

In other words, $I_{i}$ is the sum of all mutual information between $X_{i}$,
$X_{j}$ and $\mathcal{M}_{i}$. The term $I_{i}(\epsilon_{i})$ can be computed
using the results derived in the previous subsections V-A and V-B. The first
term can be computed as

$I(X_{i};\mathcal{M}_{i})=H(X_{i})-\sum_{m_{i}}H(X_{i}|\mathcal{M}_{i}=m_{i})\mathbb{P}(\mathcal{M}_{i}=m_{i})$

where $H(X_{i})$ and $H(X_{i}|\mathcal{M}_{i}=m_{i})$ are defined as [16]

$\displaystyle
H(X_{i})=-\sum_{x_{i}}\mathbb{P}(X_{i}=x_{i})\log\mathbb{P}(X_{i}=x_{i}),$
$\displaystyle H(X_{i}|\mathcal{M}_{i}=m_{i})=$
$\displaystyle-\sum_{x_{i}}\mathbb{P}(X_{i}=x_{i}|\mathcal{M}_{i}=m_{i})\log\mathbb{P}(X_{i}=x_{i}|\mathcal{M}_{i}=m_{i})$

and $\mathbb{P}(\mathcal{M}_{i}=m_{i})$ can be computed as

$\displaystyle\mathbb{P}(\mathcal{M}_{i}=0)=$
$\displaystyle\mathbb{P}(\mathcal{M}_{i}=0|X_{i}=0)\mathbb{P}(X_{i}=0)$
$\displaystyle+$
$\displaystyle\mathbb{P}(\mathcal{M}_{i}=0|X_{i}=1)\mathbb{P}(X_{i}=1)$
$\displaystyle=$
$\displaystyle\mathbb{P}(X_{i}=0)+e^{-\epsilon_{i}}\mathbb{P}(X_{i}=1)$

and similarly,

$\displaystyle\mathbb{P}(\mathcal{M}_{i}=1)=(1-e^{-\epsilon_{i}})\mathbb{P}(X_{i}=1)$

For simplicity, denote $\mathbb{P}(X_{i}=0)=\theta_{i}$. Then, given these
equations, we can simplify $I(X_{i};\mathcal{M}_{i})$ as

$I(X_{i};\mathcal{M}_{i})=H(X_{i})-H_{2}(\theta_{1}^{(ii)})\mathbb{P}(\mathcal{M}_{i}=0)$

where
$\theta_{1}^{(ii)}=\frac{\theta_{i}}{e^{-\epsilon_{i}}(1-\theta_{i})+\theta_{i}}$,
and $H_{2}(\theta)$ is the binary entropy defined as

$H_{2}(\theta)=-\theta\log\theta-(1-\theta)\log(1-\theta)$

Similarly, $I(X_{j};\mathcal{M}_{i})$ is given as

$\displaystyle I(X_{j};\mathcal{M}_{i})$ $\displaystyle=$ $\displaystyle
H(X_{j})-H_{2}(\theta_{1}^{(ij)})(\theta_{i}+e^{-\epsilon_{i}}(1-\theta_{i}))$
$\displaystyle-$ $\displaystyle
H_{2}(\theta_{2}^{(ij)})(1-e^{-\epsilon_{i}})(1-\theta_{i})$

where $\theta_{j}=\mathbb{P}(X_{j}=0)$ and $\theta_{1}^{(ij)}$ and
$\theta_{2}^{(ij)}$ can be computed from equations in Theorems 2 and 3 given
as

$\frac{\theta_{1}^{(ij)}}{1-\theta_{1}^{(ij)}}=f_{1}^{(ij)}(\epsilon_{i})\frac{\theta_{j}}{1-\theta_{j}},\frac{\theta_{2}^{(ij)}}{1-\theta_{2}^{(ij)}}=f_{2}^{(ij)}\frac{\theta_{j}}{1-\theta_{j}}$

Therefore, $I_{i}(\epsilon_{i})$ can be written explicitly as a function of
$\epsilon_{i}$. Given this, one possible optimization problem that trades off
between utility and privacy can be given as

$\displaystyle\mbox{max.}\sum_{i}\epsilon_{i}$ $\displaystyle\mbox{subject to
}\sum_{i}I_{i}(\epsilon_{i})\leq T,\epsilon_{i}\geq 0$

where $T$ is some threshold value predefined by the query engine. The above
optimization problem states that the sum of the $\epsilon_{i}$ values should
be maximized subject to the constraint that the total information leakage is
less than or equal to some threshold value. It should be noted that the
optimization problem is not necessarily a convex optimization problem [17].
This is because $f_{1}^{(ij)}(\epsilon_{i})$ is not necessarily a convex nor
concave function for all values of $\epsilon_{i}$. However, as long as the
dependency information do not rapidly change over time, the optimization
problem can be solved offline once and the values obtained can be used for a
prolonged period of time until the dependency information has significantly
changed. Finding a convex relaxation that does provide provable optimality
bound will be part of future work.

##  VI Conclusions

In this paper, we studied the privacy leakage in ODSP when the records are
statistically dependent. We showed that the robustness against the exclusion
attack can be quantified in a closed-form in the case of a single query as
well as the case of multiple independent queries.

We also considered the case when the applications are actively colluding with
each other by exchanging query responses and quantified the privacy leakage.
We showed that multiplicative composition rule can be derived from two pieces
of information to quantify the overall privacy leakage.

Finally, we set up an optimization framework that trades-off between the
utility and the privacy leakage of data.

While this paper studied the overall information leakage in terms of
sensitivity of attributes denoted as $X_{i}$, extending the approach to
describe the complete conditional distribution space of a dependent attribute
is an interesting future work. In addition, we will investigate how the
privacy leakage change when only partial dependency information is given to
the adversary.

## References

  * [1] J. Gubbi, R. Buyya, S. Marusic, and M. Palaniswami, “Internet of things (iot): A vision, architectural elements, and future directions,” _Future generation computer systems_ , vol. 29, no. 7, pp. 1645–1660, 2013.
  * [2] D. Kozlov, J. Veijalainen, and Y. Ali, “Security and privacy threats in iot architectures,” in _Proceedings of the 7th International Conference on Body Area Networks_. ICST (Institute for Computer Sciences, Social-Informatics and …, 2012, pp. 256–262.
  * [3] S. Mehrotra, A. Kobsa, N. Venkatasubramanian, and S. R. Rajagopalan, “Tippers: A privacy cognizant iot environment,” _IEEE International Conference on Pervasive Computing and Communication Workshops (PerCom Workshops)_ , pp. 1–6, 2016.
  * [4] Y. Agarwal, B. Balaji, R. Gupta, J. Lyles, M. Wei, and T. Weng, “Occupancy-driven energy management for smart building automation,” in _Proceedings of the 2nd ACM workshop on embedded sensing systems for energy-efficiency in building_. ACM, 2010, pp. 1–6.
  * [5] Q. Ni, E. Bertino, J. Lobo, C. Brodie, C.-M. Karat, J. Karat, and A. Trombeta, “Privacy-aware role-based access control,” _ACM Transactions on Information and System Security (TISSEC)_ , vol. 13, no. 3, p. 24, 2010.
  * [6] C. Dwork, “Differential privacy,” _Encyclopedia of Cryptography and Security_ , pp. 338–340, 2011.
  * [7] S. Ghayyur, Y. Chen, R. Yus, A. Machanavajjhala, M. Hay, G. Miklau, and S. Mehrotra, “Iot-detective: Analyzing iot data under differential privacy,” in _Proceedings of the 2018 International Conference on Management of Data_. ACM, 2018, pp. 1725–1728.
  * [8] S. Doudalis, I. Kotsogiannis, S. Haney, A. Machanavajjhala, and S. Mehrotra, “One-sided differential privacy,” _arXiv preprint arXiv:1712.05888_ , 2017\.
  * [9] A. Ukil, S. Bandyopadhyay, and A. Pal, “Iot-privacy: To be private or not to be private,” _IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_ , pp. 123–124, 2014.
  * [10] C. M. Medaglia and A. Serbanati, “An overview of privacy and security issues in the internet of things,” in _The internet of things_. Springer, 2010, pp. 389–395.
  * [11] J.-W. Byun, E. Bertino, and N. Li, “Purpose based access control of complex data for privacy protection,” in _Proceedings of the tenth ACM symposium on Access control models and technologies_. ACM, 2005, pp. 102–110.
  * [12] Y. Chen, A. Machanavajjhala, M. Hay, and G. Miklau, “PeGaSus: Data-adaptive differentially private stream processing,” in _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_. ACM, 2017, pp. 1375–1388.
  * [13] S. Rizvi, A. Mendelzon, S. Sudarshan, and P. Roy, “Extending query rewriting techniques for fine-grained access control,” in _Proceedings of the 2004 ACM SIGMOD international conference on Management of data_. ACM, 2004, pp. 551–562.
  * [14] R. J. Thomas, N. A. Anderson, S. G. Donaldson, and M. A. Behar, “Building management system,” Jul. 28 2009, uS Patent 7,567,844.
  * [15] A. V. Mahasenan, H. Khurana, A. Kulkarni, and J. S. Puri, “Building management using location information,” Dec. 13 2018, uS Patent App. 15/843,958.
  * [16] T. M. Cover and J. A. Thomas, _Elements of information theory_. John Wiley & Sons, 2012.
  * [17] S. Boyd and L. Vandenberghe, _Convex optimization_. Cambridge university press, 2004.


1072 Research

# Assessing Graphical Perception of Image Embedding Models
using Channel Effectiveness

Soohyun Lee
Seoul National University  e-mail<EMAIL_ADDRESS>Minsuk Chang
Seoul National University  e-mail<EMAIL_ADDRESS>Seokhyeon Park
Seoul National University  e-mail<EMAIL_ADDRESS>Jinwook Seo
Seoul National University  e-mail<EMAIL_ADDRESS>
###### Abstract

Recent advancements in vision models have greatly improved their ability to
handle complex chart understanding tasks, like chart captioning and question
answering. However, it remains challenging to assess how these models process
charts. Existing benchmarks only roughly evaluate model performance without
evaluating the underlying mechanisms, such as how models extract image
embeddings. This limits our understanding of the model’s ability to perceive
fundamental graphical components. To address this, we introduce a novel
evaluation framework to assess the graphical perception of image embedding
models. For chart comprehension, we examine two main aspects of channel
effectiveness: accuracy and discriminability of various visual channels.
Channel accuracy is assessed through the linearity of embeddings, measuring
how well the perceived magnitude aligns with the size of the stimulus.
Discriminability is evaluated based on the distances between embeddings,
indicating their distinctness. Our experiments with the CLIP model show that
it perceives channel accuracy differently from humans and shows unique
discriminability in channels like length, tilt, and curvature. We aim to
develop this work into a broader benchmark for reliable visual encoders,
enhancing models for precise chart comprehension and human-like perception in
future applications.

###### keywords:

Graphical perception, channel effectiveness, image embeddings, clip

Introduction

Nowadays, emerging vision models are strongly influencing the domain of
visualization, especially in handling charts. Image encoders are employed to
automatically classify chart images [32, 3], explain charts [4, 34], or answer
chart-based questions [16, 28]. This is due to the recent advancements in
vision models’ ability to process visual data and perform diverse tasks (e.g.,
saliency prediction [24], image captioning [31, 36], or visual question
answering [2]), often surpassing human-level performance [13, 17].

However, most existing benchmarks for chart understanding models focus on
high-level tasks, such as task performance in question answering [28, 40] or
image captioning [34] scenarios. These benchmarks can evaluate the model’s
overall performance and utility but are too coarse to address how they
perceive and interpret the fundamental graphical elements in charts at a
perceptual level.

To address this gap, we introduce a novel evaluation framework for image
embedding models based on the concept of ‘channel effectiveness,’ which
considers two main aspects: accuracy (section 2, section 3) and
discriminability(section 3). Our framework can measure how precisely vision
models can interpret and discriminate the magnitude channel typically used in
charts [27, 29]: length, tilt, area, color luminance, color saturation, and
curvature.

First, we suggest using the linearity of image embeddings as a proxy for each
channel’s accuracy while their magnitude increases. According to Steven’s
power law, channel accuracy improves as the perceived magnitude increases
linearly with the given stimuli. Then, we broadened our investigation of
whether the order of measured linearity could be generalized across all
combinations of controlled variables. Secondly, we suggest analyzing the
distances between consecutive embeddings to evaluate each channel’s
discriminability. We calculated the peaks from the smoothed distance graph to
ascertain the number of distinguishable groups and how sensitive the model
reacts to the magnitude of the channel.

We also present that our evaluation framework can measure the low-level
performance of the model depending on the model’s goal:

  * 1.

Tasks requiring precise quantitative analysis (e.g., determining exact values
from a bar chart). In such cases, models should give precise answers from the
graphical elements. Therefore, they must achieve higher channel accuracy and
maintain low discriminability when the magnitude increases.

  * 2.

Tasks where models need to process charts as humans do (e.g., interpreting
trends from a line graph [6] or mimicking user studies [15]). In this
scenario, the accuracy should align with the known perceptual effectiveness of
human vision [20, 8] (should follow human perceptual ranking), and
discriminability should mirror human ability [29, 35].

We applied our framework on CLIP [31], one of the state-of-the-art image
embedding models pre-trained on a large-scale dataset of natural images. The
result reveals that CLIP’s order of channel accuracy differs from human
perception and each accuracy is much lower than being ideally linear.
Furthermore, CLIP exhibits unique discriminability patterns that seem to
follow human perception on certain channels, such as length, tilt, and
curvature. We also found that CLIP’s perception conforms to Weber’s law [11],
indicating that perceived changes in stimuli are proportionate to the
magnitude of the initial stimuli. Comprehensively, we observed a tradeoff
between accuracy and discriminability, where accuracy can be lowered when
there exists a certain amount of discriminability.

We present our framework for channel effectiveness as a foundational effort in
establishing low-level benchmarks for chart comprehension. Furthermore, we
suggest the visualization community explore additional low-level benchmarks,
such as pre-attentive processing [19] or just-noticeable difference (JND)
[11]. Our future initiatives include collecting crowdsourced data to validate
our findings from discriminability and comparing them with results from
various image embedding models to confirm the robustness and applicability of
our benchmark.

##  1 Related Work

###  1.1 Graphical Perception

Cleveland and McGill [8] tried to understand encodings in visualization
through graphical perception. They measured humans’ graphical perception by
defining 10 elementary perceptual tasks (e.g., position, length, angle, area,
and volume), collectively known as channels, that people use to extract
quantitative information from graphs. They also performed pairwise
experiments, such as comparing bar charts and pie charts to compare the
difficulty between position and angle, and then ranked these channel
effectiveness based on the accuracy of human perception.

Various research extended this in terms of participant scale [20], data type
[22, 21], or task complexity [5, 39], leading to a broader and more solid
understanding of graphical perception. Furthermore, the emergence of CNN
models questioned researchers on whether the same findings also apply to the
trained models [14].

Traditional methods primarily evaluate graphical perception by assessing
channel effectiveness in terms of accuracy with human subjects or through
models trained with predetermined answers. However, these approaches cannot be
easily applied to computer vision models. Also, they typically miss examining
other critical aspects of channel effectiveness [29] (e.g., discriminability
[23], separability, popout, and grouping), which are crucial for understanding
how visual information is perceived and processed.

Therefore, our paper introduces a method for understanding how unsupervised
image training models perceive channels by analyzing the raw outputs of image
embedding models. Beyond accuracy, our investigation includes
discriminability, which refers to the ability to differentiate between similar
visual elements, illustrating a broader perspective on the components of
channel effectiveness.

###  1.2 Image Embeddings

Computer images are structured pixels of light and color intensities, which
are not directly related to their intrinsic meaning. Therefore, various image
encoding models were suggested to transform images into embeddings, a fixed-
length vector representing their semantics [1, 28, 31, 25]. These image
embedding models are often used in other models’ backbone to classify,
describe, interpret, or perform multimodal tasks [26, 9]. Also, various
benchmarks were suggested to evaluate such models through QA tasks [40, 34].
However, we found that the image embedding itself has neither been
investigated nor evaluated. Therefore, we present a methodology to measure
graphical perception within these image embeddings and experiment with CLIP
[31], a general state-of-the-art image embedding model used in various domains
(medicine [37], fashion [7], or even user interfaces [30]).

Figure 1:  Examples of our variations for each channel. Length and Area of
100% means the line or square fills the screen. Tilt is adjusted from 0∘ to
90∘. Curvature starts from a straight line to a semicircular arc. Color Hue is
fixed to 0 (red) when the Luminance and Saturation increase from 0% to 100%.

##  2 Linearity as Channel Accuracy

In pursuit of understanding how image embedding models like CLIP capture
variations on different visual channels, we designed experiments to assess
their sensitivity to changes in six different channels: Length, Tilt, Area,
Color Luminance, Color Saturation, and Curvature. Previous studies have shown
that the accuracy of human perception of these visual channels differs by
order: length is most accurately perceived, followed by tilt, area, color
luminance, color saturation, and curvature [8, 20]. We examined whether an
image embedding model can produce embeddings with a strict order of accuracy.

###  2.1 Linearity with Fixed Control Variables

####  2.1.1 Experiment Design

In our experiment, we generated an image dataset of simple shapes, following
the prior work [20]. Our goal was to eliminate any unintended bias from the
background, ensuring a focus purely on the graphical perception of the
elements. We first created images of a line segment with each channel applied
with a certain magnitude on a white background. For each channel, we encoded
the range of values in Figure 1 over 1000 steps. While testing on one channel,
other channels are fixed to the controlled (default) value in Figure 1
(Length: 50%, Tilt: 0∘, Area: None, Curvature: 0∘, Luminance: 50%, Saturation:
100%). For example, in the luminance channel, the line segments with a Length
of 50% and no Tilt or Curvature were rendered with varying degrees of
brightness.

For each image, we extracted embeddings using three CLIP models [31] with
different visual architecture; one ResNet [18] model (RN50x64) and two Vision
Transformer [10] models (ViT-B/32 and ViT-L/14@336px). We then analyzed
linearity using principal component analysis (PCA) [38], observing how well
the first principal component could represent the distribution of embeddings.
This allows us to measure the linearity of each channel’s embedding space
quantitatively. We also claim that linearity can be a good proxy for measuring
channel accuracy, where the single-scale change in its stimuli directly
appears in the embedding space. Also aligned with that, an accurate channel to
humans means that human perception is proportional to stimuli [33].

####  2.1.2 Result

The linearity of each channel for each model is plotted in Figure 2. On the
y-axis of the figure, the channels are arranged in the order that humans
perceive more accurately, starting from the top. We can find that the order
does not align with human perception for all models. Notably, model ViT-B/32
shows significantly lower linearity in channel tilt than other models.
Additionally, for all models, color luminance shows the lowest linearity
compared to other channels. This suggests that important data encoded as color
luminance can potentially cause the CLIP model to recognize or misinterpret
its precise value barely.

Figure 2:  Linearity of various visual channels across different CLIP models.
The Y-axis is the channel arranged in the order that humans perceive more
accurately. Each channel’s linearity varies between models, which does not
closely align with human perceptual accuracy. Also, the ViT-L/14@336px model
usually shows better accuracy compared to other models.

###  2.2 Linearity with Every Controlled Variables

We also investigated whether the findings can be generalized into
circumstances where other channels are not fixed. This experiment reflects a
more complex and realistic scenario similar to natural visual environments
where data tends to be encoded in multiple channels simultaneously.

####  2.2.1 Experiment Design

We explored the linearity of channels by examining all possible combinations
of channel variations, finding out whether a general order of channel
effectiveness exists. In subsection 2.1, we experimented with varying channel
magnitude with 1000 steps where other channels are fixed as controlled values
in Figure 1. However, in this extended experiment, we reduced the number of
steps to 20 while testing all combinations of other channels, resulting in
$20^{4}$ image variations per channel. We then measured every channel
combination’s linearity and observed whether a general order of channel
accuracy exists.

####  2.2.2 Result

The calculated linearity scores are plotted in Figure 3. We can easily observe
a general order of linearity among the channels (Color Saturation $>$
Curvature $>$ Length $>$ Color Luminance $=$ Tilt), which is also similar to
the result from subsection 2.1. Furthermore, we conclude that the CLIP model
shows a significant difference in channel accuracy compared to human
perception. This disproves the assumption that vision models would process the
data similarly to humans.

###  2.3 Discussion

The previous two experiments reveal that CLIP’s channels’ effectiveness
ranking differs from that of humans, and some of the channels show low
linearity. Different channel rankings indicate that the model perceives images
differently from humans, leading to a risk of inaccurate results when using
CLIP embeddings to mimic human perceptions. Also, the low linearity channels
can cause inaccurate answers to be produced when performing quantitative QA
based on graphical elements through CLIP embedding. We suggest these results
should be considered when using the image embedding model.

Figure 3:  The box plot illustrates the linearity scores for each channel
under every combination of controlled variables, showcasing general patterns
and deviations. Since area cannot be applied together with length or
curvature, we have generated combinations without area. Based on the plot, all
models have similar overall rankings for the channels they perceive (Color
saturation $>$ Curvature $>$ Length $>$ Tilt $=$ Color luminance). The whisker
of this boxplot represents the min and max of the full data.

##  3 Distance as Channel Discriminability

Figure 4:  The smoothed plot of the Euclidean distances between image
embeddings for incremental changes in each visual channel. Sample images below
the chart are illustrations of stimuli variations in each channel. Peaks
represent thresholds where the model perceives significant differences between
images, indicating the discriminability of each channel. This visualization
aids in identifying how many perceptual groups the model can distinguish in
each channel.

In this section, we explore the concept of discriminability (one measure of
the channel’s effectiveness) within the context of image embedding models.
Discriminability refers to the capacity to perceive distinct steps or changes
within visual elements of an image. Conversely, the existence of such
discriminability suggests that accuracy may be low. For instance, it has been
observed that distinguishing more than six hues or more than six symbol shapes
within a visual array can be challenging, suggesting a perceptual threshold
for discrimiability [27].

This threshold indicates the minimum difference required between two objects
to be considered distinct. To assess this, we measured the Euclidean distance
between image embeddings, as these distances can be interpreted as the model’s
ability to differentiate between two images.

We measured the Euclidean distance between embeddings, calculated with the
best-performing model (ViT-L/14@336px), of each consecutive pair in a series
of 1000 images, each created by incrementally changing the value of one
channel as described in subsection 2.1. The results of these measurements are
smoothed with a Gaussian filter [12]
($\sigma=\left\lfloor\sqrt{1000}\right\rfloor=32$) and plotted in Figure 4.
The smoothed plot helps us observe the boundary between the groups the model
perceives as different, thereby showing how much change in one channel is
necessary before the model perceives the two images as different. We expect
the number of distinct peaks can be a proxy for extracting separable groups
throughout each channel.

###  3.1 Result & Discussion

The result from this experiment roughly explains how the model discriminates
changes across different channels.

  * Length: First, when analyzing the discriminability of the length channel, we can see that when the length is short, the distance between adjacent embeddings becomes relatively high. Supported by Weber’s law [11], the model captures subtle changes well when the length is short, similar to humans. Interestingly, the distance graph for Length shows three or four distinct peaks with valleys between, indicating that the model recognizes length in four separate stages.

  * Tilt: The distances are noticeably higher for tilt at angles of 0∘, 45∘, and 90∘. This pattern shows that the model primarily differentiates images based on whether the tilt is less than, equal to, or greater than 45∘. In other words, we can assume that the model uses 45∘ as an important threshold for processing images.

  * Area: Upon analyzing the area, several small peaks were identified throughout the range. Unlike length, we cannot easily distinguish or split into distinct groups.

  * Color Luminance: We can observe a small peak near 0% and an extreme peak at 100%. This indicates that the model is particularly sensitive to changes in luminance at very low and very high values. It suggests that when it is very dark or very bright, it responds greatly to small changes in luminance, and in other areas, images are viewed relatively similarly.

  * Color Saturation: Distance for color saturation was high near the value of 0%. This peak indicates that the model is highly responsive to initial saturation increases in the low saturation state but becomes less sensitive once the change has been made.

  * Curvature: Curvature has very high distance values when approaching 0∘, showing high sensitivity when there are almost no curves. Also, a peak around 90∘ appears to be a critical point similar to tilt, which becomes a perceptional boundary.

##  4 General Discussion & Future Application

We proposed an evaluation framework (section 2) that extensively investigated
the channel effectiveness of the image embedding model and then applied it to
the CLIP model. However, we summarize our limitations and suggest our
corresponding future work.

###  4.1 Reliable Visual Encoders for Charts

The analysis from section 2 shows that generally trained vision models may
interpret the encoded data unreliably, where linearity for channels except
color saturation stays around 0.6. This can be problematic in chart question-
answering models where accurate interpretation of visual cues is essential.
Accurate interpretation requires an accurate perception of channels. Thus,
accuracy for all channels should be linear (linearity score close to 1).
Conversely, checking whether the model’s discriminability matches human
perception can be crucial in chart captioning models. Chart captioning
requires a holistic understanding of existing visual elements, where matching
its discriminability with humans is essential. Therefore, in this case, the
order and intensity should be similar to that of humans besides having higher
channel accuracy. Therefore, we suggest that chart question-answering models
should be trained to have higher channel accuracy, while chart captioning
models should have similar accuracy as humans.

###  4.2 Ambiguity in Peak Analysis for discriminability

In our analysis of discriminability in section 3, we conducted peak analysis
to investigate the model’s effectiveness in differentiating channels. As
discussed in the previous section (subsection 4.1), two-directional goals
emerge: reporting high accuracy and matching human discriminability. To
interpret charts accurately, the graph shapes for each channel in Figure 3
should remain constant, as consistent perception under consistent stimuli is
required. In other words, no discriminability should be found. Conversely, if
the goal is to align with human perception, the graph shapes should mirror the
discriminability observed in humans.

However, several challenges arise with this approach in terms of reliability.
First, hyperparameters for the Gaussian filter should be chosen carefully.
Excessive smoothing and noise reduction might lead to missing peaks in the
original graph, potentially overlooking significant details. Additionally,
when analyzing peaks in the graph, the threshold for distance between
embeddings was set arbitrarily, leading to a subjective inspection of peaks.
For instance, in the area under consideration in Figure 4, multiple peaks are
evident and appear regular, yet the interpretation of each peak remains
unclear.

Given that no studies have deeply investigated how similar these results are
to human perception, our future work could involve detailed human studies. We
believe that more thorough comparisons could be made to evaluate how closely
the graph shapes resemble those humans perceive rather than focusing solely on
peak analysis.

###  4.3 General Benchmark for Channel Effectiveness

Our current evaluation of channel effectiveness primarily focuses on the
accuracy and discriminability of embeddings across six different magnitude
channels. However, a comprehensive assessment of channel effectiveness should
include additional metrics such as separability, popout, and grouping, which
are crucial for understanding pre-attentive processing and just-noticeable
difference (JND) in graphical perception.

To address these gaps, we propose developing a framework that measures model
performance at a low level across these various metrics. Our framework can be
extended as a standardized benchmark that evaluates these fundamental aspects
of graphical perception and provides a platform for comparing different visual
encoders. This benchmark would allow for a deeper understanding of how various
models interpret and process graphical data, paving the way for advancements
in chart comprehension technologies.

##  5 Conclusion

Our work introduces a novel framework for evaluating the graphical perception
of image embedding models, focusing on the concept of channel effectiveness.
Our comprehensive experiments using the CLIP model have revealed significant
disparities in how vision models and humans perceive and interpret visual
channels. We observed that the accuracy and discriminability of these channels
differ markedly between the CLIP model and human perception, suggesting the
careful use of image embedding models on perception-related tasks. Our
findings highlight the potential for improving model reliability in tasks
requiring human-like perception and precision, such as chart question
answering and captioning. As a future work, we suggest extending our benchmark
to assess other low-level channel effectiveness, enhancing the robustness and
reliability of visual encoders across diverse applications. This approach not
only promises reliable models in terms of graphical perception but also paves
the way for future innovations in graphical data interpretation and machine
learning in visualization.

###### Acknowledgements.

This work was supported by the National Research Foundation of Korea (NRF)
grant funded by the Korean government (MSIT) (No. 2023R1A2C200520911)

## References

  * [1] J.-B. Alayrac, J. Donahue, P. Luc, A. Miech, I. Barr, Y. Hasson, et al.  Flamingo: a visual language model for few-shot learning.  In Advances in Neural Information Processing Systems, vol. 35, pp. 23716–23736, 2022.
  * [2] S. Antol, A. Agrawal, J. Lu, M. Mitchell, D. Batra, C. L. Zitnick, and D. Parikh.  Vqa: Visual question answering.  In Proceedings of the IEEE international conference on computer vision, pp. 2425–2433, 2015.
  * [3] F. Bajić and J. Job.  Chart classification using siamese cnn.  Journal of Imaging, 7(11), 2021.
  * [4] A. Balaji, T. Ramanathan, and V. Sonathi.  Chart-text: A fully automated chart image descriptor.  arXiv preprint arXiv:1812.10636, 2018.
  * [5] C. X. Bearfield, C. Stokes, A. Lovett, and S. Franconeri.  What does the chart say? grouping cues guide viewer comparisons and conclusions in bar charts.  IEEE Transactions on Visualization and Computer Graphics, 30(8):5097–5110, 2024.
  * [6] C. X. Bearfield, L. van Weelden, A. Waytz, and S. Franconeri.  Same data, diverging perspectives: The power of visualizations to elicit competing interpretations.  IEEE Transactions on Visualization and Computer Graphics, 30(6):2995–3007, 2024.
  * [7] P. J. Chia, G. Attanasio, F. Bianchi, S. Terragni, A. R. Magalhães, D. Goncalves, C. Greco, and J. Tagliabue.  Contrastive language and vision learning of general fashion concepts.  Scientific Reports, 12(1):18958, 2022.
  * [8] W. S. Cleveland and R. McGill.  Graphical perception: Theory, experimentation, and application to the development of graphical methods.  Journal of the American statistical association, 79(387):531–554, 1984.
  * [9] W. Dai, J. Li, D. Li, A. M. H. Tiong, J. Zhao, W. Wang, B. Li, P. N. Fung, and S. Hoi.  Instructblip: Towards general-purpose vision-language models with instruction tuning.  Advances in Neural Information Processing Systems, 36, 2024.
  * [10] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [11] G. T. Fechner.  Elements of Psychophysics, vol. 1.  Holt, Rinehart and Winston, United States of America, 1966.  Original work published 1860.
  * [12] C. F. Gauss.  Theoria motus corporum coelestium in sectionibus conicis solem ambientium, vol. 7.  FA Perthes, 1877.
  * [13] R. Geirhos, D. H. Janssen, H. H. Schütt, J. Rauber, M. Bethge, and F. A. Wichmann.  Comparing deep neural networks against humans: object recognition when the signal gets weaker.  arXiv preprint arXiv:1706.06969, 2017.
  * [14] D. Haehn, J. Tompkin, and H. Pfister.  Evaluating ‘graphical perception’ with cnns.  IEEE Transactions on Visualization and Computer Graphics, 25(1):641–650, 2019.
  * [15] P. Hämäläinen, M. Tavast, and A. Kunnari.  Evaluating large language models in generating synthetic hci research data: a case study.  In Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems, pp. 1–19, 2023.
  * [16] Y. Han, C. Zhang, X. Chen, X. Yang, Z. Wang, G. Yu, B. Fu, and H. Zhang.  Chartllama: A multimodal llm for chart understanding and generation.  arXiv preprint arXiv:2311.16483, 2023.
  * [17] K. He, X. Zhang, S. Ren, and J. Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In Proceedings of the IEEE international conference on computer vision, pp. 1026–1034, 2015.
  * [18] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778, 2016.
  * [19] C. Healey and J. Enns.  Attention and visual memory in visualization and computer graphics.  IEEE Transactions on Visualization and Computer Graphics, 18(7):1170–1188, 2012.
  * [20] J. Heer and M. Bostock.  Crowdsourcing graphical perception: using mechanical turk to assess visualization design.  In Proceedings of the SIGCHI conference on human factors in computing systems, pp. 203–212, 2010.
  * [21] J. Heer, N. Kong, and M. Agrawala.  Sizing the horizon: the effects of chart size and layering on the graphical perception of time series visualizations.  In Proceedings of the SIGCHI conference on human factors in computing systems, pp. 1303–1312, 2009.
  * [22] W. Javed, B. McDonnel, and N. Elmqvist.  Graphical perception of multiple time series.  IEEE Transactions on Visualization and Computer Graphics, 16(6):927–934, 2010.
  * [23] H. Jeon, G. J. Quadri, H. Lee, P. Rosen, D. A. Szafir, and J. Seo.  Clams: a cluster ambiguity measure for estimating perceptual variability in visual clustering.  IEEE Transactions on Visualization and Computer Graphics, 2023.
  * [24] A. Kroner, M. Senden, K. Driessens, and R. Goebel.  Contextual encoder–decoder network for visual saliency prediction.  Neural Networks, 129:261–270, 2020.
  * [25] K. Li, Y. Zhang, K. Li, Y. Li, and Y. Fu.  Image-text embedding learning via visual and textual semantic reasoning.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):641–656, 2023.
  * [26] H. Liu, C. Li, Q. Wu, and Y. J. Lee.  Visual instruction tuning.  Advances in neural information processing systems, 36, 2024.
  * [27] J. Mackinlay.  Automating the design of graphical presentations of relational information.  ACM Trans. Graph., 5(2):110–141, apr 1986.
  * [28] A. Masry, D. Long, J. Q. Tan, S. Joty, and E. Hoque.  ChartQA: A benchmark for question answering about charts with visual and logical reasoning.  In Findings of the Association for Computational Linguistics: ACL 2022, pp. 2263–2279. Association for Computational Linguistics, Dublin, Ireland, May 2022.
  * [29] T. Munzner.  Visualization analysis and design.  CRC press, 2014.
  * [30] S. Park, W. Kim, Y.-H. Kim, and J. Seo.  Computational approaches for app-to-app retrieval and design consistency check.  arXiv e-prints, pp. arXiv–2309, 2023.
  * [31] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, et al.  Learning transferable visual models from natural language supervision.  In International conference on machine learning, pp. 8748–8763. PMLR, 2021.
  * [32] M. Savva, N. Kong, A. Chhajta, L. Fei-Fei, M. Agrawala, and J. Heer.  Revision: Automated classification, analysis and redesign of chart images.  In Proceedings of the 24th annual ACM symposium on User interface software and technology, pp. 393–402, 2011.
  * [33] S. S. Stevens.  On the psychophysical law.  Psychological review, 64(3):153, 1957.
  * [34] B. J. Tang, A. Boggust, and A. Satyanarayan.  Vistext: A benchmark for semantically rich chart captioning.  arXiv preprint arXiv:2307.05356, 2023.
  * [35] R. Veras and C. Collins.  Discriminability tests for visualization effectiveness and scalability.  IEEE Transactions on Visualization and Computer Graphics, 26(1):749–758, 2020.
  * [36] O. Vinyals, A. Toshev, S. Bengio, and D. Erhan.  Show and tell: A neural image caption generator.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3156–3164, 2015.
  * [37] Z. Wang, Z. Wu, D. Agarwal, and J. Sun.  Medclip: Contrastive learning from unpaired medical images and text.  arXiv preprint arXiv:2210.10163, 2022.
  * [38] S. Wold, K. Esbensen, and P. Geladi.  Principal component analysis.  Chemometrics and intelligent laboratory systems, 2(1-3):37–52, 1987.
  * [39] C. Xiong, C. Stokes, Y.-S. Kim, and S. Franconeri.  Seeing what you believe or believing what you see? belief biases correlation estimation.  IEEE Transactions on Visualization and Computer Graphics, 29(1):493–503, 2023.
  * [40] Z. Xu, S. Du, Y. Qi, C. Xu, C. Yuan, and J. Guo.  Chartbench: A benchmark for complex visual reasoning in charts.  arXiv preprint arXiv:2312.15915, 2023.