Automatically generating personalized user interfaces with Supple

K.Z. Gajos et al. / Artificial Intelligence 174 (2010) 910–950
935
Fig. 25. The performance (quantified by the number of nodes considered by the search algorithm) of the two parallel algorithms compared to the best- performing single-threaded variant from Fig. 24. The Parallel algorithm combines algorithms driven by the bottom-up and the MRV heuristics. Results are presented for three different user interfaces studied systematically oversize constraints. To enable direct comparison, we use a log scale on the y-axes.
The worst-case performance of the parallel algorithms is up to two orders of magnitude better than of any of the single algorithms.
Note that the number of possible interfaces considered spans 15 orders of magnitude, from 216 for the map interface to
2
.
8
×
10 for the stereo interface. Yet, across this entire range, the median time to find the best interface remains under second.
The median performance of the two algorithms did not vary significantly when measured by the number of nodes explored by the search algorithm. But running on a dual-core processor, the Parallel algorithm was a little faster on average than Parallel. In the worst case, the Parallel algorithm typically explored fewer nodes, but required more time.
Again, this result reflects the particular hardware architecture used in the experiments.
While the average performance does not correlate with interface complexity, the worst-case performance does. In fact,
exponential regression reveals an exponential relationship between the number of possible interfaces and the worst-case execution time or the number of nodes explored by the search algorithm. For the Parallel algorithm, the relationship between the number of possible interfaces, n, and the number of nodes expanded is 22
.
52
×
n
0
.
246
(R
2
=
0
.
97), and for
Parallel-3 it is 18
.
83
×
n
0
.
247
(R
2
=
0
.
94). Fig. 26 illustrates these relationships. Of course, because the exponents smaller than 1, the performance scales sub-linearly, specifically as a root of n. Furthermore, the nearly identical exponents suggest that there is not substantial difference in performance between the two parallel algorithms. This is consistent with our earlier observation that the worst-case performance for the top-down variable ordering tended to overlap with one of the other two (Fig. 24).

936
K.Z. Gajos et al. / Artificial Intelligence 174 (2010) 910–950
Fig. 26. The worst-case performance of the two parallel algorithms with respect to the complexity of the user interface. The x-axes show the number of possible user interfaces. In the left graph, the y-axis shows the maximum number of nodes explored by the search algorithms before the best solution was found. In the right graph, the y-axis shows the actual time taken. The tests were conducted on a dual core machine. This is why the Parallel algorithm took more time than Parallel even though it explored fewer nodes on average.
Fig. 27. The worst-case performance of the Parallel algorithm with only forward checking (a limited version of constraint propagation) with respect to the complexity of the user interface. The x-axis shows the number of possible user interfaces and the y-axis shows the maximum number of nodes explored by the search algorithm. For comparison, the performance of the algorithm with full propagation of the size constraints enabled is shown in solid black line (bottom of the graph).
7.4.3. Importance of constraint propagation
Unsurprisingly, constraint propagation has a significant impact on the algorithm’s performance. Fig. 27 shows the performance of the Parallel algorithm with only forward checking instead of full constraint propagation for the size constraints.
For comparison, the dark line toward the bottom of the graph shows the performance of the algorithm with full constraint propagation enabled. For this interface (classroom, the performance was an order of magnitude worse both in the average case (936 versus 84 nodes) and in the worst case (21,088 versus 2131 nodes. The performance of the algorithm with constraint propagation entirely turned off was too slow to measure.
7.5. Performance when optimizing for expected speed of use
The cost function introduced in Section 5.2 allows Supple to generate user interfaces that are predicted to be the fastest fora particular person to use. The structure of that cost function does not support as efficient computation of an admissible heuristic for guiding the search as does the first cost function that was used for earlier analyses.
With this cost function, Supple needed between 3.6 seconds and 20.6 minutes to compute user interfaces. These results take advantage of the lower-bound estimation method for EMT
nav
, which reduced the runtime for one of the less complex interfaces from over 5 hours to 3.6 seconds, and without which more complex interfaces would have required days to be rendered.

K.Z. Gajos et al. / Artificial Intelligence 174 (2010) 910–950
937
Table 3
Lines of code used to construct and manage the user interfaces for several of the applications presented throughout this paper.
Classroom
Map
Email
Amazon
Font formatting
Stereo
Ribbon
Lines of user interface code 70 515 59 125 125 We note that execution times on the order of 10–20 minutes (in the worst case) will still allow practical deployment of the system, if caching is used, for users whose conditions do not change frequently.
7.6. Model complexity
Comparisons of code quantity among different approaches are often controversial. Yet, we feel it is useful to report the amount of code
4
devoted to the description and management of the user interface for several of the examples reported in this paper. These numbers are reported in Table 3. While we do not have the data showing how much code would be required to build analogous interfaces by hand, the numbers in Table 3 provide some evidence that our approach does not impose excessive burden on the programmer.

Download 5.78 Mb.

Share with your friends: