Serkan Özdemir
email: serkan.oezdemir@icb.uni-due.de

Rainer Unland Dawis

Wholesale Power to Hydrogen: Adaptive Trading Approaches in a Smart Grid Ecosystem

Keywords: trading, hydrogen, transportation, simulation, power to gas

Fossil based liquid fuels, primarily used in transportation systems, are likely to be replaced with renewable resources thanks to energy transition policies. However, shifting from stable energy production (using coal, natural gas) to highly volatile renewable production will bring a number of problems as well. On the other side, tremendous developments in solar and wind power technologies encourage energy investors to maximize their contributions over the electricity grid. This highly volatile energy resources bring a strong research question to the attention: How to benefit from excess energy? Power-to-gas seems to be a strong candidate to store excess energy. Besides, power-tohydrogen is seen as a liquid fuel for fuel cell vehicles. This paper aims to analyze trading approaches of a power-to-hydrogen system to minimize the energy costs. To achieve that, Markov Decision Process (MDP) along with Q-learning is modelled as well as a number of trading approaches. This research aims to reveal the feasibility of hydrogen as a fuel option in future smart grid.

Introduction

Due to energy transition policies of governments and recent developments in renewable energy technologies, fossil and nuclear based power plants tend to be replaced with renewable resources. Recent developments show that the number of installed capacity will dramatically increase in the near future. Solar siding and roof-top panel technologies are rapidly growing since they have a large footprint compared to other renewable resources. This work assumes that energy transition will shift towards renewables as already planned by many countries.

In case of high renewable penetration, future smart grid will face with a number of challenges, such as meeting the supply and demand in balance. Since the renewable energy production is highly weather-depended, a distributed energy storage is needed at off-peak hours or days to benefit from excess energy. Among other storage options, power-to-gas has the most storage capacity over other technologies [START_REF] Hall | Energy-storage technologies and electricity generation[END_REF][9] [START_REF] Reichert | Wind-to-Gas-to-Money? Economics and Perspectives of the Power-to-Gas Technology[END_REF]. The first step product of power-to-gas, obtained through electrolysis process, can be used as fuel in fuel cell vehicles. This way is more efficient than methane in terms of energy loss. Hydrogen is also nature friendly fuel and the output of fuel cell vehicles is only water. However hydrogen cannot be delivered to far away due to high pressure problems. For this reason, on-site production is one of the proposed methods for hydrogen production [START_REF]Price List[END_REF][9] [START_REF] Regio | The future cost and competitiveness of hydrogen as a transport fuel in Europe[END_REF].

Fuel cells are usually considered as a competitor of battery electric vehicles. However, fuel cell vehicles are replacement of traditional combustion engine vehicles. Moreover, fuel cells are also battery electric vehicles. In addition to all functionalities of battery electric vehicles, fuel cells have high pressure hydrogen tank and fuel cell stack which converts hydrogen into electricity. For this reason, fuel cells can be solution to charging, efficiency and driving-range problems of battery electric vehicles.

This works aims to analyze hydrogen production through electrolysis process on the city level. Power Trading Agent Competition (Power TAC) is selected to simulate future smart grid conditions [START_REF] Ketter | The 2015 Power Trading Agent Competition[END_REF]. A hydrogen station is designed as a server module in which a number of fuel cell and conventional vehicles are simulated. Refilling station consists of an electrolysis unit, high pressure storage unit, dispensers and onsite renewable resources. The station is an active participant of a local wholesale market. The wholesale market is a typical hour-ahead market which allows participants to submit orders 24 hours prior to delivery. Proposed Markov Decision model and trading approaches are explained in Section 3.

State of the Art

Both power-to-hydrogen (PtH 2 ) and fuel cells are quite old concepts. Basically, the electrolysis extracts water into oxygen and hydrogen (H 2 O → H 2 + O). Among different electrolysis approaches, alkaline electrolysis is the most common one in use. Conversion efficiency rate depends on the load, but the typical rate is 60-70% at full load.

Hydrogen can be also injected into natural gas grid [START_REF] Sterner | Power-to-Gas: Perspektiven einer jungen Technologie[END_REF]. In a typical PtH 2 power plant, investment and operation-management costs have severe roles on the profitability of the plant. Following table shows the basic inputs and outputs of a PtH 2 power plant. Besides the advantages of CO 2 emission level and driving range, fuel cells also performs a promising well-to-wheel performance for the future transportation. Fol-lowing table compares roughly the well-to-wheel performances of fuel cell vehicles, battery electric vehicles and diesel vehicles. Well-to-wheel retail 9 EUR [START_REF] Kurier | Erste Wasserstoff-Tankstelle: Künftig tanken wir Kilos[END_REF] 4.68 EUR [START_REF] Verivox | Direktvergleich[END_REF] 5.75 EUR [START_REF] Tanken | [END_REF] There are a number of possible incentives that are subject to PtH 2 plants. However, on the legal side, some are not matured due to uncertainties on the future fuel options. But the good news is, there are many ongoing acts regarding to hydrogen fuel utilizing renewable electricity. Currently, many companies, such as OMV, Hydrogenics, Toyota and e-on are active in the hydrogen business by producing fuel cell cars, power plants and refilling stations.

On the other side, energy markets have the vital role on power-to-gas power plants and will be more important in the future due to high fluctuations. In the current situation, electric vehicles are exposed to retailer prices since it is not possible for each electric vehicle to trade in wholesale markets. Unlike electric vehicles, power-to-gas power plants and their refilling stations are able to trade in energy markets. For this reason, fuel cell transportation is seen as one of the strongest candidates for the future transportation system.

Methodology

In order to analyze hydrogen as a fuel option, a Power TAC server module is created. This module simulates a hydrogen refilling station and on-site hydrogen production.

Local wholesale market and on-site renewables are electricity resources of hydrogen production. Note that Power TAC is simulated on the city level with a population of about 50 thousand residents, which fits to on-site PtH 2 power plant scenario since the long-haul distribution of hydrogen is not possible [START_REF] Sterner | Power-to-Gas: Perspektiven einer jungen Technologie[END_REF]. Figure 1 illustrates the schematic landscape of proposed environment.

24

Bidding margin M Margin that is added to the price obtain through MDP.

EUR

The proposed refilling station simulates the following components:

─ Electrolysis Unit: Converts input power to hydrogen having an efficiency rate which depends on the size of electrolysis unit and input power. ─ Hydrogen Storage Unit: This unit stores the produced hydrogen thorough electrolysis process. It also supplies hydrogen to dispensers. ─ Dispensers: Final end-point where refilling hydrogen to simulated fuel cell vehicles takes place. ─ A number of fuel cell and traditional vehicles. ─ On-site solar panels and wind mills which supply electricity to electrolysis unit. ─ Trader module: Trades in the wholesale market and optimize the costs considering various variables and on-site production.

Trading in the wholesale market is the most significant part of the research since the motivation of the research is to benefit from the excess energy. Unlike electricity retailers, hydrogen trader unit can make flexible decisions and watch cheap prices at future hours thanks to its hydrogen storage unit. Storage unit can easily tolerate several time slots to let trader unit find cheaper energy in an hour-ahead market.

Trading Model

Unlike broker models in the ecosystem, power-to-gas models are supposed to have an appropriate trading model. Brokers have to deal with balancing problems and make careful decisions to avoid balancing penalties. In order to meet supply and demand, brokers might submit extremely generous bids. However, this landscape is a bit different for power-to-gas plants. Thanks to their storage units, they are able to make more flexible decisions. Following statement presents the optimization problem of overall cost over time horizon H.

𝑚𝑚𝑚 ∑ ∑ 𝑒 𝑛 𝑡 𝑇 𝑛=1 . 𝑝 𝑛 𝑡 𝐻 𝑡=1 (1)
Where e is energy and p is energy price over time horizon H and enable future time slots T. In order to optimize the wholesale market cost over a time horizon, we propose a trading model using Markov Decision Process (MDP) design, deploying a Qlearning method [START_REF] Watkins | Q-learning[END_REF]. In this approach, all hours are represented as 24 individual processes. Each process has 25 states which represent the future time slot proximity as well as completed state. Proposed MDP is designed as follows: In this MDP design, actions are defined as difference of limit price and clearing price which cleared in previous state. In other words, actions indicate increment values as state s transitions to s -1. This way provides many opportunities such as catching price trends regardless of weather conditions. Even if a bid does not clear at s = 24, next bids eventually become more adaptive. In the learning mode, delayed market data is used to update Q-matrix. Therefore, actions are defined as clearingPrice s ∈ ℤ : s = 24, clearingPrice s -clearingPrice s+1 ∈ ℤ : s < 24. Following Q-learning formula evaluates the market experience of the agent. 𝑄 𝑡+1 (𝑠 𝑡 , 𝑎 𝑡 ) = 𝑄 𝑡 (𝑠 𝑡 , 𝑎 𝑡 ) * α + (𝑅 𝑡+1 + ɣ * max 𝑎 𝑄 𝑡 (𝑠 𝑡+1 , 𝑎 𝑡 )) * (1 -α)

(2) Subject to 0 ≤ α ≤ 1 and 0 ≤ ɣ ≤ 1. After each iteration, Q matrix is normalized to make sure that all values are set between 1 and 0. Solving MDP is straight forward since it only requires searching the right value in the state-action vector. Following formula fetches the predicted price at current time slot t and future time slot T. 𝑀𝑀𝑀(𝑡, 𝑇) = 𝑐𝑐𝑒𝑎𝑐𝑚𝑚𝑐𝑀𝑐𝑚𝑐𝑒 𝑡-1,𝑇 + (𝑎𝑐𝑐 𝑚𝑎𝑚 𝑎 𝑄 𝑡 (𝑇 -𝑡, 𝑎 𝑡 ))

However, various trading approaches are required to optimize the overall cost. Using predicted prices through MDP's might be helpful to find the future prices. But another procedure is needed to catch cheap prices and skip expensive wholesale prices. To achieve this, we propose 4 trading approaches defined as follows.

─ Stingy: This bidding approach always submit lower prices than solved prices through MDP. Submitted price will be solveMDP(t, T) -M where M is set to 5. ─ Neutral: Solved price through MDP is directly submitted in the order. ─ Generous: Unlike Stingy approach, it always submit generous prices than solved prices through MDP. Final price will be solveMDP(t, T) + M where M is set to 5.

─ Combined: This strategy combines all of the approaches above. For a particular current time slot t, predicted prices (for future time slot T) at t, t + 1, … , T -1 are divided into 3 price zones which are defined as cheap, normal and expensive. In cheap zone, generous bidding is used to increase the chance of buying cheap energy. In normal price zone, neutral bidding strategy is used. Likewise, stingy bidding is used in expensive price zone to decrease the probability of buying expensive energy.

As a future work, these strategies will be integrated to hydrogen storage optimization problem to minimize overall cost of refilling station.

Future Work

Proposed design above enables various studies from different perspectives. First, a legal landscape (taxation, incentives and transition policies) and a future projection will be covered under this research. Second, renewables have to be taken into account deeply since they are the main drivers of the future energy production. Within this scope, all of penetration levels will be simulated with the proposed trading methods. Third, size of refilling station, such size of electrolysis unit, storage unit, pumps and so on, will be subject to an optimization problem considering investment and operational costs. This work aims to control a number of variables.

─ Size of electrolysis unit (MW). An electrolysis unit is the most efficient at 25% electricity input. ─ Size of hydrogen storage (kg). A bigger size of storage unit can put trader unit into a more flexible position. Therefore, operating modes will be defined based on the hydrogen storage. ─ Share of vehicle groups. Percentages of fuel cells, battery electric vehicles and traditional vehicles among all passenger vehicles (cars, buses, vans). ─ Production volume (including local producers). Various production rates will be subject to experiments. ─ Distribution fee. This fee is paid if the bought energy is originated from wholesale market. Incentives can waive this fee. ─ Trading approaches. These approaches will be defined in Markov processes later on. ─ Number of retailer/broker companies.

All of these variables are controlled to optimize the cost and investment problems as well as further possible analysis. Existing works in the literature are usually based on the static data or estimations. Power-to-gas is usually considered as a profitability problem or balancing approach which are far away from transportation perspective.

Conclusion

In summary, the smart grid will bring a lot of benefits such as excess energy. On the other side, fuel cells have all the functionalities of a battery electric vehicle in addition to hydrogen storage and fuel cell stack. This capability provides opportunity to drive with hydrogen or electricity no matter which one is available in the vehicle. Obviously, both ways are nature friendly and do not replace each other.

Proposed trading approaches and design show that power-to-hydrogen units are able to trade in the wholesale markets, making more flexible decisions thank to hydrogen storage units. It is noteworthy that unstable energy production by renewables eventually results in unstable price regime. This highly volatile environment will be the driver of power-to-gas plants.

Fig. 1 .

 1 Fig. 1. Simulation model in Power TAC scenario.

─

  States: s ∈ {1, … , 24, completed} ─ Terminal state: {completed} ─ Reward function: In state {completed}, the reward function returns 0. Otherwise, it returns 0. ─ Actions: limitPrice s ∈ ℤ : s = 24, limitPrice s -clearingPrice s+1 ∈ ℤ : s < 24. ─ Transition function: In a state s ∈ {1, … , 24}, if an order fully clears, it transitions to completed state. Otherwise, s transitions to s-1. In every time slot, a new episode starts for processes where s = 0.

Table 1 .

 1 Inputs and Outputs of a PtH 2 power plant and fuel station.

	Today	2030

Table 2 .

 2 Comparison of different fuel types. Reference vehicles are B segment economy cars of Mercedes, Toyota and Hyundai.

		Fuel Cell Vehicle	Battery Electric vehicle Diesel Vehicle
	Range (100 km)	1 kg H2 (48 kWh el. input)	18 kWh	5 liter
	Well-to-wheel wholesale 1	1.2 EUR	0.62 EUR	2.9 EUR [2]

Table 2 .

 2 Parameters of the proposed ecosystem.

		Symbol	Description	Value
	Size of electrolysis unit	S elc	Size of unit which converts electricity to H2.	10 MW
	Size of H 2 storage unit	S str	stored. Size of storage unit in which produced H2 is	1000 kg
	Electrolyser efficiency	E elc	Efficiency vector of an electrolysis unit	[0 -85 %]
	vector		based on the rate of (electricity input/ S elc ).
	Energy equiv. of 1 MWh	R ptg	Equivalence of 1 MWh electrical power to	30 kg H2
	electricity		H2 regardless of losses.
	Learning alpha	Q_ALPHA	Alpha parameter of Q-learning.	0.5
	Learning gamma	Q_GAMMA	Gamma parameter of Q-learning	0.0
	Time horizon	H	Total length of a game in time slot.	8765
	Future time slot	T	Future time slots which are enabled for trading.

The row indicates wholesale costs without taxes, profits and service fees.


Fahed Mostafa
email: fahedm@yahoo.com

Tharam Dillon
email: tharam.dillon7@gmail.com

Elizabeth Chang
email: e.chang@adfa.edu.au

Computational Intelligence Approach to Capturing the Implied Volatility

Keywords: Computational Intelligence, Neural Networks, Option Pricing, implied volatility, GARCH option pricing model

In this paper, a Computational Intelligence Approach and more particularly a neural network is used to learn from data on the Black-Scholes implied volatility. The implied volatility forecasts, generated from the Neural Net, are converted to option price using the Black-Scholes formula. The neural network option pricing capabilities are shown to be superior to the Black-Scholes and the GARCH option-pricing model. The neural network has also shown that it is able to reproduce the implied volatility well into the future whereas the GARCH option-pricing model shows deterioration in the implied volatility with time.

Introduction

The Black-Scholes Option Pricing Model (BSOPM) published in 1973 [START_REF] Black | The Pricing of Options and Corporate Liabilities[END_REF] remains one of the most cited scientific papers in this field. The model made a key contribution to option trading, allowing investors to calculate a fair value for an option contract. This model has its limitations, which stem from the unrealistic assumptions used in the derivation of the BSOPM. The wide success of this model was due to its ability to produce an option price instantaneously. The formulation of BSOPM was based on major assumptions which allowed for the derivation of this model. These assumptions significantly impacted the model pricing capabilities which are visible in the models pricing biases. The constant volatility assumption has captured the attention of researchers, as it contradicts the volatility behaviour observed in the underlying asset. Also, it was realised when the volatility was backed out from the BSOPM for different strike prices, the implied volatility displays a Ushape pattern (volatility smile) when plotted against the options moneyness. Moneyness is defined as the relative position of the current or future price of the underlying asset with respect to the option strike price. Nevertheless, implied volatility is derived directly from the options data, which contains vital information as it provides a forward looking view on how the market is anticipating movements in the underlying asset. This is a different view to the conditional volatility calculated from the stock returns which is a retrospective view. The other interesting feature of the implied volatility is the deterioration of the volatility surface through time caused by the changes in the implied volatility levels. Many models have emerged to overcome the limitations of the BSOPM. In the present paper, we select the GARCH option pricing model (GOPM hereafter) as it allows for the volatility to follow a GARCH specification. This specification overcomes the constant volatility assumptions and at the same time caters for key stylised facts in the underlying returns series. This model has displayed superior improvements over other pricing models. The major shortcoming for this model is the absence of a closed form solution. This means the model parameters have to be optimised using a Monte Carlo simulation, which is a computationally intensive process that limits its ability to be applied to real-life problems.

