Search

Creating computer generated human animations without the use of motion capture technology is a tedious and time consuming activity. Although there are several publications regarding animation synthesis using data driven methods, not many are dedicated towards the task of inbetweening, which consists of generating transition movements between frames. A modified version of LSTM, called Recurrent Transition Network (RTN), solves the inbetweening task for walking motion based on ten initial frames and two final frames. In this work, we are interested on the short-term inbetweening task, where we need to use the least amount of frames to generate the missing frames for short-term transitions. We are also interested on different kinds of movements, such as martial arts and Indian dance. Thus, we adapt the Recurrent Transition Network (RTN) to require only the two firts frames and the last one, called ARTN, and propose a simple post processing method combining ARTN with linear interpolation, called ARTN+. The results show that the average error of ARTN+ is less than the average error of each method (RTN and interpolation) separately in the martial arts and Indian dance dataset.

Os Processos de Decisão de Markov (MDPs) podem ser usados para controlar a propagação de doenças infecciosas e encontrar uma política ótima de controle de vacinação. No entanto, por se tratar de um problema que envolve vidas, é necessário levar em consideração a atitude do agente em relação ao risco. Assim, neste trabalho, são usados MDPs sensíveis ao risco com o modelo compartimental SIR e são propostos dois algoritmos eficientes para encontrar políticas de vacinação otimizadas que permitam controlar a propagação de uma doença infecciosa, ou seja, selecionar o número de indivíduos que devem ser vacinados a cada período considerando um parâmetro que representa a atitude frente ao risco. A primeira solução proposta encontra uma política de vacinação que é parcial e ótima dada uma determinada atitude de risco. A segunda solução proposta é aproximada e assim pode resolver problemas ainda maiores. Os resultados mostram que: (i) as políticas de vacinação dependem não apenas da taxa básica de reprodução R0, como esperado, mas também do custo e da atitude em relação ao risco de um agente; e (ii) ambas as soluções obtêm um grande ganho de tempo de execução e pouca perda de qualidade quando comparadas com as políticas completas e não aproximadas.

In stochastic sequential decision problems, such as Stochastic Shortest Path Problems, the GUBS (Goal with UtilityBased Semantics) criterion considers a trade-off between probability-to-goal and cost-to-goal using a goal semantics based on Expected Utility Theory (EUT); in such a semantics, goal paths have priority over non-goal paths, but it implies neither the MAXPROB criterion nor the dual optimization criterion that finds the cheapest policy among the policies that maximize goal probability. Whereas evaluation criteria based on a sound theory such as EUT are desirable, optimal policies under GUBS are non-markovian. Non-markovian solutions are undesirable because there is not always a finite representation and even if it can be represented in a finite way, the representation may be too large to be stored. Here we define a special case of GUBS criterion that allows a finite representation to the optimal policy, the eGUBS criterion, where the cost utility function is exponencial. Considering this special case, we contribute with: (i) the proof that the eGUBSoptimal policy has a finite representation; (ii) the first exact algorithm to obtain finite optimal policies for the eGUBS criterion, and (iii) four strategies to find sub-optimal policies. We conduct experiments on one synthetic problem to evaluate each strategy. Although optimal solutions have a high memory cost, sub-optimal policies can save memory space with a small decrease in performance.

Made available in DSpace on 2021-06-25T16:33:28Z (GMT). No. of bitstreams: 0 Previous issue date: 2020-09-29 Background subtraction is a prerequisite for a wide range of applications, including video surveillance systems. A significant number of algorithms are often developed and published in different publication mediums in the area, such as workshops, symposiums, conferences, and journals. An important task in presenting a new background subtraction algorithms is to clearly show that its performance outperforms the performance of the state-of-the-art algorithms. In this paper, we present recommendations on how to evaluate the performance of background subtraction algorithms for surveillance systems. We identified, through a systematic mapping, the key steps and components of this evaluation process - procedures, methods, and tools - most used by the authors in each of these steps. Considering this statistical analysis, we perform a theoretical analysis of the most used key components to identify their pros and cons. Then, we define a set of recommendations that aim to standardize and clarify the performance evaluation process of a new background subtraction algorithm. Univ Tecnol Fed Parana, Cornelio Procopio, Brazil Univ Estadual Paulista, Bauru, SP, Brazil Simon Fraser Univ, Burnaby, BC, Canada Univ Sao Paulo, Elect Engn, Sao Paulo, Brazil Univ Estadual Paulista, Bauru, SP, Brazil

Markov Decision Processes (MDPs) model problems where a decision-maker makes sequential decisions and the effect of decisions is probabilistic. A particular formulation of MDPs is the Shortest Stochastic Path (SSP), in which the agent seeks to accomplish a goal while reducing the cost of the path to it. Literature introduces some optimality criteria; most of them consider a priority of maximizing probability to accomplish the goal while minimizing some cost measure; such criteria allow a unique trade-off between probability-to-goal and path cost for a decision-maker. Here, we present algorithms to make a trade-off between probability-to-goal and expected cost; based on the Minimum Cost given Maximum Probability (MCMP) criterion, we propose to treat such a trade-off under three different methods: (i) additional constraints for probability-to-goal or expected cost; (ii) a Pareto’s optimality by finding non-dominated policies; and (iii) an efficient preference elicitation process based on non-dominated policies. We report experiments on a toy problem, where probability-to-goal and expected cost trade-off can be observed.

