Algorithmic challenges in green data centers

With data centers being the supporting infrastructure for a wide range of IT services, their efficiency has become a big concern to operators, as well as to society, for both economic and environmental reasons. The goal of this thesis is to design energy-efficient algorithms that reduce energy cost while minimizing compromise to service. We focus on the algorithmic challenges at different levels of energy optimization across the data center stack. The algorithmic challenge at the device level is to improve the energy efficiency of a single computational device via techniques such as job scheduling and speed scaling. We analyze the common speed scaling algorithms in both the worst-case model and stochastic model to answer some fundamental issues in the design of speed scaling algorithms. The algorithmic challenge at the local data center level is to dynamically allocate resources (e.g., servers) and to dispatch the workload in a data center. We develop an online algorithm to make a data center more power-proportional by dynamically adapting the number of active servers. The algorithmic challenge at the global data center level is to dispatch the workload across multiple data centers, considering the geographical diversity of electricity price, availability of renewable energy, and network propagation delay. We propose algorithms to jointly optimize routing and provisioning in an online manner. Motivated by the above online decision problems, we move on to study a general class of online problem named "smoothed online convex optimization", which seeks to minimize the sum of a sequence of convex functions when "smooth" solutions are preferred. This model allows us to bridge different research communities and help us get a more fundamental understanding of general online decision problems.

On Recurrent and Deep Neural Networks

L'apprentissage profond est un domaine de recherche en forte croissance en apprentissage automatique qui est parvenu à des résultats impressionnants dans différentes tâches allant de la classification d'images à la parole, en passant par la modélisation du langage. Les réseaux de neurones récurrents, une sous-classe d'architecture profonde, s'avèrent particulièrement prometteurs. Les réseaux récurrents peuvent capter la structure temporelle dans les données. Ils ont potentiellement la capacité d'apprendre des corrélations entre des événements éloignés dans le temps et d'emmagasiner indéfiniment des informations dans leur mémoire interne. Dans ce travail, nous tentons d'abord de comprendre pourquoi la profondeur est utile. Similairement à d'autres travaux de la littérature, nos résultats démontrent que les modèles profonds peuvent être plus efficaces pour représenter certaines familles de fonctions comparativement aux modèles peu profonds. Contrairement à ces travaux, nous effectuons notre analyse théorique sur des réseaux profonds acycliques munis de fonctions d'activation linéaires par parties, puisque ce type de modèle est actuellement l'état de l'art dans différentes tâches de classification. La deuxième partie de cette thèse porte sur le processus d'apprentissage. Nous analysons quelques techniques d'optimisation proposées récemment, telles l'optimisation Hessian free, la descente de gradient naturel et la descente des sous-espaces de Krylov. Nous proposons le cadre théorique des méthodes à région de confiance généralisées et nous montrons que plusieurs de ces algorithmes développés récemment peuvent être vus dans cette perspective. Nous argumentons que certains membres de cette famille d'approches peuvent être mieux adaptés que d'autres à l'optimisation non convexe. La dernière partie de ce document se concentre sur les réseaux de neurones récurrents. Nous étudions d'abord le concept de mémoire et tentons de répondre aux questions suivantes: Les réseaux récurrents peuvent-ils démontrer une mémoire sans limite? Ce comportement peut-il être appris? Nous montrons que cela est possible si des indices sont fournis durant l'apprentissage. Ensuite, nous explorons deux problèmes spécifiques à l'entraînement des réseaux récurrents, à savoir la dissipation et l'explosion du gradient. Notre analyse se termine par une solution au problème d'explosion du gradient qui implique de borner la norme du gradient. Nous proposons également un terme de régularisation conçu spécifiquement pour réduire le problème de dissipation du gradient. Sur un ensemble de données synthétique, nous montrons empiriquement que ces mécanismes peuvent permettre aux réseaux récurrents d'apprendre de façon autonome à mémoriser des informations pour une période de temps indéfinie. Finalement, nous explorons la notion de profondeur dans les réseaux de neurones récurrents. Comparativement aux réseaux acycliques, la définition de profondeur dans les réseaux récurrents est souvent ambiguë. Nous proposons différentes façons d'ajouter de la profondeur dans les réseaux récurrents et nous évaluons empiriquement ces propositions.