Neural networks have been applied previously to option pricing problems (Karaali, Edelberg et al. 1997), (Meissner and[START_REF] Lehnert | Capturing the Volatility Smile of Options on High-Tech Stocks-A Combined GARCH-Neural Network Approach[END_REF], [START_REF] Amilon | A neural network versus Black-Scholes: a comparison of pricing and hedging performances[END_REF], [START_REF] Yao | Option price forecasting using neural networks[END_REF], [START_REF] Tino | Financial volatility trading using recurrent neural networks[END_REF]) and [START_REF] Bennell | Black-Scholes versus artificial neural networks in pricing FTSE 100 options[END_REF]. The majority of research papers rely on neural networks to provide a mapping from inputs similar to the BSOPM to the option price. Training the neural network on the option price is a cumbersome task. The option itself can suffer from many issues such as stale prices due to infrequent trading [START_REF] Rubinstein | Nonparametric tests of alternative option pricing models using all reported trades and quotes on the 30 most active CBOE option classes from August 23, 1976 through August 31, 1978[END_REF]. Therefore, using the option price to guide the training of the neural network can be misleading as the neural network will attempt to map the inputs to an output that has poor correlation with the input. To overcome this limitation, many variations of this method have been developed to improve the pricing accuracy. For instance, substantial pricing performance gains are achieved when the training data set is partitioned by moneyness and different neural networks are used for each of the training sets. Yet there has been no attempt to evaluate the neural networks' performance against more advanced models. The reason for this is that the pricing capabilities of the neural networks are inferior to those of more advanced pricing models such as the GOPM. In [START_REF] Hanke | Neural Network Approximation of Option Pricing Formulas for Analytically Intractable Option Pricing Models[END_REF]), a neural network was constructed to give an approximate price to GOPM. This was achieved by training the network on different input combinations for the GOPM allowing the neural networks to approximate the GOPM, thereby overcoming the numerical simulation issues of the GOPM. In (Mostafa and Dillon 2008), a new option pricing method was proposed by allowing the neural network to learn the implied volatility behaviour of the option through time.

The main variable that can explain the option behaviour through time is the implied volatility, since the implied volatility is considered to be a forward looking view of the market anticipation. By allowing the neural network to capture the implied volatility surface through time, the neural network will be able to forecast future movements of the implied volatility across different strikes which can then be converted to an option price. This method was demonstrated to have superior option pricing over the Black-Scholes and GOPM. The option pricing of the neural network and GOPM was discussed and analysed in (Mostafa and Dillon 2008), in this paper we demonstrate the capabilities of neural networks in learning the implied volatility surface through time and its impact on option pricing. We also validate this method by studying how well the neural network can reproduce implied volatility into the future relative to the GOPM. In section two, the option pricing models are reviewed; in section three the data used in this paper is explained. In section four the performance measuring criteria are explained, in section five the results from the experiments are discussed. In section six we discuss and compare the implied volatility forecast behaviour of the neural network and GOPM. We then conclude this paper in section seven.

Option pricing models

In this section we review the option pricing models studied in this paper.

GARCH Option Pricing Model (GOPM)

