Fuzzy measures and integrals theory and applications

fuzzy information measures with applications intuitionistic fuzzy measures theory and applications
Dr.NaveenBansal Profile Pic
Published Date:25-10-2017
Your Website URL(Optional)
Fuzzy Measures and Experts’ Opinion Elicitation An Application to the FEEM Sustainable Composite Indicator 1,2 2,3 Luca Farnia and Silvio Giove 1 Mediterranean Center for Climate Change (CMCC), Bologna, Italy 2 Fondazione Eni Enrico Mattei, Venice, Italy 3 University Cà Foscari, Venice, Italy luca.farniafeem.it, sgioveunive.it Abstract. To over pass the limits inherent in liner models, suitable aggregation operators are required, taking into account interactions among the criteria. This becomes more and more crucial in Decision Theory, where all the information can be inferred by one or more Experts, using an ad hoc questionnaire. This is the case of the FEEM SI sustainability index, a composite geo-referenced index which aggregates several economic, social and environmental dimensions- structured in a decision tree- into a single number between zero (the worst sustainable country) and one (the best one). Fuzzy measure (non additive meas- ures) are here proposed for the aggregation phase. To this purpose, each inter- mediate node of the structure combines the values of the sub-nodes using a model based on second-order non additive measure. To infer the value of the measure for each node, a suitable questionnaire has been fulfilled by a set of Experts, and the obtained answers were processed using an optimization algo- rithm. To guarantee the strict convexity of the algorithm, the questionnaire needs to be carefully designed. The individual measures are subsequently ag- gregated and the numerical results permitted to compare the sustainability of all the considered territorial units. Keywords: Fuzzy measures, non-additive measures, Choquet integral, preference structure, sustainability, aggregation operators. 1 Introduction In Multi Attribute problems the Weighted Averaging operator (WA) is widely used to aggregate the normalized values of the criteria. Anywise, the linear WA method is unable to include interactions (synergies or redundancies) among the criteria. For this reason, more specialized algorithms need to be considered. One of the most common- ly used is based on fuzzy measures (or capacity, or non-additive measures, NAMs for brevity), which assigns a weight to every possible coalition of criteria, and not to a singleton only. A suitable aggregation operator, the Choquet integral Beliakov, 2009, extends the Weighted Averaging (WA) to the computation of an aggregated results using NAM. The interested reader can refer to Grabisch, 2000, Marichal, 2000-2 for a methodological analysis of fuzzy measures. In the case of WA only © Springer International Publishing Switzerland 2015 229 S. Bassis et al. (eds.), Recent Advances of Neural Networks Models and Applications, Smart Innovation, Systems and Technologies 37, DOI: 10.1007/978-3-319-18164-6_22 230 L. Farnia and S. Giove parameters need to be elicited, if is the number of the criteria to be aggregated. But in NAM the number of the required parameters – the value of the fuzzy measures - exponentially increases with , and the numerical complexity becomes crucial, espe- cially in the case of Decision Theory, where the information can be inferred only by one or more Experts. The reduced order model, which considers interactions only between subset of limited cardinality, can be applied to reduce the numerical com- plexity. In particular, the second order model admits interactions only between couple of criteria. In this paper we propose an elicitation method based on a suitable ques- tionnaire. The questionnaire is formed by a set of alternatives, i.e. what ... if... ques- tions, and the answers can be used to elicit the non-additive measure by means of the Least Square optimization algorithm that minimizes the sum of squared distances between the answers of the Expert(s) and the solutions of the problem. The procedure was applied to a real world case study, the project FEEM SI, a composite Sustainabili- ty Index including 23 indicators grouped in a tree structure. A team of Experts were asked to fulfil a questionnaire, by which the NAMs were implicitly elicited, one for each node of the tree. To avoid a too strong mental effort, the number of the questions needs to be limited, then a second order model was selected as aggregation operator. The paper is organized as follows. Section 2 introduces the concept of fuzzy meas- ures, included the reduced order model, and the Choquet integral as aggregation oper- ator. Section 3 describes the proposed elicitation approach, while Section 4 reports its application to the FEEM SI sustainability indicator. Some conclusive comments and suggestions are reported in Section 5; technical results are briefly reported in the Appendix. 2 Fuzzy Measures and the Choquet Integral A fuzzy measures or NAM, defined over the set of criteria 1 ,2,…, , is a set function : 2 0,1 satisfying the following boundary and monotonicity conditions: 0 1 (1) 1 , A NAM assigns to every subset (coalition) of criteria a measure that is not necessarily the sum of the measures of their singletons. Namely, if the measure of a coalition is greater (smaller) than the sum of the measures of their singletons, that measure represents a synergic (redundant) interaction among the criteria belonging to the coa- lition. Instead when the measure of a coalition equals the sum of the measures of the singletons belonging to it, the NAM collapses to the linear aggregation (WA) and no interaction exists among the criteria. Given a NAM , its Möbius representation is the following set function, see Marichal, 2000-2: ∑ 1 , , (2) Fuzzy Measures and Experts’ Opinion Elicitation 231 where , ). Moreover the following boundary and the mono- tonicity conditions are required, see Marichal, 2000-2: 0 ∑ 1 (3) ∑ 0, , Let be a NAM defined on and , ,…, the normalized values of the criteria belonging to N; the (discrete) Choquet integral with respect to is given by Grabisch, 2000: ,..., ∑ (4) where means that the indices have been permutated in such a way that , while ,…, and 0 . Using the Möbius representation the Choquet integral can be written as: ∑ ,..., (5) being the minimum operator. To define a capacity on , 2 parameters are required. If the capacity represents the preference structure of an Expert, it needs to be directly or implicitly elicited using a suitable questionnaire. In the case of a complete model, the number of parameters exponentially increases with , usually a prohibi- tive task, thus a reduced order model is proposed Grabisch, 1997, satisfying the compromise between criteria interaction and numerical complexity. A capacity on is said to be k-additive if its Möbius representation satisfies 0 such that , and there exists at least one subset with such that 0 . In this way a k-additive capacity with 1 ,2,…, is completely de- ∑ fined by the identification of parameters. If 2 we have a second order model (2-order model for brevity) and only parameters are required. 2.1 Behavioural Analysis We limit to mention the two most popular indices developed in order to have a direct interpretation of non additive measures: the Shapley value Shapley, 1953 and the Interaction index Grabisch, 1997. The Shapley value is a measure of the relative importance of a criterion, computed averaging all the marginal gains between any coalition not including the criterion, and the one which includes it. In terms of Möbius representation the Shapley value of criterion i is defined as following: ; ∑ (6) 232 L. Farnia and S. Giove When fuzzy measures are not additive, interaction among criteria exists; in terms of Möbius representation the Interaction index among a combination of criteria, can be formulated as: ; ∑ (7) In a 2-order model the interaction index of a coalition coincides with its Möbius representation. 3 The Least Square Elicitation Approach The specialized literature reports several approaches to elicit fuzzy measures. Among them, we limit to recall the Least Square (LS) and the Heuristic Least Square (HLS) Grabisch, 1995, the approach of Marichal and Roubens (MR) Marichal, 2000-1, the Minimum Variance (MV) Kojadinovic, 2007 and Minimum Distance (MD) Kojadinovic, 2000. Such methods differ together by the required information (for instance, cardinal or ordinal type), the objective function, and the applied algorithm. The LS and the HLS require cardinal information about the alternatives, that is, a global evaluation (sometimes defined as utility), assigned by an Expert. For this rea- son, we define these methods as cardinal-based models. Conversely, the MR, MV and MD method require only a preference order of the alternatives; they can be defined ordinal-based models. In this contribution we applied the LS, after having designed carefully the questionnaire, in such a way that the optimization problem is strictly 1 convex and thus the LS can return a unique solution . To this purpose, let be: 1. , ,…, the set of the criteria; 2. , ,…, a scenario, that is a set of alternatives; 1 ,…, 1 ……………… 3. the normalized values of the criteria for each alternative ,…, (or the criteria utility for each alternative); 4. : the utility assigned by the Expert to alternative 5. , 1,,. : the value of the -th alternative computed through the 2-order model, with the elicited parameters, ,…, ; We now briefly formalize the LS optimization algorithm which minimizes the sum squared differences between the evaluation of the Expert and the ones computed by the k-order model. 1 If the optimization problem is not strictly convex, the solution is not unique P. Miranda, M. Grabisch, 1999. Nerveless the strict convexity depends on the questionnaire structure, see Subsection 3.1. Fuzzy Measures and Experts’ Opinion Elicitation 233 : ∑ – . . (8) ∑ 0 , ∑ 1 If an algebraic condition is satisfied about the scenario’s values proposed in the ques- tionnaire -see Subsection 3.1- the solution to problem (8) is unique. 3.1 Optimization Issue We underline that the LS approach returns a unique vector of Möbius representations iff the number of alternatives to be judged and the utilities associated to the criteria satisfy the mathematical condition stated in the Property below. The property needs the following preliminary definition: let define the full scenario matrix whose elements in the first rows are partitioned by the matrix of utili- ties associated to each criteria for each alternative, and the matrix containing the minimum utilities values of each coalition and for each alternative; all the elements in the last row are equal to one (representing the boundary condition): 1 … 1 1 2 … 2 2 (9) … 1… 1 with . Property 1 The LS approach returns a unique vector of Möbius representations iff the question- naire is designed in such a way that the full scenario matrix has rank equal to the number of Möbius representations to be elicited in a k-order model. Consider for instance a 2-additive model with two criteria and two alternatives; fol- lowing the formulation in Section 3, the full scenario matrix has the following struc- ture: 1 1 1 , 1 2 2 2 , 2 11 1 A necessary and sufficient condition to have 3 is 1 1 2 2 . 234 L. Farnia and S. Giove 4 The FEEM SI Composite Index The project FEEM Sustainability Index (FEEM SI) started some years ago FEEM Sustainability Index Methodological Report, 2011 with the aim to construct a global sustainability index on a national scale. The data generating model is based on a Computable General Equilibrium (CGE) dynamic economic model which is able to forecast macro-economic variables of interest over a time window of about 20 years. The CGE furnishes for each nation and for each year inside the time window, the forecasted values of the macro variable. We do not discuss here the CGE methodolo- gy, see the quoted references for a detailed explanation, but focus the attention on the aggregation methodology that, year by year and for every nation, computes a single Sustainability Index for any considered nation in the world. Doing so, it permits an immediate ranking and comparison of nations putting in evidence possible variation of nation sustainability, strength and weakness points. Figure 1 shows the FEEM SI composite index, which is split into the three main pillars of sustainability (economic, social and environmental). Each pillar is split again into sub-dimension, and so on until the 23 leaves that are the sampled indicators. For each node and sub-node, the aggregation follows a bottom-up procedure using the 2-order model, from the leaves up to the root, the FEEM SI composite index. 4.1 Methodology FEEM SI is based on two main and complementary blocks of operations: the CGE model, which processes the macro variables used as input data, and the criteria weighting scheme which aggregates the normalized data for each block of criteria used. Data input have been normalized by means of suitable functions that transform the input criteria data on a scale between zero and one, given suitable thresholds im- posed by Experts specialized in that field. This is hence a data-insensitive normaliza- tion approach, necessary to neutralize the risk of potential rank reversal problem, as can appear, for example, in the min-max normalization approach. The criteria weighting scheme is based on Experts’ opinion elicitation by means of an ad-hoc questionnaire satisfying the solution uniqueness condition as explained in Subsection 3.1. Subsections below explain how the questionnaire has been developed, together with the methodology used to aggregate Experts’ preferences into a single “representative” one. 4.1.1 Ad-Hoc Questionnaire for Fuzzy Experts ‘Opinion Elicitation’ Each Expert has been asked to evaluate some hypothetical nations on the base of the joint performance of some criteria considered. Given the structure of the decision tree whose nodes are formed by different set of criteria, this process has been performed for all nodes. Table 1. shows the discrete qualitative scale used in the questionnaire to describe the criteria performance (first column) and the Expert choices to evaluate alternatives (second column); the third column describes the equivalent numerical scale used in the elicitation algorithm. Fuzzy Measures and Experts’ Opinion Elicitation 235 Table 1. Evaluation scheme Qualitative Scale Numerical Scale Criteria Performance Expert Evaluation Very bad Very Dissatisfied 0 Bad Dissatisfied 0.25 Fair Nor Diss./ Sat. 0.5 Good Satisfied 0.75 Excellent Very Satisfied 1 The criteria performance of each alternative has been set according to Property 1 (see Subsection 3.1). Table 2 is an example of the FEEM SI main node, where 5 hy- pothetical nations with different performances in the economic, social and environ- mental dimension have to been evaluated by each interviewed Expert. Table 2. FEEM SI (main node) questionnaire example Criteria Expert Overall Nation Economic Social Environment Evaluation 1 Excellent Good Bad - 2 Excellent Bad Good - 3 Good Excellent Bad - 4 Bad Excellent Good - 5 Bad Good Excellent - 4.1.2 Experts’ Opinion Elicitation and Their Aggregation Given that NAM approach is sufficiently general to cover many preference structures, Expert’s preference has been weighted according to his/her overall consistency in judging the alternatives proposed. This is indeed an important step, especially when a survey is conducted without having a direct and immediate control on Expert’s evalu- ation. We measure Expert’s consistency as a function of the sum of squared distances in problem 8), in such a way that the greater (smaller) this sum, the smaller (greater) the contribution from the relative Expert. The above conditions can be formalized as following. Given alternatives to be judged, let define the vector 1 whose elements represent the differences between the overall utilities values set by the j-th Expert and the respective Choquet values (solution of the problem 8)). Let be the sum of squared distances for the j-th Expert: . (10) The sum of squared distances for the j-th Expert is filtered using an exponential model: with 0 , (11) 236 L. Farnia and S. Giove In such a way that 0, 1 , being a suitable positive constant. The relative contribution from the j-th Expert (on a total of interviewed) is defined as the following importance weight: . (12) ∑ The final Möbius representation as the result of the weighted average of each Expert’s preference, can be defined in the following: ∑ (13) 4.2 Some Results We limit to show the results of the elicitation process in the main node of the FEEM Si index where the three pillars of sustainability have been jointly considered. Figure 2 illustrates the results of the weighting scheme with 3 ; from the left to the right are shown in decreasing order the weights to be associated to each of the 23 Expert interviewed in accordance to their overall coherence in this node. The data row of Figure 2 represent the numerical values of equations 10), 11) and 12) respectively. Figure 3 illustrates the Shapley values derived by the elicited Möbius representation for each Expert. Figure 4 illustrates the Interaction indices derived by the elicited Möbius representation. Table 3 shows the results of Experts’ preferences aggregation in terms of Shapley values, from which the social dimension appears to be the most important pillar (38.6%), followed by the environmental pillar (35.70%), while the economic pillar is the least (25.70%). Table 4 shows the relative importance of the criteria belonging to the second level of the decision tree; wellbeing is considered the most important factor of sustainability and GDP p.c. the least one. 5 Conclusions In this paper we proposed a multi-criteria approach based on the second order Cho- quet Integral, with the aim to take interaction among the criteria into account and, at the same time, to maintain the numerical complexity as low as possible. The fuzzy measures are elicited using an ad hoc questionnaire to be fulfilled by a panel of Ex- perts, and a suitable optimization algorithm based on Least Square approach. In par- ticular we showed that, when the questionnaire is structured in a particular way, the solution of the optimization problem is unique. The method was applied to the FEEM SI project, which is a computable geo-referenced sustainability index, organized into an hierarchical tree. For each node of the tree, the second order Choquet algorithm aggregates the values of the sub-node referring to it, bottom-up moving from the leaves up to the root. The aggregated sustainability index is computed for every con- sidered territorial unit, permitting an immediate comparison. We are going to develop other optimization techniques based on alternative algorithms, like Goal Program- ming, testing the efficiency in comparison with the Least Square method. Fuzzy Measures and Experts’ Opinion Elicitation 237 References 1. Athanasoglou, S., Weziak-Bialowolska, D., Saisana, M.: Environmental Performance In- dex, – JRC Analysis and Recommendations, EPI-JRC, pp. 1–33 (2014) 2. Beliakov, G.: Construction of aggregation functions from data using linear programming. Fuzzy Sets and Systems 160, 65–75 (2009) 3. Cardin, M., Giove, S.: Approximation of fuzzy measures using second order measures: Es- timation of andness bounds. In: Masulli, F. (ed.) WILF 2013. LNCS (LNAI), vol. 8256, pp. 150–160. Springer, Heidelberg (2013) 4. Decanq, K., Lugo, M.A.: Weights in environmental indices of wellbeing: an overview. Econometric Review 32(1), 7–34 (2013) 5. Despic, O., Simonovic, S.P.: Aggregation operators for decision making in water re- sources. Fuzzy Sets and Systems 115(1), 11–33 (2000) 6. FEEM Sustainability Index Methodological Report 2011, Fondazione Eni Enrico Mattei (2011), http://www.feemsi.org/documents/ 7. Jones, D., Mehrdad, T.: Practical Goal Programming, vol. 141. Springer (2010) 8. Ishii, K., Sugeno, M.: A model of human evaluation process using fuzzy measure. Interna- tional Journal of Man-Machine Studies 67, 242–257 (1996) 9. Grabisch, M., Nguyen, H.T., Walker, E.A.: Fundamentals of uncertainty calculi with ap- plications to fuzzy inference. Kluwer Academic, Dordrecht (1995) 10. Grabisch, M.: A new algorithm for identifying fuzzy measures and its application to pat- tern recognition. In: Proceedings of international 4th IEEE Conference on Fuzzy Systems, Yokohama, pp. 145–150 (1995) 11. Grabisch, M.: k-order additive discrete fuzzy measures and their representation. Fuzzy Sets and Systems 92, 167–189 (1997) 12. Grabisch, M., Roubens, M.: Application of the Choquet integral in multicriteria deci-sion making. In: Grabisch, M., Murofushi, T., Sugeno, M. (eds.) Fuzzy Measures and Integrals – Theory and Applications, pp. 348–374. Physica Verlag (2000) 13. Ishii, K., Sugeno, M.: A model of human evaluation process using fuzzy measure. Interna- tional Journal of Man-Machine Studies 67 14. Kojadinovic, I.: Quadratic distances for capacity and bi-capacity approximation and identi- fication. A Quarterly Journal of Operations Research (in press), doi: 10.1007/s10288-006- 0014-4; Marichal, J.-L., Roubens, M.: Determination of weights of interacting criteria from a reference set. European Journal of Operational Research 124, 641–650 (2000) 15. Kojadinovic, I.: Minimum variance capacity identification. European Journal of Opera- tional Research 177, 498–514 (2007) 16. Marichal, J.: An axiomatic approach of the discrete Choquet integral as a tool to aggregate interacting criteria. The IEEE Transactions on Fuzzy Systems 8(6), 800–807 (2000) 17. Marichal, J.-L.: Tolerant or intolerant character of interacting criteria in aggregation by the Choquet integral. European Journal of Operational Research 155, 771–791 (2004) 18. Marichal, J.-L.: K-intolerant capacities and Choquet integrals. European Journal of Opera- tional Research 177, 1453–1468 (2007) 19. Meyer, P., Roubens, M.: Choice, ranking and sorting in fuzzy Multiple Criteria Decision Aid. In: Figueira, J., Greco, S., Ehrgott, M. (eds.) Multiple Criteria Decision Analysis: State of the Art Surveys, pp. 471–506. Springer, New York (2005) 20. Miranda, P., Grabisch, M.: Optimization issues for fuzzy measures. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 7(6), 545–560 (1999) 238 L. Farnia and S. Giov ve 21. Mori, T., Murofushi, T.: An analysis of evaluation model using fuzzy measure and the Choquet integral. In: P Proceedings of 5th Fuzzy System Symposium, Kobe, Jap pan, pp. 207–212 (1989) (in Ja apanese) 22. Murofushi, T.: A techniqu ue for reading fuzzy measures (I): the Shapley value with resp pect to a fuzzy measure. In: 2n nd Fuzzy Workshop, Nagaoka, pp. 39–48 (1992) (in Japanese) ) 23. OECD/EC JRC, Handboo ok on Constructing Composite Indicators: Methodology and U User Guide. OECD, Paris (2008) 24. Pinar, M., Cruciani, C., G Giove, S., Sostero, M.: Constructing the FEEM sustainability y in- dex: A Choquet integral a application. Ecological Indicator 39, 189–202 (2014) 25. Shapley, L.S.: A value for r n-person games. In: Kuhn, H.W., Tucker, A.W. (eds.) Contr ribu- tions to the Theory of f Games, Vol. II. Annals of Mathematics Studies, vol.. 28, pp. 307–317. Princeton U University Press, Princeton (1953) Appendix Fig. 1. FEEM SI decision tree 1.20 1.00 0.80 0.60 0.40 0.20 0.00 12 34 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 3 g(j) 0.0 0.0 0.0 0.0 0.0 0 0.0 0.0 0.0 0.0 0.0 0.1 0.1 0.2 0.2 0.3 0.3 0.3 0.4 0.5 0.5 0.5 0.6 0.6 6 h(j) 1.0 1.0 1.0 1.0 0.9 0 0.9 0.9 0.8 0.7 0.7 0.6 0.6 0.5 0.5 0.4 0.3 0.3 0.2 0.2 0.2 0.1 0.1 0.1 1 w(j) 0.0 0.0 0.0 0.0 0.0 0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0 Fig.. 2. Weighting scheme - FEEM SI node Fuzzy Measures and Experts’ Opinion Elicitation 239 1.00 0.80 0.60 0.40 0.20 0.00 12 345 6 6 7 8 9 1011 121314 151617 181920 212223 3 Eco 0.2 0.3 0.3 0.1 0.1 0 0.2 0.2 0.3 0.2 0.2 0.3 0.0 0.0 0.2 0.3 0.3 0.3 0.4 0.0 0.2 0.3 0.3 0.3 3 Soc 0.1 0.1 0.4 0.4 0.5 0 0.4 0.3 0.3 0.3 0.4 0.3 0.5 0.5 0.3 0.3 0.4 0.3 0.3 0.6 0.5 0.3 0.3 0.3 3 Env 0.6 0.4 0.2 0.4 0.3 0 0.3 0.3 0.3 0.3 0.3 0.3 0.4 0.4 0.3 0.3 0.1 0.2 0.2 0.3 0.3 0.2 0.3 0.3 3 Fig. 3. Shapley values for each respondent - FEEM SI node 1.00 0.50 0.00 -0.50 -1.00 123 4 5678 9 1011121314151617181920212223 3 Env - Soc 0.2 0.2 -0. 0.4 0 0.5 0.1 0.6 -0. 0.2 0.6 0.3 0.2 0.4 0.4 -0. 0.0 0.2 0.4 0.7 0.1 0.2 0.3 0.3 3 Env - Eco -0. -0. 0.2 0.1 0 0.0 -0. -0. -0. 0.1 0.0 0.3 0.0 0.0 0.2 0.5 0.2 0.2 0.0 0.0 0.4 0.2 0.3 0.3 3 Soc - Eco 0.0 -0. 0.0 -0. 0 0.3 0.3 -0. 0.3 0.4 0.1 0.3 0.0 0.0 0.2 0.1 -0. 0.5 0.2 0.0 0.0 0.4 0.3 0.3 3 Fig. 4. Interac ction indices for each respondent - FEEM SI node Environmental Pillar Social Pillar Economy Pillar 240 L. Farnia and S. Giove Table 3. Shapley values in each node Pillar Node Criteria Shapley (%) Environment 35.70 FEEM SI Society 38.60 Economy 25.70 Natural Endowment 35.59 Environment Energy & Resources 30.70 Pollution 33.71 Water 48.59 Natural Endowment Biodiversity 51.41 Animals 51.07 Biodiversity Plants 48.93 Material Intensity 32.01 Energy & Resources Energy Intensity 31.93 Renewables 36.06 GHG p.c. 37.33 Pollution CO2 Intensity 33.65 Waste 29.02 Vulnerability 29.47 Society Well-Being 41.19 Transparency 29.34 Food Relevance 33.91 Vulnerability Private Health 32.28 Energy Security 33.81 Energy Imported 29.69 Energy Security Energy Access 70.31 Population Density 21.04 Well-Being Education 49.09 Life Expectancy 29.87 Corruption 70.47 Transparency ICT Access 29.53 Growth Drivers 38.34 Economy Exposure 31.42 GDP p.c. 30.24 R&D 56.92 Growth Drivers Investment 43.08 Relative Trade Balance 57.69 Exposure Public Debt 42.31 Fuzzy Measures and Experts’ Opinion Elicitation 241 Table 4. Marginal criteria importance in the second level Marginal Pillar Criteria Importance (%) Natural Endowment 12.71 Environment Energy & Resources 10.96 Pollution 12.03 Vulnerability 11.38 Society Well-Being 15.90 Transparency 11.32 Growth Drivers 9.85 Economy Exposure 8.07 GDP p.c. 7.77 Algorithms Based on Computational Intelligence for Autonomous Physical Rehabilitation at Home 1 2 Nunzio Alberto Borghese , Pier Luca Lanzi , 1 1 1 Renato Mainetti , Michele Pirovano , and Elif Surer 1 Department of Computer Science, University of Milan, Milan, Italy alberto.borghese,renato.mainetti,michele.pirovano, elif.surerunimi.it 2 Department of Electronics, Information Science and Bioengineering, Polytechnic University of Milan, Milan, Italy pierluca.lanzipolimi.it Abstract. Exergames provide efficient and motivating training mechanisms to support physical rehabilitation at home. Nonetheless, current exergame exam- ples lack some important aspects which cannot be disregarded in rehabilitation. Exergames should: (i) modify the game difficulty adapting to patient’s gamep- lay performance, (ii) monitor if the exercise is correctly executed, and (iii) pro- vide continuous motivation. In this study, we present a game engine which implements computer intelligence-based solutions to provide real-time adapta- tion, on-line monitoring and an engaging gameplay experience. The game en- gine applies real-time adaptation using the Quest Bayesian approach to modify the game difficulty according to the patient’s performance. Besides, it employs a fuzzy system to monitor the execution of the exercises according to the para- meters set by the therapists and provides on-line feedback to guide the patient during the execution of the exercise. Finally, a motivating game experience is provided using rewards and adding random enrichments during the game. Keywords: Rehabilitation, Bayesian optimization, Gamification, Exergames, Fuzzy systems. 1 Introduction Stroke is the leading cause of death in adults 1 and physical rehabilitation is needed to recover from its consequences 2. With stroke figures increasing every year, reha- bilitation is bound to have an even bigger impact on the expected costs of healthcare providers. On the other hand, healthcare providers strive to reduce those same costs, reducing personnel, discharging patients as soon as possible and reducing support. Rehabilitation is presently based on intensive exercising with an almost daily schedule that is carried out with a therapist; new solutions that can extend traditional rehabilitation, or even replace it, are needed. Exergaming represents one promising solution to this problem. Exergames merge the therapeutic effects of exercises to the engaging factors of games. They guide © Springer International Publishing Switzerland 2015 243 S. Bassis et al. (eds.), Recent Advances of Neural Networks Models and Applications, Smart Innovation, Systems and Technologies 37, DOI: 10.1007/978-3-319-18164-6_23 244 N.A. Borghese et al. patients to autonomously perform the exercises required by the rehabilitation therap- ists, thus requiring less supervision and opening to the possibility of self-rehabilitation at home, further reducing costs both for the healthcare provider and for the patient on one side, and supporting intensive rehabilitation on the other side. In addition, exer- games add a layer of engagement to the traditionally boring repetitive exercising re- quired by rehabilitation session, allowing the patient to exercise longer and have even fun while doing it 3. Several instances of successful rehabilitation exergames have been reported 4, but there are still many open problems concerning how to properly structure exergames so that the therapeutic validity of the exercises is not sacrificed and no hazard occurs to the patient. For this reason, exergames are presently used mainly inside the rehabilitation centers or with remote supervision by the therapist (tele-rehabilitation). Recent commercial video games require the player to move in order to play cor- rectly. For instance, WiiFit is a collection of games produced for the Nintendo Wii, a gaming console that requires the player to use her body movements to play, has been successfully used for in-hospital rehabilitation 5. However, video games such as Wii Fit have been designed with a different scope in mind than professional rehabilitation and they lack many of the needed features that would make such exergames usable without the presence of a therapist. For instance, commercial games usually impose fixed difficulty settings, making them impractical for impaired people; they do not track nor log the player’s movements and do not provide any supervision. These prac- tical considerations are of utmost importance if we want exergames to be useful in an at-home setting, and thus further reduce the costs of healthcare. We propose here, as a solution to these issues, the application of intelligent algo- rithms inside a game engine to support the features needed for a correct therapy. Such features can be summarized as follows 6: a) Scheduling, as the configuration of an exercises session must be carefully tailored to the patient’s current state; b) Adapta- tion, as the same exergames should be played by patients with varying degrees of impairment and still provide a reasonable challenge. c) On-line monitoring, as the movements of the patient must be evaluated in real-time to avoid dangerous move- ments and maladaptation. d) Assessment, as the results of the exercises have to be reviewed by the therapist for tuning and evaluation. e) Motivation, as the gaming elements of the exergames must be carefully designed to maximize compliance both in the short and in the long term. Specific intelligence-based algorithms can be ap- plied to all these different features, allowing exergames to be safely used at home. We delineate here how computational intelligence can be used to empower exergames, and we focus especially on the solutions we have introduced for adaptation and moni- toring. We incorporated the design considerations we have presented into a game engine that we have fully realized and that is currently being tested by patients. 2 Methodology In this section, our game engine and its computational intelligence based solutions that mainly address adaptation and monitoring, are presented in detail. Algorithms Based on Computational Intelligence 245 2.1 Intelligent Game Engine for Rehabilitation The Intelligent Game Engine (IGER) 7 has been developed as part of Rewire p plat- form1. The main objective e of Rewire is to develop a low-cost game-based platfo orm that assists patients, discha arged from the hospital, to pursue their rehabilitation au uto- nomously at home under re emote supervision of the clinicians. The Rewire platform m is constituted of three main components: a patient station (PS), a hospital station (H HS), and a networking station (N NS). The HS allows therapists to monitor remotely the on- going rehabilitation at pati ient’s home. It also provides features for the therapists s to schedule rehabilitation exe ergames and assess the rehabilitation outcomes. The NS provides advanced data mi ining tools that analyze common features of rehabilitat tion treatment among hospitals a and regions. The PS is installed at the patient’s home an nd it is the core of the Rewire p platform. It guides the patient through exercises prescribed by the HS by games. The PS has four main m modules. The hospital module is used by patients to inter ract with the therapists at the h hospital through audio/video communication and to dow wn- load their scheduled exergames. The lifestyle module collects data on the patien nt’s daily activity through a bod dy sensor network. The community module allows patie ents to interact with other patien nts online. Finally, the IGER module guides the actual l re- habilitation using 3D exerg games. IGER’s structure (Figure 1) and its computatio onal intelligence based features a are the focus of the present work. IGER has at its core a ty ypical game engine, i.e. a software architecture designed d to support video games. We h have used Panda3D here, but any other game engine ( (e.g. Unity 3D) can be used. Th he Game engine has been expanded through scripting l lan- guage to support a set of fe eatures tailored to rehabilitation, and especially post-str roke physical rehabilitation for b balance and posture. Fig. 1. The e components of the PS and the IGER module The IGER module embo odies two components: the game engine and the game c con- trol unit. The former provi ides all the gaming functionalities: input data, animati ion, collision detection, rendering, scoring and game logic. The latter contains the ga ame control unit that provides t the features needed for rehabilitation-oriented exergam mes. IGER presents modules for therapist-driven scheduling and assessment. 1 REWIRE project: http://www.rewire-project.eu 246 N.A. Borghese et al. The exercises associated to each rehabilitation session are configured off-line at the hospital by the therapists and their parameters are configured for each patient. The therapists can select which exercises and consequently which games to include in each training session, the duration of each exercise, the number of repetitions, and the difficulty level. In addition, the therapists can also select the most suitable input device for each rehabilitation task. Finally, the therapist can access the detailed out- come of the rehabilitation session and assess the patient’s performance and status. 2.2 Adaptation In video-games field, the widely accepted flow theory 8 defines flow as a state of heightened focus during which he/she is completely immersed in the activity, time flies by, and external inputs are ignored; a person can enter the state of flow while performing an activity, on the condition that the difficulty of the activity matches the person’s skills. This state is desirable because it is engaging, and many games strive to provide it by changing their difficulty in real-time, either through their intrinsic design or through specific Dynamic Difficulty Adaptation (DDA) algorithms. To design a DDA algorithm, one or more parameters can be selected for adapta- tion, making sure to choose parameters that directly affect the difficulty of the task. A simple method uses heuristics to change dynamically the parameters according to a metric derived from the patient’s input, such as the number of correct trials performed during a session of play. An alternative is to resort to statistical methods to support adaptation. In our sys- tem, we perform adaptation through a Bayesian framework, based on the QUEST psychometric method 9, to update one parameter and adapt it to the patient’s beha- vior. The parameter is changes on a trial or epoch basis, analyzing the success rate in the game tasks such that the overall rate approaches a desired score. The optimal pa- rameter value according to the therapist plays the role of a-priori value. This method is based on three assumptions that are all satisfied in our case. First, the function that relates the parameter to the performance in the game must have the same shape under all conditions. This can be obtained by considering an adequate function (in our case, Weibull distribution). Second, the subject’s threshold should not vary from trial to trial. Third, individual trials must be statistically independent. The last two assump- tions are satisfied, since the adaptation scope is a single session of a game and thus patient’s skill improvement can be safely disregarded. 2.3 On-line Monitoring One of the most important roles of the physical rehabilitation therapist, if not the one of utmost importance, is real-time monitoring of the user’s performance and move- ments. Video-games, in fact, try to challenge the user to move fast and this can become dangerous for patients with limited motion control and capabilities 10. Monitoring is aimed to avoid mal-adaptation, i.e. it avoids making the patient perform movements that would be detrimental to the therapy while attempting to perform the exercises correctly. Algorithms Based on Computational Intelligence 247 In classical rehabilitation n the exercises are performed in presence of the thera apist who can correct the posture e of the patient when she does not move correctly throu ugh verbal feedback or direct intervention. In an autonomous setting, such as at-ho ome rehabilitation, the watching g eye of the therapist must be replaced by a suitable soft- ware system. In fact, the foc cus of the exergames alone may be on the games instead d of on the exercise (and this is a all the more likely if a state of flow is reached), we see t that correct and responsive mon nitoring becomes even more important. In addition, consid- er that the autonomous and d nonintrusive system cannot directly intervene on the pa- tient’s movement as a thera apist would do, hence why clear visual and audial feedb back is needed. Note that correc ct monitoring cannot be achieved with commercial act tive games, as they provide fee edback based on the game’s results but fail to give use eful feedback to the patient abo out her actual movements. This might be one of the cau uses the leads to a relatively high h drop out in the first tests on using exergames for rehab bili- tation at home. Monitoring g can greatly benefit from Computational Intelligence t that can provide algorithms suit table to be used to analyze in real-time the movements s of the patient and select what feedback to give to the patient as well as its frequency y in time. From a high-level perspective, we can see monitoring as being composed of th hree parts: the inputs given by th he patient (i.e. her movements), the rules that dictate when the movements are correct a and what is more important, as chosen by the therapist, and the generated feedback. A A fuzzy system 11 has been developed for this purp pose (Figure 2). Fig. 2. The scheme of the monitoring mechanism in IGER The rules on the movem ments are created by the therapist inside the hospital and d in- corporate the therapist’s kn nowledge and requirements on the exercises. These ru ules map the input variables to t the alarm level output, according to the monitor configu ura- tions; they are translated in nto fuzzy clauses that are associated with an alarm level. For instance: “If bend latera ally_MEDIUM spine, raise alarm_MEDIUM”. At run-ti ime the monitoring system rece eives as input all the motion data and feeds them to a fu uzzy inference engine that outputs an alarm level for each chosen monitor. Such ala arm level is used by the feedbac ck system to notify the patient of wrong movements. Fr rom the different alarm level a single global alarm level is raised through defuzzificati ion. The alarm level is transfo ormed into a color code that is applied to the ava atar: 248 N.A. Borghese et al. (a) (b) Fig. 3. Color-coded monitoring examples from games (a)Fruit Catcher (b)Animal Hurdle er white means no error and a color progressively going towards red indicates danger rous postures. The patient can th herefore see immediately how she is performing (Figure e 3). If the patient movement is b beyond the maximum allowed range defined by the ther rap- ist, the game pauses and a virtual therapist appears and advice the patient on how w to perform the exercise correc ctly. Afterwards, the game resumes. 3 Results and Disc cussion IGER offers efficient exerg games for rehabilitation and provides computer-intellige ence solutions to adaptation, mo onitoring and motivation mechanisms as described in the previous sections. These s solutions allow us to tailor rehabilitation to the patien nt’s performance, monitor the correctness of the exercise and motivate the patient by combining good game desi ign principles with an engaging gaming environment. We have designed and implem mented a total of 18 exergames that incorporate all th hese features and that are aimed d to posture and balance and neglect rehabilitation. Th hese games have been designed starting from the inputs provided by the therapists. For instance, the Animal l Hurdler exergame (Figure 4a) aims at training patients s on balance, while providing an n additional cognitive load (dual task). In the gameplay, the patient is guided to raise her r leg such that the avatar can step over worms that appro oach it. To step over the creatures, the patient, alternatively, can move laterally (lateral ste ep). Thus, the game supports sev veral exercises: lateral stepping and leg-rising exercises. L Leg rising exercise can be track ked through Kinect device and a balance board can also o be used to have a direct and re eliable estimate of the center of mass. When lateral stepp ping exercise is performed, motio on is tracked only with the Kinect device. An additional cognitive lo oad can be added to the game, by asking the patient to keep p his arm at ninety degrees, asking g him to let her avatar to carry logs with its arms (Figure 4b b). The performance of the patient in each exergame is computed by considering h how many worms have been cau ught in respect to how many have been missed on a se et of trials. The adaptable parame eter of Animal Hurdler is set as the number of approach hing worms per minute. Therefo ore, when the patient performs well during the exergame, the number of animals is in ncremented so that the user has to perform the same ex xer- cise more times in the same e time period. The animal size and the speed of the anim mal are also adaptable paramete ers. However, it was considered unsafe to ask the patien nt to perform higher or faster ste eps and therefore the height of the foot and the speed of f the motion are not controlled or r adapted. Algorithms Based on Computational Intelligence 249 (a) (b) Fig. 4. (a) Animal Hurdler exergame (b) Animal Hurdler exergame with dual task Monitoring is applied on the avatar’s spine and neck, to make sure the patient does not bend them, and on the COP of the patient to make sure she does not move around the playing area. As described in Section 2.3, the therapist sets the optimal range for the monitoring exercises and visual and audial feedback is given to the patient depending on the alarm severity. Another game example is Fruit Catcher (Figure 5), which is designed for weight- shift and lateral steps exercises. In Fruit Catcher, the player must catch fruits falling from the top of a tree. The player, represented in third view by an avatar, stands below the tree with a basket on her head and can either shift her body to the left and to the right, while keeping the feet still on the ground, or move the body laterally to catch the fruits in the basket; depending on the requisite of the exercise. Fig. 5. Fruit Catcher exergame The game can be played with different devices for different exercise goals, with a balance board (weight shift) or a Kinect (lateral steps). The performance of the patient is measured by the number of fruits caught by the patient with respect to the number of fruits missed. The adaptable parameter of Fruit Catcher is set as the frequency of the falling fruits. Monitoring is applied on the avatar’s spine and neck, to make sure the patient does not bend them, and on the COP of the patient to make sure she does not move around the playing area or she does not exceed the defined limits. The bend- ing of the knee can be also monitored, as well as the movement of the arms.

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.