Jennifer L Wong

Weiping Liao

Fei Li

Lei He

Miodrag Potkonjak

Scheduling of Soft Real-Time Systems for Context-Aware Applications

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Application domains often imply a need for unique computational models and unique optimization goals. Recently, a new domain of context-sensitive mobile wireless applications emerged. Context can be defined as the set of environmental states and settings that either determine an application's behavior or in which an application event occurs and is interesting to the user [START_REF] Chen | A survey of context-aware mobile computing research[END_REF]. Context-sensitive applications include mobile applications, sensor networks, pervasive and ubiquitous computing, Internet browsing, video games, and virtual reality. In all these applications, the next set of computational tasks which might be executed statistically depend on the current context of the user and the current executed tasks. Additionally, there is intrinsic uncertainty about which context direction the user will follow.

We have developed a new computational model, statistical soft real-time systems (SSRTS). We represent the workload of a user as a system of tasks with execution dependencies. At each moment of time, the scheduler has information about the tasks in the current context of the user and statistical information about the likelihood of future pending tasks to be executed by the user. For all tasks, we have statistical information about the likelihood that they will be completed in a given amount of time on a given processor. Therefore, SSRTS considers uncertainty at two levels: the execution time for a single task and the user invoked subset of tasks. What is unique for SSRTS is that uncertainties are addressed using statistical techniques.

The SSRTS model is related to both hard and soft real time systems. The main difference from hard real-time systems and the SSRTS model is that the only a subset of the tasks needs to be executed and therefore their exists uncertainty. In comparison to classical soft real time systems, SS-RTS differs in the presence of statistical information about tasks and requirements which one has to complete the task in order to achieve a measure of benefit. Note that one can interpret traditional soft real-time systems (SRTS) as a special case of SSRTS, by partitioning each task in the SRTS into a series of smaller tasks.

Related Work

In this section, we briefly survey the related work in several directly related fields. The pervasive computing community and many others have contributed a number of notable efforts in this area, including [START_REF] Want | The active badge location system[END_REF]. Models of computation have been recognized as the first building block for the development of formally sound systems [START_REF] Jantsch | Modeling Embedded Systems and SoC's: Concurrency and Time in Models of Computation[END_REF]. Shin et al. discuss the task-level computational models for real-time applications [START_REF] Shin | Real-time computing: a new discipline of computer science and engineering[END_REF]. Scheduling of hard, soft, and a combination of hard and soft real-time systems has been also addressed in CAD literature [START_REF] Richter | Model composition for scheduling analysis in platform design[END_REF]. While hard real-time systems [START_REF] Ramamritham | Scheduling algorithms and operating systems support for real-time systems[END_REF] ask for an absolute guarantee that all deadlines are satisfied, there is no such requirement for soft real-time systems. Soft real-time systems has been mainly motivated by applications from two domains: databases [START_REF] Kao | Deadline assignment in a distributed soft real-time system[END_REF], and multimedia [START_REF] Jones | CPU reservations and time constraints: Efficient, predictable scheduling of independent activities[END_REF]. An important characteristic of real-time systems is the timing constraints of each task. Determining an esti- mate of the worst case execution time (WCET) for tasks is often crucial for making judgments concerning timing properties in real-time systems [START_REF] Li | Efficient microarchitecture modeling and path analysis for real-time software[END_REF]. We use non-parametric statistical techniques for the development of the task model due to their application to data which has arbitrary distributions and without any assumptions on the data [START_REF] Thisted | Elements of statistical computing[END_REF].

Preliminaries and Global Flow

A task is a single program which can be invoked and executed. For example, a task may be a single execution of a jpeg decoder, audio decompression, or audio player. Each task has a set of attributes including its name, type, utility (benefit), arrival time, deadline, and a statistical distribution function that characterizes its execution time. The utility of the task is the benefit gained by the user for complete execution of the task. The utility or benefit is proportional to the value of the programs that are executed within time intervals specified by the user. The point in time at which the task must be completed in order to receive benefit for the task is the deadline. The utility and the deadline can be statistically determined based on the users previous behavior i.e. according to their profile. The statistical distribution function (SDF) for execution time provides information about the statistical likelihood of specific runtimes for a task. The runtime of the task is plotted versus the likelihood of the task completing execution at each runtime. Between two tasks there can be two types of relationships: dependency and weighted likelihood. If the results of one task is needed for the execution of another task, we specify this relationship as a dependency. A weighted likelihood relationship reflects the user's likelihood to request the execution of a task after the completion of another task.

The system, shown in Figure 1 consists of three stages: off-line, on-line, and evaluation. The goal of the off-line stage is to statistically characterize each of the tasks in terms of their runtime and to determine the user profiles. In the on-line stage, the information learned in the off-line stage is used to guide the real-time scheduler. Lastly, the evaluation stage evaluates and validates the performance of the scheduler against lower bound estimates. The off-line stage starts with an analysis of the possible tasks that the user can invoke. Analysis of each of the tasks on different simulation platforms is performed in order to gather statistical runtime data for each of the tasks. Non-parametric statistical techniques are use to model the runtime of each task. The resulting output is the statistical distribution function (SDF) of execution times for each task. We discuss the technical details concerning this process in Section 4. Additionally, in this stage, information from the user concerning the user's task preferences is gathered.

Once the user profile and the task profiles have been established, the user can start to use the system. As the user changes contexts (e.g. moves from a particular place to a new place), different tasks can be invoked. The possible tasks in the user's context are contained in an instance of the task model which we discuss in Section 4, i.e. window of consideration. It is often beneficial to invoke a subset of pending tasks in order to maximize the overall benefit. The real-time scheduler schedules the possible tasks with the goal of providing the user with the maximal amount of benefit. When the user invokes a task, one of two situations may occur. In the first situation, the scheduler had pre-fetched the invoked task and the data is available. In this case, the scheduler has provided benefit to the user. However, if the scheduler had not pre-fetched the task, the task may still be finished by the tasks deadline. If so, and the task has exceeded its deadline the task finishes execution prior to the deadline placed according to the user's profile, benefit is gained. Otherwise, the task is dropped from consideration and the user gains no benefit. The purpose of the final stage, evaluation, is to determine the effectiveness of the modeling software and scheduling heuristic. Evaluation is done through a comparison with lower bound estimates.

Statistical Model of Task

The purpose of the task model is to provide a compact and accurate representation of soft real-time tasks with respect to their execution time. The task model has three hierarchical layers: window of consideration, intertask, and intratask. At the top is the window of consideration, which determines the current prospective of the model. The middle layer, intertask, encompasses the interaction between different tasks. Finally, the lowest level models each task in detail. Figure 2 illustrates these layers.

The intratask layer defines a single task according to its process requirements and statistical information. Each task is represented by four components: name or type of task, utility, deadline, and a statistical distribution function (SDF) for the task's runtime. The utility of the task measures the benefit that is gained by the application or user if the task is completed. The utility can be defined by the user in terms of application preferences, or can be determined based on the profile of the user. The profile can be statistical information gathered from the user's hard real-time requests or feedback from the user. The deadline of the task can be represented as absolute time or relative to the arrival time of the task. The deadline is based on the requirements placed by the user on the latency of the task. There is intrinsic uncertainty associated with the runtime of the task. In order to represent this uncertainty, a statistical distribution function (SDF) for the runtime of the task is used. The statistics for creation of the SDF can be gathered through off-line evaluation of the task under various conditions, as shown in the off-line stage of Figure 1.

In order to create a runtime model, in the form of an SDF, for each task, we use the non-parametrical statistical resubstitution technique and a greedy provably optimal algorithm. Before we discuss the iterative creation process for an SDF, we first introduce the notion of a cumulative statistical distribution function (CSDF) and a measure for differences between CSDFs. The CSDF is the likelihood that the runtime of task is less than or equal to the current time unit. The cumulative likelihood at time unit x of the CSDF as the x ∑ i=0 SDF(i) where SDF(i) is the value of the SDF at time i. The difference between two CDFs can be calculated by comparing the difference between the likelihoods at each time unit. We define the difference between a CSDF S and

k other CSDFs as m ∑ i=0 k ∑ j=0 |S(i) -CSDF j (i)|
where m is the length of the longest CSDF. This definition naturally captures the impact of differences on applications.

When creating a SDF to capture the statistical information about runtime of a task, the goal is to create an SDF which "best" represents the likelihood of the task's runtime. We define "best" as the SDF which has the smallest CSDF difference between itself and all other SDFs. The process of creating a representative SDF begins with the runtime data for each task which is collected from the simulation platforms. The initial collected data should be a representative set. Resubstitution is applied to the data for each task to form a large number of subset SDFs, at least a thousand subsets to be statistically sound. Each of the subset SDFs are then converted into CSDFs. A representative CSDF is first created that will later be converted to a representative SDF for the task. The representative CSDF is created by considering the values of each subset CSDF for each time unit. If there are an odd number of CSDF subsets, the median value is selected as the representative value for that time slot. In the case of an even number, the midpoint value between the two median defining values is selected. The selected values for each time slot are optimal. This is due to the fact that if any value selected which is between the CSDF value to the right or the left of the median value, then more than half of the other CSDF values will be at an increased distance from the representative value. Therefore, no other CSDF assignments for each value will result in a smaller difference.

The main purpose of the intertask layer is to represent the relationships between tasks. We introduce two types of directed relationships between tasks: dependencies and like- lihood. Dependency relationships imply that data from the initial task is needed in order for the second task to perform its function. For example, if the user requested a sound file to be played, the file must first be decompressed, then it can be played. In Figure 2 we represent dependency edges using solid arrows. The weighted likelihood edges, drawn as dotted arrows, represent the likelihood of the second task to be requested by the user after the execution of the initial task. Note that the resultant intertask model forms a directed acyclic graph (DAG). The highest layer in the hierarchy is the window of consideration. The window of consideration determines the portion of the model which is currently considered according to the user's context. The size of this window is dependent on the amount of available memory, the processing utility, and the requirements of the application.