It has been demonstrated by [START_REF] Duan | The GARCH Option Pricing Model[END_REF]) that under the Local Risk Neutral Valuation Relationship (LRNVR) the conditional variance does not change. However, under measure Q , the conditional expectation of rt is the risk free rate rf.

 

) exp( | ) exp( 1 f t t Q r r E    (1)
To derive the GOPM, the risk neutral valuation relationship has to be generalized to the LRNVR:

) 1 , 0 ( , 2 1 * * * 2 * N where r r t t t t f t        (2) 2 * 1 2 2 * 1 2 * 1 1 0 2 * ) (        t t t t         (3) By having     
~, the risk-neutral pricing measure is determined by four parameters: 0,1,2 and  . Using the above formulation, the asset terminal is then calculated at time T

                T t i i i T t i i f t T t T r S S 1 * * 1 2 * 2 1 ) ( exp    (4)
The terminal asset price is then calculated using Monte Carlo simulation. A set of N random path of residuals ) ,..., (

* , * , 1 j T j t   
is generated with J = 1 to N. The residuals are used to calculate the asset prices ST,j. The final option price is then approximated as follows:

      M j j T f GARCH K S N t T r C 1 , * ) 0 , max( 1 )) ( exp( (5)
Empirical Martingale Simulation (EMS) of [START_REF] Duan | Empirical Martingale Simulation for Asset Prices[END_REF] has been used which has been shown to accelerate the convergence of the Monte Carlo prices estimates. The GOPM parameters were estimated for each day of the data sample. This was achieved by minimizing the average sum squared error eqn. ( 21) [START_REF] Aboura | GARCH Option Pricing Under Skew[END_REF]) (Lehnert) over all options on day t, with parameters from day t-1 as the initial values [START_REF] Lehar | GARCH vs. stochastic volatility: Option pricing and risk management[END_REF].

                         T t N n n t n t n t C C C SSE 1 1 , , ^, ) ( Min (6) where       , , , 2 1 0  
, Ĉ and C are the model theoretical price and the actual call price respectively. The number of Monte Carlo simulations was initially set to 15,000. This was sufficient to generate stable estimates. In some cases, the number of simulations had to be increased to 30,000.

The Black-Scholes Option Pricing Model (BSOPM)

The BSOPM theorem was first published in 1971 [START_REF] Black | The Pricing of Options and Corporate Liabilities[END_REF]. It is the most widely used pricing model. The interest rate and volatility are constant; the call option on the asset, expiring at time T and with strike price K will have the following value at time t:

) ( ) ( ) ( ) , ( 2 ) ( 1 d N Ke d N t S T t C t T r     (7)
where,

  t T t T r K t S d                      2 ) ( ln 2 1 and   t T t T r K t S d                      2 ) ( ln 2 2 N(x)
is the cumulative probability distribution for a standard normally distributed variable. The BSOPM delta is given by N(d1), which also measures the sensitivity to the underlying asset.

Implied Volatility

The implied volatility is a volatility parameter, which equates the market price with the price given by the BSOPM formula. The implied volatility,

  T K BS t , 
is a function of K (Strike) and T ( time to maturity) [START_REF] Hull | Options, futures, and other derivatives[END_REF]. The two most interesting features of the volatility surface, which have been studied and analysed by researchers, are the volatility smile (skew) and the term structure or the level of implied volatility changes with time. The volatility smile is a key indicator of an unrealistic assumption of constant volatility. Whereas, the changes in the implied volatility level with time is seen by the deformation of the volatility surface with time. Therefore, the ability to capture the implied volatility term structure will lead to accurate option pricing. [START_REF] Cont | Deformation of implied volatility surfaces: an empirical analysis[END_REF] have expressed mathematically the implied volatility surface as follows:

      T K C T K K S C t BS t t BS , , , , , *    , where   0 ,  T K BS t  (8)
The value of the call option as a function of the volatility is a monotonic mapping from [0,+[ to ]0,St-Ke -rt [. The implied volatility

  T K BS t , 
of a call option with strike K and price maturity of T is dependent on K and T. If K and T are fixed,

  T K BS t , 
can be generalised to follow a stochastic process. For a fixed t, the value will depend on the options characteristics such as maturity and strike level K. Equation 9 represents the volatility surface at time t.

    T K T K BS t BS t , , :     (9) ) ), ( ( ) , (      t t mS m I BS t t (10)
Where m is the moneyness,

) , (  m I t
is the implied volatility function.

The two most important features of this surface are the volatility smile and the changes in the volatility levels with time. Thus, the evolution in time of this surface will reflect the evolution of market option prices. Many previous studies have attempted to explain the information contained in the implied volatility [START_REF] Day | Stock Market Volatility and the Informational Content of Stock Index Options[END_REF][START_REF] Canina | The informational content of implied volatility[END_REF][START_REF] Christensen | The relation between implied and realized volatility1[END_REF][START_REF] Blair | Forecasting S&P 100 volatility: the incremental information content of implied volatilities and high-frequency index returns[END_REF][START_REF] Jiang | The model-free implied volatility and its information content[END_REF] where the majority of studies have shown that the implied volatilities contain relevant measurement errors with quantifiable magnitude. Earlier research shows the implied volatility to be an inefficient forecast of volatility [START_REF] Canina | The informational content of implied volatility[END_REF]. However, more recent studies such as [START_REF] Jiang | The model-free implied volatility and its information content[END_REF] show that the implied volatility subsumes all information contained in the historical volatility and is capable of providing an accurate forecast of future volatility. This information can be utilised in many aspects since the option prices reflect the participant's expectations of the market's future movements. So, if the option market is efficient such that all information is observed and the correct option pricing model is specified, the implied volatility should subsume the information contained in other variables in explaining future volatility. That is, the implied volatility should be an efficient forecast of future trends over the life of the option.

There have been several theoretical explanations for the volatility smile such as the distribution assumption and stochastic volatility (Poon 2005). There have been other explanations proposed based on market microstructure, measurement errors and investor risk preference. However, the BSOPM assumes the asset price to have a lognormal distribution or the (logarithmic) returns to follow a normal distribution. Given a high strike price the call option is deep out-of-the-money and the option has a very low probability that it will be exercised. The leptokurtic right tail will give the option a higher probability than the normal distribution for the asset price to exceed the strike price, which means the call will be in-the-money at expiry. If we consider a low strike price, the same argument applies as above but an out-of-the-money put option is used instead. Due to the thicker left tail of the leptokurtic distribution, the probability of the out-of-the-money put option to finish in-the-money will be higher than that of the normal distribution. Therefore, the put option price should be greater than the price given by the BSOPM. If the BSOPM is used to back out the implied volatility, the BSOPM implied volatility will be higher than the actual volatility. This causes the volatility smile where the implied volatility is much higher at very low strike prices and low at high strike prices. The implied volatility for different strikes and maturities do not evolve independently and they are a highly correlated multivariate system [START_REF] Cont | Deformation of implied volatility surfaces: an empirical analysis[END_REF]. To construct a model in terms of the implied volatility rather than volatility of the underlying asset volatility may complicate the modelling procedure. However, there are advantages of modelling the implied volatility directly. For instance, the implied volatility is observable and is derived from the market data, whereas, the asset volatility is not directly observable. The implied volatility gives an insight to the option markets which can be analysed by the practitioners. The shifts in levels of implied volatility are highly correlated across strikes and maturities, which allows for the modelling of the joint dynamics. The implied volatility is now widely used by practitioners and especially with the emergence of implied volatility indexes and derivative instruments [START_REF] Cont | Deformation of implied volatility surfaces: an empirical analysis[END_REF].

Artificial Neural Network (ANN)

The ANN consists mainly of an input layer, one more hidden layer and an output layer. The layers are connected via a set of weights. The hidden layer and the output layer consist of individual neurons. The inputs are multiplied by the weights and a bias term is added which then constitutes the input to the activation function. This then serves as the input to the following layer. The activation of the output layer is given by:

) ) ( ( ) (      K J k k jk J ij B B x w H w G x F (11)
The activation functions of the neurons could be chosen to be linear or non-linear functions. A sum of error-squared function is normally used as the objective function for the training of the MLP. So the MLP is trained to minimize this function with respect to the in-sample data.

   N i i x F t N E 1 2 )) ( ( 1 (12)
The MLP performance is dependent on the initial values of the weights. To overcome this issue, the neural network is trained 50 times using different initial values for the weights. The weight set that introduces the least error is then adopted.

Given the limited success in applying neural networks to option pricing, we adopt the same method used in (Mostafa and Dillon 2008) for training the neural network with the intention of capturing the underlying asset dynamics of the instrument which then can be translated to an option price using known market variables. This new methodology allows the neural network to capture the dynamics of the underlying asset and the changes in the volatility levels through time. Using the option price to train the neural network has been proven to be ineffective; therefore, instead of training the neural network to price the option directly, we allow the neural network to learn the implied volatility. So the neural network will be optimized on the implied volatility, thereby allowing the neural network to forecast the implied volatility for different maturities and moneyness. Many studies have demonstrated that vital information is contained in the implied volatility especially since the implied volatility contains the market expectation of the underlying asset future movements. To allow the neural network to capture the entire volatility surface, the data set was not partitioned by moneyness, thereby allowing the neural network full visibility of the volatility surface. This approach is a mapping exercise described in equation 14.

The neural networks must be tested and verified on the training data set to overcome key issues such as over-fitting (Mostafa and Dillon 2008). The neural network is trained using the BSOPM implied volatility as the target output. This method allows the neural network to predict the future implied volatility, which also means that the neural network can produce the implied volatility surface over any trading horizon. The implied volatility can be converted to an option price by plugging it into the BSOPM. The neural networks were optimized by varying the number of inputs, length of in-sample and validation sets, and the number of hidden units. The combination that gives the lowest error is considered to be the optimal model and is chosen accordingly. The initial weight values were initialized randomly, and to eliminate the dependency on the initial weight values, this process was repeated 50 times.

After experimentation with the different inputs, the following combination was selected for optimal performance. The in-sample and validation set were 20 and 5 days respectively, and the output sample was 1 day. The inputs used were moneyness (index/strike), time to expiry and historical volatility. The target data set was the BSOPM implied volatility. Once the training of the ANN is completed, the implied volatility produced by the ANN would be plugged into the Black-Scholes formula to obtain an analytical price of the option. This model would be referred to as NNiv.

Data

The data used in this research consists of European call options on the FTSE 100 index traded at the London International Financial and Options Exchange (LIFFE). The data for this research was obtained from SIRCA (http://www.sirca.org.au/), which covered a two-year period starting from 2/1/2000 and ending on 31/12/2001. The sample was made up of 63,094 call options and the daily Index value (adjusted for dividends). The following constraints were applied to filter the data series: moneyness (index/strike) outside [-1.01,0.9], maturity greater 175 days and less than 7 days and close price less than five where removed. The data series was then reduced to 26533 options. GB Libor rates were used for the risk-free rate inputs to the models. The parameters for the GOPM and BSOPM were estimated on a daily basis. However, when optimising the ANN, the data was split into 3 sets: in-sample, validation and out-of-sample. The in-sample set is used as input to the ANN, thus impacting on the weights. The validation set is used to evaluate the error at each epoch. The training of the network is terminated when the error of the validation increases. The out-of-sample data set is used for evaluating the ANN model.

Performance Measure

To analyze the model's performance, Absolute Relative Pricing Error (ARPE) was calculated for each model. where Ĉ and C is the model theoretical call price and the actual call price. The errors are reported against maturity and moneyness. The models pricing performance is further analyzed by running a regression analysis to study the pricing behavior based on the moneyness and TTE (Time to Expiry).

    n i i i i C C C n ARPE 1 1 (13)      c bMon aTTE ARPE , where ) , 0 ( ~2   N (14)

Results

Below the estimated mean values of the GOPM parameters are given in Table 1.

Table 1: GOPM average parameters 0  1  2    3.109E-05 1.848E-01 3.184E-01 6.745E-01 22.37%
The risk premium is extracted from the option prices rather than from the index time series. It was found to be a little weak which in turn will have a minor impact on the option price. The annual volatility was found to be approx 22.37% which is a close approximation to the historical volatility when estimated on the index prices 20.7%.

The ARPE figures are displayed in Table 2. On average, the performances of GOPM and NNiv models increase with maturity. Again, the BSOPM performs the worst on all accounts. On average, the NNiv has a slightly better performance than the GOPM. The GOPM model performs slightly better for MT contracts and the NNiv has a better performance for ST and LT contracts. All models have performed the worst for ST-DOTM contracts. In addition, the GOPM performs the best for LT-DITM, whereas the NNiv and BSOPM are at their best for ST-DITM contracts. The NNiv seems to perform best for the MT-ITM contracts. The ARPE is regressed on TTE (Time to Expiry) and Mon (Moneyness). The estimated coefficients are displayed in Table 3. The coefficients R 2 and F-test for NNiv and the GOPM are similar. This indicates that the models price the options in a similar manner. For all models, the ARPE is smaller for longer maturities and increased moneyness. Therefore, ITM options are priced more accurately than the OTM options and the models price LT contracts with better accuracy than ST contracts

The Empirical Dynamics of the Volatility Smile

In this section, we study the behavior of the implied volatility of the GOPM and the NNiv over time. The implied volatility of NNiv is given directly as the output of the model, whereas the GOPM produces a theoretical option price. To extract the implied volatility from the GOPM, the option prices are equated to the BSOPM formula and the implied volatility is backed out. To study the volatility smile, a theoretical series is generated by an out-of-sample fit of the GOPM parameters calculated on the previous day. The implied volatility is then backed out for each option price using the BSOPM formula. Figure 1 shows the first day out-of-sample forecast for the GOPM. It can be seen that the volatilities are higher for the shorter maturities. As the option moves from ITM to ATM, they converge and the slopes are reversed. This has been highlighted by [START_REF] Aboura | GARCH Option Pricing Under Skew[END_REF], where this point is of importance because the model is able to classify the volatilities according to their moneyness. Figure 2 displays the implied volatility for the end of the month using the same parameters as those for the first day of the month. The deformation of the smiles is obvious. The short maturity has a higher implied volatility; however, the skew of the longer maturities becomes more linear. The theoretical volatilities calculated for NNiv at the first day of the month are displayed in Figure 3. The volatility smile is apparent in the graph. The graph also shows a similar behavior to the skews generated by the GOPM. For all maturities, the slope of the skews changes as it moves from ITM to OTM. So, as the option approaches ATM, the volatilities across all maturities become similar. For the ITM -LT option, the skew tends to be linear; then as it moves past the ATM point, the NN gives higher volatilities. For ITM-ST options, the NN generates much larger volatilities than the ITM-LT options. As ST option passes the ATM range, the slope changes direction forming the smile. However, the volatilities are smaller than the LT for OTM options. In Figure 4, there does not seem to be any deformation of the skews. The skews also follow the same behavior as those in Figure 3. The deformation of the GOPM skews through time displays that the model is sensitive to changes in the underlying asset. The GOPM parameters are calibrated under LRNVR conditions by simulating the underlying asset process and pricing the options at expiry accordingly. However, the NNiv is designed and trained differently. The ability of the NNiv to price options out-of-sample is a key indicator of the ability of the NN to capture the dynamics of the options. The NNiv trained on mapping the input space (TTE, Moneyness, Historical Volatility) to Black-Scholes implied volatility. Due to the high number of variables in the NN, 1 day of historical data was not sufficient to produce a stable result. Hence, the NN was trained on 20 days of data, which contains substantial information. Therefore, when the smiles are generated out-of-sample towards the expiry of the options, the neural network is able to display the actual skew at that point in time. This is a good indication that the NN is a suitable tool for long-term forecasting.

Conclusion

The neural network was trained using the implied volatility as the target output of the neural network rather than the options price. This method has shown to have superior out-of-sample pricing performance over the BSOPM and GOPM. The neural network's performance was also compared to those of the GOPM and the BSOPM. The regression analysis shows the neural network behaves in a similar manner to the GOPM. This demonstrates the neural networks are capable of learning and reproducing option prices accurately by learning the implied volatility. The neural network was also shown to reproduce the implied volatility well into the future where as the GOPM start to show deformation. This behavior of the neural network demonstrates its capabilities to capture the underlying asset volatility structure and volatility levels through time. This can contain vital information on future market behaviors. In future research, this method will be further expanded and applied to Value-at-Risk models.

Figure 1 :Figure 2 :Figure 3 :Figure 4 :

 1234 Figure 1: GOPM out-of-sample skews for 4/9/2000

Table 2 :

 2 ARPE for all models against the options time to maturity.

				Time to Maturity
	Moneyness	Model	LT (Long TTE)	MT (Medium TTE)	ST (Short TTE)	TOTAL
	DOTM	GOPM	0.179	0.246	0.384	0.267
	(Deep Out of the money)	BSOPM	0.993	1.815	1.289	1.584
		NNiv	0.167	0.269	0.358	0.273
	OTM	GOPM	0.105	0.157	0.272	0.202
	(Out of The Money)	BSOPM	0.502	0.713	0.984	0.809
		NNiv	0.102	0.154	0.262	0.195
	ATM	GOPM	0.078	0.1	0.139	0.116
	(At the money)	BSOPM	0.274	0.262	0.277	0.27
		NNiv	0.086	0.094	0.135	0.112
	ITM	GOPM	0.082	0.074	0.079	0.077
	(In The Money)	BSOPM	0.169	0.12	0.077	0.104
		NNiv	0.081	0.071	0.075	0.074
	DITM	GOPM	0.039	0.061	0.05	0.053
	(Deep In The Money)	BSOPM	0.099	0.074	0.051	0.069
		NNiv	0.098	0.066	0.058	0.068
		GOPM	0.121	0.167	0.233	0.188
	All	BSOPM	0.589	0.924	0.742	0.818
		NNiv	0.119	0.172	0.222	0.185

Table 4 :

 4 Regression results

	C	NNiv 2.097	GOPM 2.052	BSOPM 13.931
		(-46.116)	(-45.072)	(69.214)
	A	-0.327	-0.330	-0.769
		(-26.065)	(-26.306)	(-13.869)
	B	-1.900	-1.851	-13.372
		(-40.983)	(-39.865)	(-65.148)
	R 2	14.66%	13.71%	25.05%
	F-test	1047.439	1014.297	2133.957


Zhongzhi Shi

Jinpeng Yue

Gang Ma

Xi Yang

CCF-Based Awareness in Agent Model ABGP

Keywords: Compact coding, Awareness, Agent model ABGP

scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Cyborg intelligence is dedicated to integrating artificial intelligence with biological intelligence by tightly connecting machines and biological beings [START_REF] Wu | Cyborg Intelligence[END_REF]. The key issue is how to collaborate between machines and biological beings? In our project entitled Cognitive Computational Model for Brain Machine integration we use multi-agent collaboration to simulate their behaviors. We consider that under practical environment the agent should be rational. Rational agents have an explicit representation for their environment and objectives they are trying to achieve. Rationality means that the agent will always perform the most promising actions to achieve its objectives. For a rational agent faced with a complex natural scene, how to get knowledge from scenes to drive their actions? Most agent designer maybe have a common view that either create a virtual scene or set some single inflexible rules for agent to recognize surrounding.

As an internal mental model of agent, BDI model has been well recognized in philosophical and artificial intelligence area. Bratman's philosophical theory was formalized by Cohen and Levesque [START_REF] Cohen | Intention is choice with commitment[END_REF]. In their formalism, intentions are defined in terms of temporal sequences of agent's beliefs and goals. Rao and Georgeff have proposed a possible-worlds formalism for BDI architecture [START_REF] Rao | Modeling rational agents within a BDI-architecture[END_REF]. The abstract architecture they proposed comprises three dynamic data structures representing the agent's beliefs, desires, and intentions, together with an input queue of events. The update operations on beliefs, desires, and intentions are subject to respective compatibility requirements. These functions are critical in enforcing the formalized constraints upon the agent's mental attitudes. The events the system can recognize include both external events and internal events.

A cognitive model for multi-agent collaboration should consider external perception and internal mental state of agents. Awareness is knowledge created through interaction between an agent and its environment. Endsley pointed out awareness has four basic characteristics [START_REF] Endsley | Toward a Theory of Situation Awareness in Dynamic Systems[END_REF]: a) Awareness is knowledge about the state of a particular environment. b) Environments change over time, so awareness must be kept up to date. c) People maintain their awareness by interacting with the environment. d) Awareness is usually a secondary goal-that is, the overall goal is not simply For internal mental state of agents we can consult BDI model which was conceived by Bratman as a theory of human practical reasoning. Its success is based on its simplicity reducing the explanation framework for complex human behavior to the motivational stance [START_REF] Pokahr | The active components approach for distributed systems development[END_REF]. This means that the causes for actions are always related to human desires ignoring other facets of human cognition such as emotions. Another strength of the BDI model is the consistent usage of folk psychological notions that closely correspond to the way people talk about human behavior.