Analyse du comportement hétérogène des usagers dans un réseau

Le nombre important de véhicules sur le réseau routier peut entraîner des problèmes d'encombrement et de sécurité. Les usagers des réseaux routiers qui nous intéressent sont les camionneurs qui transportent des marchandises, pouvant rouler avec des véhicules non conformes ou emprunter des routes interdites pour gagner du temps. Le transport de matières dangereuses est réglementé et certains lieux, surtout les ponts et les tunnels, leur sont interdits d'accès. Pour aider à faire appliquer les lois en vigueur, il existe un système de contrôles routiers composé de structures fixes et de patrouilles mobiles. Le déploiement stratégique de ces ressources de contrôle mise sur la connaissance du comportement des camionneurs que nous allons étudier à travers l'analyse de leurs choix de routes. Un problème de choix de routes peut se modéliser en utilisant la théorie des choix discrets, elle-même fondée sur la théorie de l'utilité aléatoire. Traiter ce type de problème avec cette théorie est complexe. Les modèles que nous utiliserons sont tels, que nous serons amenés à faire face à des problèmes de corrélation, puisque plusieurs routes partagent probablement des arcs. De plus, puisque nous travaillons sur le réseau routier du Québec, le choix de routes peut se faire parmi un ensemble de routes dont le nombre est potentiellement infini si on considère celles ayant des boucles. Enfin, l'étude des choix faits par un humain n'est pas triviale. Avec l'aide du modèle de choix de routes retenu, nous pourrons calculer une expression de la probabilité qu'une route soit prise par le camionneur. Nous avons abordé cette étude du comportement en commençant par un travail de description des données collectées. Le questionnaire utilisé par les contrôleurs permet de collecter des données concernant les camionneurs, leurs véhicules et le lieu du contrôle. La description des données observées est une étape essentielle, car elle permet de présenter clairement à un analyste potentiel ce qui est accessible pour étudier les comportements des camionneurs. Les données observées lors d'un contrôle constitueront ce que nous appellerons une observation. Avec les attributs du réseau, il sera possible de modéliser le réseau routier du Québec. Une sélection de certains attributs permettra de spécifier la fonction d'utilité et par conséquent la fonction permettant de calculer les probabilités de choix de routes par un camionneur. Il devient alors possible d'étudier un comportement en se basant sur des observations. Celles provenant du terrain ne nous donnent pas suffisamment d'information actuellement et même en spécifiant bien un modèle, l'estimation des paramètres n'est pas possible. Cette dernière est basée sur la méthode du maximum de vraisemblance. Nous avons l'outil, mais il nous manque la matière première que sont les observations, pour continuer l'étude. L'idée est de poursuivre avec des observations de synthèse. Nous ferons des estimations avec des observations complètes puis, pour se rapprocher des conditions réelles, nous continuerons avec des observations partielles. Ceci constitue d'ailleurs un défi majeur. Nous proposons pour ces dernières, de nous servir des résultats des travaux de (Bierlaire et Frejinger, 2008) en les combinant avec ceux de (Fosgerau, Frejinger et Karlström, 2013). Bien qu'elles soient de nature synthétiques, les observations que nous utilisons nous mèneront à des résultats tels, que nous serons en mesure de fournir une proposition concrète qui pourrait aider à optimiser les décisions des responsables des contrôles routiers. En effet, nous avons réussi à estimer, sur le réseau réel du Québec, avec un seuil de signification de 0,05 les valeurs des paramètres d'un modèle de choix de routes discrets, même lorsque les observations sont partielles. Ces résultats donneront lieu à des recommandations sur les changements à faire dans le questionnaire permettant de collecter des données.

Advances in scaling deep learning algorithms