Problem Formulation

In this section, we introduce the benefit maximization under uncertainty scheduling optimization problem. We also establish the computational complexity of the problem. For a context-sensitive computing application, the user has the opportunity to execute a variety of tasks dependent upon the users current context. Each task has uncertainty in terms of its execution time. It is also uncertain which of the tasks will be eventually request for execution. The goal is to pre-fetch, schedule, and execute tasks to achieve the highest overall utility.

A single directed acyclic graph, such as the subgraph defined by the window of consideration presented in the task model, is composed of task vertices and dependencies (partial order) and weighted likelihood edges. Each task in the graph corresponds to a single task to possibly be scheduled, and is composed of the four components as shown in Figure 2: name or type of task, utility of the task, deadline, and SDF. The goal is to maximize the total benefit achieved by scheduling tasks and completing each of these tasks before their deadline under the condition that benefit is only received if the task was requested (subset of tasks S).

We proved that the Maximum Benefit under Uncertainty Scheduling problem is computationally intractable since it is a special case of the Sequencing with Release Times and Deadlines Problem [START_REF] Garey | Computers and intractability: a guide to the theory of NP-completeness[END_REF] which is NP-complete. This special case occurs when the benefit for each task is 1, all tasks have a probability of execution equal to 1, the SDF of each task is replaced with a known static execution time, and all dependency and likelihood edges are removed.

Scheduling

The goal of the scheduling approach is to determine which tasks from the current window of consideration, or current context of the user, should be scheduled based on the user's likelihood to request the task to be executed and the benefit the user receives if the task is completed. The intuition behind the heuristic is to select tasks according to the following three criteria: (i) high likelihood of execution (likelihood edges), (ii) high user benefit, and (iii) SDF which show high likelihood to finish the task within its deadline. We assume that at periodic intervals of time, the current context of the user is provided to the algorithm, i.e. the window of consideration is refreshed. In our experimentation, the window of consideration is always two period lengths. The second assumption is that only single dependencies exist between two tasks, meaning a task can only be dependent on the output of one task. Note that this condition is often true in context-sensitive applications and in other situations one can reduce more complex situations to this one by introducing dummy tasks with runtime and benefit equal to zero. Using the three stated criteria, we have developed the following heuristic approach. For each period, we consider all tasks which have arrived and have not exceeded their deadline. All tasks which have dependency edges are merged into a single representative task, which we discuss later in this section. For each task, we consider its maximum potential and average potential according to the above mentioned three criteria. According to these two measures, we select the order of tasks to be executed in this period. If the task which is being executed exceeds it's deadline, the task is dropped and the next task executed. A special condition exists if the task is part of the dependency tree. In this case, if the task has exceeded its deadline, it should not necessarily be dropped due to the fact that its output maybe necessary to execute other task(s). In this case, we calculate the tasks maximum potential to finish within k additional units of time using the task's SDF. At the end of the period, each task which has not exceeded its deadline is kept to consider in the next period.

Algorithm:

1. Let b(t) be the benefit value for finishing task t; 2. Let SDF(t) be the probability distribution function for task t; 3. Let D(t) be the deadline for task t; 4. Let p(t) be the probability of executing task t, i.e. sum of all incoming probabilities; 5. Let R be the set of tasks that arrived before the current period; 6. Let MaxB be the maximum benefit density for task t; 7. Let AvgB be the average benefit density for task t;

but have not been finished; 8. Let W (t) be the weight of task t in our scheduling; 9. R = φ; 10. Foreach period P i { 11. Let S = R ∪ T i ; 12. Substitue the tasks in one dependency tree with a single task by combining SDF of tasks in the dependency tree; The pseudo-code for the approach is presented in Figure 3. Lines 1-9 define the notation used to represent the task model. The processing for each period begins on line 10. Essentially, at the beginning of period i, T i tasks arrive and are considered in conjunction with the tasks from the previous periods which have not passed their deadline. If there are any dependencies between the tasks, we combine then into a single tasks. Since only single dependencies exist, either a dependency chain or tree can be constructed. In the case of a tree, we simplify the situation, in order to make the algorithm efficient by converting the tree into a chain. It is done by performing depth-first search on the tree and placing the tasks in a chain according to order.

In order to represent the chain of dependency tasks as a single "combination" task, we must combine the SDFs to form a representative SDF. The method used to construct the combined SPDF is, for any given amount of time, we try all possible time allocation schemes to individual tasks in the dependency chain and use the best finishing probability, ie. achievable benefit, as the value for the combined SDF at that given time. For any given amount of time, there is an exponential number of possible allocation schemes for a dependency chain. We use a heuristic algorithm to create the combined SDF. First, for each task's SDF, we allocate time to that task such that the task may achieve the largest finishing probability in its SDF. Next, we sum all the best allocated times for all the tasks in the chain resulting in the total allocated time A for the dependency chain. To construct the combined SDF, we use a dynamic programming method. Suppose the given time for the combined SDF is A -1, we then examine the sensitivity of each task's PDF, i.e., if the allocated time to that task is reduced by one, how much benefit will be lost. We choose the task with the lowest sensitivity and reduce the time allocated to that task by one. This is the value of the combined SDF for A -1. Through this method, we can re-construct the combined SDF (combined benefit delivery function) by computing in both directions from A.

Once all tasks have been represented as independent tasks, we determine the suitability of each task for scheduling. The suitability is the task's potential according to the three criteria. Measures can be defined to summarize the potential benefit of a task. For example, we can define two measures: MaxB and AveB. Let l(x) be the likelihood of the SDF at time unit x. We define MaxB as the maximum( ( f (x)•b(t)•p(t))

x ), over all x in a domain where l(x) is defined. This measure essentially indicates the maximal potential benefit for a task normalized with respect to consumed time. The higher the MaxB, the more benefit this task delivers in the same amount of execution time in the best case scenario. The average expected benefit for a task with a given SDF is denoted by AvgB and defined as ∑( f (x)•b(t)•p(t)) length(SDF) . Obviously, neither the maximum nor the average metric alone is enough to guide the scheduling approach, because both abstract only some aspects of each SDF. Following, the maximum likelihood principle, for summarizing the SDF information, we use most likely expected benefit, MLEB, defined as ∑

( f (x)•b(t)•p(t))
x

. In order to prevent often selection of tasks with benefit variance too high or too low, we combine the MLEB with two other measures. If the ratio of the average runtime to the available time is low, we use MLEB and AveB and if high, we use MLEB and MaxB. The weight factor for MLEB is proportional to the square of the inverse of the ratio. The resulting weight is assigned to each task, and the tasks are sorted according to the highest weight value (line 21). Each task is scheduled in this order until the end of the period. If at any point in time a task exceeds it's deadline, the task is dropped, unless it is part of a dependency tree. For any task which has begun execution, and has not finished or passed its deadline, we shorten the task's SDF and rescale the SDF according to the amount of processing already completed. The tasks which still remain as possible executable tasks, are passed on to the next period, and the process is repeated.

Experimental Results

In this section, we present experimental evaluation of the developed techniques and algorithms. We have two goals. First, to demonstrate the relevancy and accuracy of the SDF in the task model. The second is to demonstrate the effectiveness of the benefit under optimization scheduling heuristic. In order to accomplish these goals, we compare the results with a lower bound which is also presented.

In order to evaluate the effectiveness of our approach, we introduce a lower bound technique. The approach is based on a relaxation of the benefits under uncertainty problem which replaces SDFs with static execution times, dependencies between tasks are removed, and preemption is allowed. For each fraction of a task that is executed, partial benefit is included into the overall benefit. The lower bound algorithm is applied on a period-by-period basis. For each time period, the algorithm runs the task with the highest benefit to runtime ratio, and preempts the task when a task with a higher ratio arrives or the task's deadline is reached.

In order to establish the effectiveness of both the SDF and the new approach for scheduling, we selected a variety of multimedia, statistical tasks, and sensor network tasks. The multimedia tasks (e.g. g721encode, gsmencode) were taken from the MediaBench test suite [START_REF] Lee | Mediabench: A tool for evaluating and synthesizing multimedia and communicatons systems[END_REF]. For statistical and computation tasks, we used programs (xfit, ksone, twofft) from the Numerical Recipes software [START_REF] Press | Numerical recipes in C : the art of scientific computing[END_REF]. The sensor network tasks, location discovery and exposure were used. SDFs from two benchmarks are shown in Figure 4.

In order to demonstrate the relevance and effectiveness of the SDFs as a measure of runtime over the average or worst case expected runtime in the model, we experimented using the heuristic algorithm. Fifty different real-time instances were created using the task model with the SDF, with the SDF replaced by average runtime, and with the SDF replaced by worst case runtime. Additionally, the instances varied in period length and amount of dependencies between tasks. Each of the instances were tested using the lower bound and heuristic approach. Table 1 provides the statistics for all of the examples. The use of the SDF in the task model proved to be more effective in all cases. The accuracy of the SDF to represent the expected runtime of a task was determined using the resubstitution and confidence calculation procedure presented in Section 4. For each of the SDFs created for the benchmark tasks, we validated using a 90% confidence interval of the SDF values at four likelihood intervals, 90%, 60%, 30%, and 10%. For a subset of the instances we present the true maximum trial runtime (in cycles) for each benchmark and the true confi- dence interval for each interval in Table 1. Additionally, we present the normalized confidence range.

We now present analysis of our heuristic scheduling approach. Comparison is performed against the lower bound. Additionally, we test the performance of the approach with varying processing utilization. The purpose of the utilization is to determine the effectiveness of the approach with respect to systems with varying resource limitations, such as laptops or portable devices such as PDAs. Figures 5 presents the performance results for twenty different scheduling instances, shown on the y-axis. The benefit achieved by the heuristic is normalized against the lower bound benefit (z-axis). The third dimension is the processor utilization factor. In Figure 5 the period length is 300 units. Similar results were obtained for a period of 200 units. In both cases with 100% utilization of the processor, we are able to achieve between 50-70% of the lower bound. With between 30-40% utilization, we can process all tasks.