In terms of above considerations we propose a cognitive model ABGP for multiagent collaboration through 4-tuple <Awareness, Belief, Goal, Plan> [START_REF] Shi | A Cognitive Model for Multi-Agent Collaboration[END_REF]. Awareness is an information pathway connecting to the world (including natural scenes and other agents in multi-agent system). Beliefs can be viewed as the agent's knowledge about its setting and itself. Goals make up the agent's wishes and drive the course of its actions. Plans represent agent's means to achieve its goals. If we expect the agent constructed by ABGP model has an ability to sense directly the natural scenes, a new awareness pathway must to be proposed.

In computer vision, visual feature extraction is vital for object identification, image retrieval, scene classification, etc. These features are complement and should be synthesized together in computer vision applications. For example, edge and texture features are suitable for landscape and building scene classification; shape features are suitable to recognize objects such as apples. However, existing applications mainly focus on one kind of features such as the wildly used SIFT [START_REF] Lowe | Distinctive image features from scale invariant keypoints[END_REF] texture feature. To improve the feature discriminabilty, we put forward that complement features corresponding to different reacting regions of brain should be binding together to simulate the brain.

Wu [START_REF] Wu | Bundling Features for Large Scale Partial-Duplicate Web Image Search[END_REF] proposed a method to bundle two complement feature detecting methods together, i.e. SIFT [START_REF] Lowe | Distinctive image features from scale invariant keypoints[END_REF] and MSER [START_REF] Matas | Robust wide baseline stereo from maximally stable extremal regions[END_REF]. Xie [START_REF] Xie | Effective and Efficient Image Copy Detection Based on GPU[END_REF] also bundles two detectors together. However, these two methods are detector binding methods, not considering the description aspects. The description of visual features is vital for the analysis of visual contents. Many of such methods have been proposed to code features into more compact representations, such as binary codes.

For environment awareness we propose a framework named CCF (Coding and Combining Features) to combine feature descriptors together based on the compact coding. In the CCF framework we take advantage of complement feature extracting methods, compact coding methods and multi-kernel hashing together. We encode fea-tures into compact binary codes by an effective Locality Preserving Coding method and combine the codes together by multi-kernel hashing. The combined feature achieves a good trade-off between discriminability, robust and learning efficiency. And thus our method achieves a better performance in the experiments.

In previous work we have described agent model ABGP [START_REF] Shi | A Cognitive Model for Multi-Agent Collaboration[END_REF]. In this paper we describe especially on environment awareness. This paper is organized as follows.

Briefly introduction of agent model ABGP is given in Section 2. Section 3 describes the coding and combining features framework. The experimental results are put into Section 4. Section 5 concludes with a discussion on environment awareness of rational agents.

Agent Model ABGP