Em planejamento probabilístico, um problema comum é o de caminho estocastico mais curto (SSP), no qual se deseja encontrar políticas que chegam a uma meta com o menor custo acumulado esperado. A presença de estados a partir dos quais não é possível alcançar uma meta, os dead-ends, torna esse critério indefinido nesses estados. Por isso, existem extensões e novas formulações para esse caso particular, como o critério GUBS. Embora existam algoritmos para solucionar esse critério, todos eles necessitam iterar pelo espaço completo de estados. Tendo isso em vista, no presente trabalho é proposto o UCT-GUBS, um algoritmo online de planejamento baseado no UCT para resolver SSPs sob o criterio GUBS. Os resultados dos experimentos realizados mostram empiricamente que o algoritmo demonstra um compromisso entre custo e probabilidade para a meta conforme a variação dos seus parâmetros, podendo tomar uma decisão em um tempo menor ou maior dependendo do tempo limite passado para o algoritmo, que é uma característica importante do UCT.

A definição de políticas de controle do espalhamento de doenças infecciosas, tais como a COVID19, é hoje um tema importante para a sociedade e para os agentes do governo, responsáveis pelas medidas de controle. A grande maioria das pesquisas recentes neste tópico usa dados do passado para estimar a evolução da doença considerando uma política arbitrária. No entanto, o uso de técnicas de planejamento automático baseadas em Processos de Decisão Markovianos (MDPs) tem se mostrado mais eficiente para a computação de políticas de controle otimizadas. Um dos modelos mais utilizados para o controle de doenças infecciosas é o "modelo SIR com vacinação" em que a dinâmica da quantidade de indivíduos suscetíveis, infectados e recuperados é controlada através de políticas de vacinação da população. Mas por se tratar de um problema que envolve vidas, também se faz necessário levar em consideração a atitude frente ao risco dos agentes tomadores de decisão. Assim, a proposta deste trabalho é usar MDPs sensíveis ao risco para encontrar políticas otimizadas de vacinação para o controle da propagação de doenças infecciosas considerando, além dos parâmetros do modelo SIR com vacinação, o parâmetro de risco. Os resultados mostram que as políticas de vacinação dependem da taxa de reprodução basal $R_0$, como esperado, bem como da atitude frente ao risco dos agentes de tomada de decisões.

Coclustering algorithms are an alternative to classic one-sided clustering algorithms. Because of its ability to simultaneously cluster rows and columns of a dyadic data matrix, coclustering offers a higher value-added information: it offers column clusters besides row clusters, and the relationship between them in terms of coclusters. Different structures of coclusters are possible, and those that overlap in terms of rows or columns still represent an open question with room for improvements. In addition, while most related literature cites coclustering as a means of producing better results from one-side clustering, few initiatives study it as a tool capable of providing higher quality descriptive information about this clustering. In this paper, we present a new coclustering algorithm - OvNMTF, based on triple matrix factorization, which properly handle overlapped coclusters, by adding degrees of freedom for matrix factorization that enable the discovery of specialized column clusters for each row cluster. As a proof of concept, we modeled text analysis as a coclustering problem with column overlaps, assuming that given words (data matrix columns) are associated with over one document cluster (row cluster) because they can assume different semantic relationships in each association. Experiments on synthetic data sets show the OvNMTF algorithm reasonableness; experiments on real-world text data show its power for extracting high quality information.

Computerized adaptive testing (CAT) based on item response theory allows more accurate assessments with fewer questions than the classic paper and pencil (P&P) test. Nonetheless, the CAT construction involves some key questions that, when done properly, can further improve the accuracy and efficiency in estimating the examinees’ abilities. One of the main questions is in regard to choosing the item selection rule (ISR). The classic CAT makes exclusive use of one ISR. However, these rules have differences depending on the examinees’ ability level and on the CAT stage. Thus, the objective of this work is to reduce the dichotomous test size which is inserted in a classic CAT with no significant loss of accuracy in the estimation of the examinee’s ability level. For this purpose, we analyze the ISR performance and then build a personalized item selection process in CAT considering the use of more than one rule. The case study in Mathematics and its Technologies test of the ENEM 2012 shows that the Kullback-Leibler information with a posterior distribution (KLP) has better performance in the examinees’ ability estimation when compared with Fisher information (F), Kullback-Leibler information (KL), maximum likelihood weighted information (MLWI), and maximum posterior weighted information (MPWI) rules. Previous results in the literature show that CAT using KLP was able to reduce this test size by 46.6% from the full size of 45 items with no significant loss of accuracy in estimating the examinees’ ability level. In this work, we observe that the F and the MLWI rules performed better on early CAT stages to estimate examinees’ proficiency level with extreme negative and positive values, respectively. With this information, we were able to reduce the same test by 53.3% using the personalized item selection process, called ALICAT, which includes the best rules working together.