Conclusion

We have developed a multi-resolution statistical soft real-time task model of computations that addresses the needs of context aware applications. We also have implemented a system of non-parametric statistical techniques for modeling the runtime of a specific task. Furthermore, we have proposed and tested a new cumulative potential-based task scheduling heuristic for maximizing utility.

Figure 2 .

 2 Figure 2. Task Model hierarchy: Window of Consideration, Intertask, Intratask levels.

Figure 3 .

 3 Figure 3. Pseudo-code for scheduling.

Figure 4 .

 4 Figure 4. SDFs of Benchmarks: location discovery and g721encode tasks.

Figure 5 .

 5 Figure 5. Algorithm benefit normalized vs. benefit of lower bound for varying utility.

  AveB + MLEB; } 21. Sort the tasks in S in non-increasing order by W (t); 22. Schedule the tasks in S according to W (t) until period P i is finished; 23. Drop task t in S only if it has passed its deadline D(t) and it is not a combined task from a dependency tree; 24. Truncate and re-scale the SDF(t) if task t in S is executed but not finished; 25. R = S; S = φ; }

	13. Foreach task t ∈ S{
	14.	Calculate MaxB(t, SDF(t), D(t), p(t));
	15.	Calculate AvgB(t, SDF(t), D(t), p(t));
	16. 17. 18.	Calculate MLEB(t, SDF(t), D(t), p(t)); if(ave runtime/period length > .5) W (t) = MaxB + MLEB;
	19.	else
	20.	W (t) =

Table 1 . (Left) Normalized benefit statistics for different runtime mechanisms used in task model. (Right) Confidence Intervals for SDFs of benchmarks.

 1

																		Max Value	10%	30%	60%	90%
				SDF				Ave.	Worst Case	g721encode Normalized	2.63E7	(3.6-11.4)•10 5 0.01-0.04	(2.4-3.3)•10 6 0.09-0.13	(4.5-6.2)•10 6 0.17-0.24	(1.0-1.5)•10 7 0.40-0.59
	MinB			33%				5%		9%				gsmencode	3.81E8	(.90-1.4)•10 6	(2.2-2.9)•10 7	(3.8-5.1)•10 7	(1.5-1.9)•10 8
	MaxB			71%				57%		55%			Normalized	0.02-0.04	0.06-0.08	0.10-0.14	0.40-0.51
	AveB			53%				39%		37%			xfit	2300	(1-1)•10 3	(1-1)•10 3	(1-1)•10 3	(1-1)•10 3
	Var			0.010			0.025		0.0242			Normalized	0.0478-0.0478	0.0478-0.0478 0.0478-0.0478	0.0478-0.0478
														Loc. Discovery	46200	(1.1-1.3)•10 4	(1.3-1.7)•10 4	(1.7-2.0)•10 4	(2.2-2.9)•10 4
																Normalized	0.025-0.3	0.3-0.37	0.37-0.46	0.48-0.65
		1
		0.95
		0.9
	Normailzed Benefit	0.75 0.8 0.85
		0.7
		0.65
		0.6
		10	9	8 Trial 7 6	5	4	3	2	1	1	0.9	0.8	0.7	0.6 Utilization	0.5	0.4	0.3	0.2

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE


Ali Iranli
email: iranli@usc.edu

Hanif Fatemi
email: fatemi@usc.edu

Massoud Pedram
email: pedram@usc.edu

HEBS: Histogram Equalization for Backlight Scaling

In this paper, a method is proposed for finding a pixel transformation function that maximizes backlight dimming while maintaining a pre-specified image distortion level for a liquid crystal display. This is achieved by finding a pixel transformation function, which maps the original image histogram to a new histogram with lower dynamic range. Next the contrast of the transformed image is enhanced so as to compensate for brightness loss that would arise from backlight dimming. The proposed approach relies on an accurate definition of the image distortion which takes into account both the pixel value differences and a model of the human visual system and is amenable to highly efficient hardware realization. Experimental results show that the histogram equalization for backlight scaling method results in about 45% power saving with an effective distortion rate of 5% and 65% power saving for a 20% distortion rate. This is significantly higher power savings compared to previously reported backlight dimming approaches.

Introduction

As the portable electronic devices become more intertwined with everyday life of people, it becomes necessary to put more functionality into these devices, run them at higher circuit speeds, and have them consume a small amount of energy. These electronic devices are becoming smaller and lighter and often required to operate with fancy Liquid Crystal Displays (LCD's) for increasing periods of time.

Unfortunately, the battery capacities are increasing in much slower pace than the overall power dissipation of these kinds of devices. Therefore, it is essential to develop low power design techniques to reduce the overall power dissipation of these devices. Previous studies on battery powered electronic devices have pointed out that the energy consumption in the Cold Cathode Fluorescent Lamp (CCFL), which is the backlight of an LCD, dominates the overall energy consumption of the device [1]. In the SmartBadge system for instance, the display consumes 28.6%, 28.6%, and 50% of the total power in the active, idle, and standby modes, respectively [1]. Unfortunately, as for other resources, one cannot tackle this energy hungry component with some form of power shutdown. This is due to the fact that LCD subsystem must be continuously refreshed and cannot be turned off or put to sleep without a significant penalty in performance and Quality of Service (QoS).

There are two main classes of techniques for lowering the power consumption of LCD subsystem. The first class of techniques is focused on the digital/analog interface between the graphics controller and the LCD controller [2] [START_REF] Salerno | Limited Intra-Word Transition Codes: An Energy-Efficient Bus Encoding for LCD Interfaces[END_REF]. These techniques try to minimize the energy consumption by taking advantage of different encoding schemes to minimize the switching activity of the electrical bus. For instance, reference [2] uses the spatial locality of the video data to reduce the number of transition on the DVI bus reducing its energy consumption by 75%. More recently, reference [START_REF] Salerno | Limited Intra-Word Transition Codes: An Energy-Efficient Bus Encoding for LCD Interfaces[END_REF] has extended the previous work by using the limited intra-word transition codes instead of single intra-word transition codes used in [2] and including the DC balancing conditions in the coding scheme to achieve more than 60% energy saving, on average compared to the basic transmission protocol. The second class of techniques is focused on the video controller and the backlight to lower the energy consumption of the display system. The key idea of these techniques follows from the observation that eye's perception of the light, which is emitted from the LCD panel, is a function of two parameters, 1) the light intensity of the backlight and 2) the transmittance of the LCD panel. Therefore, by carefully adjusting these two parameters one can achieve the same perception in human eyes at different values of the backlight intensity and the LCD transmittance. However, since the changes in energy consumption of the backlight lamp is higher than that of the LCD panel by orders of magnitude, one can save energy by simply dimming the backlight and increasing the LCD transmittance to compensate for the loss of backlight.

Reference [START_REF] Chang | DLS: Dynamic Backlight Luminance Scaling of Liquid Crystal Display[END_REF] was the first to propose a simple approach to the backlight scaling problem, where each pixel value is changed to achieve a higher transmittance through the LCD panel, thereby creating the possibility to reduce the backlight intensity and hence lowering the energy consumption. The main drawbacks of this approach are twofold; a) there is no measure of how distorted the new image would become, and b) manipulating pixels one by one is a time consuming process that limits the applicability of this approach. Image distortion after backlight luminance dimming is evaluated by the percentage of saturated pixels that exceed the range of pixel values, e.g., [0..255]. In contrast, reference [START_REF] Cheng | Power Minimization in a Backlit TFT-LCD by Concurrent Brightness and Contrast Scaling[END_REF] improved this basic approach by proposing the contrast fidelity as a measure of image distortion and solving the optimal transmittance scaling policy problem. Moreover, an elegant approach for hardware implementation of the transmissivity scaling function by using the builtin reference voltages is proposed which eliminates the pixel-by-pixel manipulation of the image. The authors report a 3.7X power saving with less than 10% contrast distortion in the image.

In this paper, a method is proposed for finding a pixel transformation function that maximizes backlight dimming while maintaining a pre-specified distortion level. This is achieved with the following algorithm, called HEBS (for Histogram Equalization for Backlight Scaling):

1) Given an original image, , and an upper bound on the tolerable image distortion, we determine the minimum dynamic range, R, of pixel values in a transformed image. The goal is to achieve the maximum power savings as a result of a follow-on backlight dimming. Therefore, this step also produces the optimum backlight scaling factor, . 2) We determine a transformation function, , which takes the original image histogram (with dynamic range N) to a uniform distribution histogram with a range of R. This is in turn accomplished by mapping the N pixel values in the original image to the R target values of the transformed image so that the difference between the resulting histogram and the uniform distribution histogram is minimized. 3) For reasons having to do with the existing infrastructure for grayscale level assignment and the efficiency of a hardwarebased implementation of the proposed transformation, we approximate with a piecewise linear function, such that the squared error difference between and is minimized. 4) We construct the transformed image by applying to the original image, . At the same time, we dim the backlight by factor . The advantages of HEBS compared to previous backlight dimming techniques are:

1) A more accurate definition of the image distortion which takes into account both the pixel value differences and a model of the human visual system is used. 2) A powerful image histogram "compression" technique which allows us to reduce the dynamic range of an image subject to a given image distortion level. This should be contrasted to prior works which can only reduce the image dynamic range by saturating the pixel values either at one end [START_REF] Chang | DLS: Dynamic Backlight Luminance Scaling of Liquid Crystal Display[END_REF] or both ends [START_REF] Cheng | Power Minimization in a Backlit TFT-LCD by Concurrent Brightness and Contrast Scaling[END_REF] of the image histogram. 3) Amenable to highly efficient hardware realization by making minimal change to the existing Programmable LCD Reference Driver (PLRD). 4) An additional power saving of 15% compared to the best of the existing strategies. In a typical battery-powered mobile computer system, this constitutes a total additional system power saving of 3% in active mode.

Background

