publications

2021

1. Recommendations for evaluating the performance of background subtraction algorithms for surveillance systems

   Sanches, Silvio Ricardo Rodrigues, Sementille, Antonio Carlos, Aguilar, Ivan Abdo, and Freire, Valdinei

   Multimedia Tools and Applications, 2021

   Abs HTML

   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.

2020

1. JBCS

   ALICAT: a customized approach to item selection process in computerized adaptive testing

   G. Jatobá, V.M., Farias, J.S., Freire, V., and Delgado, Karina V.

   JOURNAL OF THE BRAZILIAN COMPUTER SOCIETY, 2020

   Abs HTML

   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.

2. IJCNN

   OvNMTF Algorithm: an Overlapping Non-Negative Matrix Tri-Factorization for Coclustering

   de Freitas, W. L., Peres, S. M., Freire, V., and Brunialti, L. F.

   In 2020 International Joint Conference on Neural Networks (IJCNN), 2020

   Abs HTML

   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.

3. MICAI

   Risk Sensitive Markov Decision Process for Portfolio Management

   Neto, E.L.P., Freire, V., and Delgado, K.V.

   In Martínez-Villaseñor L., Herrera-Alcántara O., Ponce H., Castro-Espinoza F.A. (eds) Advances in Soft Computing. MICAI 2020. Lecture Notes in Computer Science, 2020

   Abs HTML

   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.

4. MICAI

   Risk-Sensitive Piecewise-Linear Policy Iteration for Stochastic Shortest Path Markov Decision Processes

   Dias Pastor, H., Oliveira Borges, I., Freire, V., and Valdivia Delgado, L.

   In Martínez-Villaseñor L., Herrera-Alcántara O., Ponce H., Castro-Espinoza F.A. (eds) Advances in Soft Computing. MICAI 2020. Lecture Notes in Computer Science, 2020

   Abs HTML

   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 γ ∈ [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 γ, 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.

5. BRACIS

   Risk Sensitive Stochastic Shortest Path and LogSumExp: From Theory to Practice

   Freitas, E.M., Freire, V., and Delgado, K.V.

   In Cerri R., Prati R.C. (eds) Intelligent Systems. BRACIS 2020. Lecture Notes in Computer Science, 2020

   Abs HTML

   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.

6. BRACIS

   Finding Feasible Policies for Extreme Risk-Averse Agents in Probabilistic Planning

   Fernandez, M.C., Barros, L.N., Mauá, D., Delgado, K.V., and Freire, V.

   In Cerri R., Prati R.C. (eds) Intelligent Systems. BRACIS 2020. Lecture Notes in Computer Science, 2020

   Abs HTML

   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 λ that is used to define the agent’s risk attitude. Moreover, a λ-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 λ. However, so far, there has been only one approach to find an extreme λ feasible i.e., an extreme risk-averse policy. In this work we propose and compare new approaches to finding the extreme feasible λ 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.

2019

1. PAD: a perceptual application-dependent metric for quality assessment of segmentation algorithms

   Sanches, Silvio Ricardo Rodrigues, Sementille, Antonio Carlos, Tori, Romero, Nakamura, Ricardo, and Freire, Valdinei

   Multimedia Tools and Applications, 2019

   Abs HTML

   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.

2. Challenging situations for background subtraction algorithms

   Sanches, Silvio Ricardo Rodrigues, Oliveira, Claiton, Sementille, Antonio Carlos, and Freire, Valdinei

   Applied Intelligence, 2019

   Abs HTML

   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.

3. ICAPS

   An Exact Algorithm to Make a Trade-Off between Cost and Probability in SSPs

   Freire, Valdinei, Delgado, Karina Valdivia, and Silva Reis, Willy Arthur

   In Proceedings of the International Conference on Automated Planning and Scheduling 2019

   Abs HTML

   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: (<em>i</em>) the proof that the eGUBSoptimal policy has a finite representation; (<em>ii</em>) the first exact algorithm to obtain finite optimal policies for the eGUBS criterion, and (<em>iii</em>) 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.</p>

2018

2017

1. AAMAS

   GUBS: A Utility-Based Semantic for Goal-Directed Markov Decision Processes

   Freire, Valdinei, and Delgado, Karina Valdivia

   In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems 2017

   Abs HTML

   A key question in stochastic planning is how to evaluate policies when a goal cannot be reached with probability one. Usually, in the Goal-Directed Markov Decision Process (GD-MDP) formalization, the outcome of a policy is summarized on two criteria: probability of reaching a goal state and expected cost to reach a goal state. The dual criterion solution considers a lexicography preference, by prioritizing probability of reaching the goal state and then minimizing the expected cost to goal. Some other solutions, consider only cost by using some math trick to guaranteed that every policy has a finite expected cost. In this paper we show that the lexicography solution does not allow a smooth trade-off between goal and cost, while the expected cost solution does not define a goal-semantic. We propose GUBS (Goals with Utility-Based Semantic), a new model to evaluate policies based on the expected utility theory; this model defines a trade-off between cost and goal by proposing an axiomatization for goal semantics in GD-MDPs. We show that our model can be solved by any continuous state MDP solver and propose an algorithm to solve a special class of GD-MDPs.

2016

2015

1. JBCS

   Evaluation of linear relaxations in Ad Network optimization for online marketing

   Freire, Valdinei, Truzzi, Flávio Sales, Reali Costa, Anna Helena, and Cozman, Fabio Gagliardi

   Journal of the Brazilian Computer Society, 2015

   Abs HTML

   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.

2. Stochastic Abstract Policies: Generalizing Knowledge to Improve Reinforcement Learning

   Koga, M. L., Freire, V., and Costa, A. H. R.

   IEEE Transactions on Cybernetics, 2015

   Abs HTML

   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.

2014

2013

2012

1. Bilayer Segmentation of Live Video in Uncontrolled Environments for Background Substitution: An Overview and Main Challenges

   Rodrigues Sanches, S. R., Nakamura, R., Freire da Silva, V., and Tori, R.

   IEEE Latin America Transactions, 2012

   Abs HTML

   Bilayer segmentation of live video in uncontrolled environments is an essential task for home applications in which the original background of the scene must be replaced, as in video chats or traditional videoconference. The main challenge in such conditions is overcome all difficulties in problem-situations (e.g., illumination change, distract events such as element moving in the background and camera shake) that may occur while the video is being captured. This paper presents a survey of segmentation methods for background substitution applications, describes the main concepts and identifies events that may cause errors. Our analysis shows that although robust methods rely on specific devices (multiple cameras or sensors to generate depth maps) which aid the process. In order to achieve the same results using conventional devices (monocular video cameras), most current research relies on energy minimization frameworks, in which temporal and spacial information are probabilistically combined with those of color and contrast.

2011

1. Navigation towards a goal position: from reactive to generalised learned control

   Silva, Valdinei Freire, Selvatici, Antonio Henrique, and Costa, Anna Helena Reali

   Journal of Physics: Conference Series 2011

   Abs HTML

   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.

2010

2009

1. JBCS

   Compulsory Flow Q-Learning: an RL algorithm for robot navigation based on partial-policy and macro-states

   Silva, Valdinei Freire da, and Costa, Anna Helena Reali

   Journal of the Brazilian Computer Society, 2009

   Abs HTML

   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.