Stochastic Shortest Path (SSP) is the most popular framework to model sequential decision-making problems under stochasticity. However, decisions for real problems should consider risk sensitivity to provide robust decisions taking into account bad scenarios. SSPs that deal with risk are called Risk-Sensitive SSPs (RSSSPs), and an interesting framework from a theoretical perspective considers Expected Utility Theory under an exponential utility function. However, from a practical perspective, exponential utility function causes overflow or underflow in computer implementation even in small state spaces. In this paper, we make use of LogSumExp technique to solve RSSSPs under exponential utility in practice within Value Iteration, Policy Iteration, and Linear Programming algorithms. Experiments were performed on a toy problem to show scalability of the proposed algorithms.

An important and often neglected aspect in probabilistic planning is how to account for different attitudes towards risk in the process. In goal-driven problems, modeled as Shortest Stochastic Path (ssp) problems, risk arises from the uncertainties on future events and how they can lead to goal states. An ssp agent that minimizes the expected accumulated cost is considered a risk-neutral agent, while with a different optimization criterion it could choose between two extreme attitudes: risk-aversion or risk-prone. In this work we consider a Risk Sensitive ssp (called rs-ssp) that uses an expected exponential utility parameterized by the risk factor \(\lambda \) that is used to define the agent’s risk attitude. Moreover, a \(\lambda \)-value is feasible if it admits a policy with finite expected cost. There are several algorithms capable of determining an optimal policy for rs-ssp s when we fix a feasible value for \(\lambda \). However, so far, there has been only one approach to find an extreme \(\lambda \) feasible i.e., an extreme risk-averse policy. In this work we propose and compare new approaches to finding the extreme feasible \(\lambda \) value for a given rs-ssp, and to return the corresponding extreme risk-averse policy. Experiments on three benchmark domains show that our proposals outperform previous approach, allowing the solution of larger problems.

In the Portfolio Management problem the agent has to decide how to allocate the resources among a set of stocks in order to maximize his gains. This decision-making problem is modeled by some researchers through Markov decision processes (MDPs) and the most widely used criterion in MDPs is maximizing the expected total reward. However, this criterion does not take risk into account. To deal with risky issues, risk sensitive Markov decision processes (RSMDPs) are used. To the best of our knowledge, RSMDPs and more specifically RSMDPs with exponential utility function have never been applied to handle this problem. In this paper we introduce a strategy to model the Portfolio Management problem focused on day trade operations in order to enable the use of dynamic programming. We also introduce a measure based on Conditional Value-at-Risk (CVaR) to evaluate the risk attitude. The experiments show that, with our model and with the use of RSMDPs with exponential utility function, it is possible to change and interpret the agent risk attitude in a very understandable way.

A Markov Decision Process (MDP) is commonly used to model a sequential decision-making problem where an agent interacts with an uncertain environment while looking for minimizing the expected cost accumulated along the process. If the process horizon is infinite, a discount factor \(\gamma \) \(\in \) [0, 1] is used to indicate the importance the agent gives to future states. If the agent’s mission is to achieve a goal state, the process becomes a Stochastic Shortest Path MDP (SSP-MDP), the in fact model used for probabilistic planning in AI. Although several efficient solutions have been proposed to solve SSP-MDPs, there are little research carried out when we consider the “risk” in such processes. A Risk Sensitive MDP (RS-MDP) allows modeling the agent’s risk-averse and risk-prone attitudes, by including a risk and a discount factor in the MDP definition. The proof of convergence of known solutions based on dynamic programming adapted for RS-MDPs, such as risk-sensitive value iteration (VI) and risk-sensitive policy iteration (PI), rely on the discount factor. However, when solving an SSP-MDP we look for a proper policy, i.e. a policy that guarantees to reach the goal while minimizing the accumulated expected cost, which is naturally modeled without discount factor. Besides, it has been shown that the discount factor can modify the chosen risk attitude when solving a risk sensitive SSP-MDP. Thus, in this work we aim to formally proof the convergence of the PI algorithm for a Risk Sensitive SSP-MDP based on operators that use a piecewise-linear transformation function, without a discount factor. We also run experiments in the benchmark River domain showing how the intended risk attitude, in an interval of extreme risk-averse and extreme risk-prone, varies with the discount factor \(\gamma \), i.e. how an optimal policy for Risk Sensitive SSP-MDP can go from being a risk-prune policy to a risk-averse one, depending on the discount factor.

Made available in DSpace on 2019-10-04T12:13:38Z (GMT). No. of bitstreams: 0 Previous issue date: 2019-05-01 Background subtraction is the prerequisite for a wide range of applications including video surveillance, smart environments and content retrieval. Real environments present some challenging situations even for the most recent algorithms, such as shadows, illumination changes, dynamic background, among others. If a real environment is previously known and the challenging situations of this environment can be predicted, the choice of an appropriate algorithm to deal with such situations may be essential for obtaining better segmentation results. In our work, we identify the main situations that affect the performance of background subtraction algorithms and present a classification of these challenging situations. In addition, we present a solution that uses videos and ground-truths from existing datasets to evaluate the performance of segmentation algorithms when they need to deal with a specific challenging situation. Univ Tecnol Fed Parana, Cornelio Procopio, PR, Brazil Univ Estadual Paulista, Bauru, Brazil Univ Sao Paulo, Sao Paulo, Brazil Univ Estadual Paulista, Bauru, Brazil