Figure 1a shows the typical architecture of the digital LCD subsystem in a microelectronic device. There are two main components in this subsystem: a) video controller and frame buffer memory and b) LCD controller and panel. The image data, which is received from the processing unit, is first saved into the frame buffer memory by the video controller and is subsequently transmitted to the LCD controller through an appropriate analog (e.g., VGA) or digital (e.g., DVI) interface. The LCD controller receives the video data and generates a proper grayscale -i.e., transmissivity of the panel -for each pixel based on its pixel value. All of the pixels on a transmissive LCD panel are illuminated from behind by the backlight. To the observer, a displayed pixel looks bright if its transmittance is high (i.e., it is in the 'on' state), meaning it passes the backlight. On the other hand, a displayed pixel looks dark if its transmittance is low (i.e., it is in the 'off' state), meaning that it blocks the backlight. For color LCD's, different filters are used to generate shades of three main colors (i.e. red, blue, and green), and then color pixels are generated by mixing three sub-pixels together to produce different colors. Figure 1b depicts the LCD controller in more detail. The data received from the video bus is used to infer a row of pixels timing information and respective grayscale levels. Then, this timing information is used to select the appropriate row in the LCD matrix. Next, the pixel values are converted to the corresponding voltage levels to drive the thin-film-transistors (TFT's) on different columns of the selected row. The backlight bulb is powered with the aid of a DC-AC converter, to provide the required illumination of LCD matrix.

Each pixel has an individual liquid crystal cell, a TFT, and a storage capacitor (cf. Figure 1c). The electrical field of the capacitor controls the transmittance of the liquid crystal cell. The capacitor is charged and discharged by the TFT. The gate electrode of the TFT controls the timing for charging/discharging of the capacitor when the pixel is scanned (or addressed) by the tracer for refreshing its content. The (drain-) source electrode of the TFT controls the amount of charge. The gate electrodes and source electrodes of all TFT's are driven by a set of gate drivers and source drivers, respectively. A single gate driver (called a gate bus line) drives all gate electrodes of the pixels on the same row. The gate electrodes are enabled at the same time the row is traced. A single source driver (called a source bus line) drives all source electrodes of the pixels on the same column. The source driver supplies the desired voltage level (called grayscale voltage) according to the pixel value. In other words, ideally, the pixel value transmittance, t(X), is a linear function of the grayscale voltage v(X), which is in turn a linear function of the pixel value X. The transfer function of source driver which maps different pixel values, X, into different voltage levels, v(X) is called the grayscale-voltage function. If there are 256 grayscales, then the source driver must be able to supply 256 different grayscale voltage levels. For the source driver to provide a wide range of grayscales, a number of reference voltages are required. The source driver mixes different reference voltages to obtain the desired grayscale voltages. Typically, these different reference voltages are fixed and designed as a voltage divider.

Mathematically speaking, in a transmissive TFT-LCD monitor, for a pixel with value X, the luminance I(X) of the pixel 1 is:

( ) . ( ) I X b t X (1a)
where t(X) is the transmissivity of the TFT-LCD cell for pixel value X, and b [0,1] is the (normalized) backlight illumination factor with b=1 representing the maximum backlight illumination and b=0 representing no backlight. Note that t(X) is a linear mapping from [0,255] domain to [0,1] range. In backlight scaled TFT-LCD, b is scaled down and accordingly t(X) is increased to achieve the same image luminance.

Reference [START_REF] Chang | DLS: Dynamic Backlight Luminance Scaling of Liquid Crystal Display[END_REF] describes two backlight luminance dimming techniques. This technique dims the backlight and compensates for the luminance loss by adjusting the grayscale of the image to increase its brightness or contrast. More precisely, ( ) . ( ( , ))

I X t X (1b)
where 0< 1 is the backlight scaling factor and (X, ) is the pixel transformation function.

Let x denote the normalized pixel value, i.e., assuming an 8-bit color depth, x=X/255. The authors of [START_REF] Chang | DLS: Dynamic Backlight Luminance Scaling of Liquid Crystal Display[END_REF] scale the backlight luminance by a factor of while increasing the pixel values from x to (x, ) by two mechanisms. Clearly, (x, )=x denotes the identity pixel transformation function (cf. Figure 2a.) The "backlight luminance dimming with brightness compensation" technique uses the following pixel transformation function (cf. Figure 2b):

( , ) min(1, 1 ) x x (2a)
whereas the "backlight luminance dimming with contrast enhancement" technique uses this transformation function (cf. Figure 2c):

( , ) min(1, ) x x (2b)
In these schemes, the optimal backlight factor is determined by the backlight luminance dimming policy subject to the given distortion rate. To calculate the distortion rate, an image histogram estimator is required for calculating the statistics of the input image. Note that the image histogram simply denotes the marginal distribution function of the image pixel values.

Reference [START_REF] Cheng | Power Minimization in a Backlit TFT-LCD by Concurrent Brightness and Contrast Scaling[END_REF] proposes a different approach in which the pixel values in both dark and bright regions of the image are used to enable a further dimming of the backlight. The key idea is to first truncate the image histogram on both ends to obtain a smaller dynamic range for the image pixel values and then to spread out the pixel values in this range (by applying an affine transformation) so as to enable a more aggressive backlight dimming while maintaining the contrast fidelity of the image. The pixel transformation function is given as (cf. Figure 2d):

1 Illuminance can be used to characterize the luminous flux emitted from a surface. Most photographic light meters measure the illuminance. In terms of visual perception, we perceive luminance. It is an approximate measure of how "bright" a surface appears when we view it from a given direction. Luminance is measured in lumens per square meter per steradian. The maximum brightness of a CRT or LCD monitor is described by luminance in its specification. 1, 1 ( , )

x g l g l cx d g x g c d u l g g g g u u l l g x u x (3)
where (g l ,0) and (g u ,1) are the points where (x, )=cx+d intersects (x, )=0 and (x, )=1, respectively. The implementation is quite simple requiring minimal change to the built-in Programmable LCD Reference Driver (PLRD). Notice that PLRD allows a class of linear transformations on the backlight-scaled image, resulting in both brightness scaling and contrast scaling. Clearly, brightness and contrast are the two most important properties of any image. Recall that for transmissive LCD monitors, the brightness control changes the backlight illumination and the contrast control changes the LCD transmittance function.

The previous approaches cannot fully utilize the power saving potential of the dynamic backlight scaling scheme, due to the fact that their measure of distortion between the original the backlightscaled image is an overestimation. This is because these approaches simply either minimize the number of saturated pixel values [START_REF] Chang | DLS: Dynamic Backlight Luminance Scaling of Liquid Crystal Display[END_REF] or maximize the number of pixel values that are preserved [START_REF] Cheng | Power Minimization in a Backlit TFT-LCD by Concurrent Brightness and Contrast Scaling[END_REF].

It is well known that image distortion (more precisely, the difference between a pair of similar images) is a complex function of the visual perception, and hence, it cannot be correctly evaluated by comparing the images pixel by pixel (i.e., calculating the root mean squared error of the corresponding pixel values) or as a whole (i.e., using the integral of the absolute value of the histogram differences) [START_REF] Teo | Perceptual image distortion[END_REF] [START_REF] Wang | A Universal Image Quality Index[END_REF]. A correct measure of distortion should appropriately combine the mathematical difference between pixel values (or histograms) and the characteristics of the human visual system. One approach presented in [START_REF] Wang | Image quality assessment: From error visibility to structural similarity[END_REF] is to perform some transformation on both the original and new (i.e., backlight-scaled) images according to a human visual system model [START_REF]Digital Image Processing[END_REF], and then, compare the transformed results using quantitative measures.

Histogram Equalization for Backlight Scaling (HEBS)

Due to the coherence of the objects within an image, pixels describing a single object generally have similar luminous intensity values [START_REF]Digital Image Processing[END_REF]. 2 The single-band grayscale spreading (cf. Figure2d) attempts to exploit this object coherence by enhancing the contrast within a band (sub-range) of the pixel values at the expense of the remaining ones, thereby, creating the opportunity for a more aggressive backlight dimming policy. However, a single band is used for the entire image. Intensity values lying above or below the band are mapped to the maximum and minimum possible intensity values, respectively. The result is that the 2 Luminous intensity is the photometric equivalent of radiance intensity.

pixel values within the window are displayed with marginal loss of quality, while information in the other parts of the image is discarded.