Les algorithmes d'apprentissage profond forment un nouvel ensemble de méthodes puissantes pour l'apprentissage automatique. L'idée est de combiner des couches de facteurs latents en hierarchies. Cela requiert souvent un coût computationel plus elevé et augmente aussi le nombre de paramètres du modèle. Ainsi, l'utilisation de ces méthodes sur des problèmes à plus grande échelle demande de réduire leur coût et aussi d'améliorer leur régularisation et leur optimization. Cette thèse adresse cette question sur ces trois perspectives. Nous étudions tout d'abord le problème de réduire le coût de certains algorithmes profonds. Nous proposons deux méthodes pour entrainer des machines de Boltzmann restreintes et des auto-encodeurs débruitants sur des distributions sparses à haute dimension. Ceci est important pour l'application de ces algorithmes pour le traitement de langues naturelles. Ces deux méthodes (Dauphin et al., 2011; Dauphin and Bengio, 2013) utilisent l'échantillonage par importance pour échantilloner l'objectif de ces modèles. Nous observons que cela réduit significativement le temps d'entrainement. L'accéleration atteint 2 ordres de magnitude sur plusieurs bancs d'essai. Deuxièmement, nous introduisont un puissant régularisateur pour les méthodes profondes. Les résultats expérimentaux démontrent qu'un bon régularisateur est crucial pour obtenir de bonnes performances avec des gros réseaux (Hinton et al., 2012). Dans Rifai et al. (2011), nous proposons un nouveau régularisateur qui combine l'apprentissage non-supervisé et la propagation de tangente (Simard et al., 1992). Cette méthode exploite des principes géometriques et permit au moment de la publication d'atteindre des résultats à l'état de l'art. Finalement, nous considérons le problème d'optimiser des surfaces non-convexes à haute dimensionalité comme celle des réseaux de neurones. Tradionellement, l'abondance de minimum locaux était considéré comme la principale difficulté dans ces problèmes. Dans Dauphin et al. (2014a) nous argumentons à partir de résultats en statistique physique, de la théorie des matrices aléatoires, de la théorie des réseaux de neurones et à partir de résultats expérimentaux qu'une difficulté plus profonde provient de la prolifération de points-selle. Dans ce papier nous proposons aussi une nouvelle méthode pour l'optimisation non-convexe.

Computationally reliable approaches of contractive MPC for discrete-time systems

La tesis pretende explorar acercamientos computacionalmente confiables y eficientes de contractivo MPC para sistemas de tiempo discreto. Dos tipos de contractivo MPC han sido estudiados: MPC con coacción contractiva obligatoria y MPC con una secuencia contractiva de conjuntos controlables. Las técnicas basadas en optimización convexa y análisis de intervalos son aplicadas para tratar MPC contractivo lineal y no lineal, respectivamente. El análisis de intervalos clásicos es ampliado a zonotopes en la geometría para diseñar un conjunto invariante de control terminal para el modo dual de MPC. También es ampliado a intervalos modales para tener en cuenta la modalidad al calcula de conjuntos controlables robustos con una interpretación semántica clara. Los instrumentos de optimización convexa y análisis de intervalos han sido combinados para mejorar la eficacia de contractive MPC para varias clases de sistemas de tiempo discreto inciertos no lineales limitados. Finalmente, los dos tipos dirigidos de contractivo MPC han sido aplicados para controlar un Torneo de Fútbol de Copa Mundial de Micro Robot (MiroSot) y un Tanque-Reactor de Mezcla Continua (CSTR), respectivamente.

On backwards and forwards reachable sets bounding for perturbed time-delay systems

Linear systems with interval time-varying delay and unknown-but-bounded disturbances are considered in this paper. We study the problem of finding outer bound of forwards reachable sets and inter bound of backwards reachable sets of the system. Firstly, two definitions on forwards and backwards reachable sets, where initial state vectors are not necessary to be equal to zero, are introduced. Then, by using the Lyapunov-Krasovskii method, two sufficient conditions for the existence of: (i) the smallest possible outer bound of forwards reachable sets; and (ii) the largest possible inter bound of backwards reachable sets, are derived. These conditions are presented in terms of linear matrix inequalities with two parameters need to tuned, which therefore can be efficiently solved by combining existing convex optimization algorithms with a two-dimensional search method to obtain optimal bounds. Lastly, the obtained results are illustrated by four numerical examples.