Processos de decisão Markovianos (Markov Decision Processes -- MDPs) são amplamente utilizados para resolver problemas de tomada de decisão sequencial. O critério de desempenho mais utilizado em MDPs é a minimização do custo total esperado. Porém, esta abordagem não leva em consideração flutuações em torno da média, o que pode afetar significativamente o desempenho geral do processo. MDPs que lidam com esse tipo de problema são chamados de MDPs sensíveis a risco. Um tipo especial de MDP sensível a risco é o CVaR MDP, que inclui a métrica CVaR (Conditional-Value-at-Risk) comumente utilizada na área financeira. Um algoritmo que encontra a política ótima para CVaR MDPs é o algoritmo de Iteração de Valor com Interpolação Linear chamado CVaRVILI. O algoritmo CVaRVILI precisa resolver problemas de programação linear várias vezes, o que faz com que o algoritmo tenha um alto custo computacional. Neste trabalho, é proposto um algoritmo que avalia uma política estacionário para CVaR MDPs de custo constante e que não precisa resolver problemas de programação linear, esse algoritmo é chamado de PECVaR. Além disso, foram realizados experimentos usando o custo total esperado e o custo usando o algoritmo PECVaR de uma política neutra para inicializar o algoritmo CVaRVILI. Os resultados mostram que utilizando essas inicializações é possível diminuir o tempo de convergência do CVaRVILI na maioria dos casos.

Made available in DSpace on 2020-12-10T16:59:51Z (GMT). No. of bitstreams: 0 Previous issue date: 2019-11-01 Extracting elements of interest from video frames is a necessary task in many applications, such as those that require replacing the original background. Quality assessment of foreground extraction algorithms is essential to find the best algorithm for a particular application. This paper presents an application-dependent objective metric capable of evaluating the quality of those algorithms by considering user perception. Our metric identifies types of errors that cause the greatest annoyance based on regions of the scene where users tend to keep their attention during videoconference sessions. We demonstrate the efficiency of our metric by evaluating bilayer segmentation algorithms. The results showed that metric is effective compared to others used to evaluate algorithms for videoconferencing systems. Univ Tecnol Fed Parana, Cornelio Procopio, PR, Brazil Univ Estadual Paulista, Bauru, Brazil Univ Sao Paulo, Escola Politecn, Sao Paulo, Brazil Univ Sao Paulo, Sao Paulo, Brazil Univ Estadual Paulista, Bauru, Brazil

This paper shows an empirical study of Value Iteration Risk Sensitive algorithm proposed by Mihatsch and Neuneier (2002). This approach makes use of a risk factor that allows dealing with different types of risk attitude (prone, neutral or averse) by using a discount factor. We show experiments with the domain of Crossing the River in two different scenarios and we analyze the influence of discount factor and risk factor under two aspects: optimal policy and processing time to convergence. We observed that: (i) the processing cost in extreme risk policies is high with both risk-averse and risk-prone attitude; (ii) a high discount increases time to convergence and reinforces the chosen risk attitude; and (iii) policies with intermediate risk factor values have a low computational cost and show a certain sensitivity to risk based on the discount factor.

Markov Decision Process (MDP) has been used very efficiently to solve sequential decision-making problems. However, there are problems in which dealing with the risks of the environment to obtain a reliable result is more important than minimizing the total expected cost. MDPs that deal with this type of problem are called risk-sensitive Markov decision processes (RSMDP). In this paper we propose an efficient heuristic search algorithm that allows to obtain a solution by evaluating only the relevant states to reach the goal states starting from an initial state.

The inventory routing problem with stochastic demand includes the inventory control, product transportation and scheduling decisions, considering an estimation of customer demands. This problem appears in several real situations, playing a fundamental role in reducing costs and improving the efficiency and reliability of the service. In practice, there are often restrictions on the "time window", which corresponds to a certain period of the day on which deliveries can be made. Despite the great relevance of this type of constraint, there are no results in the literature that combine stochastic demand and time window constraints. In this work, we propose a system, using advanced techniques of operational research, to solve the inventory routing problem with stochastic demand, considering time window constraints, as well as additional constraints of maximum inventory capacities in both the client and the depot and individual confidence level of the customer service.

The integration of inventory management, vehicle routing, and scheduling decisions is known as Inventory Routing Problem (IRP). In this problem, the main objective is to determine: (i) the quantity of products to be delivered based on customer's demand; (ii) the delivery periods and (iii) the route of vehicles. IRPs that include time window service constraints are found in real scenarios and the attendance of this type of constraints brings benefits to both the supplier and the customer. This systematic review of the literature aims to identify trends in the area that studies Inventory Routing Problems with time windows. We identify and analyze the proposed approaches, the characteristics of the solved problems and the type of experiments performed in 9 primary studies.