Let and '= ( , ) denote the original and the transformed image data, respectively. Moreover, let D( ' and P( ' ) denote the distortion of the images and ' and the power consumption of the LCD-subsystem while displaying image ' with backlight scaling factor, .

Dynamic Backlight Scaling (DBS) Problem:

Given the original image and the maximum tolerable image distortion D max, find the backlight scaling factor and the corresponding pixel transformation function '= ( , ) such that P( ' ) is minimized and D( ' D max .

The general form of DBS problem as stated above is difficult to solve due to the complexity of the distortion function, D, and also the nonlinear function minimization step that is required to determine ( , ). In the following, we will try to simplify this problem by 1) fully utilizing the dynamic range of the transformed image ' in order to achieve the minimum TFT-LCD power consumption P( ', ) and 2) by constraining the pixel transformation function to the family of piecewise linear functions (because these piecewise linear functions are desirable from implementation point of view; cf. section 4.2.) Intuitively, to reduce the dynamic range of a given image one can discard the pixels corresponding to the grayscale levels with low population. This in turn minimizes the number of discarded pixels and hence minimizes the image distortion. On the other hand, for an image with a histogram which is uniformly populated with pixels in different grayscale levels, every level is as important as the other and discarding any grayscale level can cause a significant image distortion. Therefore, a "good" transformation which solves the DBS problem i.e., minimizes P( ' , ), is the one which transforms the original image histogram into a uniform intensity histogram with a minimal dynamic range. Having made this selection, we can now deal with the complexity of the distortion function as follows. We set the dynamic range of a benchmark image to some target value and plot the distortion value of the transformed image as a function of this target range We repeat this process for a number of different target ranges per image and for a large number of images in the database. Next, resorting to standard regression analysis techniques, we will calculate the "best" global fit to these distortion values. The result will be an empirical curve which maps the observed distortion function values to target dynamic range of transformed images. We call this curve the distortion characteristic curve (cf. section 5.1c)

Global Histogram Equalization

We is minimized.

If the targeted histogram is a uniform distribution between upper and lower limits, g min and g max , 3 then to minimize (4) the transformation function can be calculated as: where h(x) denotes the marginal distribution histogram. We can then use the first order difference approximation for the differentiation operator, to calculate the discrete transfer function as

1 0 1 ( ) ( ) ( ) i k min min k k k k k m a x x g x h x g g x N
x x [START_REF] Teo | Perceptual image distortion[END_REF] where x i G are the center points for the histogram buckets and h(x k ) are the histogram value.

HEBS Implementation

Figure 4 depicts the flow of the HEBS algorithm. A user-specified maximum tolerable image distortion is first read as input and is subsequently used to look up the minimum admissible dynamic range for the image from the distortion characteristic curve (cf. Section 3.) Using this minimum admissible dynamic range and the transmissivity characteristics of the TFT display, a maximum backlight scaling factor, , is calculated and used to scale down the CCFL backlight. Moreover, this minimum dynamic range along with the original image histogram will be used by the GHE problem solver to calculate the pixel transformation function ( , ). Next, the transformation function is approximated by a piecewise linear function, ( , ), which is in turn used to determine the reference grayscale voltages, and to transform the original pixel values to new ones for the displayed image. In [START_REF] Cheng | Power Minimization in a Backlit TFT-LCD by Concurrent Brightness and Contrast Scaling[END_REF], Cheng et al proposed an elegant and highly efficient approach for backlight scaling implementation based on the reference voltages of the source drivers. Figure 5a shows the schematic of the built-in reference voltage driver of a typical LCD panel (recall that the voltage divider provides the required reference voltages for the source driver buffers.) For example in [START_REF] Philips | LP064V1 Liquid Crystal Display[END_REF], an Analog Devices input LCD reference driver [START_REF]AD8511 11-Channel, Muxed Input LCD Ref[END_REF] is used with a 10-way voltage divider. The proposed approach in [START_REF] Cheng | Power Minimization in a Backlit TFT-LCD by Concurrent Brightness and Contrast Scaling[END_REF] adds controllable switches to both ends of the voltage driver to be able to clamp the low and high gray scale levels to the minimum and maximum gray scale values, respectively, thereby reducing the dynamic range of the image and increasing the slope of the grayscale-voltage function (cf. Sec. 2) to realize contrast compensation. However, this solution is limited in two ways; 1) It can only generate a transfer function of singleband grayscale spreading form (cf. Figure 2d), and 2) the linear region of the transfer function can only have a single slope. To implement HEBS, we use a hierarchical structure for the reference voltage dividers as shown in figure 5b. This structure provides more flexibility in creating different slopes for multiple linear regions of the grayscale-voltage transfer function. Moreover, adding switches between different grayscale levels enables one to provide flat-bands not only at the two ends of the image histogram, but also in the middle range of the gray scale levels.

To achieve multiple output slopes for the grayscale-voltage transfer function, k different controllable voltage sources, V i , are needed (cf. Figure 5b.) These voltage sources are normally set to voltage levels

i d d V i V k
with i=1…k, creating a transfer function with slope of one.

Here V dd denotes the supply voltage, and i and k denote the voltage source number and total number of available voltage sources. To create different slopes for different regions of the grayscale values, one can change the voltage levels of controllable sources to create a k-band grayscale spreading function as described below. In particular we describe a procedure for approximating the pixel transformation function ( , ) with a piecewise linear function ( , ), and then explain how to determine the voltage levels V i , to implement this approximated function.

TFT-LCD displays are only capable of displaying a finite number of different grayscale levels, therefore, the input and output values of the transformation function ( , ) are discrete. This observation implies that even the exact form of the transformation function ( , ) as given by ( 7) is a piecewise linear function. However, the number of linear segments of ( , ) is ( ) O G , which is too large for efficient hardware implementation. We therefore approximate ( , ) with another piecewise linear function that has a small number of linear segments.

Let P={p 1 , …, p n }={(x 1 , y 1 ), …, (x n , y n )} denote the ordered set of endpoints of each linear segment in exact form of ( , ) starting from x 1 =0 for the darkest to x n =255 for the brightest grayscale level. Moreover, let Q={q 1 , …, q m }, denote the ordered set of the endpoints of linear segments in ( , ), which is the approximation of ( , ). Clearly, we have the following:

1 1 1 ; m n i j i k j Q P
q p and q p q p and q p where k (8)

Piecewise Linear Coarsening (PLC) Problem: Given a piecewise linear curve P, approximate it by another piecewise linear curve Q with a given number of line segments m so that the mean squared error between ( , ) and ( , ) is minimized.

The PLC problem can be solved using a dynamic programming technique. Let E(n,m) denote the mean squared error between the original curve with n points and its best approximation with m n points. Then, 1... 1 ( , ) ( ( , 1) ( ))

(1, 0) 0, ( , 0) , (1, ) 0 , Using the solution for the PLC problem, the voltage levels V i , are calculated as

. i q i d d Y V V ( 10
) i q
Y denotes the y-component of point q i . Note that the backlight dimming factor is present in denominator to spread the grayscale level of the resulting image, and hence, compensating the loss of brightness due to backlight dimming.

5

Experimental results

Characterization a) Cold Cathode Fluorescent Lamp (CCFL)

The CCFL illumination is a complex function of the driving current, ambient temperature, warm-up time, lamp age, driving waveform, lamp dimensions, and reflector design [START_REF] Williams | A fourth generation of LCD backlight technology[END_REF]. In the transmissive TFT-LCD application, only the driving current is controllable. Therefore, we model the CCFL illumination as a function of the driving current only and ignore the other parameters. Accounting for the saturation phenomenon in the CCFL light source [START_REF] Cheng | Transmittance scaling for reducing power dissipation of a backlit TFT-LCD[END_REF], we use a two-piece linear function to characterize the power consumption of CCFL as a function of the backlight factor: . 0 ( ) . 1

lin lin s backlight sat sat s A C C P A C C ( 11
)
Relationship between the CCFL illumination (i.e., luminous flux incident on a surface per unit area) and the driver's power dissipation for the CCFL in LG Philips transmissive TFT-LCD LP064V1 [START_REF] Philips | LP064V1 Liquid Crystal Display[END_REF] is shown in Figure 6a. The CCFL illumination increases monotonically as the driving power increases from 0 to 80% of the full driving power. For values of driving power higher than this threshold, the CCFL illumination starts to saturate. The saturation phenomenon is due to the fact that the increased temperature and pressure inside the tube adversely impact the efficiency of emitting visible light [START_REF] Co | CFL] cold cathode fluorescent lamps[END_REF].

After interpolation, we obtain the following coefficient values for the CCFL in LG Philips transmissive TFT-LCD LP064V1: a=0.02449, b= 0.04984, and c=0.993. The power consumption of a normally white TFT-LCD panel decreases slightly as its global transmittance increases. In other words, while maintaining the same luminance, the power consumption of the TFT-LCD decreases when dimming the backlight (which diminishes the power savings of a backlight dimming approach.). However, the change in the TFT-LCD power consumption is quite small compared to the change in CCFL power consumption. In contrast, power consumption of normally black TFT-LCD panel increases slightly as its global transmittance increases (which increases power savings of a backlight dimming approach.) However, for either type of the TFT-LCD, the change in power consumption as a function of the transmittance is so small that it can be ignored.

c) Distortion characteristic curve

To characterize the distortion of different images with respect to change in their dynamic range, we set the dynamic range of a benchmark image to some target value and plot the distortion value of the transformed image as a function of this target range. We adopted the universal image quality index proposed in [START_REF] Wang | A Universal Image Quality Index[END_REF] as our distortion measure and used a set of benchmark images from the USC SIPI Image Database (USID) [START_REF] Weber | The USC-SIPI image database version 5[END_REF]. The USID is considered the de facto benchmark suite in the signal and image processing research field [START_REF]Digital Image Processing[END_REF]. Figure 7 depicts the resulting distortion values for these images when the dynamic range of the transformed image is set to ten different values. Figure 8 is a subset of benchmarks reported to provide a visual reference for the distortion measure. Next, we used standard curve fitting tools provided in MATLAB version 7 release 14 to find the best "average" and "worstcase" global fits to these distortion values. The result is an empirical curve depicted in Figure 7, which maps the observed distortion function values to target dynamic range of transformed images.

Backlight scaling results

To show the effectiveness of HEBS approach the power saving for different images from USC SIPI database is reported in table 1. These power savings are generated for three different values of distortion levels. Clearly, by increasing the maximum tolerable distortion level the power saving should increase, which is also confirmed with listed results. Please note that the average power saving of 58% is achieved only for mere distortion level of 10%. This is about 15% increase in power saving comparing to the results reported in [START_REF] Chang | DLS: Dynamic Backlight Luminance Scaling of Liquid Crystal Display[END_REF] and [START_REF] Cheng | Power Minimization in a Backlit TFT-LCD by Concurrent Brightness and Contrast Scaling[END_REF].

Conclusions

In this paper, histogram equalization for backlight scaling with prespecified image distortion level was proposed. The proposed approach was based on an accurate definition of the image distortion.