In computer science and artificial intelligence, agent can be viewed as perceiving its environment information through sensors and acting environment through effectors [START_REF] Shi | Cognitive Cycle in Mind Model CAM[END_REF]. A cognitive model for rational agent should especially consider external perception and internal mental state. The external perception as a knowledge is created through interaction between an agent and its world. A cognitive model ABGP (shown as in Figure 1) is represented as a 4-tuple framework as Awareness; Belief; Goal; Plan, where awareness is an information pathway connecting to the world and a relationship between agents. Awareness is defined as 2-tuple MA = Element, Relation [START_REF] Shi | A Cognitive Model for Multi-Agent Collaboration[END_REF].

Fig. 1. Agent model ABGP

Belief can be viewed as the agent's knowledge about its environment and itself. Goal represents the concrete motivations that influence an agent's behaviors. Plan is used to achieve agent's goals. Policy can be seen as a state transition function, and multi-agent system changes their state based on policies.

In this paper, we only discuss how to identify who is participating. In order to identify an object we propose a coding and combining features framework described in next section.

Coding and Combining Features Framework

Introduction of the Framework

The CCF Framework process an image into a set of codes, and then bundles the codes together to accomplish recognition or identification tasks. The model is composed of three steps: isting feature e descriptors can be adopted in the model to simulate the visual processing of brain. 2. Compact coding. After various features are extracted, we compact them into efficient and effective codes. To preserve as much information as possible during the coding process, we propose a novel coding method which will be introduced in detail in the next section. 3. Learning Combined Features. The codes generated in the compact coding step are then combined by multi-kernel hashing to make a more discriminative feature representation. Since different features such as color, texture impose different information, they are complement and effective in different situations.

Compact Coding

In this step, our object is not only to encode the features to a more robust and compact codes, but also to bind the features that are visually similar but change slightly in visual contents. We seek a binary coding approach that preserves the visual similarity relationships under the encoding Hamming space. Specifically, we propose a Locality Preserving Coding (LPC) method to learn robust binary codes by exploring the underlying manifold structure of training samples, with effective and efficient optimization.

The objective in this step is to code the visually similar patches into similar binary codes. In this section, we use affine transformation to simulate patches with similar contents but different in scales, slight transitions, and small content variations, as is shown in Figure 3. The other transformations such as lighting, Gaussian noise, scaling, etc can also be used to simulate visually similar patches. Then binary codes are learned on the patch by exploring the manifold structure of patch descriptors.

We aim to preserve the manifold structure of visual similar features when compacting descriptors to binary codes. Let X={x1,...,xn} be a set of d-dimensional visual descriptors. Suppose we want to get a k-bit code yi of xi, then k hash functions leading to k Hamming embeddings are needed. We use linear projection and threshold to encode X, and then binary code is computed using the following equation:

yi = sign ( Pxi T + t ) ( 1
)
where P is a k*d matrix and t is a k*1 vector. The projection matrix P is the key of embedding and threshold t is the key of binarization. To encode the visually similar descriptors into the same binary code, we compute P by solving an optimization problem and utilizing the visual relationships between descriptors.

Given a matrix W with weights characterizing the similarity of two image patches, we want to learn a P to preserve the local structure, which satisfies the following:

2 ' ' min imize i j ij ij y y w   : (2)
where y' is the data projected by P, i.e. y'=Px T and wij is defined as (3) or (4) : 2 exp( / ) If and are visully similar 0, Otherwise

i j i j ij x x x x w                (3)
1, If and are visully similar 0, Otherwise

j ij w           i x x (4)
The similarity learning method is the spirit of LPP and P can be obtained by solving a generalized Eigen value problem as in [START_REF] He | Locality Preserving Projections[END_REF]. Then we concatenate the generated codes to the final decision code. The similarity between two objects can be measured by the distance between their final decision codes. A smaller distance means the two objects are more similar.

Learning Combined-Feature

In this section, the codes of different features are combined by multi kernel hashing. Suppose we are given a set of N training binary codes

L p lp l l V W Z l L      (4)
The p-th binary code after multi-kernel hashing is:

( ( ) ) T p p p y sign V b     (5)
Then the final combined code after multi-kernel hashing of the compact code x = [x1,…xm] is:

The formulation forces the learned hash functions to preserve the given similarity as much as possible, by optimizing both hyperplane vectors W:

2 2 ,1 1 1 1 min 2 1 . . 0, 0 N ij i j F ij N N T i i i i i S Y Y V s t Y YY N            (6) 1 ( [ ( , ),..., ( , )]
)

TT l y sign W K x Z K x Z b 
The optimization problem can be solved by the relaxed problem and details can be found in [START_REF] Liu | Compact Kernel Hashing with Multiple Features[END_REF].

The CCF framework can be applied to the object retrieval and recognition task. Take retrieval for example, the similarity between two objects can be measured by the distance of their final decision codes. The hamming distance is used to measure the similarity. A smaller distance means the two objects are more similar in the manifold structure.

Experimental Results

In our CCF framework, compact coding and multi-kernel hashing to combine features are two key steps. Firstly, we evaluate the independent compact coding step. Secondly, we evaluate the multi-kernel hashing by combining two different features.

Compact Coding Evaluation

Dataset. We simulate the affine transformations of images selected from INRIA Holiday, utilize SIFT to detect features and generate visually similar image patches.

There are totally 10k groups, some of which are illustrated in Figure 3. Each group of image patches is similar in vision but changes in computer representations. The objective of compact coding is to encode one group of patches into the same binary code. We select 5k groups randomly for training and the rest for testing.

Fig. 3. Samples of evaluation dataset

We compare our compact coding method with LSH (Locality Sensitive Hashing) [START_REF] Datar | Locality-sensitive hashing scheme based on pstable distributions[END_REF], SH (Spectral Hashing) [START_REF] Weiss | Spectral hashing[END_REF], LDAHash (Linear Discriminant Analysis Hash) [START_REF] Strecha | LDAHash: Improved Matching with Smaller Descriptors[END_REF] which are coding methods widely used in multimedia retrieval task. The experiment conducts image patch retrieval using these methods and our coding method, the results are shown in Figure 4. The LPH refers to our method using equation (3), while LPH-1 refers to the method using equation (4).

Figure 4 uses recall and rate-of-codes-retrieved curve to evaluate the retrieval task. A higher recall means more correct similar patches are found, which indicates the image patch retrieval accuracy. The rate of codes retrieved indicates the noises contained in the final results. And thus a lower rate means lower noises and the number of incorrect patches is smaller. We can conclude from the figure that our compact coding method achieves a better performance in this task. The reason is that our coding method not only utilizes the supervised visual information, but also considers the manifold structure of data.

Fig. 4. Comparison of compact coding methods

Feature Combining Evaluation

Then we evaluate the combined feature on the Ukbench [START_REF] Nister | Scalable Recognition with a Vocabulary Tree[END_REF] image retrieval dataset, which contains 10,200 images including groups of 4 similar images. In this experiment, we combine texture histogram and color histogram together based on the compact coding. The texture feature is extracted by computing texture histogram from image patches, and the dimensionality is 80. The color feature is extracted by computing quantized color histogram and the dimensionality is 27. And the compact code is of 64-bit, which consumes much less memory.

Fig. 5. Combined feature evaluation

From Figure 5, we can see that the combined feature achieves a higher recall than the color histogram and the texture feature. The combined feature utilizes two complementary features and benefit from compact coding, and thus features generated by our CCF framework is more discriminative and robust. Our method is effective with much less memory consumption, which can be used in large-scale applications.

We also use the CIFAR-10 dataset [18] to evaluate multi-kernel hashing based on compact coding, which consists of 60k 32*32 color images in 10 classes with 6k images per class. There are 50k training images and 10k test images. For each image, two features are extracted to evaluate our coding and combining framework, i.e. GIST feature of 384-D and bag of visual words of 300-D quantized from dense SIFT features of 8*8 patches with 4 space overlap. The GIST feature and SIFT features are extracted, compactly coded by LPC and then combined by multi-kernel hashing. The combining method will be evaluated in this experiment.

From the Figure 6 we can see that the precision and recall of our CCF method outperforms LSH with both 16bits and 32bits.

Fig. 6. Precision and recall comparison results

Conclusions

We propose a CCF novel feature combining framework to generate a robust and discriminative feature representation with effective coding technique. In the framework, features are encoded into compact codes which represent features with much more information and less units. Then the compact codes are combined to the final discriminative and robust feature by multi-kernel hashing.

The CCF framework is applied to environment awareness for agent model ABGP, which combines external perception and internal mental state. The CCF framework also can be applied many other feature extraction methods. Actually, the weights of different features can be utilized and learned from training samples.

Fig. 2 . 1 .

 21 Fig. 2. Coding and Combining Features Framework 1. Visual feature extraction. Visual features such as color histogram, Gabor filters, intensity histogram, etc. are widely used in content based image analysis. In Figure 2, there are only three different features referred as samples. Actually, most of ex-

1 (

 1 . The hash codes Y with p bits are learned to preserve the manifold structure of visual similar features by multi-kernel hashing. For each feature, let ij K denote the multi-kernel function between the i-th and j-th data, which is linearly combined by kernels for each feature m ij K . Let ()   denote the embedding function of the p-th multi-kernel function, the hyperplane vector p V in the kernel space can be represented as a combination of L landmarks Zl embedded in corresponding kernel space: ), 1,...