Reinforcement Learning is a general approach to learn acting optimally in a stochastic environment; however, because of a trial-and-error strategy, learning may take prohibitive long times. An effective method to accelerate the learning process is to make use of spatial abstractions to produce a generalization of experiences. Therefore, how to automatically design abstractions is an important question in Reinforcement Learning. We formalize the problem of designing abstractions as the problem of selecting abstractions, and we propose to evaluate the learning process as a surrogate of the quality of a subset of abstractions. Because evaluating the learning process is costly, we present an algorithm, the SEPO algorithm, that construct a ranking of abstractions efficiently. To evaluate the efficiency of the SEPO algorithm, experiments are done in a soccer simulator.

Co-clustering is being given increasing attention by data scientists because it reveals a priori hidden information in data, through an analysis of item clusters along with attribute clusters. The use of co-clustering methods based on non-negative matrix factorization is considered to be advantageous for contexts in which data is positive matrices. However, there are limitations in these methods when co-clusters are characterized by columns overlapping (or attributes) – a common situation in several application contexts. In this paper, we have formalized the problem of Columns Overlapping Co-clustering and introduced BinOvNMTF (Binary Overlapped Non-negative Matrix Tri-Factorization), a new algorithm to analyze attribute clusters independently for each item cluster. This analysis is particularly useful for discovering information embedded in attribute clusters. We tested the BinOvNMTF algorithm in synthetic and real (textual) datasets; BinOvNMTF achieved superior results than those obtained by correlated algorithms.

Fornecedores necessitam atender a demanda de seus clientes da forma mais otimizada possível e mantendo a qualidade de seu serviço. Porém, em muitos casos essa demanda é desconhecida. O problema conhecido como problema de roteirização e inventário com demanda estocástica combina: (i) o controle de estoque; (ii) o transporte do produto; e (iii) decisões de agendamento da entrega considerando essa classe de demanda. Este trabalho tem como objetivo melhorar o algoritmo estado da arte baseado em programação matemática e relaxação lagrangeana visando encontrar soluções com custo menor. Para tal, foram propostas três variantes do algoritmo considerando diferentes heurísticas. Foram realizados experimentos com instâncias de teste contendo 15, 25 e 50 clientes; e foram analisados o custo final da solução e o tempo computacional para a solução convergir.

Os processos de decisão de Markov (em inglês Markov Decision Process - MDP) têm sido usados com muita eficiência para resolução de problemas de tomada de decisão sequencial. Existem problemas em que lidar com os riscos do ambiente para obter um resultado confiável é mais importante do que maximizar o retorno médio esperado. MDPs que lidam com esse tipo de problemas são chamados de processos de decisão de Markov sensíveis a risco (em inglês Risk-Sensitive Markov Decision Process - RSMDP). Esta revisão sistemática da literatura tem por objetivo identificar os resultados teóricos e os algoritmos propostos para resolver problemas de RSMDP que tenham função utilidade exponencial, avaliando as suas principais características, semelhanças, particularidades e diferenças de modo a permitir ao leitor o conhecimento desta ferramenta de tomada de decisão sequencial para problemas sensíveis ao risco.

Markov Decision Processes (MDPs) have long been the framework for modeling optimal decisions in stochastic environments. Although less known, Risk Sensitive Markov Decision Processes (RSMDP) extend MDPs by allowing arbitrary risk attitude. However, not every environment is well-defined in MDPs and RSMDPs and both versions make use of discount in costs to turn every problem well-defined, because of the exponential grow in RSMDPs, the problem of a well-defined problem is even harder. Here, we show that the use of discount in costs: (i) in MDPs induces a risk-prone attitude in MDPs, and (ii) in MDPs, hinders risk-averse attitude for some scenarios.

The Goal-Directed Risk-Sensitive Markov Decision Process allows arbitrary risk attitudes for the probabilistic planning problem to reach a goal state. In this problem, the risk attitude is modeled by an expected exponential utility and a risk factor λ. However, the problem is not well defined for every λ, posing the problem of defining the maximum (extreme) value for this factor. In this paper, we propose an algorithm to find this e-extreme risk factor and the corresponding optimal policy.

The use of computer vision to analyze human movement has been growing considerably, facilitated by the increased availability of depth cameras This paper describes the results of a systematic review about the techniques used for movement tracking and recognition, focusing on metrics to compare choreographed movements using Microsoft Kinect as a sensor. Several techniques for data analysis and pattern recognition are explored for this task, particularly Dynamic Time Warping and Hidden Markov Models. Most papers we discuss used a single sensor instead of more complex setups and most took advantage of the Kinect SDK instead of alternatives. Rhythm is rarely considered in these systems due to the temporal alignment strategies used. While most systems that use the sensors for some form of interaction instead claim that this interaction is natural, very few actually perform any sort of usability or user experience analysis.