Experimental results showed the effectiveness of HEBS method. In future work alternative distortion measures and histograms equalization methods will be evaluated.

  a. LCD subsystem architecture b. LCD component architecture c. TFT cell schematic Figure 1. TFT-LCD screen 0

  propose a global histogram equalization scheme in which the intensity values in the image are altered such that the resulting image has the uniform intensity histogram, with the desired minimum (g min ) and maximum (g max ) grayscale limits. This transformation may be accomplished by the use of the cumulative distribution function of the pixel intensities to generate the intensity remapping function. In this approach the resulting image will utilize the available display levels very well, because the transformation function is based on the statistics of the entire image. More precisely, let us denote the cumulative distribution histogram of the original image by H, and the different grayscale values of the image pixels by x which are selected from a finite set of values G, (e.g. G=[0..1]). Transformation function : G G is a monotonic function, which maps the original pixel values x into a new pixel values x' and as a result equalizes cumulative histogram H to become the cumulative uniform histogram, U. (that is a sloped line going from 0 to N, where N represents the number of pixels over which the histogram has been calculated, i.e. number of pixels in the image.) Global Histogram Equalization (GHE) Problem: Given the original image cumulative histogram H, find a monotonic transformation : G G where G=[0..1] such thata. identity b. grayscale shift c. grayscale spreading d. single-band grayscale spreading Figure 2. Pixel transformation functions(

  actual implementation, it is common to have a discrete version of histogram instead of the cumulative histogram. To convert (5) into a histogram based formulation one can differentiate both sides of (5

Figure 3 .

 3 Figure 3. k-window grayscale spreading function 3 U(x)=0 for x < g min ; U(x)=N.(x-g min ) / (g max -g min ) for g min x g max ; and U(x)=N for x>g max .

Figure 4 .

 4 Figure 4. Histogram Equalization for Backlight Scaling flow

  e(j) denotes the mean squared error incurred by approximating all segments between p j and p n by a single line connecting p j to p n . The time complexity of this algorithm is

  C s =0.8234, A lin =1.9600, C lin =-0.2372, A sat =6.9440, and C sat = 4.3240. b) TFT-LCD display matrix The hydrogenated amorphous silicon (a-Si:H) is commonly used to fabricate the TFT in display applications. For a TFT-LCD panel, the a-Si:H TFT power consumption can be modeled by a quadratic function of pixel value x [0,1] [15] performed the current and power measurements on the LG Philips, LP064V1 LCD. The measurement data are shown in Figure 6b. The regression coefficients are thus determined as:

Figure 6

 6 Figure 6.a. CCFL illuminance (i.e., backlight factor b) versus driver's power consumption for a CCFL source

Figure 7 .

 7 Figure 7. Distortion vs. dynamic range [3] S. Salerno, A. Bocca, E. Macii, M. Poncino, "Limited Intra-Word Transition Codes: An Energy-Efficient Bus Encoding for LCD Interfaces," Proc. Of ISLPED, Aug. 2004, pp. 206-211. [4] N. Chang, I. Choi, H. Shim, "DLS: Dynamic Backlight Luminance Scaling of Liquid Crystal Display," IEEE Transactions on Very Large Scale Integration Systems, Vol. 12, No. 8, Aug. 2004, pp.837-846. [5] W-C. Cheng and M. Pedram, "Power Minimization in a Backlit TFT-LCD by Concurrent Brightness and Contrast Scaling," IEEE Transactions on Consumer Electronics, Vol. 50, No. 1, Feb. 2004, pp. 25-32. [6] Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, "Image quality assessment: From error visibility to structural similarity," IEEE Transactions on Image Processing, vol. 13, no. 4, pp.600-612, Apr. 2004. [7] P.C. Teo and D.J. Heeger, "Perceptual image distortion," ISET/SPIE's Symposium on Electronic Imaging: Science and Technology, 1994. [8] Zhou Wang and Alan C. Bovik, "A Universal Image Quality Index," IEEE Signal Processing Letters, vol. 9, no. 3, March, 2002. [9] Digital Image Processing, W. K. Pratt, Third Ed., John Wiley & Sons, 2003. [10] W-C. Cheng and M. Pedram, "Transmittance scaling for reducing power dissipation of a backlit TFT-LCD," In Ultra Low-power Electronics and Design, Edited by Enrico Macii, Kluwer Academic Publisher, June 2004. [11] LG Philips, LP064V1 Liquid Crystal Display. [12] Analog Devices, AD8511 11-Channel, Muxed Input LCD Ref. Drivers. [13] J. Williams, "A fourth generation of LCD backlight technology," Linear Technology Application Note 65, Nov. 1995. [14] Stanley Electric Co., Ltd., [CFL] cold cathode fluorescent lamps, 2003. [15] H. Aoki, "Dynamic characterization of a-Si TFT-LCD pixels," HP Labs 1996 Technical Reports (HPL-96-19), February 21, 1996. [16] A. G. Weber, "The USC-SIPI image database version 5," USC-SIPI Report #315, Oct. 1997. Also http://sipi.usc.edu/services/ database/Database.html.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE


Fabien Lauer
email: fabien.lauer@loria.fr

Error bounds with almost radical dependence on the number of components for multi-category classification, vector quantization and switching regression

Keywords: Learning theory, Rademacher complexity, Kernel methods, Regularization

This paper presents a simple approach for obtaining efficient error bounds in learning problems involving multiple components. In particular, we obtain error bounds with a close to radical dependency on the number of components for multi-category classification, vector quantification and switching regression when the regularization scheme relies on a sum of norms over the components. These results are obtained thanks to the combination of a number of structural results on Rademacher complexities and a suitable handling of the structure of the regularizer.

Introduction

This paper focuses on learning problems involving multiple components. A good example is multi-category classification with margin classifiers based on one score function (here called component) per category. Other examples include vector quantization/clustering and switching regression. In vector quantization, one is interested in estimating a model (or codebook) made of a finite number of components (or codepoints) that can well approximate the observations of a random variable. Switching regression works similarly, but with random input-output pairs and components that are functions approximating the output given the input. In this paper, we propose a unified approach to derive generalization error bounds with sublinear dependency on the number of components for all these problems.

For such problems, the literature provides error bounds based on the analysis of Rademacher complexities [START_REF] Bartlett | Rademacher and Gaussian complexi-ties: Risk bounds and structural results[END_REF]. These bounds are linear in the number C of components as they are derived from a decomposition of the Rademacher complexity of interest into a sum of Rademacher complexities over the component function classes, see [START_REF] Kuznetsov | Multi-class deep boosting[END_REF] for multi-category classification, [START_REF] Biau | On the performance of clustering in Hilbert spaces[END_REF] for clustering and [START_REF] Lauer | Error bounds for piecewise smooth and switching regression[END_REF] for switching regression. This dependency on the number of components can be made sublinear by using chaining arguments and covering numbers, see, e.g., [START_REF] Guermeur | L p -norm Sauer-Shelah lemma for margin multi-category classifiers[END_REF][START_REF] Musayeva | A sharper bound on the Rademacher complexity of margin multi-category classifiers[END_REF][START_REF] Lauer | Error bounds for piecewise smooth and switching regression[END_REF]. However, this comes at the cost of slower convergence rates in the sample size n, except for linear models in a finite-dimensional space where a dependency on the dimension is introduced, see, e.g., [START_REF] Bartlett | The minimax distortion redundancy in empirical quantizer design[END_REF].

These results typically consider that the model belongs to a product of independent component classes, usually containing elements with bounded norm, while many practical methods implement a regularization scheme corresponding to a bound on a sum of norms over the components. By exploiting this form of regularization more precisely, we show how to derive error bounds with a O( √ C log C) growth rate with respect to C without hindering the convergence rate. More precisely, our approach uses previous results by [START_REF] Kuznetsov | Multi-class deep boosting[END_REF][START_REF] Biau | On the performance of clustering in Hilbert spaces[END_REF][START_REF] Lauer | Error bounds for piecewise smooth and switching regression[END_REF] on the decompositions of the Rademacher complexities and leads to convergence rates similar to those obtained in these references, i.e., in O(1/ √ n).

For multi-category classification, our assumption on the regularization scheme was previously used in [START_REF] Lei | Multi-class SVMs: From tighter datadependent generalization bounds to novel algorithms[END_REF] in a more efficient manner, resulting in a growth rate that varies between O(log C) and O( √ C) depending on the precise form of the regularization. 1 However, the derivation of this result requires additional tools and a more involved analysis, while our proofs remain shorter and more simple. In addition, the simplicity of the proposed approach allows its easy extension to other settings, whereas it is not known yet whether the technique of [LDBK15] also applies to vector quantization or switching regression.

For clustering/vector quantization and switching regression, it appears that such assumptions on the model class have not been considered in previous work to tighten the error bounds. However, note that for data living in a finite-dimensional Euclidean space, known bounds, see e.g., [START_REF] Bartlett | The minimax distortion redundancy in empirical quantizer design[END_REF], are in O( √ C), so that we here focus on Hilbert spaces of large or infinite dimension. Specifically, when considering the finitedimensional case we assume that the input data live in R d with d > log C. Indeed, our analysis shows that we can remove the radical dependency on d at the cost of an additional √ log C factor. We claim to provide a "simple" approach to derive our bounds. However, since this approach easily applies to many different settings, we present it in a rather abstract framework before instantiating it for classification, clustering or switching regression. As a result, the paper might not read as smoothly as it could have, but this is mostly due to notational complexities implied by the abstraction rather than true technical difficulties.

Paper organization. We start in Section 2 by formalizing our general framework and how it can be specified for the three problems of interest. Then, Section 3 presents the derivation of the error bounds, again, first in the general framework and next in a dedicated form for classification, vector quantization and switching regression. Concluding remarks are given in Section 4.

Notation. We denote by [C] the set of integers from 1 to C. For two sets, A and B, B A denotes the the set of functions from A into B. The notation • is used for the norm in the Hilbert space H induced by the inner product •, • in H.

General setting

We focus on learning problems in which the aim is to learn C ≥ 2 components from a Hilbert space H on the basis of data points z i ∈ Z, i = 1, . . . n. In the following, Z will be instantiated either as X × Y for problems with input space X and output space Y or just as X in contexts without outputs. Specifically, let Z be a random variable taking values in Z. A particular problem is characterized by a loss functional : Z × H C , which measures the pointwise error of a model g = (g k ) 1≤k≤C made of C components g k from H. Then the aim is to minimize, over a predefined model class G ⊂ H C , the risk

L(g) = E (Z, g) (1)
on the basis of a sample of n independent copies Z i of Z. In particular, we concentrate on the standard strategy minimizing the empirical risk