Acknowledgment.

This work was supported by the National Program on Key Basic Research Project (973 Program) (No. 2013CB329502), National Natural Science Foundation of China (61035003), National Science and Technology Support Program (2012BA107B02).


Morteza Saberi

Zahra Saberi

ANOVA Based Approch for Efficient Customer Recognition: Dealing with Common Names

Keywords: Contact centres, customer recognition, Customer common name, I

This study proposes an Analysis of Variance (ANOVA) technique that focuses on the efficient recognition of customers with common names. The continuous improvement of Information and communications technologies (ICT) has led customers to have new expectations and concerns from their related organization. These new expectations bring various difficulties for organizations' help desk to meet their customers' needs. In this paper, we propose a technique that provides the most beneficial information to the Customer service representative that will assist in the efficient recognition of the customer. The proposed algorithm determines which features of a customer should be asked that would result in his/her prompt recognition. Moreover, to have a clean database, the framework uses the features of customers for which a standard format is available such as street address, month of birth etc. We evaluate our algorithm on synthetic dataset and demonstrate how we can recognize the right customer in the optimum manner.

INTRODUCTION

Customer relationship management (CRM) is a framework for managing a company's interactions with current and future customers [START_REF] Faed | An Intelligent Customer Complaint Management System with Application to the Transport and Logistics Industry[END_REF]2]. In this highly competitive world, it is essential for every organization to have an efficient and smart CRM system. One important part of CRM system is contact center which is in direct contact with the customers. Contact center has been termed as the new version of call centers which allow customers to express their queries via different communication channels: telephone, touch-point telephone, fax, letter, email and online live chat [START_REF] Saberi | Intelligent Online Customer Recognition Framework: Dealing with Common Personal Names[END_REF]. However, for the contact centers to be effective, they need to be able to identify the customers in question from their database efficiently and effectively. To achieve that, in this study a framework is proposed that utilizes the ANOVA technique to assist contact centers with efficient customer recognition which using telephone and online live chat as the main communication channels.

Currently, individuals are in contact with organization via diverse communication channels [START_REF] Pan | Using e-CRM for a unified view of the customer[END_REF]. This diversity has two impacts: increasing easiness and flexibility of communication and producing dirty data [START_REF] Hussain | A Customer Relationship Management ecosystem that utilizes multiple sources and types of information conjointly[END_REF]. The first one is beneficial for the customers while the second one can be a risk for the efficient working of a CRM system. Performance of CRM systems is decreased by existence of dirty data in them. Another issue with CRM system is that customers have different IDs from different organizations. It should be noted that they do not normally memorize all of their IDs. From a psychological perspective, customers prefer to be recognized by their name as their identity, not by a customer number or ID number. The feeling of ownership achieved from a name is much greater than that achieved from address, phone number etc. In some cultures, people who have nicknames prefer to use them as their official given names. Recognizing customers using their name is not a difficult task if the same or similar names are not available in the organization database. However, the recognition is difficult when there are common names in the CRM database. As an example, 7.4% of family name in china is 'Li' and by considering 1 milliard as the china population it is 74 million individuals with "Li" as the family name [START_REF] Saberi | In-house crowdsourcing-based entity resolution: dealing with common names[END_REF] In the current study, we have focused on customer recognition in the case of existence of the common name in CRM database by making use of ANOVA Based Approach. The main aim of the proposed algorithm is to recognize the customer by asking the minimum number of questions with them. The output of the algorithm is a sequence of most informative questions (customer features) that needs to be asked from the customer. It achieves this by using two sources of information: customer record(s) in organization database and customer interactions (answer) with the CSR (or: information provided by customers in their interaction) The proposed framework links the customer interactions (responses) with the organization database in order to fulfill customer recognition task. The first data source of information (CRM database) can contain noisy and dirty data.

Figure 1. Problem definition

The paper is organized as follows: Section II defines the problem along with a discussion on common name issue for contact centers. The framework of ANOVA based approach for efficient customer recognition is explained in Section III.

II. COMMON NAMES Individuals use their personal names for communication purposes [START_REF] Saberi | In-house crowdsourcing-based entity resolution: dealing with common names[END_REF]. A personal name usually includes a given name and a surname (or family name). In some countries and cultures, a middle name is used as part of the personal name. For example, in Brazil the mother's family name is given to the child as his/her middle name at birth. In some countries, it is common for individuals to have only one name (mononymous) by which they are recognized. It is interesting to note the various origins of given names:

It is evident that various factors such as culture, language, religion, history, translation to a new language, and environment may determine the personal name given to an individual [START_REF] Fisher | Studies in Crop Variation. I. An examination of the yield of dressed grain from Broadbalk[END_REF]. These fields have been also studied by researchers and are known as Anthroponymy study. Briefly the mentioned various factors lead to produce different variations of personal names.

Figures. Some figures are presented here about the statistic of popular and common name. Table 1 shows the top five popular boys and girls name in 2013 in UNSW, Australia. It is clear even within a given state the number of common name is high. This issue is more severe in countries such china. As an example, 7.4% of family name in china is 'Li' and by considering 1 milliard as the china population it is 74 million individuals with "Li" as the family name. Some organization such as health care, insurance, telecommunications company that have high number of customer are more faced with the issue of common name.

III. ANOVA BASED APPROCH FOR EFFICIENT CUSTOMER RECOGNITION

This section presents the general framework of interactive customer feature selection. This framework assists CRM systems with customer recognition when the system faces the common name issue. The proposed framework relies on two integrated modules as shown in Figure 1.

Analysis of Variance(ANOVA) is developed by Fisher to find out whether is it any difference among groups average [START_REF] Fisher | Studies in Crop Variation. I. An examination of the yield of dressed grain from Broadbalk[END_REF]. We performed ANOVA on customer standard features to find if means of these features are statistically different or not. Null hypothesis can be accepted or rejected by performing ANOVA F-test in a consequence. We use average of feature values as the index for selecting the first question if ANOVA shows no difference among standard features (Null Hypothesis acceptance). Also if the null hypothesis in ANOVA F-test is rejected, multiple pair comparison is performed to find the most informative question. Before presenting the proposed Duncan's multiple range test (DMRT) based algorithm in a formal way it has been explained with the following three examples.

Example 1.

This example shows how we select the first question when the null hypothesis is rejected. A multiple pair comparison is performed in this case, as shown in Table 2. The number of rejections associated with each feature is highlighted in Table 3. As the maximum number belongs to Street, it has been selected in this example. This maximum number is the reason that Street is the source of rejection in the null hypothesis. Now we should answer this question:

How we should determine the optimum attribute in case of two or three nominated attributes?

As formally P-value shows how rejection or acceptance is strong, we use this value to come up to the best question (attribute). We utilize this nature of P-value that the more P-value distance with confidence levels the more robust statistical rejection. The detailed mathematical presentation of this approach has been explained later.

A. Analysis of Variance based algorithm formal definition

In the previous section we have provided intuitive example that shows how ANOVA approach help us to find the most informative question. We have two main hypothesis regarding ANOVA usage in customer recognition. The null hypothesis assume the statistically equality of all customer profile features average and on the other hand alternative hypothesis assume average of customer profile features are different. If null hypothesis is rejected then we are in need of finding the cause of this rejection. The feature that leads to this rejection (inequality of features average) is the most informative question and should be asked from the customer. Lines 3 to 18 in Figure 1 shows how find the cause of this rejection. When we get rejection the multiple pair comparison test is then performed and based on number of rejection that is associated with each feature the first feature is selected. The detail of selection is highlighted in the algorithm. Also the process of finding sequence of questions has been depicted in next section. In ANOVA based algorithm some functions have been used as their task are listed in Table 8. Return the matrix T that is average distance of correspondent member of A from other members in its column ANOVA (T)

ANOVA based algorithm (A) Input: A set of records with standard features

Perform ANOVA F-test and determine the acceptance or rejection status of Null Hypothesis.

If test reject the null hypothesis then the H is equal to 1. M ←Mul_Comp (T, 𝜶) Perform multiple pair comparison on T and returns a matrix M of pairwise comparison results with α confidence level. 𝑳 ← 𝑁_𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝐶𝑅(𝑴)

Return dataset array L that shows the number of rejection which each feature got in total pairs. 𝒛 ← 𝑀𝑀𝑀𝑅𝐶𝑀𝑀_𝐼𝑅𝐼𝑅𝑀(𝑳)

Returns indices of the maximum values of L in output vector z.

Max_Distance (T/z):

Returns indices of features which the distance between its string values is the maximum (maximal) in comparison with other features. Max_dif_Pvalue(M/z):

first calculate the difference between p-value and critical value and find index(es) with the maximum(maximal) value(s). The detail about this function has been highlighted in Figure.

In the following figures (2-4), procedures of finding out the three functions are explained: Distance, Max_Distance and Max_dif_Pvalue.

