Anis Yazidi
email: anis.yazidi@hioa.no.

Xuan Zhang

Lei Jiao
email: lei.jiao@uia.no.

B John Oommen
email: oommen@scs.carleton.ca.

The Hierarchical Continuous Pursuit Learning Automation for Large Numbers of Actions

Keywords: Learning Automata (LA), Pursuit LA, Estimator-based LA, Hierarchical LA, LA with large number of actions

Although the field of Learning Automata (LA) has made significant progress in the last four decades, the LA-based methods to tackle problems involving environments with a large number of actions are, in reality, relatively unresolved. The extension of the traditional LA (fixed structure, variable structure, discretized, and pursuit) to problems within this domain cannot be easily established when the number of actions is very large. This is because the dimensionality of the action probability vector is correspondingly large, and consequently, most components of the vector will, after a relatively short time, have values that are smaller than the machine accuracy permits, implying that they will never be chosen. This paper pioneers a solution that extends the continuous pursuit paradigm to such large-actioned problem domains. The beauty of the solution is that it is hierarchical, where all the actions offered by the environment reside as leaves of the hierarchy. Further, at every level, we merely require a two-action LA which automatically resolves the problem of dealing with arbitrarily small action probabilities. Additionally, since all the LA invoke the pursuit paradigm, the best action at every level trickles up towards the root. Thus, by invoking the property of the "max" operator, in which, the maximum of numerous maxima is the overall maximum, the hierarchy of LA converges to the optimal action. Apart from reporting the theoretical properties of the scheme, the paper contains extensive experimental results which demonstrate the power of the scheme and its computational advantages. As far as we know, there are no comparable results in the field of LA.

Introduction

This paper deals with the well-trodden field of Learning automata (LA) 1 . For decades, this field, initiated by Tsetlin [START_REF] Tsetlin | Finite automata and the modeling of the simplest forms of behavior[END_REF], has been studied as a typical model for learning in random environments, and has served as the precursor for the area of reinforcement learning. Unlike other fields of Artificial Intelligence (AI), an LA, by definition, operates in random environments, where the "Teacher" can respond differently and randomly, for the same query, at different time instances. More specifically, an LA is an adaptive decision-making unit that learns the optimal action from among a set of actions offered by the Environment that it operates in. Without loss of generality, to render the problem non-trivial, the Environment is stochastic. At each iteration (or time step), the LA selects one action and communicates it to the Environment. This, in turn, stochastically triggers either a reward or a penalty as a response from the Environment. Based on the response and the knowledge acquired in the past iterations, the LA, either deterministically or stochastically, adjusts its action selection strategy. This is done so as to make a "wiser" decision in the next iteration. Thus the LA, even though it lacks a complete knowledge about the Environment, is able to learn through repeated interactions with the Environment, and adapts itself, or "converges", to the optimal decision.

Although LA have been studied extensively [START_REF] Agache | Generalized pursuit learning schemes: new families of continuous and discretized learning automata[END_REF][START_REF] Zhang | The Bayesian pursuit algorithm: A new family of estimator learning automata[END_REF][START_REF] Zhang | Discretized Bayesian pursuit -a new scheme for reinforcement learning[END_REF][START_REF] Zhang | On incorporating the paradigms of discretization and Bayesian estimation to create a new family of pursuit learning automata[END_REF][START_REF] Zhang | The design of absorbing Bayesian pursuit algorithms and the formal analyses of their ε-optimality[END_REF] and been applied in many fields [START_REF] Jiao | Optimizing channel selection for cognitive radio networks using a distributed bayesian learning automata-based approach[END_REF][START_REF] Thathacha | Networks of Learning Automata: Techniques for Online Stochastic Optimization[END_REF], designing LA when the number of actions involved, R, is large is extremely complex. The solution that we propose in this paper attempts to resolve this problem.

Contributions of the Paper

The contributions of this paper are the following:

1. We propose a hierarchical LA strategy which superimposes the learning process on a tree structure. Unlike the traditional hierarchical schemes, we do not resort to Fixed Structure Stochastic Automata (FSSA) or Variable Structure Stochastic Automata (VSSA) to achieve the learning. 2. We propose a novel learning process that involves multi-level two action Continuous Pursuit Algorithm (CPA) machines. The estimation and interaction with the real-world environment occur only at the leaf level. 3. We propose the process of trickling-up the estimates and accomplishing the learning by only invoking learning between a node and its sibling. 4. The scheme that we have proposed is novel in that it never involves action probabilities that are below machine accuracy. It also involves estimates whose accuracies can easily be attained. 5. The scheme that we have proposed is ε-optimal in all random environments [START_REF] Yazidi | The Hierarchical Continuous Pursuit Learning Automation: A Novel Scheme for Environments with Large Numbers of Actions[END_REF].

6. The speed of the proposed scheme is many times faster than that of all the LA reported in the literature. It is thus the fastest and most accurate reported LA for environments with a large number of actions. As far as we know, no experiments have ever been done in the field of LA for environments when the number of actions was so large, and in that sense, this is truly a pioneering and ground-breaking venture, clearly proving the power of the scheme! 2 The HCPA LA

Rationale for Our Solution

The philosophy motivating our new scheme resorts to superimposing the actions onto a binary tree2 , in which, the leaves are the actual actions themselves. Further, each internal node represents the best action in the entire subtree below that node. By performing comparisons between the actions in a pairwise manner, i.e., at the leaves of the tree, only the superior actions are trickled up towards the root. By doing this, one always deals with 2-action LA. Here, however, unlike the work of previous researchers [START_REF] Baba | A new learning algorithm for the hierarchical structure learning automata operating in the nonstationary S-model random environment[END_REF], we do not resort to FSSA or traditional VSSA, to differentiate between the various pairs of actions at the leaves. Rather, we shall use the 2-action continuous pursuit LA [START_REF] Zhang | A formal proof of the ε-optimality of absorbing continuous pursuit algorithms using the theory of regular functions[END_REF]. Since R = 2 at every level, the number of iterations required to achieve the estimation is considerably less. Further, the estimation that is achieved at the leaf level, is all that is required for the entire tree -no estimation operations are required at the internal nodes.

A notable attempt to devise hierarchical LA is due to Papadimitriou [START_REF] Papadimitriou | Hierarchical discretized pursuit nonlinear learning automata with rapid convergence and high accuracy[END_REF]. Before we comment on this work, we mention that the Pursuit concept can be used in a Continuous or Discretized paradigm, and that the action probabilities can be changed on Reward-Penalty (RP), Reward-Inaction (RI) and Inaction-Penalty (IP) scenarios. Consequently, we would have six Pursuit variants: CP RP , DP RP , CP RI , DP RI , CP IP and DP IP , and of these, Agache and Oommen [START_REF] Oommen | Continuous and discretized pursuit learning schemes: various algorithms and their comparison[END_REF] showed that the DP RI is the most superior one. The author of [START_REF] Papadimitriou | Hierarchical discretized pursuit nonlinear learning automata with rapid convergence and high accuracy[END_REF] has precisely used this machine, and this is commendable. The differences between that work and the work that we have done here is, however, significant. First of all, this lies is in the way that we have modeled the tree along which the actions have been placed. Secondly, the strategy by which we have trickled up the "maximum" estimate at every node is quite unique and novel, and it does not require us to probe (query) the environment at every time instant, implying that these interactions with the Environment are only at the leaves. All of these lead to the superiority of our scheme over the recorded ones, demonstrated for experiments done for a much larger set than what has been reported in the literature3 !

Construction of the Hierarchy

The search space for the binary tree alluded to above is constructed as follows. First of all, the hierarchy is organized as a balanced full 4 binary tree with maximal depth K. For the sake of convenience and in the interest of mathematical formalism, we will use the same notation adopted in [START_REF] Granmo | Solving stochastic nonlinear resource allocation problems using a hierarchy of twofold resource allocation automata[END_REF][START_REF] Yazidi | A novel strategy for solving the stochastic point location problem using a hierarchical searching scheme[END_REF], and index the nodes using both their depth in the tree and their relative order with respect to the nodes located at the same tree depth. The details of the hierarchy as described as follows.

1. Root node: The LA at the root of the hierarchy is the one at depth 0.

2. The various LA: At each node, we invoke a 2-action LA A, whose actions are cited as 0 and 1. 3. LA activations for K levels: from 0 to K-1:

-The different LA at depth k: The LA j ∈ {1, ..., 2 k } at depth k, is referred to as A {k, j} , where 0 ≤ k < K -1, and it has two actions α {k+1,2 j-1} and α {k+1,2 j} .

• Whenever the action α {k+1,2 j-1} is chosen, the LA A {k+1,2 j-1} is activated.

• Whenever the action α {k+1,2 j} is chosen, the LA A {k+1,2 j} is activated.

• We can informally say that A {k+1,2 j-1} and A {k+1,2 j} are the Left Child and Right Child of the parent LA A {k, j} respectively.

-The LA at depth K -1: The LA at depth K -1 (i.e., at the level just above the leaves) is responsible for choosing the action from the stochastic environment.

• This LA has two actions α {K,2 j-1} and α {K,2 j} .

• At this level, there are 2 K actions: α {K, j} where j ∈ {1, ..., 2 K } at depth K.

• Observe that α {K, j} is attached to (or associated with) its "parent LA"

A {K-1, j/2 } .

4. At level K: Finally, at depth K, i.e., at the maximal depth of the tree, the nodes do not have children.

The Proposed Solution

At the bottom-most level, i.e., the level of the leaves, we invoke a two-action CPA to determine which is the superior action between two actions that are siblings at this level. To do this, we merely maintain running estimates of the reward probabilities of these two actions, and using this two-dimensional estimate vector and the corresponding two-action probability vector, the updating is achieved. The larger of these estimates is trickled to their common parent, and this estimate is now compared with the corresponding reward probability estimate of its sibling whose value was obtained from its children. This process is now recursively repeated, using the estimate of the reward probability at this level and the probability vector at this level, whence the updates are performed. The same process continues up the tree to the root itself.

The Algorithm of the Proposed Solution

Notation and Definitions The notation that we shall use is as follows:

-The 2 K actions that interact with the Environment are elements from the set {α {K,1} , . . . , α {K,2 K } }. Further, the actions {α {K,2 j-1} , α {K,2 j} } are the two only actions that can be selected by the LA at level K -1, namely A {K-1, j} . -Each LA j ∈ {1, ..., 2 k } at depth k, called A {k, j} , where 0 ≤ k ≤ K -1 has two actions, namely, α {k+1,2 j-1} and α {k+1,2 j} .

-P {k, j} = [p {k+1,2 j-1} , p {k+1,2 j} ] T is the action probability vector of LA A {k, j} , where

0 ≤ k ≤ K -1.
Begin Algorithm HCPA Parameters: λ: The learning parameter, where 0 < λ < 1, where λ is close to zero. u {K,2 j-1} , u {K,2 j} : The number of times α {K,2 j-1} , α {K,2 j} have been rewarded when it has been selected. v {K,2 j-1} , v {K,2 j} : The number of times α {K,2 j-1} , α {K,2 j} , has actually been selected. d{K,2 j-1} , d{K,2 j} : The estimate of the reward probabilities of d {K,2 j-1} , d {K,2 j} , computed as:

d{K,2 j-1} = u {K,2 j-1} v {K,2 j-1} , d{K,2 j} = u {K,2 j} v {K,2 j} .
D is the vector of the estimates { d}. m: The index of the optimal action. h: The index of the greatest element of D. R: The response from the Environment, where R = 0 corresponds to a Reward, and R = 1 to a Penalty. T : A Threshold, where T ≥ 1ε. Initialization: Traditional Pursuit algorithms require that we choose each action a few times to initialize the estimates of the reward probabilities. This step is really not so crucial and so we have avoided it and assumed that the estimate of the reward probabilities are initialized to 0.5.

Initialization: t = 0 For i= 1 to 2 K Do: u {K,i} (0) = 1 v {K,i} (0) = 2 d{K,i} (0) = u {K,i} (0) v {K,i} (0)
EndFor Loop

1. 0 ≤ k < K -1: Levels 0 to K -1 -LA A {0,1}
selects an action by randomly sampling as per the action probability vector

[p {1,1} (t), p {1,2} (t)
]. -Let j 1 (t) be the index of the chosen action where j 1 (t) ∈ {1, 2}.

-The next LA is activated A {1, j 1 (t)} which in turn chooses an action and activates the next LA at level '2'.

-The procedure continues recursively until LA at level K -1.

-Let A {k, j k (t)} be the set of activated LA, where j k denotes the activated LA at level k.

2. k = K: Level K -Update D{K, j K (t)} based on the response from the Environment at the leaf level, K:

u {K, j K (t)} (t) = u {K, j K (t)} (t -1) + (1 -R(t)) v {K, j K (t)} (t) = v {K, j K (t)} (t -1) + 1 d{K, j K (t)} (t) = u {K, j K (t)} (t)
v {K, j K (t)} (t) . -For all other "leaf actions", where j ∈ {1, ..., 2 k } and j = j K (t),

u {K, j} (t) = u {K, j} (t -1) v {K, j} (t) = v {K, j} (t -1) d{K, j} (t) = u {K, j} (t)
v {K, j} (t) . 3. Define the reward estimate for all other actions along the path from the root, 0 < k < K -1 in a recursive manner 5 , where the LA at any one level inherits the feedback from the LA at the next level: d{k, j} (t) = max( d{k+1,2 j-1} (t), d{k+1,2 j} (t)).

Perform the probability updating for the corresponding vectors as follows:

-By definition, each LA j ∈ {1, ..., 2 k } at depth k, referred to as A {k, j} , where 0 ≤ k ≤ K -1, has two actions α {k+1,2 j-1} and α {k+1,2 j} . Let j h (t) ∈ {2 j -1, 2 j} be the larger of the elements between d{k+1,2 j-1} (t) and d{k+1,2 j} (t).

-Let j h (t) = {2 j -1, 2 j} \ j h (t) be the opposite action, i.e., the one that has the lower reward estimate. -Update p {k, j h (t)} and p {k, j h (t)} using the estimates d{k+1,2 j-1} (t) and d{k+1,2 j} (t) as:

If R(t) = 0 Then p {k, j h (t)} (t + 1) = (1λ)p {k, j h (t)} p {k, j h (t)} (t + 1) = 1p {k, j h (t)} (t + 1). Else p {k, j h (t)} (t + 1) = p {k, j h (t)} (t) p {k, j h (t)} (t + 1) = p {k, j h (t)} (t). EndIf -For each A {k, j} , if either of its action probabilities p {k+1,2 j-1} and p {k+1,2 j} surpasses a threshold T , where T is a positive number that is close to unity, the action probabilities for this LA will stop updating, with its larger action probability jumping to unity.

t = t + 1

EndLoop End Algorithm HCPA

The HCPA scheme proposed and described above has been shown to be ε-optimal in all random environments. The proofs are quite deep and intricate. However, due to the space limitations, these theoretical results are omitted here. They are included in [START_REF] Yazidi | The Hierarchical Continuous Pursuit Learning Automation: A Novel Scheme for Environments with Large Numbers of Actions[END_REF]. 5 More specifically, the LA at level K -2, inherit the feedback from the LA at level K -1 as: d{K-2, j} (t) = max( d{K-1,2 j-1} (t), d{K-1,2 j} (t)) and so on. As a consequence, notice that at every level, the reward vector estimates of the actions of every LA, are composed of the respective maxima of the rewards of all the actions of the entire subtrees rooted at their children.

Experimental Results

To evaluate the performance of the LA-based schemes, we carried out extensive simulations for environments with a "large" number of actions, where the total number of actions was set to various values. The main aspect that we intended to demonstrate was that if the learning problem was tackled using traditional VSSA, the convergence would be both less accurate and very slow. The reason for this, as mentioned earlier, is that if the number of actions is large, many of the action probabilities would be small, implying that these would be chosen seldom. Thus, even if we invoked estimator-based LA, it would be unreasonable to assume that each action would be chosen "a large number of times". Further, the estimates would be correspondingly inaccurate. The HCPA resolves both of these issues.

The simulations that we conducted were intended to capture two important metrics, namely, the accuracy of the convergence of HCPA, and its speed of the convergence. Our goal was also to compare its convergence with the existing LA.

The Data Sets for the Environment

The benchmark datasets reported in the existing literature had at most ten actions. In the absence of established benchmarks for larger numbers of actions, we have designed a set of Environments which can be used as benchmarks by other researchers. First of all, we determined the number of actions involved in the learning problem. To render the problem non-trivial, the total numbers of actions was initially configured to be 16, 32 and 64. Once the number of actions was set, the actual reward probabilities associated with the different actions were uniformly distributed in the interval between zero and unity. Understandably, the difficulty the Environment increased with the the number of actions. The reward probabilities associated with the configurations for 16 and 32 actions are the first 16 and 32 elements in Table 1, respectively. The reward probabilities of the configuration with 64 actions constitute the entire set given in Table 1.

Convergence of the HCPA Algorithm

If λ is sufficiently small, the HCPA will converge to the action with the maximum reward probability. To observe the convergence of the algorithm with a minimum number of iterations, our task was to determine the optimal value for λ for different configurations. The optimal λ value is the maximum λ value that will make the LA to consistently converge to the correct action. Obviously, for different configurations for the Environment, the value for optimal λ would vary. In this simulation, to find the optimal λ, we decreased the value of λ until we reached the one that provided the LA for the first 200 consecutive occurrences of convergence to the correct action.

Based on our simulations, for the configuration with 64 actions, the optimal λ was 0.000051. In other words, with this value of λ ≤ 0.000051 system would consistently converge accurately. Similarly, the optimal values for λ for the configurations for 32 and 16 actions were 0.00085 and 0.0065 respectively. Understandably, the values of λ have an increasing trend when the environment becomes less challenging.

Average Convergence Iterations

To illustrate the average number of iterations before convergence, we present the simulation results of the experiments6 in Tables 2. The standard deviation of the iterations are also included. To compare the HCPA with existing approaches, we include the simulation results for the L R-I and CPA machines in the same environment. The λ values utilized in the HCPA are the ones shown in Section 3.2 while the ones in the CPA are the optimal values found based on the same approach explained in Section 3.2.

For each replication in HCPA, we register the number of iterations when all the LAs along the correct path had converged to the action probabilities which are greater than or equal to 0.99. Similarly, for each trial for the CPA and the L R-I , we record the number of iterations when the LA had converged to the correct action with an action probability greater than or equal to 0.99. All the results presented in the table have been averaged over an ensemble of 400 independent replications using the optimal λ determined above. From Table 2, we can clearly see that HCPA outperforms CPA and L R-I in general, especially when the number of actions is large. Thus, for example, for the 64-action environment, the L R-I required 644,234 iterations. The HCPA required less than 18% of the number of iterations, namely 115,295. These results are typical. This confirms the efficiency of the hierarchical structure when the number of actions increases.

Environment with 128 actions

The HCPA was also tested on environment with 128 actions, and as mentioned earlier, the testing of LA in environments with such a large number of actions is pioneering -it has been unreported in the literature. Rather than list the reward probabilities, we have plotted them in Figures Fig. 1: An example of an 128-action Environment.

In the case of the first environment plotted in Figure 1, the L R-I required 734,474 steps for absolute convergence for an ensemble of 400 trials. The CPA, on the other hand, required 543,529 steps -which represented a decrease of about 26%. Astonishingly, the HCPA needed only 266,257 steps. This implied an advantage of about 51% over the CPA and of almost 64% over the L R-I . One can clearly see the advantage of the HCPA over the state-of-the-art.

Conclusions

In this paper, we have pioneered a new paradigm for designing and implementing Learning Automata (LA) when the number of actions is large. Learning in environments of this type is particularly hard because the dimensionality of the action probability vector is correspondingly large, and consequently, most components of the vector will, after a relatively short time, have values that are smaller than the machine accuracy, implying that they will never be chosen. This means that the traditional LA will be sluggish and inaccurate, and it would be unreasonable to assume that each action would be chosen "a large number of times" if we invoked estimator-based LA. In this paper, we have pioneered a solution that extends the Continuous Pursuit Algorithm's (CPA's) paradigm to such large-actioned problem domains. The salient feature of our new solution is that it is hierarchical, where all the actions offered by the environment reside as leaves of the hierarchy. Further, at every level, we merely require a two-action LA which automatically resolves the problem of dealing with arbitrarily small action probabilities. Most importantly, since all the LA invoke the pursuit paradigm, the best action at every level trickles up towards the root. Thus, by invoking the property of the "max" operator, in which, the maximum of numerous maxima is the overall maximum, the hierarchy of LA converges to the optimal action. The paper also reported experimental results that demonstrated the power of the scheme and its computational advantages.

Table 1 :

 1 This table lists the reward probability of the 64 actions in our experiments. The reward probabilities for 16 and 32 actions are the corresponding 16 and 32 entries in the table, respectively.

	A 1	A 2	A 3	A 4	A 5	A 6	A 7	A 8	A 9	A 10	A 11	A 12
	0.3934 0.9902 0.4883 0.5768 0.2023 0.2390 0.5887 0.8894 0.0333 0.4323 0.6926 0.3474
	A 13	A 14	A 15	A 16	A 17	A 18	A 19	A 20	A 21	A 22	A 23	A 24
	0.6152 0.0900 0.0850 0.5652 0.7362 0.7603 0.5142 0.2273 0.6080 0.4791 0.9339 0.3808
	A 25	A 26	A 27	A 28	A 29	A 30	A 31	A 32	A 33	A 34	A 35	A 36
	0.02152 0.2399 0.7509 0.8773 0.4962 0.5649 0.9202 0.1335 0.6214 0.9777 0.4232 0.02773
	A 37	A 38	A 39	A 40	A 41	A 42	A 43	A 44	A 45	A 46	A 47	A 48
	0.1255 0.5650 0.1660 0.0148 0.0970 0.1319 0.1738 0.8901 0.3511 0.8945 0.6133 0.4813
	A 49	A 50	A 51	A 52	A 53	A 54	A 55	A 56	A 57	A 58	A 59	A 60
	0.2413 0.1714 0.8512 0.9791 0.7443 0.3469 0.8707 0.3863 0.4763 0.4446 0.9617 0.0329
	A 61	A 62	A 63	A 64
	0.5004 0.3784 0.6553 0.9737

Table 2 :

 2 The simulation results obtained for various environments with different numbers of actions.

	Number of Actions	16	32		64
	Parameters	Mean SD	Mean	SD	Mean	SD
	HCPA	904.5 103.6 6,812.3 614.6 115,295.5 11,346.2
	CPA	1,584.2 62.3 7,260.0 529.1 156,616.3 6,985.0
	L R-I	3,920.8 1,629.2 28,618.2 7,911.3 644,234.0 20,0625.4

  1.

	0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1

In the interest of brevity, we assume that the reader is fairly well-versed in the fundamental concepts of LA and their convergence properties. The review here is thus necessarily brief, although the intent is that it should also be comprehensive. However, excellent surveys of the field can be found in[START_REF] Obaidat | Learning automata: Theory, paradigms, and applications[END_REF][START_REF] Poznyak | Learning Automata and Stochastic Optimization[END_REF][START_REF] Thathacha | Networks of Learning Automata: Techniques for Online Stochastic Optimization[END_REF]. Also, due to the space limitations, the theoretical results about our new scheme are omitted here. They are included in[START_REF] Yazidi | The Hierarchical Continuous Pursuit Learning Automation: A Novel Scheme for Environments with Large Numbers of Actions[END_REF].

The tree is assumed to be binary only for the sake of convenience. In a more general setting, each node may have, for example, three children.

The author of[START_REF] Papadimitriou | Hierarchical discretized pursuit nonlinear learning automata with rapid convergence and high accuracy[END_REF] tested his scheme for a maximum of 64 actions. It was not possible to do a fair comparison between our scheme and the work done in[START_REF] Papadimitriou | Hierarchical discretized pursuit nonlinear learning automata with rapid convergence and high accuracy[END_REF]. This is because the author of[START_REF] Papadimitriou | Hierarchical discretized pursuit nonlinear learning automata with rapid convergence and high accuracy[END_REF] did not report the size of the ensemble of experiments that he conducted. In our case, the ensemble was of size

400, and we sought for the best parameter that yielded "absolute" convergence -i.e., convergence in every single experiment. However, the author of[START_REF] Papadimitriou | Hierarchical discretized pursuit nonlinear learning automata with rapid convergence and high accuracy[END_REF] should be given fair credit because of his result being the first reported hierarchical Pursuit-based LA strategy!

If the number of actions is less than 2 K , one can always add dummy actions whose reward probabilities are zero.

The experiments have been done for various randomly-generated environments. In the interest of brevity, we merely report the results from one such setting. This was representative of the results obtained for other settings.

The work of this author was partially supported by NSERC, the Natural Sciences and Engineering Council of Canada.


Eoin Rogers
email: eoin.rogers@student.dit.ie

Robert J Ross
email: robert.ross@dit.iejohn.d.kelleher@dit.ie

John D Kelleher

Evaluating sequence discovery systems in an abstraction-aware manner

Activity discovery is a challenging machine learning problem where we seek to uncover new or altered behavioural patterns in sensor data. In this paper we motivate and introduce a novel approach to evaluating activity discovery systems. Pre-annotated ground truths, often used to evaluate the performance of such systems on existing datasets, may exist at different levels of abstraction to the output of the output produced by the system. We propose a method for detecting and dealing with this situation, allowing for useful ground truth comparisons. This work has applications for activity discovery, and also for related fields. For example, it could be used to evaluate systems intended for anomaly detection, intrusion detection, automated music transcription and potentially other applications.

Introduction

Activity discovery (AD) refers to the unsupervised discovery of plausible human activities in unannotated datasets composed of sensor readings of human subjects. AD is itself a sub-field of activity recognition, the recognition of activities from sensor readings in a supervised manner. These technologies have potential applications in the automatic labelling of activity recognition datasets and building profiles of normal and abnormal behaviour.

Evaluating activity discovery systems in a fair manner is a major challenge for the field. A major reason for this is that pre-annotated ground truths, often used to evaluate the performance of such systems on existing datasets, may exist at different levels of abstraction to the output of the output produced by the system. We propose a method for detecting and dealing with this situation, allowing for useful ground truth comparisons.

Activity discovery is equivalent to a number of challenging problems that are known in the wider computing literature. One good example would be anomaly detection algorithms used for such applications as intrusion detection in the field of computer security. Security practitioners have already made use of machine learning algorithms for this task [START_REF] Buczak | A survey of data mining and machine learning methods for cyber security intrusion detection[END_REF], and our work could help evaluate such systems fairly.

The layout of this paper is as follows. Section 2 investigates prior work in this area. Section 3 discusses in detail the general problem with ground truth-based methods being applied to this problem. We introduce the concept of activity abstraction in more detail in section 4, before utilising it to produce an activity discovery evaluation metric presented in section 5. We detail experiments carried out to evaluate the metric in section 6, and present the results of these before concluding in section 7.

Prior work

A number of existing approaches to evaluating activity discovery systems have already been proposed in the literature. Cook & Krishnan [START_REF] Cook | Activity learning: discovering, recognizing, and predicting human behavior from sensor data[END_REF] provide a good overview of existing approaches, and we refer the interested reader to this reference, rather than repeat its contents in detail here.

Our notation for this section will be relatively standard: we assume the input dataset D = d 1 , d 2 , . . . , d L is an ordered sequence of sensor events drawn from an alphabet Σ. An activity discovery system is modelled as a mathematical function g, which takes the dataset (or a subset of the dataset) as input and returns a set of activities Y = g(D). There are a number of forms that Y could take, and in order to keep our discussion as general as possible, we refrain from privileging one over the other. In the simplest case, each element of Y may only be a non-contiguous subset of the events in D. Alternatively, each element of Y may in fact be an ordered non-contiguous sequence of events, or even a grammaror state machine-like object that could allow for the learning of complex activities with optional and mandatory elements, complex rules relating to the allowed ordering of elements within activities, or even probabilistic activity rules.

Stability-based metrics

When we evaluate any machine learning system, we are usually interested in determining the degree to which the learned model is generalised (that is, the degree to which it can be applied to similar but unseen data). Many authors propose the use of similar criteria for the evaluation of activity discovery systems. These take the form of measures of stability, where the dataset D is split into training and test subsets, B and C respectively, such that D = B ∩ C, and the system is evaluated by demonstrating that some property of the system is stable across both subsets. For example, the Cook & Krishnan book [START_REF] Cook | Activity learning: discovering, recognizing, and predicting human behavior from sensor data[END_REF] mentioned previously outlines two stability-based metrics: predictive and compressive stability. Predictive stability measures that the activities seen in the training set are also observed in the test set with about the same frequency. By contrast, compressive stability measures the degree to which the compression ratio achieved on the training and test set is roughly equivalent. The idea of evaluating activity discovery (and related) systems via the use of compression ratios is an idea that shows great promise, and has already seen use in the wider ML community in the form of perplexity [START_REF] Jelinek | Perplexitya measure of the difficulty of speech recognition tasks[END_REF]. A related concept, although one we will skip over here due to space constraints, is minimum description length [START_REF] Rissanen | Modeling by shortest data description[END_REF].

Ward et al.'s error analysis technique

Moving away from Cook & Krishnan's proposals, we feel that the contents of [START_REF] Ward | Evaluating performance in continuous context recognition using event-driven error characterisation[END_REF] could be relevant to the task of evaluating activity discovery systems. This paper does not propose an evaluation metric, but rather an error analysis method, in other words a means to detect the types of errors a system under analysis seems to make consistently. The core mechanism proposed in the paper is presented in Figure 1, which is a figure taken from the paper itself. The three sub-figures correspond to three stages in the method itself. Here, the ground truth is depicted as pale dotted lines, and the prediction output as darker bold lines.

Fig. 1. An illustration, taken from [START_REF] Ward | Evaluating performance in continuous context recognition using event-driven error characterisation[END_REF], of the three stages involved in the proposed error analysis method. The first stage evaluates segments according to whether they match with an activity in the ground truth, irrespective of how accurately they may do this. The second evaluates segments according to the precision of the start and end of activities, and the fourth combines these into a finished per-segment evaluation.

The first stage (which the authors of the paper call event scoring) looks at each event/ground truth pair, and counts the amount of event insertions, deletions, merges and fragmentations that are observed. The second stage, time scoring, computes the temporal correspondence between the system output and the ground truth by counting overfills and underfills. Finally, the output from the two previous steps are combined to create the final output, which is called the segment scoring, and can be seen at the bottom of Figure 1. Although simple, this error analysis technique is a major inspiration behind the metric that will be proposed later in this paper.

Ground truth-based metrics

While reading section 2, one thing that may strike some readers as unusual is the fact that most of the metrics proposed (Ward's is an exception) seem to refrain from using ground truths as a gold standard with which to compare the output of the activity discovery system under evaluation. Although a perfectly valid way of evaluating machine learning models in the general case, there are two major reasons why one might be suspicious of ground truth comparisons for activity discovery. The first of these is that, by definition, and activity discovery system must be unsupervised, that is it trains without making use of any sort of output data in the dataset. The entire point of the discovery of activities is to provide a way for the detection of plausible activities in unannotated datasets without any ground truth. In a real-world use case, it is quite possible that the model will therefore be trained on a dataset for which no ground truth to compare against exists, and so we have to find a means of evaluation that can be used even in these kinds of situations.

The second issue with ground truth-based evaluation is the subjectivity inherent in the output of any activity discovery process. Although the behaviours reflected in the sensor stream may be objective and leave no room for subjective interpretation, the same cannot be said for the activities detected in the stream. For example, the point at which an activity can be said to start and end is arbitrary. Consider the hypothetical case of a sensor stream in a house where an activity corresponding to making dinner takes place every evening. One could say that this activity begins when the resident(s) of the house enter the kitchen to cook, or when they turn on the oven, or when they first put food into the oven. Different activity discovery systems (and indeed human annotators) may well use different boundaries for their activities in this manner, and one cannot privilege one annotation over the other. By extension, it is also possible for entire activities to be (in a sense) subjective. For instance, what if one argues that the resident entering the kitchen to cook does not constitute part of the making dinner activity, but rather an activity in its own right, perhaps called preparing to make dinner ? This issue provides major challenges for the evaluation of these systems. Note that we are speaking of a very particular kind of subjectivity. Intuitively, any system which fails to find a consistent activity every evening around dinner time in our hypothetical house seems to be objectively wrong in some way, since it cannot pick up a real pattern that exists in the data. But aspects of the pattern (its size, constitution, cardinality and so forth) are subjective in a way that makes comparison to a ground truth seem like an inherently unfair approach to evaluation.

Any proposed activity discovery evaluation metric must take these issues into consideration. Failure to do so could result in an unfair evaluation that biases in favour of certain systems and against others without justification. Nonetheless, if a ground truth is available, it would be sensible to make use of it, even if only in addition to, rather than instead of, the unsupervised evaluation metrics mentioned in section 2.

Instances, types and abstractions

Many of the subjective differences noted in section 3 can be attributed to differences in the level of abstraction that the various systems we are looking at are outputting. Say g and h are activity discovery models, Y g is the set of activities output by g (where each y ∈ Y g is a subset of D), and likewise Y h is the set of activities output by h (where each z ∈ Y h is a subset of D). Note that since we don't annotate these activities as instances or types we presume they could be either. We formally represent this scenario as:

g(D) = Y g (1) h(D) = Y h (2)
Suppose that for a particular y ∈ Y g and a particular z ∈ Y h , we find that y ⊂ z, in other words y is strictly a subset of z (i.e. ∀i(i ∈ y

⇒ i ∈ z), but ∃i(i ∈ z ∧ i / ∈ y)).
We say that z is thus a more abstract version of the activity y: everything in y is also in z, but the reverse is not true. To make this more concrete, we can imagine y being an activity like making dinner, and z being a more abstract version of the same activity like having dinner, which contains making dinner in its entirety, in addition to other sensor events covering the consumption of the dinner, and perhaps cleaning up after. Notationally, we represent this scenario as y ≺ z, which can be read as "y is less abstract than z", or "y precedes z".

To complicate matters further, we have to resist the temptations we may have at this point to claim that activity discovery model g is less abstract than h, simply because it output a less abstract activity in one instance. It is entirely possible that multiple levels of abstraction are interleaved in the output of our models, i.e. it may be possible to find activities for which g finds a more abstract version than h. Unless all activities found by g are less abstract than or equal to all activities found by h, we should refrain from talking about the abstraction of entire models. We will later use this concept in Section [?] as a component in our metric.

A proposal for a new metric

By combining the insights from section 4 with the error analysis from [START_REF] Ward | Evaluating performance in continuous context recognition using event-driven error characterisation[END_REF] (see section 2.2), we believe that we can propose an evaluation metric for activity discovery systems using ground truths that (at least to some extent) bypasses the second issue discussed in section 3. The idea is to use abstraction to get around the issue of subjectivity. Suppose our dataset D has an associated ground truth G, and our discovered activities Y contain an activity called making dinner, but the ground truth only recognises an activity called having dinner. The intuition is that if making dinner ≺ having dinner, we can mark each instance of making dinner as correct if it overlaps with an instance of having dinner in the ground truth. This is similar to Ward et al.'s proposal of marking merges, fragmentations, overfills and underfills, but rather than treating these as a sort of error, we instead allow them to be seen as correct once the types of the activities match.

We will formalise this intuition by first proposing a simple means for evaluating an activity discovery system, which will have the flaws described in Section 3. We will then modify the definition to match our proposal. Recall that D is a dataset, and G is the associated ground truth. We assume |G|= |D|, and that each element g ∈ G is a sequence of k Boolean values, where k is the number of activities in the ground truth. Thus, G ij is true iff activity j is true or active for the ith event in the dataset. We will also commit to a specific structure for the output Y , since not doing so would make our formalism needlessly abstract. We feel that the formalism can be easily adapted for other output structures and formats, although we will not attempt to prove this here. We model Y as a matrix, such that each value Y ij represents the probability that activity j is true or active for the ith event. This maps closely to the probabilistic output of the topic modelling based system we will be using for our experiments, yet to be discussed in Section 6 below. Given a particular ground activity g, an index into the output activities y, and a real-valued threshold value t, we can define the true positives of our AD system to be:

T P gyt (G, Y ) = L i=1 1(g ∈ G i ∧ Y iy ≥ t y ) ( 3
)
Where 1 is an indicator function that evaluates to 1 if the Boolean formula passed to it is true, and 0 if it is false. The threshold t is a meta-parameter, and we compute a different value of t y for each proposed activity in Y . It will hopefully be clear to the reader how this could be extended to compute false positives and true and false negatives also. From here, we can obviously calculate F-measures for the system.

A diagrammatic example of our proposal is shown in Fig. 5. Here, each of the horizontal lines labelled A to E represent a single channel of information. Channel A is a ground truth, as found in an annotated dataset. Channel B represents the raw output of an activity discovery system for a particular event type. The output overlaps to a degree with the ground truth. We are proposing extending the length of channel B to match channel A, as shown in channel C (which is the extended output). We can formalise this by modifying Equation 3 as follows:

T P gyt (G, Y ) = L i=1 1((g ∈ G i ∨ g ∈ G i-1 ∨ g ∈ G i+1 ) ∧(Y iy ≥ t ∨ Y (i+1)y ≥ t y ∨ Y (i-1)y ≥ t y )) (4)
Now, rather than strictly requiring that the probability of activity y during event i at least meet our threshold, we look to the events immediately before and after the current (ith) event, and we will also accept event i as a valid true positive if one of its neighbours are also a true positive. The ground truth is similarly extended in the same manner. We actually repeat this computation as many times as needed for the true positive value to stop increasing. Thus, we are willing to extend the length of both the ground truth (channel A in our diagram) and the output until their respective lengths match. Some people may object to the presented proposal on the basis that it is making the evaluation too easy for the activity recognition system. For this reason, channels D and E can be used as alternatives to C for comparison to the ground truth (channel A). In these cases, the darkness of the colour corresponds to its magnitude, with the number 1 being as dark as channels B and C, and lower numbers (closer to zero) being represented with a lighter number. Most evaluation metrics (raw similarity, F-measures and so on) work by counting the number of matches between two binary channels. For example, F-measures build a confusion matrix, and match a False from both the ground truth and output channels as a true negative, a False from the ground truth and True from the output as a false positive and so on. We are proposing to use non-binary, fuzzy values instead of these binary comparisons, so that we would increment the counts for the confusion matrix by a number between zero and one. For channel D (the staircase output), we use a value of 1 for the true overlaps, and a smaller value (0.4, or 2 5 in our experiments, see below) for the extensions. Formally, this becomes:

T P gyt (G, Y ) = L i=1 1(g ∈ G i ∧ Y iy ≥ t)+ 2 5 (G i-1 ∨ g ∈ G i+1 ∨ Y (i+1)y ≥ t ∨ Y (i-1)y ≥ t) (5)
Here, we now have 2 indicator functions: the 1 function from previously, and a new 2 5 function, which returns a value of 2 5 if its input is true, and false otherwise.

Finally, in channel E (the gradient output), the extensions don't have a fixed value, but rather have a value of 1 -(0.001 × n), where n is the number of events away from the true overlaps, but cannot have a value below zero. Again, we define an indicator function which is suitable for this purpose, but rather than calling it 1 -(.001 × n), we instead give it the more succinct (but less descriptive) name f.

T P gyt (G, Y ) = L i=1 f((g ∈ G i ∨ g ∈ G i-1 ∨ g ∈ G i+1 ) ∧(Y iy ≥ t ∨ Y (i+1)y ≥ t y ∨ Y (i-1)y ≥ t y )) (6)
Note that in Figure 5, we are only showing the extensions applied to the output channels. The ground truth channels should also be extended according to the above process.

At this point, the usual performance metrics used to evaluate ground truthbased systems can be employed. This could include raw percentage accuracy measures, or preferable a more sophisticated metric like F-measures.

Experiments and results

In order to try to determine if our proposed metric is useful, we used an activity discovery system that was presented previously by the same authors [START_REF] Rogers | Using topic modelling algorithms for hierarchical activity discovery[END_REF]. We refer the interested reader to the cited paper for a detailed explanation of how this system works, but in summary we split the dataset D up into L -w + 1 subsets using a sliding window of length w and run each window through a topic modelling algorithm as if it was a single document. This allows us to compute a probability distribution over topics for all events in the dataset. We threshold these values to assign each event to zero or more activities, using the t y threshold previously mentioned in Section 5. In effect, this threshold is the prior over activities. For each ground truth activity g and output activity y, we compute the candidate threshold value t gy that comes closest to making c gy = P (g ∈ G i ) -P (Y iy ≥ t gy ) (the difference between the ground truth and output activity probabilities) equal to zero. The final threshold t y is then simply the threshold that has the minimal c gy value over all gs, i.e. t y = argmin tgy c gy . This thresholding gives us a dataset of 10 channels, consisting of 5 ground truths and 5 discovered topics (outputs). We then compute the F1 score for each (ground truth, topic) pair for each of the 4 types of evaluation shown in Fig. 5. Each ground truth is then associated with the single topic that scores highest with it according to the extended F1 score.

We present here the result of the experiment described above on two different datasets. The first of these datasets was generated by the author using a state machine probabilistically moving from state to state and emitting events, with some events being more common than others for each state. The results of this experiment are shown in in Table 6 below. The first two columns show the (ground truth, topic) pairs, and the remaining columns show the raw F1 score (i.e. the score calculated without using our method), the extended F1, the staircase F1 and the gradient F1 respectively. The results show an interesting pattern: for each row, the raw F1 score is substantially lower than the equivalent scores computed with our proposed method. Bearing in mind that the only difference between these metrics are that the latter three take the concept of abstraction into account in the manner described above, we take this as evidence that our metrics are a fairer way to evaluate such systems. The raw F1 score is unfairly penalising the system for what could actually be valid disagreements over abstraction levels and the start and end times of activities, while our method does not do so. In order to evaluate the metric on a more challenging dataset, we repeated the experiment on the SCARE corpus [START_REF] Stoia | SCARE: A Situated Corpus with Annotated Referring Expressions[END_REF]. SCARE is an annotated corpus of human actions in a 3D game-like environment. This dataset has already been converted to the necessary binary-event-based format that our system expects [START_REF] Ross | A comparative study of the effect of sensor noise on activity recognition models[END_REF], so we used this version of the dataset. The results of this experiment are presented in Table 6. Again, one can see a substantial improvement in performance when our metric is employed. Note that the SCARE corpus is extremely challenging: it is unusual for activity recognition systems to obtain a score greater than about 0.6, let alone activity discovery systems, which must produce their output without access to the ground truth. This metric could not only give a fairer means to evaluate activity discovery systems, but potentially a fairer means to evaluate corpora used also, by highlighting excessively narrowly defined activities in a corpus's ground truth. Before moving on to the conclusion, we also present Figure 3. This consists of a selection of visualisations of the output of our system (shown as red bars in the upper half of the images) compared to the associated ground truth (shown as blue bars in the lower half of the images) running on the SCARE corpus. The complete images are of course extremely wide, and cannot therefore be reproduced in full here. However, the extracts show real-world examples of the issues that we were highlighting in this paper. Figure 3(a) shows a typical example of a length mismatch between the output and ground truth events. Here, the output is more conservative than the ground truth, and assumes that the activity both starts later and ends sooner. As noted in Section 3, a human directly annotating this dataset could have a legitimate disagreement with the annotator of the ground truth, which would lead to the system being given an unreasonably poor score. Figure 3(b) shows an example of the output activity starting later, but ending later also. Again, most metrics would penalise a system which did this, which is unfair, since the sensor event that allowed the system to recognise that the activity has started may occur after the ground truth annotation declares the onset of the activity. One interesting aspect of this is that one could argue that the quality of the output should depend on how far to the left the ground truth continues for. If the ground truth activity is very long, but was only picked up for a short while, that could indicate that the output activity was a spurious co-incidence, rather than the system finding the activity at all. This presents a case to use the staircase or gradient based versions of the metric that we have discussed. Another interesting scenario is shown in Figure 3(c). Here the ground truth shows a strange pattern: an activity comes to an end, there is a short pause, and then it resumes. This presents some questions about the annotation of the dataset: would it be fair to just bridge the gap, and say that there was simply one long instance of the activity rather than two short instances? If the output from the system was to bridge the gap, would it be fair to give it a poorer or better score for doing that? Ones view on these issues could lead one to therefore argue against using the staircase or gradient variants of the metric. Again, it pays to be aware that there is in fact a degree of subjectivity on this evaluation problem, and assuming something is set in stone can lead to unreasonable conclusions.

Conclusion

This paper has presented an argument as to why current means of evaluating the performance of existing activity discovery systems by comparison of outputs to ground truth may be construed as unfair and misleading, due to valid disagreements in abstraction level. We have proposed an extension to existing methods that we feel remedies this issue. Our experiments show that an existing activity discovery system gets a better result from our metrics. Since our metric only aims to resolve the abstraction issue, we feel that there is an argument to be made that our metrics are a fairer way to evaluate activity discovery systems, and thus help progress the state-of-the-art in the field. We are not, however, claiming that our metric is a one-size-fits-all panacea to the activity discovery evaluation problem: rather, it would be better served by using it in conjunction with other metrics (for instance, the stability-based metrics detailed in Section 2.1. We advocate the use of a suite a disparate metrics to illuminate the strengths and weaknesses of activity discovery systems.

Fig. 2 .

 2 Fig. 2. If channel A is an output, and channel B is the output from a system under evaluation, we propose extending B to match A (extended output, channel C), optionally making the extensions values less than 1. In channel D (staircase output) we use a small value for the extensions, and we use a reducing gradient for channel E (gradient output).

Fig. 3 .

 3 Fig.3. A sample of a side-by-side comparison of an output and the ground truth. This illustrates some of the issues that we have discussed in this paper.

Table 1 .

 1 Performance metrics gathered by our experiment on an artificial dataset

	Topic	Label	F1 Extended F1 Staircase F1 Gradient F1
	Activity A Topic 2 0.6385	0.9521	0.9865	0.9896
	Activity B Topic 3 0.2269	0.9211	0.9834	0.9853
	Activity C Topic 1 0.3159	0.876	0.9619	0.977
	Activity D Topic 4 0.1146	0.8426	0.8923	0.8994
	Activity E Topic 0 0.01835	0.1428	0.8053	0.8192

Table 2 .

 2 Performance metrics gathered by our experiment on an artificial dataset

	Topic	Label	F1 Extended F1 Staircase F1 Gradient F1
	goal˙move˙box	Topic 1 0.1349	0.6441	0.6831	0.8309
	goal˙move˙rebreather Topic 5 0.3057	0.9484	0.9575	0.9589
	goal˙move˙quad	Topic 2 0.1111	0.623	0.5625	0.5472
	goal˙move˙silencer Topic 4 0.05674	0.5812	0.8176	0.8444
	goal˙move˙picture Topic 3 0.07292	0.5128	0.6491	0.6379
	null˙goal	Topic 0 0.0	0.0	0.0	0.0


Yigit Mehmet

Mert Yildirim
email: yigityildirim@asu.edu

Hasan Ozer
email: mozer@asu.edu

Davulcu
email: hdavulcu@asu.edu

Cost-Sensitive Decision Making for Online Fraud Management

Keywords: fraud detection, cost-sensitive learning, risk management, e-commerce

Every online transaction comes with a risk and it is the merchant's liability to detect and stop fraudulent transactions. Merchants utilize various mechanisms to prevent and manage fraud such as automated fraud detection systems and manual transaction reviews by expert fraud analysts. Many proposed solutions mostly focus on fraud detection accuracy and ignore financial considerations. Also, highly effective manual review process is overlooked. We propose Profit Optimizing Neural Risk Manager (PONRM), a decision maker that (a) constitutes optimal collaboration between machine learning models and human expertise under industrial constraints, (b) is cost and profit sensitive. We suggest directions on how to characterize fraudulent behavior and assess the risk of a transaction. We show that our framework outperforms cost-sensitive and cost-insensitive baselines on three real-world merchant datasets.

Introduction

In 2016, card fraud cost businesses over $20 billion and it is still continuing to grow dramatically [START_REF]Card Fraud Losses Reaches $21.84 Billion[END_REF]. Around 60% of this loss was caused by online transactions, as e-commerce fraud rates have doubled since last year. E-commerce fraud magnitude is estimated to reach $71 billion during the next five years due to the steady rise in cost per fraudulent transaction while fraud rates continue to increase [START_REF] Juniper | Online Payment Fraud: Emerging Threats, Key Vertical Strategies & Market Forecasts[END_REF].

During fraud management, merchants are generally liable for paying for the fraud costs in the e-commerce ecosystem. They suffer the losses arising from shipped merchandise, shipping and handling costs alongside chargeback fees issued by the card processor [START_REF] Montague | Essentials of Online Payment Security and Fraud Prevention[END_REF]. Lexis Nexis reports that for every dollar of loss, merchants end up losing $2.40 on average as fraud management costs [START_REF] Ks&r | 2016 LexisNexis True Cost of Fraud Study[END_REF]. When aggregated, they lose around 1.5 percent of their total revenue to fraud today -three times increase during the last 3 years. So, they implement various strategies to fight fraud from automated fraud prevention systems to manual order reviews by expert fraud analysts [6].

One may think that manual reviews will be going away with advances in artificial intelligence; however, they remain very much relevant to the industry thanks to their accuracy. According to CyberSource, manual review is an established mechanism for fraud prevention with adoption by 79% of North American businesses [7]. Despite all efforts to fight fraud, significant improvements can still be made by investigating and answering the following questions: What are the most important characteristics of a fraudulent transaction that a merchant can capture without causing friction? As state-of-the-art machine learning algorithms are not perfect how should a merchant use them? What is the cost optimal role of expert manual reviews in this process?

Improving fraud prevention is not as straightforward as increasing fraud detection accuracy due to several factors: firstly, rejecting a legitimate order and approving a fraudulent transaction do not incur the same cost, secondly, transaction amount varies greatly by order, thus affecting profitability of a sale. Hence, merchants need to implement cost and profit sensitive fraud prevention strategies.

In this work, we introduce Profit Optimizing Neural Risk Manager (PONRM), a cost-sensitive decision maker for e-commerce fraud management. Our framework infers the risk of a transaction being fraud and combines it with the transaction amount to make an optimal decision regarding its fraud management strategy (i.e. automated accept, reject or manual review). The main contributions of our work are: ─ A cost-sensitive decision making framework to manage fraud while maximizing profits and minimizing costs; ─ A transaction risk model incorporating fraud characteristics and financial constraints relevant to a merchant; ─ An optimal collaboration strategy between human experts and machine learning models for fraud management

Related Work

Fraud detection has been an active area for data mining researchers since 1994 [START_REF] Ghosh | Credit Card Fraud Detection with a Neural-Network[END_REF]; however, it has not been extensively studied due to private and confidential nature of financial data. Despite these limitations, researchers managed to conduct studies with industry partners on proprietary datasets. Major studies focusing on credit card fraud include: [START_REF] Bolton | Statistical Fraud Detection: A Review[END_REF], [START_REF] Maes | Credit Card Fraud Detection Using Bayesian and Neural Networks[END_REF], and [21. In related areas, product review fraud detection work [START_REF] Hooi | Fraudar: Bounding Graph Fraud in the Face of Camouflage[END_REF] have also received attention. Theoretical contributions focusing on fraud detection applications such as [START_REF] Zhang | HiDDen: Hierarchical Dense Subgraph Detection with Application to Financial Fraud Detection[END_REF] and [START_REF] Zhou | A Local Algorithm for Structure-Preserving Graph Cut[END_REF] are also made. Survey papers on fraud detection methods include [START_REF] Phua | A Comprehensive Survey of Data Mining-Based Fraud Detection Research[END_REF] and [START_REF] Ngai | The Application of Data Mining Techniques in Financial Fraud Detection: A Classification Framework and an Academic Review of Literature[END_REF]. Although fraud loss is an enormous problem for e-commerce merchants, there is only a pair of studies [START_REF] Halvaiee | A Novel Model for Credit Card Fraud Detection Using Artificial Immune Systems[END_REF] and [START_REF] Carneiro | A Data Mining Based System for Credit-Card Fraud Detection in E-Tail[END_REF] investigating this problem from a merchant's perspective. However, these works aim to improve the accuracy of fraud detection alone, instead of developing a profit and loss aware fraud management strategy.

Fraud prevention teams must take various complications that arise from allowing or rejecting a transaction into account. Declining a legitimate transaction would often result in a loss of that customer's business whereas approving a fraudulent transaction would force the merchant to cover the fraud costs. Simply training a machine learning classifier by overlooking various costs leads to a less than optimal fraud management strategy. Researchers have been developing cost-sensitive learning frameworks including [START_REF] Domingos | Metacost: A General Method for Making Classifiers Cost-Sensitive[END_REF], [START_REF] Elkan | The Foundations of Cost-Sensitive Learning[END_REF], [START_REF] Zadrozny | Cost-Sensitive Learning by Cost-Proportionate Example Weighting[END_REF], [START_REF] Abe | An Iterative Method for Multi-Class Cost-Sensitive Learning[END_REF], and [START_REF] Ling | Cost-Sensitive Learning[END_REF].

In [START_REF] Carneiro | A Data Mining Based System for Credit-Card Fraud Detection in E-Tail[END_REF], the role of manual reviews in fraud prevention process is recognized; however, authors do not provide a systematic analysis on how to integrate machine learning based detection with manual reviews under cost and capacity constraints. In this paper, we develop a cost-sensitive fraud management framework incorporating all relevant capacities, costs and evaluate its financial impact with real-world merchant datasets.

Problem Definition

Every online transaction comes with a risk of being fraudulent. As merchants are responsible for detecting fraud, they must take this risk into account or they would suffer from losses due to fraud. So, when a merchant receives an order it can accept, reject or manually review that transaction based on their risk assessment of that transaction. Brief explanation of each decision is as follows: Accept: Accepting a transaction means that merchant approves the transaction and processes the payment. Accepting a legitimate transaction yields some profit. If the transaction turns out to be fraudulent, merchant becomes responsible for the dispute handling and losses. Reject: Rejecting a transaction means that merchant declines the transaction and payment does not go through. In this case, sale does not happen, so they will not be earning a profit even if the order was legitimate. However, rejecting a legitimate transaction may cause the loss of lifetime value of the customer. Review: In the case of sending the transaction to manual review, merchant halts the order and sends the transaction details to an expert fraud analyst for investigation. Fraud analyst would confirm the legitimacy of the order by manually analyzing the transaction details and by following-up with the consumer directly before approving or rejecting it. For the sake of our modeling, we assume that manual review always leads to correct decisions. However, expert fraud analysts are scarce and expensive resources and should be utilized wisely. We refer to these decisions made for a set of transactions as the fraud management strategy. We define the task of finding an optimal fraud management strategy as follows: Given a streaming set of transactions, determine the accept, reject, and review populations to maximize profits by accepting most of the legitimate transactions; and achieve this objective by minimizing customer insults, fraud losses, and costly manual reviews.

Methodology

Figure 1 presents an overview of our system. It consists of two learning and a pair of data manipulation components. The workflow starts with a data preprocessing and feature extraction task. 2nd component of the system carries out the task of inferring the probability of each transaction being fraudulent. 3rd component of the system generates cost-sensitive labels. 4th and final component of the system learns a function to maximize the profit based on a criteria incorporating the transaction amount and its fraud risk probability. We call this component as Profit Optimizing Neural Risk Manager (PONRM). Each following subsection explains one component of our system in detail and their order is aligned with the numbering in Figure 1.

Feature Extraction

Identifying consumer behavior to detect fraud is a delicate task. Businesses are hesitant to implement multi-factor authentication systems since it can be a source of friction and collecting invasive information such as cookie mining and device fingerprinting may damage the merchant's reputation. However, it may be possible to develop fraud prevention models without above options since merchants already have access to a rich source of information about their customers: the order form. Customers provide their personal and contact information to ensure the delivery of their order, so these can be leveraged by the fraud teams to build models. We present 4 types of patterns that merchants can reproduce: Location Based Patterns: We measure the distance between IP geolocation and physical addresses. We create risk profiles for zip codes based on historical fraud behaviors observed from corresponding districts. Phone Intelligence Patterns: Usage of VOIP, prepaid, spoofed, or invalid phone number is detected and may indicate malicious intent. Area code of a phone number is used to verify the (in-)consistency with the physical address. IP Intelligence Patterns: An IP address coming through a proxy or an anonymous network could indicate risky behavior. We also profile the risk based on historical fraudulent behavior observed from blocks of IPs.

Email Address Patterns: We create email domain related attributes such as existence, disposability, anonymity, tenure, and category. Informed by [START_REF] Zafarani | 10 Bits of Surprise: Detecting Malicious Users with Minimum Information[END_REF], we derive features directly from the email handle (i.e. different email address characteristics such as character diversity, typing efficiency, proportion of numbers, etc.) to determine if an email address has been created with malicious intent. By normalizing, profiling and combining these patterns, we come up with a set of 102 features that is used in our fraud classification model.

Fraud Classification Model & Risk Score Calculation

Risk score constitutes the input of the proposed model, PONRM. It is composed of a pair of elements: first element is the transaction amount ($) and second element is a probability score of the transaction being fraudulent given its features. We propose using any supervised learner (𝜃) providing a robust posterior probability for fraud probability estimation such as:

𝐟 & = 𝑃(𝐘 &* = 1|𝐗 & ; 𝜃) where 𝐟 = {𝐟 & ; 𝐟 & ∈ [0,1] ∧ 𝑖 = 1 … 𝑁}.
As given in Equation [eq:f], 𝐟 is assigned with the probability of a transaction being fraudulent. Finally, the risk score matrix 𝐑 is built by concatenating 𝐟 and the transaction amount ($) as; 𝐑 = [𝐟, $]

Cost-Sensitive Label Derivation

The 3rd component is concerned with the training labels that PONRM will use. Costsensitive models require a pair of entities to be trained with: ground-truth decisions and cost-sensitive incentives for those decisions [START_REF] Elkan | The Foundations of Cost-Sensitive Learning[END_REF]. Possible decisions are to accept, review, and reject a transaction. Incentives are determined based on earnings and losses that may arise from accepting, reviewing, or rejecting.

From Binary Labels to Trinary Ground-Truth Decisions: In the ideal binary decision making process, the model would accept all legitimate and reject all fraudulent transactions. However, models often fall short in performance compared to time consuming expert manual reviews in reality. Computing Cost-Sensitive Decision Incentives: By following the fraud management strategy considerations from Section 3, we incentivize our decisions with 4 parameters, namely: profit rate (𝑝𝑟), lifetime value multiplier (𝑙𝑡𝑣), fraud loss multiplier (𝑓𝑙𝑚), and review cost (𝑟𝑐). Profit rate is defined as the percentage of the transaction amount the merchant is earning as profit. Lifetime value multiplier simply models the lost opportunity due to losing customer's future business when a legitimate transaction is rejected (customer insult). Fraud loss multiplier weights the losses due to fraudulent activity to represent associated legal and chargeback costs. Finally, review cost is the compensation expert manual reviewers are paid per transaction. Derivation of the incentives for each decision is presented in Table 1. Although rejecting a fraudulent transaction does not provide any benefit, it is still the most desirable decision for a fraudulent transaction. From an information theoretic perspective, there is a need for a positive scalar to incentivize the learning process. To stay truthful to the initial incentives but represent most desirable decisions we offset the incentives: we add the initial incentive of accepting a fraudulent transaction to every decision incentive for fraudulent transactions. We add the initial incentive of rejecting a legitimate transaction to every decision incentive for legitimate transactions.

Profit-Optimizing Neural Risk Manager

Many of the off-the-shelf classification models are cost-insensitive; thus are sub-optimal for our task. Cost of accepting a fraudulent transaction and cost of rejecting a legitimate transaction can vary largely in different settings. While these costs differ between legitimate and fraudulent cases, they are also dependent on the transaction amounts. Moreover, off-the-shelf classification tools are not very adaptable for the expert opinion to intervene when necessary. Hence, we formally define Profit Optimizing Neural Risk Manager (PONRM) which produces decisions as accept, review, or reject for transactions according to each transaction's risk score. PONRM mostly mimics a multilayer perceptron structure with sigmoid activation functions;

𝐑 & = [𝐟 & , $ & ] 𝐇 (J) = 𝜎(𝐖 (J) 𝐑 + 𝐛 (J) ) 𝐇 (&) = 𝜎(𝐖 (&) 𝐇 (&N<) + 𝐛 (&) ) for 𝑖 = 1, . . . , 𝑙 𝐙 = 𝑠𝑜𝑓𝑡𝑚𝑎𝑥(𝐖 (YZ<) 𝐇 (Y) + 𝐛 (YZ<) )

where 𝐑 ∈ ℝ Z \×* is the risk score matrix. Each 𝐇 (&) ∈ ℝ \× _ is a higher dimensional( 𝐿 _ ) internal representation of the risk score in the multilayer perceptron. It outputs the decisions for each transaction in the output layer 𝐙 ∈ [0,1] \×= . To learn the parameters of the model, we use log loss multiplied by cost sensitive incentives and minimize the loss function by tuning 𝐖 (&) ,𝐛 (&) :

𝐿𝑜𝑠𝑠 = - 1 𝑁 [ [𝐙 &a log 𝐙 &a ] YdeNYdff 𝐁 &a &haihj&ki = al< ] \ &l< + 𝛼 & ||𝐖 (&) || * * Y &l< nieoYpn&qpj&dh
where 𝑁 is the number of transactions. 𝐙 &a quantifies the weight of assignment of the ground-truth decision 𝑐 to the transaction 𝑖. 𝐙 &a is the predicted assignments by the PONRM model for transaction 𝑖 and decision 𝑐. 𝐁 ∈ ℝ \×= and 𝐁 &a quantifies the incentive of assigning the 𝑖 jr transaction to decision 𝑐. We use L-BFGS quasi-newton optimization implementation of ScipyOptimizer interface of Tensorflow to minimize the proposed loss function [START_REF] Abadi | TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems[END_REF].

Experiments

Here, we evaluate the performance of our framework in various settings. In the first experiment, we present the effectiveness of PONRM in comparison to other cost-sensitive and cost-insensitive approaches. Next, we evaluate the performance of our system alongside baseline risk managers under different manual review capacities. Finally, we explore how fraud classification models perform with and without risk managers.

Evaluation Metrics

We introduce a new metric, named profit gain (PG), to measure the performance of our framework and the baseline models in a financially sound way. We normalize this metric using two extreme fraud management strategies: No Fraud Management: A merchant can choose not to interfere with any orders and accept all transactions as if they were legitimate. Then, it would suffer the maximum loss from fraudulent orders but not from any customer insults. We refer the total profit this company makes as $ hdsnpotuphpeiuihj .

Oracle: If a merchant could model the fraud characteristics perfectly, it would be accepting all legitimate orders and rejecting the fraudulent ones. In this case, its fraud and customer insult loss would be zero. It would earn the profit from all the legitimate transactions. We refer its total profit as $ dnpaYi .

To robustly measure the financial performance gain with a standardized scoring mechanism, we introduce profit gain as:

𝑝𝑟𝑜𝑓𝑖𝑡 𝑔𝑎𝑖𝑛 = $ u -$ hdsnpotuphpeiuihj $ dnpaYi -$ hdsnpotuphpeiuihj
where $ u is the profit of the model under experimentation. While calculating the profits, not-offset decision incentives in Table 1 is used. Also, we use F-measure to evaluate our fraud detection performance. As we assume perfect decisions by reviewers, review decisions are treated as accept for legitimate and reject for fraudulent transactions in calculation of F-measure. Each experiment is run 16 times and the average performance is reported for each parameter setting. For each parameter configuration, the best performing setting in terms of PG is reported as the representative performance of a model.

Dataset & Parameter Settings

We work with online transactions of three e-commerce merchants; an online travel agency, a physical goods store, and a digital goods store. We sample 1 month of transactional data for each company (October 2017), and remove transactions that do not include a transaction amount. Since some of the transactions have different currencies than USD, all the transaction amounts are converted to USD equivalent. Next, features are extracted as described in Section 4.1 for all datasets. Categorical features are onehot encoded to ensure compatibility across different classifiers. Missing values are imputed with mean-values for the numeric, with 'Category-other' for the categorical variables. We estimate each merchant's manual review capacity according to [7]. Table 2 presents the datasets' descriptive statistics. We use the first 80% of the transactions as the training dataset, and the rest as the test dataset. To calculate the decision incentives, we set profit rate (𝑝𝑟) to 5%, lifetime value multiplier (𝑙𝑡𝑣) to 3, fraud loss multiplier (𝑓𝑙𝑚) to 2.4, and review cost to $3 based on estimates from the merchants. For fraud classification models, we experiment with logistic regression (LR), gradient boosting machine (GBM), multilayer perceptron (MLP), and random forests (RF).

PONRM vs. Cost-Sensitive and Cost-Insensitive Baselines

In this experiment set, we investigate PONRM's performance in different settings in comparison with baseline cost sensitive and cost insensitive approaches. Experimental Setup: Among all fraud classification models multilayer perceptron (MLP) resembles a similar structure to PONRM, hence, we report its performance characteristics alongside PONRM.

Baselines: We introduce the following baseline architectures:

─ MLP is the multilayer perceptron classifier. We train a cost insensitive MLP classifier to detect legitimate and fraud detections. Transactions classified as legitimate are given accept, and those as fraudulent are given reject decisions. ─ CostMLP is a cost sensitive binary classification model. It uses MLP as its learning component. Incentives of rejecting and accepting are given alongside with binary transaction labels. As in MLP, transactions classified as legitimate are given accept, and fraudulent are given reject decisions. ─ CostMLPwithR is a cost sensitive trinary classification model. It uses MLP as its learning component. Incentives are given alongside trinary ground-truth decisions. Practically, it is the same as feeding transaction features to PONRM directly and bypassing the fraud classification model. ─ MLP+PONRM is our proposed framework. It uses MLP as its fraud classification model component and PONRM as the risk manager. We use profit gain (PG) and F-Measure to evaluate performances of above listed models. A grid search with 𝑙 = [0,1,2,3] and 𝛼 = [0,0.0001] is performed for each MLP based model. First layer's layer size (𝐿) is set to 300 in PONRM and other MLP based models. Each consecutive layer's size is calculated by square-rooting the previous layer's size. Results: MLP+PONRM framework shows superior performance in terms of both performance metrics. Models with review decision options (CostMLPwithR, MLP+PONRM) also achieve superior results than models without review decision options (MLP, CostMLP). Cost sensitive approaches (CostMLP, CostMLPwithR) perform better than their cost insensitive counterpart (MLP) for maximizing the profit gain and increasing F-Measure. One exception is the F-Measure performance in PGS dataset where having the smallest average fraudulent transaction amount leads to lower gains in decision incentives biased for rejecting fraudulent transactions. Thus, CostMLP performs worse than MLP.

Our proposed framework MLP+PONRM consistently overperforms CostMLP-withR. Even in CostMLPwithR's best performing case, MLP+PONRM achieves 20% greater profit gain and 24% better F-Measure overall. To achieve this, it first finds a transaction amount threshold based on the observed historical data, then sends the transactions exceeding this threshold until the specified review capacity is filled. Experimental Setup: To be able to compare the performance of different risk managers, we fix the fraud classification model. Due to the space constraints, we only report the experiments with RF and others can be found in the supplementary material. 1 RF is chosen due to its superior performance. We explore different parameters of RF as number of trees being 𝑛 = [START_REF] Ghosh | Credit Card Fraud Detection with a Neural-Network[END_REF]50,100,200].

We run experiments with review ratios of 10%, 20%, 30%, and 40% and report their profit gain accordingly. Since there is no standard setting to enforce PONRM to produce any of the review ratios of 10%, 20%, 30% or 40%, we experiment with different values of the parameter review class weight (𝑟) between 0.4 and 1.1 with 0.05 increments. According to the review ratio each PONRM experiment produces, we chunk them into bins of 10%, 20%, 30% or 40% review rates. We pick the best average performance of PONRM in the bins as the representative performance of the corresponding bin. Setting the review ratios for NRM and PPRM is straightforward. Results: Figure 2 shows PONRM's performance in terms of Profit Gain when manual review capacity of the user is tweaked between 0.1 and 0.4. At first sight, it is clear that PONRM performs superior to the two baseline risk managers. Some other key findings are given as follows: ─ Profit gain improves when manual review capacity is increased in OTA Dataset. For most of its transactions, review cost is negligible compared to the expected loss or profit, thus, when given maximum capacity, sending as much transactions as possible to review makes sense. ─ Sending most transactions to manual review may not be a sound strategy for PGS and DGS datasets due to lower transaction amounts. Each merchant must identify the optimal manual review ratio and implement its model accordingly. This would also let the merchant save time and resources by automating the process more. ─ When manual review capacity is 10%, PONRM performs up to 3 times better than PPRM and 4 times better than NRM. However, PPRM slowly catches up when the manual review ratio is unrealistically high. ─ PPRM's constantly superior performance compared to NRM asserts that consideration of the transaction amount is crucial for risk management.

Which Classifier to Use as the Fraud Classification Model

Posterior probability distribution based on the selected classifier may greatly affect the performance of PONRM. Thus, we experiment with four previously mentioned supervised learners to demonstrate their effects in the framework. Experimental setup and parameter settings are explored as in Section 5.4 and results with best parameter combinations are reported here for the sake of brevity. More detailed parameter analysis and guidance can be found in the supplementary material.

Results: Figure 3 demonstrates the performance of fraud classification models with and without PONRM. Some major findings are given as follows:

─ RF based fraud classification model with no risk manager often produces better results than the others with no risk manager. Especially its effectiveness in terms of profit gain contributes significantly to the RF+PONRM's performance, hence RF+PONRM generally gives the best performance. ─ MLP+PONRM performs well on all datasets. Specifically, on OTA, it is marginally the best model where MLP uses only one hidden layer. There is a negative correlation between MLP+PONRM performance and number of layers in the MLP fraud classification model as it does not represent uncertainty accurately when complex. ─ GBM+PONRM does not perform well as GBM is known to distort its posterior probabilities [START_REF] Niculescu-Mizil | Obtaining Calibrated Probabilities from Boosting[END_REF]. Since PONRM relies on the representation power of posterior probabilities, GBM is not an appropriate choice for our purposes. ─ As a heuristic, profit gain of the fraud classification model can be used for model selection due to its positive correlation with PONRM's profit gain. In this study, we propose a cost-sensitive decision making framework and demonstrate its effectiveness in fraud management. We reveal how human expertise can be combined with machine learning to make decisions under risk and cost considerations. Future work includes developing a novel metric to characterize the relationship between fraud classification models and PONRM performances. Also, we plan to investigate the generalizability of our framework to other domains such as loan evaluation and healthcare decision support.

Fig. 1 .

 1 Fig. 1. System Overview

Fig. 2 .

 2 Fig. 2. Performance of Risk Managers under Different Review Capacities

Fig. 3 .

 3 Fig. 3. Profit gain of fraud classification models with and without risk managers

Table 1 .

 1 Incentives for accepting, reviewing or rejecting a transaction

			Decision Incentives
		Accept	Review	Reject
	Legitimate	𝑝𝑟 * $ &	𝑝𝑟 * $ & -𝑟𝑐 -𝑝𝑟 * $ & * 𝑙𝑡𝑣
	Legitimate -Offset	(1 + 𝑙𝑡𝑣) * 𝑝𝑟 * $ & (1 + 𝑙𝑡𝑣) * 𝑝𝑟 * $ & -𝑟𝑐	0
	Fraudulent	-𝑓𝑙𝑚 * $ &	-𝑟𝑐	0
	Fraudulent -Offset	0	𝑓𝑙𝑚 * $ & -𝑟𝑐	𝑓𝑙𝑚 * $ &

Table 2 .

 2 Descriptive Statistics

		OTA	PGS	DGS
	Transactions	22,203	36,783	39,784
	Fraudulent Transactions	349 (1.57%) 253 (0.69%) 1,536 (3.86%)
	Transaction Amount Mean (𝜇)	$622.25	$177.22	$75.61
	𝜇 snpotoYihj /𝜇 Yie&upji	1.06	0.84	0.87
	Manual Review Capacity	30%	20%	10%

Table 3 .

 3 Comparison between PONRM and cost sensitive and insensitive baselines

			OTA		PGS		DGS
			PG	F-Meas	PG	F-Meas	PG	F-Meas
	MLP		0.1207	0.2769	0.0170	0.3115	0.1727	0.4143
	CostMLP	0.0325	0.2874	0.0673	0.3048	0.2100	0.4222
	CostMLPwithR 0.5954	0.7599	0.5280	0.7510	0.4541	0.5021
	MLP+PONRM 0.8113	0.8690	0.6514	0.8523	0.5876	0.6661
	5.4	PONRM vs.

Risk Managers Under Different Review Capacities In

  our third experiment set, we aim to show the efficacy of PONRM in comparison with other baseline risk managers in maximizing profit gain. We also explore the performance under different review capacities to ensure robust execution of our framework under various financial settings. Similar to NRM, this risk manager uses a fraud classification model to produce initial decisions as accept or reject. Next, it assigns the transactions having the highest transaction amounts to review considering the capacity under experimentation.

	Baselines: Coupled with RF fraud classification model, we introduce 2 baseline fraud
	management strategies to compare with PONRM as follows:
	─ Naive Risk Manager (NRM): This model assigns accept/reject decisions based on
	a fraud classification model. If fraud classification model classifies the transaction
	as legitimate, it accepts, and if as fraudulent, it rejects. Next, it selects transactions
	randomly based on the review capacity and converts their decisions to review.
	─ Price Prioritized Risk Manager (PPRM):

http://www.public.asu.edu/~myildir3/cost_supp.pdf

Acknowledgements We thank Amador Testa and Ozgun Baris Bekki from Emailage Corp. for providing the datasets and their valuable industry insights.