In this systematic review we approach the problem of light variation in tasks related to automatic facial recognition, a feature that can significantly affect the performance of automatic systems. We then carry out a broad research on the state of the art, describing and comparing current research in this subject. The review relies on a set of processes for searching, analysing and describing research that is considered relevant to this work, and which are reported in more detail in this article. In analysing the results, we could notice that the problem of light variation is still one of the greatest challenges in the area of facial recognition, which translates in a good deal of research directly tackling this problem, trying to solve it or, at least, mitigate it somehow, so as to improve the performance of facial recognition techniques and algorithms. Finally, results also show that this is a problem of great concern by researchers in the field, insomuch that even those articles that do not directly deal with it still make explicit the researchers' concern about it.

The ability to automatically determine a human body’s sequence of postures during movement has many practical applications, from the evaluation of the performance of physical activity practitioners to the evaluation and design of the user experience in certain systems. Current representations for such postures, however useful, are not capable of capturing all necessary features for a complete description of a human stance, such as the relationship between non-directly connected body parts. In this article, we introduce a mark-up language for body stance and movement description, designed to allow for the unambiguous representation of movement as well as the extraction of relationships between directly and non-directly connected body parts. Along with the language, we also present a computer program, developed to help end users in codifying stance and movement without having to know the language in detail.

Reinforcement Learning is carried out on-line, through trial-and-error interactions of the agent with the environment, which can be very time consuming when considering robots. In this paper we contribute a new learning algorithm, CFQLearning, which uses macro-states, a low-resolution discretisation of the state space, and a partial-policy to get around obstacles, both of them based on the complexity of the environment structure. The use of macro-states avoids convergence of algorithms, but can accelerate the learning process. In the other hand, partial-policies can guarantee that an agent fulfils its task, even through macro-state. Experiments show that the CFQ-Learning performs a good balance between policy quality and learning rate.

Recentemente, várias tarefas tem sido delegadas a sistemas computacionais, principalmente quando sistemas computacionais são mais confiáveis ou quando as tarefas não são adequadas para seres humanos. O uso de extração de preferências ajuda a realizar a delegação, permitindo que mesmo pessoas leigas possam programar facilmente um sistema computacional com suas preferências. As preferências de uma pessoa são obtidas por meio de respostas para questões específicas, que são formuladas pelo próprio sistema computacional. A pessoa age como um usuário do sistema computacional, enquanto este é visto como um agente que age no lugar da pessoa. A estrutura e contexto das questões são apontadas como fonte de variações das respostas do usuário, e tais variações podem impossibilitar a factibilidade da extração de preferências. Uma forma de evitar tais variações é questionar um usuário sobre a sua preferência entre dois comportamentos observados por ele. A questão de avaliar relativamente comportamentos observados é mais simples e transparente ao usuário, diminuindo as possíveis variações, mas pode não ser fácil para o agente interpretar tais avaliações. Se existem divergências entre as percepções do agente e do usuário, o agente pode ficar impossibilitado de aprender as preferências do usuário. As avaliações são geradas com base nas percepções do usuário, mas tudo que um agente pode fazer é relacionar tais avaliações às suas próprias percepções. Um outro problema é que questões, que são expostas ao usuário por meio de comportamentos demonstrados, são agora restritas pela dinâmica do ambiente e um comportamento não pode ser escolhido arbitrariamente. O comportamento deve ser factível e uma política de ação deve ser executada no ambiente para que um comportamento seja demonstrado. Enquanto o primeiro problema influencia a inferência de como o usuário avalia comportamentos, o segundo problema influencia quão rápido e acurado o processo de aprendizado pode ser feito. Esta tese propõe o problema de Extração de Preferências com base em Comportamentos Observados utilizando o arcabouço de Processos Markovianos de Decisão, desenvolvendo propriedades teóricas em tal arcabouço que viabilizam computacionalmente tal problema. O problema de diferentes percepções é analisado e soluções restritas são desenvolvidas. O problema de demonstração de comportamentos é analisado utilizando formulação de questões com base em políticas estacionárias e replanejamento de políticas, sendo implementados algoritmos com ambas soluções para resolver a extração de preferências em um cenário sob condições restritas. Recently, computer systems have been delegated to accomplish a variety of tasks, when the computer system can be more reliable or when the task is not suitable or not recommended for a human being. The use of preference elicitation in computational systems helps to improve such delegation, enabling lay people to program easily a computer system with their own preference. The preference of a person is elicited through his answers to specific questions, that the computer system formulates by itself. The person acts as an user of the computer system, whereas the computer system can be seen as an agent that acts in place of the person. The structure and context of the questions have been pointed as sources of variance regarding the users answers, and such variance can jeopardize the feasibility of preference elicitation. An attempt to avoid such variance is asking an user to choose between two behaviours that were observed by himself. Evaluating relatively observed behaviours turn questions more transparent and simpler for the user, decreasing the variance effect, but it might not be easier interpreting such evaluations. If divergences between agents and users perceptions occur, the agent may not be able to learn the users preference. Evaluations are generated regarding users perception, but all an agent can do is to relate such evaluation to his own perception. Another issue is that questions, which are exposed to the user through behaviours, are now constrained by the environment dynamics and a behaviour cannot be chosen arbitrarily, but the behaviour must be feasible and a policy must be executed in order to achieve a behaviour. Whereas the first issue influences the inference regarding users evaluation, the second problem influences how fast and accurate the learning process can be made. This thesis proposes the problem of Preference Elicitation under Evaluations over Observed Behaviours using the Markov Decision Process framework and theoretic properties in such framework are developed in order to turn such problem computationally feasible. The problem o different perceptions is analysed and constraint solutions are developed. The problem of demonstrating a behaviour is considered under the formulation of question based on stationary policies and non-stationary policies. Both type of questions was implemented and tested to solve the preference elicitation in a scenario with constraint conditions.