1 n n i=1 (Z i , g). (2)
However, we here focus on statistical aspects of learning and will not discuss algorithmic issues related to the actual minimization of this quantity, which can be highly nontrivial [AK98, ADHP09, Lau16].

For our approach to apply, we require that the loss can be computed (or upper bounded) through a convenient mapping f : Z × H C → R of g, i.e., such that

∀(z, g) ∈ Z × H C , (z, g) ≤ φ • f (z, g) (3)
for some Lipschitz function φ : R → R. The meaning of "convenient" here shall become clear when we state our main technical result. Basically, the aim of f is twofold: to formulate the analysis in terms of Lipschitz functions and to allow efficient decompositions of the capacity measures. Given (3), the empirical risk (2) is equal to or upper bounded by

Ln (g) = 1 n n i=1 φ • f (Z i , g),
which will be used as a proxy for (2) in the subsequent analysis. Similarly, the risk of any g ∈ G is upper bounded by Eφ • f (Z, g), which, in turn, can be bounded uniformly over G via an analysis of the complexity of the real-valued function class

F G = {f g ∈ R Z : f g (z) = f (z, g), g ∈ G}. (4)
In particular, our results will be targeted at model classes of the form

G = g ∈ H C : C k=1 g k p ≤ Λ p , (5)
in which the vector of the norms of the components has a bounded p -norm. Note that such constraints implement a coupling between the components and imply that G cannot be written as a mere product of C independent classes.

We now describe a few example applications of this setting.

Margin multi-category classification

For classification problems with C categories, we focus our attention on the risk of margin classifiers h :

X → Y = [C]. Such classifiers are classifiers whose output in [C] is based on a score per category computed by a component function g k : X → R (thus, H ⊂ R X in this setting)
. Specifically, we have

h(x) = argmax k∈[C] g k (x)
and, with Z = X × Y, the standard classification loss,

h (h(x), y) = 1 h(x) =y (6) = 1 argmax k∈[C] g k (x) =y = (z, g),
can be upper bounded using the Lipschitz function

φ(u) =      1, if u ≤ 0 1 -u γ , if u ∈ (0, γ) 0, if u ≥ γ (7) as (z, g) ≤ 1 gy(x)-max k =y g k (x)≤0 ≤ φ g y (x) -max k =y g k (x) .
Note that the output of φ in (7) is not influenced by values of its argument outside of [0, γ]. Therefore, we can clip these values and define

f (z, g) = min γ, max 0, g y (x) -max k =y g k (x) (8)
to satisfy the requirement in (3). Finally, note that the regularization scheme hinted at by ( 5) is commonly implemented in this context, for instance by multi-class support vector machines [WW98, CS01, LLW04, GM11, LDBK15], and most often with p = 2.

Vector quantization / clustering

Let X be a Hilbert space. The aim of vector quantization, as described in [START_REF] Bartlett | The minimax distortion redundancy in empirical quantizer design[END_REF], is to learn a subset

{g k } C
k=1 ⊂ X C of C elements from X , called codepoints, that can well represent the observations of the random variable X ∈ X . Specifically, we can limit the analysis to nearest neighbors quantizers, for which the error of a model g = (g k ) 1≤k≤C is measured via the loss (x, g) = min

k∈[C]
x -g k 2 .

(9)

Then, the quantity (1) (with Z = X) is known as the distortion of g for which upper bounds are of primary importance. This problem can also be seen as a center-based clustering one, in which the goal is to divide the observations of X into C groups centered at the g k 's by minimizing the empirical risk (2) based on (9). By considering the Voronoï partition of X associated to these centers, [START_REF] Biau | On the performance of clustering in Hilbert spaces[END_REF] interprets the quantity (1) as the clustering risk measuring the performance of a particular model g ∈ X C .

The setting just described enters our framework in a straightforward manner with Z = X , H = X , f = in (9) and φ set as the identity.

Switching regression

In a regression problem, one must learn a model that can accurately predict the real output Y ∈ Y ⊆ R given the input X ∈ X . Switching regression refers to the specific case where the process generating Y can arbitrarily switch between different behaviors. The difficulty then comes from the fact that the switchings are not observed and the association of the observations to these behaviors is unknown. Thus, the aim is to learn a collection of functions g k : X → R from a mixed training sample including examples from multiple sources. An important application is that of switched system identification in control theory, see [PJFTV07, GPV12, LG18] for an overview.

In such a context, the goal is to find g ∈ (R X ) C so that at least one of its components can accurately estimate the output Y given X. The loss can thus be defined on the basis of

1 min k∈[C] (y -g k (x)) 2 .
More precisely, we assume that Y is bounded and, without loss of generality, that Y = [-1/2, 1/2]. Thus, we can clip the outputs of the components at 1/2 without increasing the error and compute the loss with respect to the clipped functions as in [START_REF] Lauer | Error bounds for piecewise smooth and switching regression[END_REF], i.e., by

(z, g) = min k∈[C] y -min 1 2 , max -1 2 , g k (x) 2 .
(10) This ensures that the loss is bounded by 1 for all y ∈ Y, which simplifies the analysis below.

The switching regression problem just described can be characterized in our framework with Z = X × Y, H ⊂ R X , φ set as the identity and f = in (10).

In this context, the learning algorithms in, e.g., [START_REF] Le | Reducedsize kernel models for nonlinear hybrid system identification[END_REF][START_REF] Pham Dinh | A difference of convex functions algorithm for switched linear regression[END_REF], implement a regularization scheme in accordance with (5).

Error bounds

Here, we first derive our main technical result in a rather abstract framework before instantiating it for the three settings presented above in dedicated subsections. This result will allow us to bound the complexity of a function class under sum-of-norms constraints as in (5) via the maximum complexity of function classes related to the components (to be defined precisely below).

First, we need the following result showing that G can be embedded in a class G built as a union of product classes with decaying components. More precisely, we mean that the Rademacher complexities of the component classes (see Definition 1 below) are decaying with the component index k. This result will allow us to work on a class with an easier to handle structure than that of G.

The idea, made precise in the lemma below, is that if a function g belongs to G, a large norm for one component must be compensated by a small norm for another. Thus, the component functions can be ordered so as to belong to a sequence of balls of decreasing radius. The union in the definition of G implements the fact that different functions of G result in different orderings of their components that must all be taken into account when building an embedding of G.

Lemma 1. Let G be as in (5) and

(k l (j)) 1≤l≤C ∈ [C] C denote the jth permutation of [C] among J = C!, the first of which is just [C].
Then, for all p > 0, there are classes

G 1,k = g k ∈ H : g k ≤ k -1 p Λ , k = 1, . . . , C, G j = C l=1 G 1,k l (j) , j = 1, . . . , J, such that G ⊂ G = J j=1 G j .
Proof. For any g, let g be a version of g with its components reordered such that g1 ≥ g2 ≥ ... ≥ gC .

Then, the construction of G is such that g ∈ G implies that g belongs to a product of some permutation of the G 1,k 's, which makes g also belong to a product of a (possibly different) permutation of the G 1,k 's. Thus, g ∈ G implies g ∈ G. As a result, showing that for all g ∈ G, g ∈ G is sufficient to prove that G ⊂ G.

With G as in (5), we have, for all g ∈ G, Given this embedding of G, we now aim at error bounds that hold uniformly over G instead of G. Despite the apparent loss due to the increase of the size of the class, the union structure of G will help us to optimize the bound thanks to the following lemma, which basically states the simple fact that if a risk bound holds uniformly over G j for each j, then a bound of the same flavor holds uniformly over G. Specifically, we consider bounds based on Rademacher complexities.

Definition 1 (Rademacher complexity). Let T be a random variable with values in T . For n ∈ N * , let T n = (T i ) 1≤i≤n be an n-sample of independent copies of T , let σ n = (σ i ) 1≤i≤n be a sequence of independent random variables uniformly distributed in {-1, +1}. Let F be a class of real-valued functions with domain T . The Rademacher complexity of F is

R n (F) = E sup f ∈F 1 n n i=1 σ i f (T i ) ,
where the expectation is taken over both σ n and T n . This measure of capacity allows for the derivation of the following generic bound.

Theorem 1 (After, e.g., Theorem 3.1 in [START_REF] Mohri | Foundations of Machine Learning[END_REF]). Let F be a class of functions from Z into [0, 1] and (Z i ) 1≤i≤n be a sequence of independent copies of the random variable Z ∈ Z. Then, for a fixed δ ∈ (0, 1), with probability at least 1-δ, uniformly over all f ∈ F,

Ef (Z) ≤ 1 n n i=1 f (Z i ) + 2R n (F) + log 1 δ 2n .
Bounds of this flavor are used in the following to bound the risk uniformly over G.

Lemma 2. Let G = J j=1 G j be a union of J sets G j . Given a mapping f : Z × H C → R, define, for each one of these sets, F G j as in (4). If, for some constant α > 0, for all j ∈ [J] and all δ j ∈ (0, 1), the bound

∀g ∈ G j , L(g) ≤ Ln (g) + αR n (F G j ) + log 1 δj 2n ( 11
)
holds with probability at least 1 -δ j , then, for any δ ∈ (0, 1), the bound

∀g ∈ G, L(g) ≤ Ln (g) + α max j∈[J] R n (F G j ) + log J δ 2n
holds with probability at least 1 -δ.

Proof. Setting δ j = δ/J and using the union bound, we obtain that all the J bounds (11) hold simultaneously with probability at least 1 -J j=1 δ j = 1 -δ. Then, for any g ∈ G, there is some j ∈ [J] such that g ∈ G j and for which we can apply the bound (11). Upper bounding the corresponding Rademacher complexity by the maximum complexity over all j ∈ [J] completes the proof.

We can now state the main theorem, in which the "convenient" form of f that we require appears as a condition on the decomposition of its Rademacher complexity.

Theorem 2. Let f be as in (3) and such that for any