Stable feature selection with support vector machines

The support vector machine (SVM) is a popular method for classification, well known for finding the maximum-margin hyperplane. Combining SVM with l1-norm penalty further enables it to simultaneously perform feature selection and margin maximization within a single framework. However, l1-norm SVM shows instability in selecting features in presence of correlated features. We propose a new method to increase the stability of l1-norm SVM by encouraging similarities between feature weights based on feature correlations, which is captured via a feature covariance matrix. Our proposed method can capture both positive and negative correlations between features. We formulate the model as a convex optimization problem and propose a solution based on alternating minimization. Using both synthetic and real-world datasets, we show that our model achieves better stability and classification accuracy compared to several state-of-the-art regularized classification methods.

Detection of dynamic background due to swaying movements from motion features

Dynamically changing background (dynamic background) still presents a great challenge to many motion-based video surveillance systems. In the context of event detection, it is a major source of false alarms. There is a strong need from the security industry either to detect and suppress these false alarms, or dampen the effects of background changes, so as to increase the sensitivity to meaningful events of interest. In this paper, we restrict our focus to one of the most common causes of dynamic background changes: 1) that of swaying tree branches and 2) their shadows under windy conditions. Considering the ultimate goal in a video analytics pipeline, we formulate a new dynamic background detection problem as a signal processing alternative to the previously described but unreliable computer vision-based approaches. Within this new framework, we directly reduce the number of false alarms by testing if the detected events are due to characteristic background motions. In addition, we introduce a new data set suitable for the evaluation of dynamic background detection. It consists of real-world events detected by a commercial surveillance system from two static surveillance cameras. The research question we address is whether dynamic background can be detected reliably and efficiently using simple motion features and in the presence of similar but meaningful events, such as loitering. Inspired by the tree aerodynamics theory, we propose a novel method named local variation persistence (LVP), that captures the key characteristics of swaying motions. The method is posed as a convex optimization problem, whose variable is the local variation. We derive a computationally efficient algorithm for solving the optimization problem, the solution of which is then used to form a powerful detection statistic. On our newly collected data set, we demonstrate that the proposed LVP achieves excellent detection results and outperforms the best alternative adapted from existing art in the dynamic background literature.

Controle preditivo robusto baseado em desigualdades matriciais lineares aplicado a um sistema de tanques acoplados

This work deals with an on-line control strategy based on Robust Model Predictive Control (RMPC) technique applied in a real coupled tanks system. This process consists of two coupled tanks and a pump to feed the liquid to the system. The control objective (regulator problem) is to keep the tanks levels in the considered operation point even in the presence of disturbance. The RMPC is a technique that allows explicit incorporation of the plant uncertainty in the problem formulation. The goal is to design, at each time step, a state-feedback control law that minimizes a 'worst-case' infinite horizon objective function, subject to constraint in the control. The existence of a feedback control law satisfying the input constraints is reduced to a convex optimization over linear matrix inequalities (LMIs) problem. It is shown in this work that for the plant uncertainty described by the polytope, the feasible receding horizon state feedback control design is robustly stabilizing. The software implementation of the RMPC is made using Scilab, and its communication with Coupled Tanks Systems is done through the OLE for Process Control (OPC) industrial protocol

H-2 and H-infinity - norm control of intelligent structures using LMI techniques

Linear Matrix Inequalities (LMIs) is a powerful too] that has been used in many areas ranging from control engineering to system identification and structural design. There are many factors that make LMI appealing. One is the fact that a lot of design specifications and constrains can be formulated as LMIs [1]. Once formulated in terms of LMIs a problem can be solved efficiently by convex optimization algorithms. The basic idea of the LMI method is to formulate a given problem as an optimization problem with linear objective function and linear matrix inequalities constrains. An intelligent structure involves distributed sensors and actuators and a control law to apply localized actions, in order to minimize or reduce the response at selected conditions. The objective of this work is to implement techniques of control based on LMIs applied to smart structures.

