=Paper=
{{Paper
|id=Vol-2327/ESIDA1
|storemode=property
|title=Content-based layout optimization
|pdfUrl=https://ceur-ws.org/Vol-2327/IUI19WS-ESIDA-1.pdf
|volume=Vol-2327
|authors=Balaji Vasan Srinivasan,Vishwa Vinay,Niyati Chhaya
|dblpUrl=https://dblp.org/rec/conf/iui/SrinivasanVC19a
}}
==Content-based layout optimization==
https://ceur-ws.org/Vol-2327/IUI19WS-ESIDA-1.pdf
Content-based Layout Optimization
Balaji Vasan Srinivasan Vishwa Vinay Niyati Chhaya
balsrini@adobe.com vinay@adobe.com nchhaya@adobe.com
Adobe Research Adobe Research Adobe Research
Bangalore, India Bangalore, India Bangalore, India
ABSTRACT with the target audience. The commercial metrics vary with the kind
Effective personalization of web experiences constitutes matching of enterprise, e.g. number of subscription sign-ups triggered from
the intent and interest of a user (or a group of users) to content the experience for a media house, number of orders for a retailer,
they consume, while optimizing a set of target engagement metrics. etc.
With improved content consumption tracking via web analytics, Currently, an enterprise employs a team of web designers and
such personalization is not only feasible but also valuable for a developers who put together an experience from a repository of
content publisher/owner with large volumes of content to choose content in a manner suitable for consumption on a chosen device
from. However the multitude of media (desktop, mobile, etc.) and the by a user segment [21]. The designer/developer starts with a target
diversity of users’ interests necessitates automation in this process metric (e.g. orders, signups) to be optimized and short-lists content
of constructing personalized content experiences. In this paper, we items that have historically performed well on that metric. The set
propose a genetic algorithm based framework that chooses a subset of content items are then laid out into an experience appropriate
of content items (from a large collection) that are relevant to a given for the corresponding medium - for e.g., mobile layouts may be
user and determines their respective sizes and relative positions to narrower with popular content items placed at the top, while desktop
construct a layout that is optimized for a chosen engagement metric. layouts can accommodate more items with high user interest areas
Comparisons against existing frameworks based on crowd-sourced reserved for the popular items. This allocation of content items
annotations indicate improved prominence of key content (based to locations in the experience is an iterative process - items that
on historic engagement metrics) by the proposed approach, while gather more engagement from users may progressively be promoted
improving the information diversity of the content presented in the to more prominent positions. Similarly, extensive experimentation
layout. (A/B testing) may be involved in identifying truly good quality
content rather than items that attract user attention by merely being
CCS CONCEPTS placed in attractive locations.
This manual process limits the extent of personalization achiev-
• Human-centered computing → Human computer interaction
able by an enterprise given the sheer volume of available content
(HCI); • Computing methodologies → Learning to rank.
to choose from, the multitude of media for experience delivery and
the variety of target consumer preferences. The effort involved mul-
KEYWORDS
tiplies when the experience is dynamic and changes in response to
layout; content ranking; optimization user activity. This calls for a mechanism to automate the process of
ACM Reference Format: rendering content in a given layout while optimizing a target metric
Balaji Vasan Srinivasan, Vishwa Vinay, and Niyati Chhaya. 2019. Content- across various consumers or audience segments. Such a mechanism
based Layout Optimization. In Joint Proceedings of the ACM IUI 2019 can both provide assistance to content developers and designers,
Workshops, Los Angeles, USA, March 20, 2019. , 8 pages. as well as aid personalized experience delivery at scale by quickly
putting together renditions for varied target audience settings.
1 INTRODUCTION We consider the problem of automatically constructing layouts of
With the evolution of digital technology, content is increasingly be- content items (also referred to as fragments in the rest of the paper).
ing consumed in a variety of environments ranging from desktops to These fragments can be of different sizes (Figure 2) and we refer to
mobiles to wearable devices. An enterprise with an online presence each size of the fragments as one of its variants. The target is a home
would like to engage with its customers across these channels. To page like experience similar to Figure 1 which displays summaries
do so, it would need to create engaging content and experiences of these individual fragments that a user can click through for a
appropriate for each channel, and this can be a non-trivial task. An ‘detailed information page’. We aim to personalize this experience
engaging experience requires relevant, non-redundant and diverse by automatically choosing a subset of the content from the reference
information [26]. Once the content is available, it needs to be trans- collection optimized for certain metrics and also choose the appropri-
formed and delivered based on the mode of consumption. Every ate size variant depending on the required emphasis for the selected
enterprise would want to optimize certain commercial metrics via content. The proposed approach is a genetic algorithm-based frame-
its digital experiences while maintaining a high engagement level work [14] where the fitness function captures various factors that
contribute to the engagement on a given layout - prominence of pop-
IUI Workshops’19, March 20, 2019, Los Angeles, USA
ular items, relevance to the target user and diversity of the displayed
Copyright © 2019 for the individual papers by the papers’ authors. Copying permitted content. We concentrate on rectangular grid-like layouts - which
for private and academic purposes. This volume is published and copyrighted by its are common in several home page templates. The algorithm starts
editors.
with a metric that we choose to maximize, a reference collection
IUI Workshops’19, March 20, 2019, Los Angeles, USA Balaji Vasan Srinivasan, Vishwa Vinay, and Niyati Chhaya
of fragments (and their variants) and the target layout configuration chain management [12], scheduling problems [22], and video-on-
(such as the size), and proceeds to select and lay out the appropriate demand applications [31].
variants of the content on the grid. Bin packing can be particularly well-suited for grid layouts, due
to parallels between the bins and the cells in the grid layouts. In our
proposed approach, we utilize the First Fit Decreasing approximation
of the bin packing algorithm [17] to define a decoder (defined later)
and pack an ordered list of fragments into a grid. As we show later,
such an approach aids in placing prominent fragments in prominent
locations of the grid. Similar to methods in the earlier section, bin
packing requires that each fragment be associated with a single
weight that dictates its priority. Our method not only removes the
need for such a singular characterization of the content, but also
allows for considering interactions between fragments.
Another closely related problem is that of Search Engine Re-
sult Page (SERP) composition [29] in the context of Aggregated
Search [18], where results from multiple verticals are blended into a
single experience. The verticals are for example web, images, videos
and local. Typically, one of the verticals (e.g. the web) is nominated
as primary and results from the other verticals are introduced at
Figure 1: A sample home page layout for desktop, mobile and pre-selected slots. The pre-selected slots along the primary vertical
tablets. As would be expected, the layout, emphasis and choice defines the layout, and results from each source need to be mapped
of fragments changes from the desktop to mobile versions. to the slots/bins. There have been studies on what constitutes a good
SERP [2, 28], with factors including the specific verticals that the
results are from, and coherence across the verticals. Arguello [1]
provides a comprehensive overview, including the related problem
2 RELATED WORK of evaluating a given SERP layout. The scenario described in the
In this section, we provide an overview of papers addressing prob- current paper shares many of the same concerns as above for two
lems similar to the one described here. dimensional layouts [8] and we also consider the impact of inter-
Layout optimization is the process of finding a good layout ef- fragment diversity, as well as allowing for individual fragments to
ficiently and attempts to find techniques that create well serving not be of uniform size.
layouts for different purposes. Gonzalez et al. [15] explored the prob- Closest in spirit to the current paper are the works described in
lem of optimizing the content in a newspaper layout using simulated [23–25]. The application scenario considered in these papers are
annealing. Barbrand [4] extended this work using a genetic algo- interactivity assistance in the construction of graphic designs. With
rithm framework. Duarte et al. [11] use a tree-map based structure to input from design principles, factors capturing design quality can
layout images efficiently. However, all these works focus on reducing be encapsulated into an energy function that can then be optimized.
the gaps/white-spaces in between the fragments and do not account The fitness function commonly used within a genetic algorithm
for the content that is being laid out. Often the layouts are dictated setup serves a similar purpose. In the current paper, we have not
by the historic performances and the information presented in the considered aesthetics - focusing instead on individual item properties
fragments. In our approach, we use a genetic algorithm framework to (relevance) and inter-item considerations (diversity). An advantage
account for these content factors along with the engagement metrics of the framework described here is however that it is easily extensible
to optimize the layout distribution. by extending the fitness function to include other factors.
Kumar et al. [19] create web pages from sample templates by While layout optimization and content distribution in a 2-d space
identifying 1 : 1 mappings between layout elements. Srinivasan have been independently explored, to the best of our knowledge,
et al. [27] extend this and propose ESCORT that maps important automatic laying-out of content with simultaneous optimization of
content to important parts of the layout based on a predefined notion engagement and content metrics across mediums is less studied and
of the ‘criticality’ of content items. However, the importance of a is our primary contribution.
fragment is often determined by multiple factors and the approach in
[27] cannot scale for compound importance functions. Our approach
allows for such scaling across multiple content related characteristics 3 GENETIC ALGORITHM FRAMEWORK
as components of a composite ‘fitness function’. We use ESCORT In this section, we describe the problem in detail so as to motivate
as one of our baselines and show improvement with our framework the use of genetic algorithms as the solution approach. Revisiting the
in both information diversity and prominence of key fragments. problem definition, we have a set of candidate content items, each of
Bin packing [3, 9] is a class of algorithms for the assignment of which is called a ‘fragment’. Each fragment is a representation of the
pre-selected items to locations. The underlying optimization problem content to be used for the experience and a subset of these fragments
starts with a set of rectangles (or any other shape) and finds the need to be chosen for the target experience. We assume that each
optimal way of ‘packing’ them into specified locations, i.e., ‘bins’. fragment includes some content - e.g. text in the form of a title or
Bin packing has been used for various applications including supply description, or images and other visual content. Other metadata,
Content-based Layout Optimization IUI Workshops’19, March 20, 2019, Los Angeles, USA
Fragments that are likely to make larger contributions to the
engagement are preferred in regions of the screen that attract most at-
tention. Existing literature (e.g. [5]) provides guidance about where
these might be. A strategy to maximize engagement would be to
place the content items with most historical engagement in the lo-
cations corresponding to high user attention. While intuitive, this
greedy strategy has the downside that it does not account for inter-
content characteristics and might result in a situation where two
very similar fragments are placed next to each other - this can be
undesirable from a user’s perspective.
2x1 The optimization problem is therefore complicated by having
to account for interactions among content items. Two layouts with
Fragment
the same set of fragments that are different only in terms of the
Variant positions of the fragments might have very different characteristics
2x2 Fragment Variant Source Code from the users’ perspective due to the difference in the user attention
Source Code to different fragments [5].
A concrete illustration of the scenario considered in the current
paper is the creation of genre/category level pages at a site like
IMDB. In fact, the experiments described in Section 4 address this
1x2 setting. Given a genre (e.g. ‘action’, ‘comedy’, ‘drama’), we could
Fragment utilize a historical metric (e.g. revenue or ratings) to pick movies in
Variant order of their popularity. Given constraints on the number of items
Source Code that could be included (due to the size of the layout), we might
1x1 Variant decide to display the top-ℒ most popular movies. If the list is to
Source Code be personalized, the global popularity needs to be balanced against
relevance to the individual. We might decide to allow some of the
movies to be present in tiles of a larger size - e.g. allow the top-ranked
movie to take up 2 slots in the grid layout and therefore drop the
Figure 2: Content Element/Fragment and its different variants
bottom ranked item from the shortlist. Also, to ensure diversity in the
considered in our analysis. Due to the proprietary nature of the
displayed fragments, an item of lower popularity might be promoted
underlying content used for the layout, we use an ‘indicative’
into the layout. Therefore, the layout construction algorithm has to
image and text here. However, all our experiments included the
not only choose the set of items, but also their individual positions
actual content from a popular media platform.
and sizes, to ensure that the resulting experience is engaging.
The discontinuous nature of the perceived quality of the layout
with respect to these configurations, coupled with the large search
space means that this problem does not lend itself easily to tradi-
tional optimization approaches. To account for this, we propose
such as the historical performance of the content in terms of user a genetic algorithm framework. Genetic algorithms [14, 30] are a
engagement, may also be available. The fragments are considered class of computational approaches that are typically concerned with
to have different variants - each of different size. Figure 2 shows problems that are non-linear, and where it is not possible to treat
different variants of the fragments considered in our paper. Such each parameter as an independent variable that can be solved in
variants would typically be defined via a template used commonly isolation from the other variables. The proposed genetic algorith-
across several fragments. Layout optimization involves identifying a mic framework simultaneously optimizes the performance metrics
subset of the provided fragments that make the layout, as well as the of experience fragments along with content-affinities and diversity
position and relative sizes of the individual fragments. Note that we properties.
take the fragments and their constituent content to be a given, and This framework begins with the assignment of a Chromosome -
optimize their assembly into a layout. Optimizing the aesthetics of which is a representation of the layout that is being optimized. We
the layout is beyond the scope of our exploration. initialize this to a vector of size of ℒ and with each entry being an
The target layout is described in terms of its shape and size, identifier to a unique fragment. The vector is initialized to the set of
and here we focus on grid-shaped rectangular layouts defined by fragments in descending order of their respective metrics. Since the
the number of rows (NR ) and columns (NC ). Such a layout can distribution is pivoted on this initialization, we ensure that the initial
accommodate a maximum of L NR × NC fragments, each of unit distribution has the best (engagement) metric combination.
size. The set of displayed fragments might be fewer than L if larger- Central to the genetic algorithm framework is the notion of a
sized fragments have been chosen - for example, popular/highly fitness function, which takes the current configuration, represented
relevant content might deserve more screen area. The algorithm also by the Chromosome, as input and outputs a number indicating the
simultaneously optimizes an engagement metric like the expected quality of the layout that would result from displaying this set of
number of clicks on fragments. fragments laid out as controlled by the decoder (described in detail
IUI Workshops’19, March 20, 2019, Los Angeles, USA Balaji Vasan Srinivasan, Vishwa Vinay, and Niyati Chhaya
later). Apart from the metric tied to each fragment, the fitness func- Algorithm 1: Genetic Algorithm Framework for content-based
tion also accounts for the inter-content affinities, expected relevance layout optimization
to the user, overall content diversity, and coverage of all possible Input: ℱ : Set of all fragments, ℳ: metric to optimize, ℒ:
aspects and concepts across the content in the input fragment set, Layout size to optimize
motivated by their use in information retrieval scenarios [10]. The Output: Decoded Layout
resulting fitness value gives an objective measure of the goodness of Layout ← Chromosomeℱ , ℳ, ℒ;
the distribution of fragments in the layout across the content param- Layout. f itness ← computeFitnessLayout;
eters and the target metric. The fitness function is thus a mechanism
curGeneration ← 0;
within the framework that allows easy extensibility. Note that the
repeat
different factors affecting the fitness may not agree with each other.
tempLayout ← mutateLayout;
For example, the best collection of fragments as per the individual
metrics might have very low inter-fragment diversity - and hence tempLayout. f itness ← computeFitnesstempLayout;
may not be the optimal experience for the consumer (due to redun- if (tempLayout.fitness-Layout.fitness)>0 OR
dant information). Our fitness function addresses this by including RandomNumber < δ then
a variety of factors to determine the ‘goodness’ of the collection of Layout ← tempLayout;
fragments. end
The decoder takes an ordered list of fragments along with the curGeneration ;
layout configurations to distribute the fragments currently within the until curGeneration > totalGeneration;
Chromosome on to the layout. To ensure that a sufficient variety of return decodeLayout
configurations of fragments is explored, a mutation operation needs
to be defined that makes alterations to the existing Chromosome. If
a particular mutation leads to an increase in the fitness value, the
corresponding change is retained. In the proposed framework, the The FFD algorithm starts with a ranked set of fragments (as
purpose of mutation is 2-fold. Firstly, it aids in the exploration of defined by the Chromosome) and iteratively creates an updated
different permutations of the input set of fragments thus evolving layout (bin dimension) and an updated fragment list (of all fragment
the chromosome/layout to a distribution that has better overall fit- variants that have not been placed on the layout yet) till the point all
ness. Additionally, a factor is used to insert fragments that would locations on the layout have been filled. We leverage the study in
have otherwise not featured in the distribution. This not only al- [5] to assign an exponentially-decaying weight/importance to every
lows newer fragments with no performance metrics to feature in bin in the layout based on their 2-dimensional location. The bins are
the distribution but can also introduce better content diversity. After then filled in the order of the assigned importance - thus ensuring
exploring alternative configurations in this manner across many iter- that important parts of the layout are filled before the other parts.
ations/generations, the Chromosome with the highest fitness can be Utilizing the ranking from the Chromosome ensures achieving the
identified, and this is taken to be the optimized layout of the content. target layout with the key fragments in key locations. Figure 3 shows
Repeating this sequence of steps for every target user (or user a schematic diagram for the algorithm.
segment) for the respective metric (based on the consumption en- It is easy to see that the decoding is a highly discontinuous op-
vironment) yields the personalized experience for every possible eration. Making a minor alteration in the Chromosome - e.g. via
combination. Algorithm 1 outlines the different steps in the pro- a mutation - potentially alters the fitness of the resulting layout in
posed framework. In the subsequent subsections, we elaborate the non-trivial ways. The proposed genetic algorithm framework ad-
key components of our framework: decoder, fitness computation and dresses this by decoupling the optimization and fitness computation.
mutation. Running the framework across several generations explores various
layout against the fitness function to achieve a stable optimized lay-
out. The proposed framework is generic since it allows the fitness
function to be a black box, and ensures that the resulting layout puts
3.1 Decoder the key fragments in key locations.
The Chromosome corresponds to a set of input candidate fragments
that need to be allocated a location in the layout and is an ordered set 3.2 Fitness function
of fragments. The decoder controls how the linear ordered collection Given a spatial arrangement of fragments (i.e., output of the De-
of fragments is arranged according to the target layout dimensions coder), the fitness function produces a numeric value indicating
provided by the designer. It takes the fragments (each of a currently how desirable the given configuration is. In that sense, the fitness
chosen size) in the order defined by the Chromosome along with the computation needs to encapsulate factors that affect the quality of a
layout dimensions and outputs the arranged layout. This allocation particular layout. We use [10] to help design the components of this
can be simple (e.g. via a reverse raster scan), but should be able to fitness function. In [10], set in the Information Retrieval domain, an
handle the fact that fragments potentially are of differing sizes. In this initial set of results for a user’s query are available. Based on this
paper, we use a decoder inspired by the bin packing algorithm[20] evidence, we may decide to add new terms to the query that were
which is a variant of the knapsack algorithm in 2−dimensions. We not provided explicitly by the user (‘Query Expansion’), expecting
extend the complete bounding box-based strategy using the First Fit that these will likely return more relevant results. The risk of doing
Decreasing (FFD) algorithm[16]. so is that the added terms do not match the user’s intent, thereby
Content-based Layout Optimization IUI Workshops’19, March 20, 2019, Los Angeles, USA
Identify fragment
Input: Fragment
variant that
ranking from
Find empty areas covers maximum
Chromosome, Optimized layout
in the layout (and area with
Layout with XFs
its importance) maximum fitness
dimensions &
contribution (or
metadata
ranking)
Repeat until no more
spaces in layout or all
fragments covered
Figure 3: Sequence of steps in the Bin Packing based decoder
leading to a drop in quality of results. The author uses ‘coverage’ and coverage as
‘balance’ across topics/aspects, and trades these off against relevance. i∈L a∈A xia
(2)
We follow a similar template. Our proposed algorithm includes the ‖L‖‖A‖
following factors in our fitness computation to account for different where xia is the weight of concept attribute a to item i
aspects of the layout. (b) where possible, all topics/concepts in the full set of candi-
dates are represented in the final chosen set, this is termed
(1) Metric-contribution indicates the total expected value of the as balance. We define balance as
engagement metric for this chosen set of fragments displayed (︃ )︃
i∈C xia x
in the given arrangement. Since we would like to pick a layout − i∈L ia (3)
that maximizes the metric value, we would choose to place a∈A ‖C‖ ‖L‖
fragments that have historically seen larger values of the met- We extract the key entities in the fragment (from the title and
ric at locations that are most likely to receive user attention. description) as its concepts. The combination of coverage
We compute a weighted average of individual fragment met- and balance over the attributes yields a diverse selection of
rics, where the weight is based on its current assigned location fragments that covers information about different aspects of
in the 2-dimensional and represents user attention based on the initial set. Increasing diversity is a well known strategy
an exponential decay function as in the user study in [5]: that reduces the risk of producing a layout with no relevant
content for a given user [7].
i2 j2 We compute the fitness as a weighted-sum of these factors to get
exp− *M (1) an estimated utility/quality of the layout. Note that our framework
NR 2 NC 2
is generic - other factors that we expect to contribute to the quality
of a particular layout can be readily incorporated, with the rest of
for an item that the Decoder is currently placing at row i and
the mechanism within the framework designed to optimize the net
column j on the grid, and M is the value of the engagement
fitness.
metric for this item.
(2) While the metric captures historical performance across a set
of users, it is important to ensure that all the fragments that
3.3 Mutation
are part of the current display include those that are relevant Genetic algorithms operate by constructing multiple layout config-
to the current user. The fitness function therefore includes the urations, and evaluating each via the fitness function. Mutation is
fragment’s relevance to ensure that utility of the fragments to the process of taking the current configuration (represented by the
the target user. This component helps achieve personalization Chromosome) and producing an altered version of it. This step is
since the computed fitness is now dependent on a particular used to explore alternate configurations to hopefully identify a more
user. When the fragments have textual content associated optimal (as per the fitness function) layout. In the proposed approach,
with them, relevance can be computed by standard measures the mutation component includes one of the following 3 steps:
(e.g. tf-idf) with respect to the user profile - based on historic (1) With probability α1 , choose fragment in the top 20-percentile
preferences. of the fragments ordered by their individual metrics, and
(3) The candidate set of fragments span topical concepts (ex- select its variants whose Mcost > Σ, where M is the metric
tracted from the text in the title and description). The fitness value as before, cost is its size. The current nominated size
computation attempts to ensure that the chosen set in the lay- of the fragment is taken to be the largest one that satisfies
out (represented by L) is representative of the larger candidate the above constraint. This ensures that apart from choosing
set (represented by C) in the sense that: a good set of fragments and their corresponding positions,
(a) the important topic/concepts in the candidates are present promising fragments are given a larger share of the layout
in the chosen set, this is termed as coverage. We define (screen) real estate.
IUI Workshops’19, March 20, 2019, Los Angeles, USA Balaji Vasan Srinivasan, Vishwa Vinay, and Niyati Chhaya
(2) With probability α2 , exchange the position of two chosen frag- fragments that have performed well on the target metric to be placed
ments in the chromosome. Via the Decoder, the fragment’s in prominent locations. In our approach, a bin packing based decoder
location in the final displayed layout will now be different. together with the fitness ranking ensures that the good-performing
This alternative, aids in exploring different permutations of fragments are placed in key locations. To evaluate this, our first
fragments in the same Chromosome, i.e., alternate locations survey is aimed at capturing the perceived importance of the various
for each fragment. fragments at different locations in the layout. Every layout produced
(3) With probability α3 , swap one of the fragments in the chosen by each of the methods were annotated by 5 distinct users - each
set with a fragment that is in the larger candidate set but not user annotating the prominence of 4 fragments at different locations
in the layout right now. This alters the set of fragments that in the layout generated by all 4 candidate methods - resulting in 16
will be in the layout. annotations for this category per annotator.
In our experiments, we empirically set α1 0.3, α2 0.6, α3 0.1. However, as discussed before, optimizing just based on good-
Exploring different sets of fragments, as well as different configu- performing fragments can lead to redundant layouts. Our approach
rations, attempts to ensure that the final chosen layout is of high avoids this by having additional content-based metrics in our fitness
quality. The key idea in the genetic algorithmic framework is to run function to introduce diversity of the information in the fragments.
the mutations over a large number of iterations (generations) and To evaluate this, our second survey asked annotators to rate the ‘infor-
this will yield a stable generation that has an optimal fitness across mation diversity’ of layouts from two different algorithms. Repeating
the various parameters of evaluation. this across different combinations yields a preference ranking of dif-
ferent algorithms in terms of the diversity that they afford. Every
4 EVALUATION method combination is annotated by 5 different annotators, with
every annotator annotating all 6 possible combinations.
To demonstrate how the algorithm works, we used the set of frag-
Thus every annotator recorded 22 total annotations. We paid 25
ments based on the top 1000 movies in IMDB for 2006 to 2016
cents per worker, and the work took 4 minutes on an average. Initial-
from Kaggle1 . In our dataset, every movie’s data included its title, a
izing the different layouts based on one of the 8 genres mentioned
short description about the movie, its genre, its IMDB Rating, IMDB
above allows for debiasing any content-induced biases in the annota-
User Votes along with its revenue. We used the movie revenue as a
tion. To avoid any grid-size induced bias, we expose every annotator
surrogate for its historic performance. The movie description and
to a single grid-size only. Finally, ordering of the methods in the two
genre were used to determine the content level features in our fitness
tasks were shuffled to safeguard against positional/order induced
function. For our experiments, we defined variants of the fragment
biases.
with sizes (height-by-width) - 2x2, 2x1, 1x2 and 1x1 as shown in
Figure 2. Since the proposed algorithm does not modify the internals
of the fragments (or its variants), we assume that the aesthetics of 4.1 Prominence of key fragments
the fragments are not modified with these variants. The first experiment measures the perceived importance of various
We constructed different layouts based on the movies belonging fragments at different locations in a layout. Figure 4 shows a screen
to the major genres (Action, Adventure, Comedy, Crime, Drama, shot of the performed evaluation where we asked the annotators to
Mystery, Romance, Thriller) in the dataset. Layouts of sizes suitable annotate the perceived importance of a highlighted part of the layout
to a mobile environment (e.g. 4x3, 5x3) were defined with shorter on a scale of 0 − 100.
columns and the desktop grids were defined with more columns. For every layout, we calculate the Pearson’s correlation ρ between
Every grid is then populated by each of the candidate methods. We the human-annotated perceived importance of the fragment in the
extend the ESCORT approach in [27] as our primary baseline for layout and its actual metric. Table 1 shows the correlation between
comparisons. ESCORT defines a criticality/ranking for different the perceived importance and the metric value for the proposed
‘slots’ in the layout and we use [5] to define this in our setup. We method (GA+diversity) against the various approaches including the
use the Maximum-Marginal Relevance based diversified ranking one in [27] - ESCORT.
[6] to define the criticality of the fragments. Additionally, we also The average correlation indicate that the 3 approaches (ESCORT,
include the version of the proposed Genetic Algorithm (GA) where GA-Relevance, GA-Diversity) exhibit a good correlation between
our fitness function was based on the target metrics and relevance the perceived importance of the fragments against its metrics un-
to the user (without the diversity considerations). Finally, we also like the Random layout (as would be expected). Further, note that
included a random layout rendition - thus resulting in 4 distinct both the frameworks based on the proposed approach (GA and
layouting methods. GA+diversity) beat ESCORT [27] in terms of the overall correlation
To evaluate the ‘goodness’ of the proposed layout, we conducted - indicating that the proposed approach does well in placing key
two different experiments on Amazon Mechanical Turk2 . Annota- fragments in prominent locations. Between GA and GA+Diversity,
tors were limited to those who have over 100 completed hits with the framework without diversity performs better since it specifically
95% acceptance rates. Additionally, since the dataset is based on optimizes the metric (prominence).
Hollywood movies, we limited the annotators’ geo to US only.
As mentioned previously, the layout optimization algorithm for 4.2 Content Diversity in the layout
personalized delivery optimizes a target metric. This calls for the
The additional factors in our fitness function further ensures a diverse
1 https://www.kaggle.com/PromptCloudHQ/imdb-data set of fragments being shown in the layout to avoid content redun-
2 https://www.mturk.com/ dancy. To measure this, we further asked the human annotators to
Content-based Layout Optimization IUI Workshops’19, March 20, 2019, Los Angeles, USA
ESCORT GA-Relevance GA-Diversity Rand
All Grids 0.3161 0.4297 0.3777 0.0565
Mobile Grids 0.3874 0.5014 0.4785 0.0468
Web Grids 0.2319 0.3451 0.2587 0.0679
Table 1: Pearson’s Correlation between ‘perceived importance’ of a movie fragment against its actual metric (Revenue) across multi-
ple layout settings.
Please answer the question below Please answer the question below based on your
impression about the layout
based on your impression about the layout
Please select
The The Dark The
Avatar... the layout
Avengers... Knight... Avengers...
that is a
better
arrangement
of a more
The Avengers... representative
set of items
i.e., which Avatar...
Finding Dory... The Dark
layout are Knight...
you more
likely to have
a higher
engagement
with?
Jurassic World... The Dark <>
The Hunger Jurassic World... The Dark
Toy Story 3... Frozen...
Games... Knight Rises...
Next
Finding Dory...
Figure 5: A screen shot of the survey to compare diversity of
layouts from various algorithms. Every annotator was asked to
compare the layouts from two algorithms in terms of informa-
tion diversity. Table 2 shows the statistics around the ratings
Jurassic World... from the annotators across different pairs.
The Dark Knight Rises...
Please rate your perceived significance of the highlighted cell
relative to the rest of the overall layout. i.e., how likely are you to
click-through on the highlighted item given the others?
We compute the WMW statistic (extended from learning-to-rank
problems [13]) to measure the fraction of all possible layout pairs
50 where one layout is marked more diverse than the other by the
annotators. A lower WMW statistic indicates a relatively less diverse
Next layout against the compared approach. The statistics for various
configuration is summarized in Table 2. A value of WMW statistic
> 0.5 indicate that more than half of the total annotations favored
Figure 4: Survey to get the perceived importance of a fragment Method 1 over Method 2.
in the layout. Every annotator was asked to annotate the per- It can be seen that the proposed approach (GA+Diversity) con-
ceived importance of the indicated fragment based on their lay- sistently outperforms the other approaches in terms of information
out position. Table 1 shows the statistics around the ratings diversity. Across all the settings, approximately 60% of the annota-
from the annotators. tors rated our approach to be more diverse over ESCORT [27]. Note
that a random selection of fragments was rated to be more diverse
against all candidate approaches. This is expected since the variety
in the dataset yields such diversity. While diversity is preferrable,
compare the content diversity between two layouts. Figure 5 shows this comes at the cost of prominence to key fragments as indicated
the corresponding human experiment. by Table 1.
IUI Workshops’19, March 20, 2019, Los Angeles, USA Balaji Vasan Srinivasan, Vishwa Vinay, and Niyati Chhaya
Method 1 GA-Diversity GA-Diversity GA-Relevance Random Random Random
Method 2 GA-Relevance ESCORT ESCORT GA-Diversity GA-Relevance ESCORT
All Grids 0.6825 0.6508 0.7143 0.6825 0.7143 0.7460
Mobile Grids 0.7941 0.7941 0.9412 0.5588 0.6765 0.7059
Web Grids 0.5517 0.5272 0.5517 0.8276 0.7586 0.7931
Table 2: WMW Statistic between pairs of layouts as annotated by annotators towards diversity computation. Every cell indicates the
WMW statistic (fraction of annotators rating the Method 1 to produce more diverse layout than the Method 2.
Tables 1 and 2 establish that the proposed approach produces lay- [12] Ugur Eliiyi and Deniz Eliiyi. 2009. Applications of Bin Packing Models Through
outs with diverse information without compromising on the promi- The Supply Chain. (2009).
[13] Glenn Fung, Rómer Rosales, and Balaji Krishnapuram. 2006. Learning Rankings
nence for key fragments. via Convex Hull Separation. In Advances in Neural Information Processing
Systems 18.
5 CONCLUSION [14] David E Goldberg. 2006. Genetic algorithms. Pearson Education India.
[15] Jesús González, Ignacio Rojas, Héctor Pomares, Moisés Salmerón, and Juan Julián
We have presented an algorithm to automatically layout a set of Merelo. 2002. Web newspaper layout optimization using simulated annealing.
IEEE Transactions on Systems, Man, and Cybernetics (2002).
fragments across different layouts by simultaneously optimizing [16] Eric Huang and Richard E Korf. 2013. Optimal rectangle packing: an absolute
for different metrics and content factors. Human annotations of the placement approach. Journal of Artificial Intelligence Research (2013).
resulting distribution indicate superior performance of the proposed [17] Eric C Huang and Richard E. Korf. 2013. Optimal Rectangle Packing: An Absolute
Placement Approach. J. Artif. Intell. Res. (2013), 47–87.
approach over existing baselines. Future work includes further qual- [18] Arlind Kopliku, Karen Pinel-Sauvagnat, and Mohand Boughanem. 2014. Aggre-
itative experiments to extract aspects of layouts that govern users’ gated Search: A New Information Retrieval Paradigm. Comput. Surveys (2014).
[19] Ranjitha Kumar, Jerry O Talton, Salman Ahmad, and Scott R Klemmer. 2011.
engagement with them. Once these have been identified, these factors Bricolage: example-based retargeting for web design. In SIGCHI Conference on
would need to be incorporated into the layout generation algorithm. Human Factors in Computing Systems. ACM.
[20] EG Co man Jr, MR Garey, and DS Johnson. 1996. Approximation algorithms for
bin packing: A survey. Approximation Algorithms for NP-Hard Problems (1996).
REFERENCES [21] Jakob Nielsen. 1999. User Interface Directions for the Web. Commun. ACM 42, 1
[1] Jaime Arguello. 2017. Aggregated Search. Foundations and Trends in Information (Jan. 1999), 65–72.
Retrieval (2017). [22] Taiwo O. 2015. Bin Packing Algorithms with Applications to Passenger Bus
[2] Jaime Arguello and Robert Capra. 2012. The Effect of Aggregated Search Coher- Loading and Multiprocessor Scheduling Problems. (2015).
ence on Search Behavior. In 21st ACM International Conference on Information [23] Peter O’Donovan, Aseem Agarwala, and Aaron Hertzmann. 2014. Learning
and Knowledge Management (CIKM). layouts for single-page graphic designs. IEEE transactions on visualization and
[3] J. O. Berkey and P. Y. Wang. 1987. Two-Dimensional Finite Bin-Packing Algo- computer graphics 20, 8 (2014), 1200–1213.
rithms. Journal of the Operational Research Society (1987). [24] Peter O’Donovan, Aseem Agarwala, and Aaron Hertzmann. 2015. Designscape:
[4] Gjermund Bø Brabrand. 2008. Dynamic layout optimization for newspaper web Design with interactive layout suggestions. In Proceedings of the 33rd annual
sites using a controlled annealed genetic algorithm. Masters Thesis, Gjovik ACM conference on human factors in computing systems. ACM, 1221–1224.
University College (2008). [25] Seonwook Park, Christoph Gebhardt, Roman Rädle, Anna Maria Feit, Hana
[5] Georg Buscher, Edward Cutrell, and Meredith Ringel Morris. 2009. What do you Vrzakova, Niraj Ramesh Dayama, Hui-Shyong Yeo, Clemens N Klokmose, Aaron
see when you’re surfing?: using eye tracking to predict salient regions of web Quigley, Antti Oulasvirta, et al. 2018. AdaM: Adapting Multi-User Interfaces
pages. In SIGCHI Conference on Human Factors in Computing Systems. for Collaborative Environments in Real-Time. In Proceedings of the 2018 CHI
[6] Jaime Carbonell and Jade Goldstein. 1998. The use of MMR, diversity-based Conference on Human Factors in Computing Systems. ACM, 184.
reranking for reordering documents and producing summaries. In Proceedings of [26] Filip Radlinski, Paul N. Bennett, Ben Carterette, and Thorsten Joachims. 2009.
the 21st annual international ACM SIGIR conference on Research and develop- Redundancy, Diversity and Interdependent Document Relevance. SIGIR Forum
ment in information retrieval. ACM, 335–336. 43, 2 (Dec. 2009).
[7] Harr Chen and David R. Karger. [n. d.]. Less is More: Probabilistic Models for [27] Balaji Vasan Srinivasan, Tanya Goyal, Varun Syal, Shubhankar Suman Singh, and
Retrieving Fewer Relevant Documents. In Proceedings of the 29th Annual Inter- Vineet Sharma. 2016. Environment Specific Content Rendering & Transformation.
national ACM SIGIR Conference on Research and Development in Information In Companion Publication of the 21st International Conference on Intelligent
Retrieval. User Interfaces. ACM.
[8] Flavio Chierichetti, Ravi Kumar, and Prabhakar Raghavan. 2011. Optimizing Two- [28] Shanu Sushmita, Hideo Joho, Mounia Lalmas, and Robert Villa. [n. d.]. Factors
dimensional Search Results Presentation. In 4th ACM International Conference Affecting Click-through Behavior in Aggregated Search Interfaces. In 19th ACM
on Web Search and Data Mining (WSDM). International Conference on Information and Knowledge Management (CIKM).
[9] E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson. 1997. Approximation 519–528.
Algorithms for NP-hard Problems. Chapter Approximation Algorithms for Bin [29] Yue Wang, Dawei Yin, Luo Jie, Pengyuan Wang, Makoto Yamada, Yi Chang, and
Packing: A Survey. Qiaozhu Mei. 2016. Beyond ranking: Optimizing whole-page presentation. In
[10] Kevyn Collins-Thompson. [n. d.]. Reducing the Risk of Query Expansion via Proceedings of the 9th ACM International Conference on Web Search and Data
Robust Constrained Optimization. In Proceedings of the 18th ACM Conference on Mining.
Information and Knowledge Management. [30] Darrell Whitley. 1994. A genetic algorithm tutorial. Statistics and computing
[11] Felipe SLG Duarte, Fabio Sikansi, Francisco M Fatore, Samuel G Fadel, and (1994).
Fernando V Paulovich. 2014. Nmap: A novel neighborhood preservation space- [31] Eduardo Xavier and Flavio Keidi Miyazawa. 2006. The Class Constrained Bin
filling algorithm. IEEE Transactions on Visualization & Computer Graphics 12 Packing Problem with Applications to Video-on-Demand. (2006).
(2014), 2063–2071.