𝐝𝐃𝐃𝐃𝐃𝐃𝐃𝐃(𝐀)

Input: A set of records with standard features A, Number of rows (A) m, Normalized levenshtein distance Leven; Output: Distance of matrix A member from others 𝒅𝒅𝒅𝒅𝒅𝒅𝒅𝒅 𝑗 = 𝐴𝐴𝑅𝐹𝑀𝐴𝑅 𝑖≠ℎ (𝑁𝐶𝐹𝐶𝑀𝑀𝑅𝑧𝑅𝐼_𝐿𝑅𝐴𝑅𝑅(A(i, j), A(h, j)) Return 𝒅𝒅𝒅𝒅𝒅𝒅𝒅𝒅;

B. Generating sequence of questions by using ANOVA algorithm: Formal definition

The way of generating sequence of questions by using ANOVA is explained here. As it is stated in line 14 (Figure 5), when we have two remained feature then we select the question by using Max_distance function. Actually when we have two features using ANOVA test is meaningless and we just used simply edit distance metric. The feature with highest distance among its values is selected with this function. To have a better follow up the example has been given here as well that shows how the sequence of questions is generated in ANOVA approach. As number of rejections is equal for all three features (Table 12) the P-value is employed to determine the first question. According to the reported values in Table 13, Month is the first question that should asked from John. As John's month of birth is July, we come up with the following updated records (Table 14). As we have just two remaining features the next question is selected by using Max_distance function. Examination of Table 15 shows the next question is John's Street address.

As John's month of birth is July, we come up with the following updated records (Table 14). As we have just two remained feature the next question is selected by using Max_distance function. Examination of Table 15 shows the next question is John's Street address.

SQ=(Month, Street )

Conclusion

This study present an interactive customer feature selection to deal with common variations in personal names. Three algorithms from different schools of thoughts, information retrieval, machine learning, and statistical analysis, to find the optimum sequence of questions. These algorithms are IDF and Levenshtein based , C4.5 based and ANOVA based. The preferred approach is the one which require the minimum number of customer interactions. About 60000 records as the synthetic data are used to show the applicability of the proposed framework. Febrl software as the data generator used various parameters that these let get more insights from the framework's operation. The unique features of the proposed framework enable it to: have online responses, deal with common names, improve the cleansing of the database, have faster performance. The preferred algorithm is selected fast and smooth recognition. The framework has been designed so that it improves the cleansing quality of the CRM system database (customer"s data); a clean database improves performance and subsequently leads to better customer satisfaction.

Figure 2 .Figure 3 .Figure 4 .

 234 Figure 2. Distance function 𝐌𝐃𝐌_𝐝𝐃𝐃𝐃𝐃𝐃𝐃𝐃(𝑨|𝒛) Input: A set of records with standard features A, Number of rows (A) m, ; Output: indices of the maximum distances among each feature For 𝑅 ∈ 𝑧: (𝐴|𝑧) ← 𝐴 -𝐴(: , 𝑅) End 𝒅𝒅𝒅𝒅 𝑗 = 𝐝𝐃𝐃𝐃𝐃𝐃𝐃𝐃(𝑨|𝒛) 𝑅 * ← arg _ max 𝑗 (𝐼𝑅𝑑𝑅 𝑗 ) Return 𝑅 * ; Figure 3. Max_Distance function 𝐌𝐃𝐌_𝐝𝐃𝐝_𝐏𝐏𝐃𝐏𝐑𝐃(𝑴|𝒛) Input: A set of records with standard features A, Number of rows (A) m, Normalized levenshtein distance Leven; Output: indices of the maximum difference of P-value and confidence level 𝐼𝑅𝑑_𝐶𝐴𝑀𝑀𝑀𝑅 𝑗 = ∑ |𝐶 𝑣𝑣𝑣𝑠𝑠 (𝑅, 𝑅) -0.05| 𝑖≠𝑗 ; 𝑅 ∈ 𝑧& M(i,j)=0 𝑅 * ← arg _ max 𝑗 (𝐼𝑅𝑑_𝐶𝐴𝑀𝑀𝑀𝑅 𝑗 ) Return 𝑅 * ; Figure 4. Max_dif_Pvalue function

Table 1 . Popular Baby Names in UNSW 2013

 1

	Boys	Number	Girls	Number
	William	696	Charlotte	613
	Oliver	630	Olivia	551
	Jack	574	Amelia	540
	Noah	555	Chloe	517
	James	510	Mia	517

Table 2 . Multiple pair comparison example with 1 hypothesis acceptance

 2

	Null Hypothesis & Pairwise Comparisons	Decision	Selected
	𝜇 𝑠𝑠𝑠𝑠𝑠𝑠 = 𝜇 𝑠𝑠𝑠𝑠𝑠𝑠 = 𝜇 𝑀𝑀𝑀𝑠ℎ	reject	Question

Table 3 . Associated Number of rejection for customer features in Multiple pair comparison test (Example ) Example 2.

 3 Examination of Table 4, as the second example, shows the first question could be determined between Street & Suburb in this case. From statistical viewpoint customers month values are not different (statistically) with Street and suburb and the most informative question should be determined from Street & Suburb. Also number of rejections for these two features is equal as mentioned in Table 5.

Table 4 . Multiple pair comparison example with 2 hypothesis acceptancesTable 5 . Associated Number of rejection for customer features in Multiple pair comparison test Example 3.

 45 In Table6, we have the case in which three attribute are nominated after performing multiple pair comparison. As in Table7stated the number of rejection for all customer features is equal

Table 6 . Multiple pair comparison example with 3 hypothesis rejectionsTable 7 . Associated Number of rejection for customer features in Multiple pair comparison test

 67

Table 8 . ANOVA Algorithm functions definition

 8

		A,
		Number of rows (A) m, ANOVA F-test ANOVA;
		Output: preferable feature
		𝑻 ← 𝐃𝐃𝐃𝐃𝐃𝐃𝐃𝐃(𝐀);
	1	𝑯 ← 𝐀𝐀𝐀𝐀𝐀(𝐓);
	2	If (H=1)

  We show how ANOVA based algorithm finds Mary Miller profile which is mentioned in Table9. As stated in Table10by ANOVA F-test, Null Hypothesis is rejected and we should do the multiple comparisons test to find the sequence of questions.

		Algorithm_ANOVA(Customer Name)
		Input: X as common name, a set of records with Name (X)
		A, List of Common names C, number of customer standard
		features n, a set of standard features Z, Successful
		customer recognition flag;
		Output: Sequence of questions (features) SQ
	1	𝑰𝑰 𝑌 € 𝐶 𝑻𝑯𝑻𝑻
	2	Break
	3	Else 𝑋 ← 𝑌 End
	4	𝑨 ← 𝑅𝑅𝑅𝐶𝐹𝐼𝑑 𝑤𝑅𝑅ℎ 𝑅𝑀𝐶𝑅 𝑋
	5	𝒇𝒇𝒅𝒇, 𝒅 ← 0
	7	While flag = =0
	8	𝑘 ← 𝑅 -𝑅
	9	If (k>2 )
	10 11	𝑸 * ← 𝑨𝑻𝑨𝑨𝑨(𝐀) 𝑺𝑸(𝒅) ← 𝑸 * ; 𝒁 ← 𝒁 -{𝑸 * }
	13	Else
	14 15	𝑸 * ← 𝐌𝐃𝐌_𝐝𝐃𝐃𝐃𝐃𝐃𝐃𝐃(𝑨|𝒛) 𝑺𝑸(𝒅) ← 𝑸 *
	16	End
	17	𝒇𝒇𝒅𝒇 ← 𝐑𝐃𝐃𝐑𝐑𝐃𝐃𝐃𝐃𝐑𝐃(𝐀, 𝒌 * , 𝐩)
	18	𝒅 ← 𝑅 + 1
	19	End
	20	𝑨 ← Records with customer answer
	21	If i==n
	22	Go to 20
	23	End
	24	Go to 9
	25	Ask sequence of other features
	26	END
	27	Return SQ;
		Figure 5. ANOVA Based Approach pseudo-code
	Figure 6 also depicts flowchart of generating sequence of questions by using ANOVA algorithm.
	Figure 6. Generating sequence of questions by using ANOVA algorithm
	C. Example

Table 11 . Multiple comparisons result with correspondent P-Values Result

 11 of Multiple comparisons test can be obtained from Table11. Rejection[START_REF] Faed | An Intelligent Customer Complaint Management System with Application to the Transport and Logistics Industry[END_REF] or acceptance (0) and associated p-values are reported in this table.

Table 12 . Associated Number of rejection for customer features in Multiple pair comparison test Table 13. Max_dif_Pvalue results

 12

Table 14 . Updated dataset based on customer answer

 14

		Street	Suburb	Month of Birth
	2	Hart close	Dural	July
	3	Neerabup	Doodenanning	July

Table 15 . Max_distance function Result

 15

	Feature	Value
	Street	0.9
	Suburb	0.83