G = C k=1 G k , for F G as in (4), R n (F G ) ≤ c C k=1 R n (Ψ G k ),
where c > 0 is a constant and Ψ G k is a real-valued function class deduced from G k via a mapping ψ : Z × H → R as

Ψ G k = {ψ g k ∈ R Z : ψ g k (z) = ψ(z, g k ), g k ∈ G k }. (12) If ψ is such that, for any G k = {g k ∈ H : g k ≤ Λ}, the bound R n (Ψ G k ) ≤ Λ q R(n) (13)
holds with q ≥ 1 and a function R(n) that does not depend on Λ, then, for G as in (5), all p ∈ (0, 2] and any δ ∈ (0, 1), the bound ∀g ∈ G, L(g) < Ln (g) + 4cL φ Λ q √ CR(n)

+ C log C + log 1 δ 2n , (14)
in which L φ is the Lipschitz constant of φ, holds with probability at least 1 -δ.

Proof. By Lemma 1, we have

G ⊂ G = J j=1 G j with J = C! < C C .
For any G j of Lemma 1, we have by (3) and Theorem 1 that, with probability at least 1 -δ, for any g ∈ G j ,

L(g) ≤ 1 n n i=1 φ • f (Z i , g) + 2R n (φ • F G j ) + log 1 δ 2n .
In addition, by the contraction principle, see e.g., Lemma 4.2 in [START_REF] Mohri | Foundations of Machine Learning[END_REF],

R n (φ • F G j ) ≤ L φ R n (F G j ).
Thus, we can apply Lemma 2 with α = 2L φ and it remains to show that for all p ∈ (0, 2], max j∈[J] R n (F G j ) ≤ 2cΛ q √ CR(n). Using the assumptions and the fact that, for any j ∈ [J], G j is the product

C k=1 G j,k , we have R n (F G j ) ≤ c C k=1 R n (Ψ G j,k ) = c C l=1 R n (Ψ G 1,k l (j) ) ≤ cΛ q R(n) C l=1 k l (j) -q/p = cΛ q R(n) C k=1 k -q/p .
Thus, for all q ≥ 1 and p ∈ (0, 2],

R n (F G j ) ≤ cΛ q R(n) C k=1 1 √ k ≤ cΛ q R(n) C+1 1 1 √ t -1 dt = 2cΛ q R(n) √ C,
which completes the proof.

Note that for specific values of p < 2, tighter bounds on the second term in the right-hand side of ( 14) are typically available. For instance, for p = 1, the √ C can be replaced by (1 + log C). However, the growth rate with respect to C remains determined by the last term in (14).

In the next subsections, we detail the consequences of Theorem 2 for the three considered settings.

Multi-category classification

In the multi-category classification setting of Sect. 2.1, the conditions of Theorem 2 are verified for kernel machines thanks to two results from the literature. The first one is a classical bound on the Rademacher complexity of balls in a reproducing kernel Hilbert space (RKHS) (see [START_REF] Berlinet | Reproducing Kernel Hilbert Spaces in Probability and Statistics[END_REF] for definitions and properties of RKHSs):

Lemma 3 (After Lemma 22 in [START_REF] Bartlett | Rademacher and Gaussian complexi-ties: Risk bounds and structural results[END_REF]). Given an RKHS H of reproducing kernel K,

R n ({g k ∈ H : g k ≤ Λ}) ≤ Λ x Λ √ n ,
where

Λ x = sup x∈X K(x, •) = sup x∈X K(x, x).
The second one is a decomposition result due to [START_REF] Kuznetsov | Multi-class deep boosting[END_REF]:

Lemma 4 (After Theorem 2 in [START_REF] Kuznetsov | Multi-class deep boosting[END_REF]). Let the mapping f be as in (8) and F G be defined as in (4).

If G = C k=1 G k , then 2 R n (F G ) ≤ C k=1 R n (G k ) .
Therefore, with ψ(z, g k ) = g k (x), q = 1 and L φ = 1 γ , Theorem 2 yields the following bound.

Theorem 3. Let H be an RKHS of reproducing kernel K. Then, for the class G as in (5) and any δ ∈ (0, 1), the multi-class risk based on the loss (6) is bounded with probability at least 1 -δ, uniformly for all g ∈ G, by

L(g) ≤ Ln (g) + 4ΛΛ x γ C n + C log C + log 1 δ 2n ,
with Λ x as in Lemma 3.

2 Theorem 2 in [START_REF] Kuznetsov | Multi-class deep boosting[END_REF] actually states that Rn (F G ) ≤ CRn C k=1 G k , but the proof essentially allows for the derivation of the bound stated here.

Note that, under the assumptions of Theorem 3, a growth rate in C between logarithmic and radical (depending on p) can be obtained as detailed in [START_REF] Lei | Multi-class SVMs: From tighter datadependent generalization bounds to novel algorithms[END_REF] so that Theorem 3 does not constitute an improvement over the literature. However, for the most common case of p = 2, our result only adds a √ log C factor compared to the one of [START_REF] Lei | Multi-class SVMs: From tighter datadependent generalization bounds to novel algorithms[END_REF] with a much shorter and simpler proof.

Clustering

We now consider the clustering case and the setting of Sect. 2.2. In this context, Theorem 2 yields a bound with almost radical dependency on C. The remaining ingredients can be found in the derivation of Theorem 2.1 in [START_REF] Biau | On the performance of clustering in Hilbert spaces[END_REF].

Theorem 4. Let G be as in (5) and assume that P ( X ≤ Λ x ) = 1. Then, for any δ ∈ (0, 1), the clustering risk based on the loss (9) is, with probability at least 1 -δ, uniformly bounded for all g ∈ G by

L(g) ≤ Ln (g) + 4(2Λ x + 1)Λ q C n + C log C + log 1 δ 2n with q = 1 if Λ ≤ 1 and q = 2 otherwise.
Proof. Given that f = (9), we can rewrite the functions f g ∈ F G (4) as

f g (x) = min k∈[C] x -g k (x) 2 = x 2 + min k∈[C] -2 x, g k + g k 2 ,
which leads to

R n (F G ) = E sup g∈G 1 n n i=1 σ i X i 2 + min k∈[C] -2 X i , g k + g k 2 ≤ E 1 n n i=1 σ i X i 2 + E sup g∈G 1 n n i=1 σ i min k∈[C] -2 X i , g k + g k 2 .
The fact that the σ i 's are centered and independent of the X i 's yields

E 1 n n i=1 σ i X i 2 = 0.
Then, by following the proof of Lemma 4.3 in [START_REF] Biau | On the performance of clustering in Hilbert spaces[END_REF] (or by using Lemma 8.1 in [START_REF] Mohri | Foundations of Machine Learning[END_REF]), we obtain that

R n (F G ) ≤ C k=1 R n (Ψ G k ) ,
where Ψ G k is built as in (12) with ψ(x, g k ) = -2 x, g k + g k 2 . In addition, [BDL08] also shows that for

G k = {g k ∈ H : g k ≤ Λ}, R n (Ψ G k ) ≤ 2Λ E X 2 n + Λ 2 √ n ≤ Λ q 2 E X 2 + 1 √ n with q = 1 if Λ ≤ 1 and q = 2 otherwise. Therefore, since P ( X ≤ Λ x ) = 1, E X 2 ≤ Λ 2
x and Theorem 2 applies to this setting to yield the claimed risk bound.

Switching regression

For the switching regression setting of Sect. 2.3, the conditions of Theorem 2 are fulfilled by making use of the analysis in [START_REF] Lauer | Error bounds for piecewise smooth and switching regression[END_REF]. In particular, we rely on the following decomposition result.

Lemma 5

(After Theorem 3 in [Lau17]). Let G = C k=1 G k ⊂ H C and F G be as in (4) with f = (10). Then, R n (F G ) ≤ 2 C k=1 R n (Ψ G k ),
where Ψ G k is as in (12) for the clipping function ψ: ψ(z, g k ) = min 1 2 , max -1 2 , g k (x) .

The condition (13) is in turn satisfied with a contraction argument and the application of Lemma 3, which yields, for any RKHS H and all G k = {g k ∈ H :

g k ≤ Λ}, R n (Ψ G k ) ≤ R n (G k ) ≤ ΛΛ x √ n .
Therefore, we can apply Theorem 2 with c = 2 and q = 1 to obtain a risk bound with almost radical dependence on C.

Theorem 5. Let H be an RKHS of kernel K and set Λ x = sup x∈X K(x, x). Then, for the class G as in (5) and any δ ∈ (0, 1), the switching regression risk based on the minimal squared loss (10) is bounded with probability at least 1 -δ, uniformly for all g ∈ G, by

L(g) ≤ Ln (g) + 8Λ x Λ C n + C log C + log 1 δ 2n .

Conclusions

The paper presented a unified approach to the derivation of error bounds for problems in which one is to learn C components from a Hilbert space. With this approach, and under appropriate assumptions on the model class, we could obtain an almost radical dependence on C (up to logarithmic factors) for multicategory classification, vector quantization and switching regression. Future work will study the applicability of this approach to other problems involving multiple components, such as multi-task learning and structured prediction. In addition, recall that for multi-category classification, logarithmic to radical dependency on C can be obtained as in [START_REF] Lei | Multi-class SVMs: From tighter datadependent generalization bounds to novel algorithms[END_REF] via a somewhat more involved analysis of Gaussian complexities (that can be used to bound the Rademacher complexity). As hinted at in the introduction, future work will aim at extending this analysis to the other settings of clustering and switching regression in the hope of further reducing the influence of the number of components on the bounds. On the algorithmic side, a practical evaluation of methods implementing the regularization scheme suggested by our analysis in vector quantization should also be conducted.

  p .Thus, and by the definition of g, for any l ∈ [C], l -1/p Λ, which implies gl ∈ G 1,l . Therefore, g ∈ G 1 ⊂ G and the statement is proved.

Other choices involving for instance absolute deviations instead squared errors are also possible here; see[START_REF] Lauer | Error bounds for piecewise smooth and switching regression[END_REF] for a description of switching regression in a more general setting.