Ad Networks connect advertisers to websites that want to host advertisements. When users request websites, the Ad Network decides which ad to send so as to maximize the number of ads that are clicked by users. Due to the difficulty in solving such maximization problems, there are solutions in the literature that are based on linear programming (LP) relaxations. We contribute with a formulation for the Ad Network optimization problem, where it is cast as a Markov decision process (MDP). We analyze theoretically the relative performance of MDP and LP solutions. We report on an empirical evaluation of solutions for LP relaxations, in which we analyze the effect of problem size in performance loss compared to the MDP solution. We show that in some configurations, the LP relaxations incur in approximately 58 % revenue loss when compared to MDP solutions. However, such relative loss decreases as problem size increases. We also propose new heuristics to improve the use of solutions achieved by LP relaxation. We show that solutions obtained by LP relaxations are suitable for Ad Networks, as the performance loss introduced by such solutions are small in large problems observed in practice.

Sistemas de Recomendação baseados em Conteúdo (SRbC) é uma área em que estratégias de Aprendizado de Máquina (AM) podem ser potencialmente aplicadas com êxito. Contudo, especificamente na área de SRbC textual, o uso de AM não tem sido expressivo nos últimos anos. Neste artigo é apresentada uma Revisão Sistemática para identificação, interpretação e avaliação de como estratégias de AM vêm sendo utilizadas no contexto de SRbC textual a fim de contribuir para a evolução da interseção de tais áreas.

Reinforcement learning (RL) enables an agent to learn behavior by acquiring experience through trial-and-error interactions with a dynamic environment. However, knowledge is usually built from scratch and learning to behave may take a long time. Here, we improve the learning performance by leveraging prior knowledge; that is, the learner shows proper behavior from the beginning of a target task, using the knowledge from a set of known, previously solved, source tasks. In this paper, we argue that building stochastic abstract policies that generalize over past experiences is an effective way to provide such improvement and this generalization outperforms the current practice of using a library of policies. We achieve that contributing with a new algorithm, AbsProb-PI-multiple and a framework for transferring knowledge represented as a stochastic abstract policy in new RL tasks. Stochastic abstract policies offer an effective way to encode knowledge because the abstraction they provide not only generalizes solutions but also facilitates extracting the similarities among tasks. We perform experiments in a robotic navigation environment and analyze the agent's behavior throughout the learning process and also assess the transfer ratio for different amounts of source tasks. We compare our method with the transfer of a library of policies, and experiments show that the use of a generalized policy produces better results by more effectively guiding the agent when learning a target task.

In this paper we improve learning performance of a risk-aware robot facing navigation tasks by employing transfer learning; that is, we use information from a previously solved task to accelerate learning in a new task. To do so, we transfer risk-aware memoryless stochastic abstract policies into a new task. We show how to incorporate risk-awareness into robotic navigation tasks, in particular when tasks are modeled as stochastic shortest path problems. We then show how to use a modified policy iteration algorithm, called AbsProb-PI, to obtain risk-neutral and risk-prone memoryless stochastic abstract policies. Finally, we propose a method that combines abstract policies, and show how to use the combined policy in a new navigation task. Experiments validate our proposals and show that one can find effective abstract policies that can improve robot behavior in navigation problems.

This paper presents a theoretical and empirical analysis of linear programming relaxations to ad network optimization. The underlying problem is to select a sequence of ads to send to websites, while an optimal policy can be produced using a Markov Decision Process, in practice one must resort to relaxations to bypass the curse of dimensionality. We focus on a state-of-art relaxation scheme based on linear programming. We build a Markov Decision Process that captures the worst-case behavior of such a linear programming relaxation, and derive theoretical guarantees concerning linear relaxations. We then report on extensive empirical evaluation of linear relaxations, our results suggest that for large problems (similar to ones found in practice), the loss of performance introduced by linear relaxations is rather small.

Assessment of video segmentation quality is a problem seldom investigated by the scientific community. Nevertheless, recent studies presented some objective metrics to evaluate algorithms. Such metrics consider different ways in which segmentation errors occur (perceptual factors) and its parameters are adjusted according to the application for which the segmented frames are intended. We demonstrate empirically that the performance of existing metrics changes according to the segmentation algorithm; we applied such metrics to evaluate bilayer segmentation algorithms for compose scenes in Augmented Reality environments. We also contribute with a new objective metric to adjust the parameters of two bilayer segmentation algorithms found in the literature.