Robust control applications for smart truss structure

A finite element modeling of an intelligent truss structure with piezoelectric stack actuators for the purpose of active damping and structural vibration attenuation is presented. This paper concerns with the following issues aspects: the design of intelligent truss structure considering electro-mechanical coupling between the host structure and piezoelectric stack actuators; the H 2 norm approach to search for optimal placement of actuators and sensors; and finally some aspects in robust control techniques. The electro-mechanical behavior of piezoelectric elements is directly related to the successful application of the actuators in truss structures. In order to achieve the desired damping in the interested bandwidth frequency it is used the H ∞ output feedback solved by convex optimization. The constraints to be reached are written by linear matrix inequalities (LMI). The paper concludes with a numerical example, using Matlab and Simulink, in a cantilevered, 2-bay space truss structure. The results demonstrated the approach applicability.

Active control in flexible plates with piezoelectric actuators using linear matrix inequalities

The study of algorithms for active vibrations control in flexible structures became an area of enormous interest, mainly due to the countless demands of an optimal performance of mechanical systems as aircraft, aerospace and automotive structures. Smart structures, formed by a structure base, coupled with piezoelectric actuators and sensor are capable to guarantee the conditions demanded through the application of several types of controllers. The actuator/sensor materials are composed by piezoelectric ceramic (PZT - Lead Zirconate Titanate), commonly used as distributed actuators, and piezoelectric plastic films (PVDF-PolyVinyliDeno Floride), highly indicated for distributed sensors. The design process of such system encompasses three main phases: structural design; optimal placement of sensor/actuator (PVDF and PZT); and controller design. Consequently, for optimal design purposes, the structure, the sensor/actuator placement and the controller have to be considered simultaneously. This article addresses the optimal placement of actuators and sensors for design of controller for vibration attenuation in a flexible plate. Techniques involving linear matrix inequalities (LMI) to solve the Riccati's equation are used. The controller's gain is calculated using the linear quadratic regulator (LQR). The major advantage of LMI design is to enable specifications such as stability degree requirements, decay rate, input force limitation in the actuators and output peak bounder. It is also possible to assume that the model parameters involve uncertainties. LMI is a very useful tool for problems with constraints, where the parameters vary in a range of values. Once formulated in terms of LMI a problem can be solved efficiently by convex optimization algorithms.

An application of a modified constructive heuristic algorithm to transmission expansion planning

Transmission expansion planning (TEP) is a non-convex optimization problem that can be solved via different heuristic algorithms. A variety of classical as well as heuristic algorithms in literature are addressed to solve TEP problem. In this paper a modified constructive heuristic algorithm (CHA) is proposed for solving such a crucial problem. Most of research papers handle TEP problem by linearization of the non-linear mathematical model while in this research TEP problem is solved via CHA using non-linear model. The proposed methodology is based upon Garver's algorithm capable of applying to a DC model. Simulation studies and tests results on the well known transmission network such as: Garver and IEEE 24-bus systems are carried out to show the significant performance as well as the effectiveness of the proposed algorithm. © 2011 IEEE.

An application of CHA to concurrent short-term transmission expansion & reactive power planning

In this paper a heuristic technique for solving simultaneous short-term transmission network expansion and reactive power planning problem (TEPRPP) via an AC model is presented. A constructive heuristic algorithm (CHA) aimed to obtaining a significant quality solution for such problem is employed. An interior point method (IPM) is applied to solve TEPRPP as a nonlinear programming (NLP) during the solution steps of the algorithm. For each proposed network topology, an indicator is deployed to identify the weak buses for reactive power sources placement. The objective function of NLP includes the costs of new transmission lines, real power losses as well as reactive power sources. By allocating reactive power sources at load buses, the circuit capacity may increase while the cost of new lines can be decreased. The proposed methodology is tested on Garver's system and the obtained results shows its capability and the viability of using AC model for solving such non-convex optimization problem. © 2011 IEEE.

Identificação experimental e controle ativo de vibrações aplicadas em estruturas inteligentes

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)