In an environment of uncertainty where decisions must be taken, how to make a decision considering the risk? The shortest stochastic path (SSP) problem models the problem of reaching a goal with the least cost. However under uncertainty, a best decision may: minimize expected cost, minimize variance, minimize worst case, maximize best case, etc. Markov Decision Processes (MDPs) defines optimal decision in the shortest stochastic path problem as the decision that minimizes expected cost, therefore MDPs does not care about the risk. An extension of MDP which has few works in Artificial Intelligence literature is Risk Sensitive MDP. RSMDPs considers the risk and integrates expected cost, variance, worst case and best case in a simple way. We show theoretically the differences and similarities between MDPs and RSMDPs for modeling the SSP problem, in special the relationship between the discount factor γ and risk prone attitudes under the SSP with constant cost. We also exemplify each model in a simple artificial scenario.

Video segmentation to extract a person in foreground has been a common task in many Augmented Reality (AR) applications. In natural environments which the background color and the light environment are not constant the segmentation method must be able to extract the element of the interest in these conditions. However, methods for segmentation in natural environment are more error prone than the traditional ones which are based on a constant color elimination. Thus, in order to use them in a large number of applications it is necessary to know how the segmentation errors are perceived by the users in order to focus on development of algorithms which avoid the more perceptible ones. In this work a video quality subjective assessment method was applied to obtain the AR user's opinions about videos with different misclassified pixels rates. The results showed that segmentation errors are perceived by AR applications users. However, the video quality was not related with the number of the misclassified pixels. In addiction, it was noted that when the errors concentrated in the element of the interest increase the score of the associated video decreases.

Relational representations let sequential decision problems be described through objects and relations, resulting in more compact, expressive, and domain-independent representations that make it possible to find and generalize solutions much faster than propositional representations. In this paper we propose a modified policy iteration algorithm (AbsProb-PI) for the infinite-horizon discounted-reward criterion; the algorithm finds a memoryless probabilistic relational abstract policy that abstracts well the solution from source problems so that it can be applied in new, similar problems. Experiments in robotic navigation validate our proposals and show that we can find effective and efficient abstract policies, outperforming solutions by inductive approaches in the literature.

Augmented Reality (AR) systems which use optical tracking with fiducial marker for registration have had an important role in popularizing this technology, since only a personal computer with a conventional webcam is required. However, in most these applications, the virtual elements are shown only in the foreground a real element does not occlude a virtual one. The method presented enables AR environments based on fiducial markers to support mutual occlusion between a real element and many virtual ones, according to the elements position (depth) in the environment.

This paper presents an algorithm that augments a previous model known in the literature for the automatic segmentation of monocular videos into foreground and background layers. The original model fuses visual cues such as color, contrast, motion and spatial priors within a Conditional Random Field. Our augmented model makes use of bidirectional motion priors by exploiting future evidence. Although our augmented model processes more data, it does so with the same time performance of the original model. We evaluate the augmented model within ground truth data and the results show that the augmented model produces better segmentation.

Markov Decision Processes (MDPs) provide a mathematical framework for modelling decision-making of agents acting in stochastic environments, in which transitions probabilities model the environment dynamics and a reward function evaluates the agent's behaviour. Lately, however, special attention has been brought to the difficulty of modelling precisely the reward function, which has motivated research on MDP with imprecisely specified reward. Some of these works exploit the use of nondominated policies, which are optimal policies for some instantiation of the imprecise reward function. An algorithm that calculates nondominated policies is π Witness, and nondominated policies are used to take decision under the minimax regret evaluation. An interesting matter would be defining a small subset of nondominated policies so that the minimax regret can be calculated faster, but accurately. We modified π Witness to do so. We also present the π Hull algorithm to calculate nondominated policies adopting a geometric approach. Under the assumption that reward functions are linearly defined on a set of features, we show empirically that pHull can be faster than our modified version of π Witness.

Most work in navigation approaches for mobile robots does not take into account existing solutions to similar problems when learning a policy to solve a new problem, and consequently solves the current navigation problem from scratch. In this article we investigate a knowledge transfer technique that enables the use of a previously know policy from one or more related source tasks in a new task. Here we represent the knowledge learned as a stochastic abstract policy, which can be induced from a training set given by a set of navigation examples of state-action sequences executed successfully by a robot to achieve a specific goal in a given environment. We propose both a probabilistic and a nondeterministic abstract policy, in order to preserve the occurrence of all actions identified in the inductive process. Experiments carried out attest to the effectiveness and efficiency of our proposal.

The task of navigating to a target position in space is a fairly common task for a mobile robot. It is desirable that this task is performed even in previously unknown environments. One reactive architecture explored before addresses this challenge by denning a hand-coded coordination of primitive behaviours, encoded by the Potential Fields method. Our first approach to improve the performance of this architecture adds a learning step to autonomously find the best way to coordinate primitive behaviours with respect to an arbitrary performance criterion. Because of the limitations presented by the Potential Fields method, especially in relation to non-convex obstacles, we are investigating the use of Relational Reinforcement Learning as a method to not only learn to act in the current environment, but also to generalise prior knowledge to the current environment in order to achieve the goal more quickly in a non-convex structured environment. We show the results of our previous efforts in reaching goal positions along with our current research on generalised approaches.