Florin Coras
email: fcoras@ac.upc.edu

Albert Cabellos-Aparicio

Jordi Domingo-Pascual

An Analytical Model for the LISP Cache Size

Keywords: LISP, Internet architecture, cache modeling, working set

Concerns regarding the scalability of the inter-domain routing have encouraged researchers to start elaborating a more robust Internet architecture. While consensus on the exact form of the solution is yet to be found, the need for a semantic decoupling of a node's location and identity is generally accepted as the only way forward. One of the most successful proposals to follow this guideline is LISP (Loc/ID Separation Protocol). Design wise, its aim is to insulate the Internet's core routing state from the dynamics of edge networks. However, this requires the introduction of a mapping system, a distributed database, that should provide the binding of the two resulting namespaces. In order to avoid frequent lookups and not to penalize the speed of packet forwarding, map-caches that store temporal bindings are provisioned in routers. In this paper, we rely on the working-set theory to build a model that accurately predicts a map-cache's performance for traffic with time translation invariance of the working-set size. We validate our model empirically using four different packet traces collected in two different campus networks.

Introduction

The fast paced growth [START_REF] Huston | BGP Report[END_REF] of the global inter-domain routing table and infrastructure has recently raised a series of concerns and spurred debate regarding the Internet's architectural inability to scale. Reasons for the growth are partly organic in nature, as new domains are continuously added to the topology, but also related to operational practices that defeat provider-based aggregation of prefixes. In this sense, multihoming, traffic engineering and allocations of providerindependent prefixes are the main drivers behind prefix de-aggregation [START_REF] Meyer | Report from the IAB Workshop on Routing and Addressing[END_REF].

In a recent Internet Advisory Board workshop [START_REF] Meyer | Report from the IAB Workshop on Routing and Addressing[END_REF] participants deemed the routing table growth as one of the Internet's most important problems and tracked down its origins to the semantic overloading of the IP addresses with both location and identity information. As a result, a set of architectures inspired by the loc/id split paradigm have been proposed [START_REF] Li | Recommendation for a Routing Architecture[END_REF] to overcome the limitation. Most notably, LISP [START_REF] Farinacci | Locator/ID Separation Protocol (LISP)[END_REF] aims to alleviate the routing state pressure exerted by edge networks on core networks by means of an identity-location separation at network level. It is designed for an incremental deployment and it relies on a pilot network [START_REF]LISP Testbed[END_REF] for experimentation.

For the binding of identifiers and locators, LISP introduces a distributed database called the mapping-system. As LISP routers are typically domain border routers, the identifier resolution delays through the mapping system (hundreds of ms [START_REF] Jakab | LISP-TREE: A DNS Hierarchy to Support the LISP Mapping System. Selected Areas in Communications[END_REF]) are several orders of magnitude higher than packet inter-arrival times (ns). Therefore, to speed up intra-router packet forwarding and to protect the mapping system from floods of resolution requests, the LISP routers are provisioned with mapping caches (map-caches) that temporarily store in use mappings. Given the map-cache's primordial role in assuring LISP's data-plane (packet forwarding) and control-plane (mapping-system) scalability, a better understanding of its behavior is crucial.

In this paper we aim to improve the understanding of the map-cache's performance by developing an analytical model that links miss rate with cache size. Specifically, we rely on the working-set theory [START_REF] Denning | The working set model for program behavior[END_REF] to build a model that accurately predicts the performance based on simple and measurable parameters of packet traces that possess time translation invariance of the working-set curves. We validate our model empirically using four different packet traces collected in two different campus networks. Our findings show that the miss rate decreases at an accelerated pace with the cache's size, and that even for a relative small size (5% of the Internet's aggregated routing table) the performance is acceptable (below 0.6% miss-rate).

LISP Overview

LISP [START_REF] Farinacci | Locator/ID Separation Protocol (LISP)[END_REF] is one [START_REF] Li | Recommendation for a Routing Architecture[END_REF] of the recently emerged architectural solutions to the Internet's scalability problem [START_REF] Meyer | Report from the IAB Workshop on Routing and Addressing[END_REF]. Its main goal is that of splitting the semantics of IP addresses with the aim of forming two namespaces that unambiguously identify core (locators) and edge (identifiers) network objects. To facilitate transition from the current Internet infrastructure, both of the resulting namespaces use the existing IP addressing scheme. As a result, the split does not affect routing within existing stub or transit networks. Nevertheless, as identifiers and locators bear relevance only within their respective namespaces, a form of conversion, from one to the other, has to be performed at border points between core and edge networks. Traditionally, the two techniques that may be employed for a fast translation are address rewriting [START_REF] O'dell | GSE -An Alternate Addressing Architecture for IPv6[END_REF] and map-and-encap [START_REF] Hinden | New Scheme for Internet Routing and Addressing (ENCAPS) for IPNG[END_REF]. Unfortunately, besides their need for data plane modifications, both also require the introduction of a new control-plane mapping function able to provide bindings that link identifiers to locators. Out of the two, LISP enabled border routers make use of the latter. Therefore, prior to forwarding a host generated packet, a LISP router maps the destination address, or Endpoint IDentifier (EID), to a corresponding destination Routing LOCator (RLOC) by means of a LISP specific distributed database, called the mapping system [START_REF] Farinacci | LISP Alternative Topology (LISP+ALT)[END_REF][START_REF] Fuller | LISP Delegated Database Tree (LISP-DDT)[END_REF][START_REF] Jakab | LISP-TREE: A DNS Hierarchy to Support the LISP Mapping System. Selected Areas in Communications[END_REF][START_REF] Menth | FIRMS: a future Internet mapping system. Selected Areas in Communications[END_REF]. Once a mapping is obtained, the border router tunnels the packet from source edge to corresponding destination edge network by means of an encapsulation with a 1). At the receiving router, the packet is decapsulated and forwarded to its intended destination. In LISP parlance, the source router, that performs the encapsulation, is called an Ingress Tunnel Router (ITR) whereas the one performing the decapsulation is named the Egress Tunnel Router (ETR). One that performs both functions is referred to as an xTR.

Because all packets need to be encapsulated, the packet throughput of an ITR is highly dependent on the time needed to obtain a mapping. In consequence, all ITRs are provisioned with a cache, called map-cache, that stores the recently used EID-prefix-to-RLOC mappings to avoid frequent EID resolutions through the mapping system. Stale entries are avoided with the help of validity periods (timeouts) that mappings carry as attributes. One can easily observe that the map-cache is most efficient in situations when destination EIDs present high temporal and/or spatial locality and that its size depends on the diversity of the visited destinations. As a result, a cache's performance depends entirely on its provisioned size and on traffic characteristics. Given the map-cache's critical role in the LISP architecture, a good understanding of the properties linking its size and performance with the traffic's characteristics is fundamental.

LISP Cache Modeling

This section presents the theoretical background and methodology used to model the LISP map-cache's performance. After a brief presentation of the working-set model we perform an analysis of the traffic pertaining to several network traffic traces. The observed traffic properties enable us to analytically link cache size and miss rate.

Working-Set Theory

As our goal is to determine suitable caching strategies and to better model their performance for LISP routers, we leverage previous resource allocation and cache performance research carried out in the field of operating systems. Consequently, in order to unify language, we are forced to draw parallels between concepts pertaining to our two disciplines. We associate to what systems understand by a program a network traffic trace, and in a similar vein, to a page an address prefix.

Although seemingly unrelated, from an abstract point of view, the properties of the above pairs of objects influence in similar ways a cache's performance. We depict this point further in what follows.

For operating systems, a general resource allocation treatment was possible after it was observed that programs more or less obey the so called principle of locality. In such situations, a program's past referenced pages may be used as a good predictor for near future, to be re-referenced pages. We speculate that network traffic traces might roughly obey the same principle mainly because of flow burstiness in time but also due to traffic aggregation. Consequently, we try to evaluate the feasibility of in-router prefix caching by first building and then using a working-set model for network traffic.

In what follows, in order to avoid repetitive text, we shall be using the term unit of reference as a substitute for both pages and prefixes; and reference set to represent the set of all referenced pages or prefixes. Further, given a reference set N, we define a reference string as the sequence ρ = r 1 r 2 . . . r i . . . where each unit r i belongs to N.

As explained by Denning in [START_REF] Denning | Properties of the working-set model[END_REF], a working-set analysis in this context may be performed only if based on three constraints that provide for a more rigorous definition for locality of reference:

1. Reference strings are unending 2. The stochastic mechanism underlying the generation of a reference string is stationary, i.e. independent of absolute time origin. 3. For all t > 0, r t and r t+x become uncorrelated as x → ∞

The first of the constraints, though obviously not fulfillable, introduces an insignificant error because the reference strings generated by practical programs or traces are long from a statistical standpoint. The third of the assumptions requires that the references become uncorrelated as the distance (in units) goes to infinity. This can usually be asserted as being true in practice. The most restrictive of the three is the second assumption which limits the analysis to a locality where all three constraints, including stationarity are satisfied.

If all of the above requirements are satisfied, and t is a measure of time in units, then we can formally define the working-set W (t, T ), as: the set of distinct units that have been referenced among the T most recent references, or in the time interval [t -T + 1, t] (see Fig. 2). In accordance with [START_REF] Denning | Properties of the working-set model[END_REF] we shall refer to T as the window size. Also, we will be using the term working-set curve when referring to W (t, T ) as a function of T , when t is constant.

We exploit the above definition to present some of the working-set's properties of further use in our analysis. For a broader scope discussion of the subject and complete proofs, the interested reader is referred to [START_REF] Denning | Properties of the working-set model[END_REF]. The first of the properties we are interested in is the average working-set size, s(T). It measures the growth of the working-set with respect to the size of the window T, extending in the past, but independent of absolute time t. If w(t,T) measures the number of units in W(t,T) then, considering the first locality property, one can compute s(T) as the averaged working-set size over an infinite number of windows:

s (T ) = lim k→∞ 1 k k t=1 w(t, T ) (1)
It is also shown in [START_REF] Denning | Properties of the working-set model[END_REF] that the the miss rate, m(T), which measures the number of units of reference per unit time returning to the working-set, is the derivative of the previous function:

m(T ) = s(T + 1) -s(T ) (2)
In other words, if both s(T ) and m(T ) are viewed as functions of T, the miss rate can be regarded as the slope of the average working-set size. Finally, the sign inverted slope of the miss rate function, the second slope of s(T ), represents the average interreference density function.

-f (T + 1) = m(T + 1) -m(T ) (3)

Traffic Properties

In order to ascertain the practical feasibility of using the working-set model to evaluate a LISP cache's performance we applied the theory presented in Section 3.1 to several network traffic traces. Details regarding the network captures can be found in Section 4.1. Foremost, we were interested in discovering if our traces satisfy the three constraints introduced in Section 3.1. As previously explained, the first and third introduce negligible errors and thus present no practical limitations. In order to verify the second, and therefore determine the trace segments generated by distinct stationary processes, we devised a simple experiment. For each trace we computed multiple empirical destination prefix working-set curves with start times spanning one day and spaced by half an hour. Intuitively, we were expecting to discover that curves with close start times have a similar growth shape (cluster), whereas those separated by larger time gaps behave differently.

By necessity [START_REF] Denning | Properties of the working-set model[END_REF], if working-set curves are generated by the same stationary process then, they will tend to cluster. For a certain window size the working-set size should be normally distributed. In other words, one may use the clusters of the working-set curves to discriminate between trace segments with different underlying generating processes. Figure 3 presents the results obtained in log-log plots. Surprisingly, all traces exhibit a strong clustering and sublinear growth, due to locality, of the working-set curves. We also tested and confirmed (not shown here) that the interreference interval and the relative frequency of reference distributions for our traces are approximately time translation invariant. Only upc 09 presents a subtle time-of-day behavior with two perceptible clusters while upc 11b and auck 08 each have one discordant curve that seems to be due to localized scanning attacks. Nevertheless, the results suggest that one could approximate the traces as being generated by a stationary process and as an implication, that any conclusions drawn after analyzing the average working set size function would characterize the whole trace. Similarly, Kim et al. observed in [START_REF] Kim | Revisiting Route Caching: The World Should Be Flat[END_REF] that the working-set size for prefixes tends to be highly stable with time for traffic pertaining to a large ISP. It's worth noting that we do not assume that all Internet traffic possesses this approximate time translation invariance of the working-set curves. And in fact, we require that the model we develop further be applied only to traces that have it.

Analytical Model

Considering that the working-set, W (t, T ), always contains the w(t, T ) most recently referenced units then, the time translation invariance of w(t, T ) for a constant T implies that the working-set actually models a cache of fixed size. Similarly, a cache of size c that uses the Least Recently Used (LRU) eviction policy will always store the c most recently referenced units. Therefore, if s(T ) = c, the working-set simulates a LRU eviction policy. In other words, due to the time translation invariance of the working-set curves the working-set can be seen as modeling a LRU cache.

With hindsight, one can recognize that the empirical working-set curves from Fig. 3 are piecewise linear when depicted in log-log scale. The observation enabled us to compute for each trace the average working-set size function by means of a piecewise linear fit of the log-log scale plot. As a result, we obtained estimates of both the slope α and the y-intercept β for all of a working-set's segments. We limited the number of knots to just three, however if better fits are desired more knots can be used. Figure 4 presents the goodness of fit for two of our traces. Next, through conversion to linear scale the equations become piecewise power law of the type:

s f it (u) = exp(β(u))u α(u) (4)
Where u represents the number of referenced destination prefixes, s f it (u) is the fitted working-set size function and α(u) and β(u) are piecewise constant functions obtained through fitting. With the help of (2) one can estimate the miss rate for a trace by computing the derivative of s f it like:

m est (u) = exp(β(u)) α(u) u α(u)-1 (5)
Combing the last two equations one obtains an analytical relation that links the cache size and the estimated miss rate.

m est (c) = exp β * (c) α * (c) α * (c) c 1-1 α * (c) (6)
Where, c represents the cache size in number of entries and α * (c) and β * (c) are piecewise constant functions with knees dependent on c. We put to test the accuracy of the above equation in Section 4.3.

Evaluation

In this section, we present the four data sets used to build and evaluate the map-cache model. We then describe the simulator employed in the empirical

Traces and IP Aggregation

Four one-day packet traces were used for the purpose of our experiments. Three of them have been captured at the 2Gbps link connecting several of our University's campus networks to the Catalan Research Network (CESCA) and consist only of egress traffic. UPC Campus has more than 36k users. One dates back to May 2009 while the other two are from October 2011. The fourth trace belongs to the University of Auckland and has been downloaded from a public trace repository [20]. Its capture date is March 2008 and it consists of University egressing traffic. Further, the addresses have been anonymized and one hour's worth of midday traffic, from 12 to 13, is missing. We shall further refer to these four traces as upc 09, upc 11a, upc 11b and auck 08 respectively. Both for the evaluation of the working-set in Section 3.3 and for the cache performance evaluation to be presented in Section 4.3, IP addresses had to be mapped to their corresponding prefixes. We considered EID-prefixes to be of BGP-prefix granularity. In the case of UPC traces, we used BGP routing tables downloaded from the RouteViews archive [START_REF]RouteViews Project[END_REF] that matched the exact capture date of the traffic traces. The only preprocessing we performed was to filter out more specific prefixes. Generally, such prefixes are used for traffic engineering purposes however, the LISP protocol provides mechanisms for a more efficient management of these functions that do not require EID-prefix de-aggregation. In the case of auck 08, the anonymized traffic is prefix preserving but the lack of an anonymized routing table made it impossible for us to determine the exact clustering of anonymized IPs into prefixes. Consequently, we constructed a virtual routing table made up of all prefixes with a 24 bit netmask. We chose the 24 bit limit as it is the longest netmask (corresponding to the most specific prefix) currently accepted for BGP announcements in the Internet's DFZ.

Simulator

We indirectly assess the effectiveness of the working-set model as a tool for LISP cache performance evaluation by practically testing the soundness of equation [START_REF] Feldmeier | Improving gateway performance with a routing-table cache[END_REF]. For this we implemented a packet trace based simulator that mimics a subset of a LISP ITR's functionality. In short, for each processed packet, the simulator maps the destination IP address to a prefix in accordance with the methodology presented in Section 4.1. If this prefix is already stored in the ITR's cache, no further processing is done and the simulation continues with the next packet. Should the prefix not yet be stored in the cache, two possibilities arise. First, if the cache is not full, the destination prefix is stored in and the processing proceeds to the next packet. Second, if the cache is full, an entry is evicted, the new prefix is stored in and then the simulator moves to the next packet. The entry to be evicted is chosen according to the LRU eviction policy. We use LRU because, as mentioned in Section 3.3, its performance should be appropriately described by equation ( 6) for our traffic.

Results

We ran simulations with several cache sizes for all traces. Figure 5 presents the results for just two, upc 09 and upc 11a, of our traffic captures as they are representative for all four. Cache size is normalized with routing table size. It can be noticed that the absolute error of the estimation is negligible when compared to simulation results. Even in the case of upc 09, the only trace to present a more pronounced time-of-day behavior, the absolute error is of small proportions. Further, the model appropriately predicts that even for small LISP cache sizes the performance still stays acceptable, fact also observed by [START_REF] Iannone | On the Cost of Caching Locator/ID Mappings[END_REF][START_REF] Kim | A deep dive into the LISP cache and what ISPs should know about it[END_REF][START_REF] Jakab | LISP-TREE: A DNS Hierarchy to Support the LISP Mapping System. Selected Areas in Communications[END_REF]. This is even more remarkable as we do not consider TTL, a timeout after which stale entries are removed, in our simulation.

Because of its proven good performance, we can now recommend the use of the LRU eviction policy in LISP caches, at least for traces that present an approximate time translation invariance of the working-set curves. Still, the diversity of our data sets and previous results from Kim [START_REF] Kim | Revisiting Route Caching: The World Should Be Flat[END_REF] suggest that this property is not due to an isolated event. In this situation, equation ( 6) may be used to dimension the cache size according to the desired miss rate. Further, the prediction of its mathematical expression, due to discontinuity at the knots, is that miss rate decreases at an accelerated pace with cache size and finally settles to a power law decrease. However, the speed of the decrease depends on the degree of locality present in the trace. This leads us to conclude that cache sizes need not be very large for obtaining good performance. For instance, in the case of upc 11a, for a cache having 8.4k entries (0.05% of the Internet's aggregated DFZ routing table) the miss rate is around 0.6%. Feldmeier [START_REF] Feldmeier | Improving gateway performance with a routing-table cache[END_REF] and Jain [START_REF] Jain | Characteristics of destination address locality in computer networks: A comparison of caching schemes[END_REF] were among the first to evaluate the possibility of performing destination address caching by exploiting the locality of the reference strings in network environments. Feldmeier analyzed traffic on a gateway router and showed that caching of both flat and prefix addresses can significantly reduce routing table lookup times. Jain however performed his analysis in an Ethernet environment. He was forced to concede that despite the locality observed in the traffic, small cache performance was struggling due to traffic generated by protocols with deterministic behavior. Both works were fundamental to the field however their results were empirical and date back to the beginning of the 1990s, years when the Internet was still in its infancy. Recently, Kim et al. [START_REF] Kim | Revisiting Route Caching: The World Should Be Flat[END_REF] showed the feasibility of route caching after performing a measurement study within the operational confinement of an ISP's network. They show by means of an experimental evaluation that LRU performs close to an optimal eviction policy and that working-set size is generally stable with time. We also observe the stability of the working-set for our data sets but we further leverage it to build a LRU model instead of just empirically evaluating its performance.

Iannone et al. [START_REF] Iannone | On the Cost of Caching Locator/ID Mappings[END_REF] performed an initial trace driven study of the LISP mapcache performance. Instead of limiting the cache size by using an eviction policy, their cache implementation evicted stale entries after a configurable timeout value. Further, Kim et al. [START_REF] Kim | A deep dive into the LISP cache and what ISPs should know about it[END_REF] have both extended and confirmed the previous results with the help of a larger, ISP trace and by considering LISP security aspects in their evaluation. Ignoring security concerns, which we did not consider, and despite differences regarding the cache eviction policy, the results of these last two works seem to be in agreement with ours. Zhang et al. [START_REF] Zhang | Evaluating the performance on ID/Loc mapping[END_REF] performed a trace based Loc/ID mapping cache performance analysis assuming a LRU eviction policy. They used two 24-hour traffic traces captured at two egressing links of the China Education and Research Network backbone network. They concluded that a small cache can offer good results. Finally, using trace upc 09, Jakab et al. [START_REF] Jakab | LISP-TREE: A DNS Hierarchy to Support the LISP Mapping System. Selected Areas in Communications[END_REF] analyzed the performance of several LISP mapping systems and, without focusing on a cache analysis, also observed very low miss rates for a cache model similar to that used in [START_REF] Iannone | On the Cost of Caching Locator/ID Mappings[END_REF]. Our work confirms previous LISP cache analysis results however, it also tries to provide a better understanding of the reasons behind the relatively good performance of the LISP cache. In this sense it introduces a cache model that could be used to theoretically evaluate or dimension for operational needs the caching performance.

Conclusions

The location/identity split paradigm has been recently recommended as the solution to Internet's scalability problems. Out of the proposals to follow its guidelines, LISP seems to be the one to have drawn the largest amounts of attention and support. In the set of newly introduced architectural components, the map-cache is one of the most important to LISP's own scalability and also the subject of our analysis. Given that caches have their performance driven by the characteristics of the traffic they serve, we proposed an evaluation that links the LISP map-cache performance with measurable, intrinsic properties of the traffic processed by a LISP router. In this sense, we advanced the use of the workingset model [START_REF] Denning | The working set model for program behavior[END_REF] as a tool to capture the mentioned traffic properties but also as a performance predictor. Accordingly, we also noted that the time-translation invariance of the working-set curves is a constraint that traffic traces need to observe for the theory to be applicable. After we established that our data sets are amenable to working-set modeling we deduced an analytical link between the cache size and miss rate. Finally, we validated our theoretical result by means of simulation and with the help of traffic traces collected in two different campus networks.

We note that the predictions of our model fit with previous observations however, we also remark the versatility of our result. Besides the possibility of using it as a cache dimensioning tool in operational environments it may also be used in more complex models that evaluate the scalability of LISP or other loc/id architectures. Another interesting application could be to evaluate the effects of trashing attacks on the LISP map-cache.

Fig. 1 :

 1 Fig. 1: Example LISP Architecture

Fig. 2 :

 2 Fig. 2: The Working Set Model

Fig. 3 :

 3 Fig. 3: Empirical working-set curves. Closeness of color nuance reflects closeness of start time.

Fig. 4 :

 4 Fig. 4: Fit of empirical working-set curves

Fig. 5 :

 5 Fig. 5: Comparison of empirical and estimated miss rates

Acknowledgments

This work has been partially supported by the Spanish Ministry of Education under scholarship number AP2009-3790, research project TEC2011-29700-C02, Catalan Government under project 2009SGR-1140 and a Cisco Unsolicited Research Proposal Grant.


Linpeng Tang

Zhiyong Shen
email: zhiyongs@hp.com

Qunyang Lin
email: qun-yang.lin@hp.com

Junqing Xie
email: jun-qing.xie@hp.com

Towards a Robust Framework of Network Coordinate Systems

Keywords: Network Coordinate Systems, Robust Error Measure, Metric Space Embedding, Matrix Factorization

Network Coordinate System (NCS) is an efficient and scalable mechanism to predict latency between any two network hosts based on historical measurements. Most NCS models, such as metric space embedding based, like Vivaldi, and matrix factorization based, like DMF and Phoenix, use squared error measure in training which suffers from the erroneous records, i.e. the records with large noise. To overcome this drawback, we introduce an elegant error measure, the Huber norm to network latency prediction. The Huber norm shows its robustness to the large data noise while remaining efficiency of optimization. Based on that, we upgrade the traditional NCS models into more robust versions, namely Robust Vivaldi model and Robust Matrix Factorization model. We conduct extensive experiments to compare the proposed models with traditional ones and the results show that our approaches significantly increase the accuracy of network latency prediction.

Introduction

The prediction of network latency, e.g. Round-Trip Time(RTT), has been a hot research topic over the last few years. Predicting network latencies between two network hosts without involving physical measurements may benefit many networking applications, like geometric routing [START_REF] Ledlie | Wired geometric routing[END_REF], large scale online game systems [START_REF] Agarwal | Matchmaking for online games and other latency-sensitive p2p systems[END_REF], locality-aware data center selection [START_REF] Brin | The anatomy of a large-scale hypertextual web search engine[END_REF], and P2P file sharing.

One way to predict network latency is via a Network Coordinate System (NCS) [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF][START_REF] Mao | Ides: An internet distance estimation service for large networks. Selected Areas in Communications[END_REF][START_REF] Liao | Network distance prediction based on decentralized matrix factorization[END_REF][START_REF] Chen | Phoenix: Towards an accurate, practical and decentralized network coordinate system[END_REF]. NCS tries to assign each network host some coordinates representing its virtual location in the network and the latency between two hosts is computed using a prediction function over the coordinates. To learn the coordinates for each host, we only need to measure a small fraction of all the pairs of the hosts and adjust the coordinates in order to minimize the prediction error on these records. Since the coordinates of one host are just a constant number of values, from Valiant's learning theory [START_REF] Valiant | A theory of the learnable[END_REF] we could learn the coordinates with just O(N ) measurements and predict the N 2 latencies between all host pairs, which makes the system scalable.

NCS approaches could be categorized into two classes: metric space embedding models and matrix factorization models. One of the most representative metric space embedding based approach is Vivaldi [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF], which maps the network hosts into a Euclidean space and approximates network latencies with the Euclidean distances between the image points. In matrix factorization models, such as Phoenix [START_REF] Chen | Phoenix: Towards an accurate, practical and decentralized network coordinate system[END_REF] and DMF [START_REF] Liao | Network distance prediction based on decentralized matrix factorization[END_REF], the pairwise latency matrix is approximated by the factorization of two low-rank matrices, one for the source hosts and the other for the destination hosts. Most of these traditional NCS's use the ℓ 2 -norm 3as the measure of the prediction error, due to its simplicity in model learning. However, the complexity of the Internet may cause extremely large noise in the measurement of the latency between hosts, and the quadratic ℓ 2 -norm shows high sensitivity to such erroneous data records. In this paper, we address the issue of large data noise based on an elaborately designed error measure-the Huber norm, which is more robust for the erroneous data records while remaining simplicity of learning the model. Based on the Huber norm, we propose a robust framework of NCS and further increase the accuracy of network latency prediction. The key contributions of this paper are threefold:

1. To the best of our knowledge, we are the first to introduce and study the Huber norm for network latency prediction, based on which we upgrade the traditional Vivaldi and matrix factorization models to more robust versions. 2. We derive two algorithms to learn the robust models-stochastic gradient descent and alternative damped-Newton method. The former has simple implementation and runs faster in terms of CPU time, while the latter takes fewer iterations for convergence. 3. We conduct extensive experiments to demonstrate that our robust models significantly outperform the traditional ones. Specifically, we find the robust version of Vivaldi shows much higher accuracy than other methods when neighbors of one host are fewer than 32 and may be the preferred model in many applications.

Preliminaries

Before we introduce the NCS approaches, let's formally define the problem of network coordinating. Assume that we have N network hosts. We may use an N × N matrix Y to denote the pairwise latency matrix, and let W denote the indices set of known entries, i.e., Y i,j is known(measured) for (i, j) ∈ W and generally |W | ≪ N × N . For each entry in the latency matrix Y , whether or not known, we may predict its value using Ŷi,j = pred C (i, j), where pred C (i, j) is a universal representation of the prediction function and the prediction is made based on the virtual coordinates assigned to the hosts, noted as C. The problem is now how to assign and adjust the coordinates for each network host in order to make the predicted latency matrix Ŷ as close to the matrix of true measurements Y as possible. We use the prediction error measure function ϕ( Ŷ , Y ) to characterize the closeness between the Ŷ and Y . Then in a NCS, we generally aim to solve the following optimization problem

C * = argmin C ϕ( Ŷ , Y ) (1)
Both the prediction function pred C (i, j) and the error measure function ϕ( Ŷ , Y ) should be specified for a NCS.

Related Work

Metric Space Embedding Models

In metric space embedding models, each host is associated with a position in a metric space, such as Euclidean space [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF] and hyperbolic space [START_REF] Lumezanu | Playing vivaldi in hyperbolic space[END_REF], etc. The latency between two hosts is then estimated as the distance between their positions in the space. Vivaldi [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF] is the most representative metric space embedding based approach, whose variants have been employed in real-world systems, such as Htrae [START_REF] Agarwal | Matchmaking for online games and other latency-sensitive p2p systems[END_REF]. In this model, the network hosts are embedded into a Ddimensional Euclidean space. Assume that two nodes i, j have embedded coordinates X i = (X i,1 , ..., X i,D ) and X j = (X j,1 , ..., X j,D ). We may calculate the Euclidean distance between i, j as ∥X i -X j ∥ 2 .

In Vivaldi, the authors also define quantities of heights H = (h 1 , h 2 , ..., h N ) (h i ≥ 0) for each host to characterize the host's intrinsic contribution to the latency, say the latency from a host to the nearest ISP. The prediction function is then defined as

pred X,H (i, j) := ∥X i -X j ∥ 2 + h i + h j , (2)
so we have Ŷi,j = ∥X i -X j ∥ 2 + h i + h j . The coordinates are learned by optimization algorithms so as to minimize the summation of prediction errors over the known entries in Y . Formally, in Vivaldi, we achieve the coordinates X and H by solving the the following optimization problem with an ℓ 2 -norm objective function

X * , H * = argmin X,H ϕ( Ŷ , Y ) = argmin X,H Ŷ -Y 2 (3) = argmin X,H ∑ (i,j)∈W [∥X i -X j ∥ 2 + h i + h j -Y i,j ] 2 (4)
The above problem could be solved using stochastic gradient descent [START_REF] Barto | Pattern-recognizing stochastic learning automata[END_REF] and due to the space limitation, we refer to [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF] for details.

Matrix Factorization Models

The representative matrix factorization NCS approaches include IDES [START_REF] Mao | Ides: An internet distance estimation service for large networks. Selected Areas in Communications[END_REF], Phoenix [START_REF] Chen | Phoenix: Towards an accurate, practical and decentralized network coordinate system[END_REF] and DMF [START_REF] Liao | Network distance prediction based on decentralized matrix factorization[END_REF] etc. In this kind of models, we generally seek the following approximation for the latency matrix Y .

Y ≈ U V T

The two factor matrices U, V represent the out-coordinates and the in-coordinates of the hosts. Specifically, the i-th row of U is the out-coordinate of host i and the jth row of V is the in-coordinate of node j.

Let Ŷ = U V T , so Ŷi,j = ∑ K k=1 U i,k V j,k .
The prediction function here is specified as

pred U,V (i, j) := K ∑ k=1 U i,k V j,k = (U V T ) i,j . (5)
Similar to Vivaldi, we may find U and V by minimizing the prediction error ϕ( Ŷ , Y ) over the known entries, and formally we have

U * , V * = argmin U,V ϕ( Ŷ , Y ) = argmin U,V Ŷ -Y 2 (6)
= argmin

U,V ∑ (i,j)∈W [(U V T ) i,j -Y i,j ] 2 (7)
From ( 6) and ( 3), we may see that traditional NCS's mostly use l 2 -norm in their objective function. This choice of prediction error measure has its easiness for optimization. In the next subsection, we'll discuss whether this is a proper choice for network latency prediction.

Issue of Data Noise

We must also, however, recognize the inherent complexity of network latencies. Because of the existence of inefficient routing rule, network congestions, malicious attack etc., many of data records we get and use to build the NCS may contain extremely large noise. If the NCS tries to fit these data records, it may deviate from the true distance model behind the whole network. Many people have recognized this phenomenon, and try to overcome it by introducing a "faith" factor on the host or the records. For example, Vivaldi introduced a weight in [0, 1] on each host to indicate how reliable its coordinates are. Similarly, Phoenix introduced a weight on each record indicating how reliable it is. Hosts or records with smaller weights will have less impact on the NCS. While such weight based approach can improve the stability and accuracy of NCS, it is very heuristic and often involves several parameters in the model that make tuning difficult.

We attack the issue of data noise from another direction by leveraging a noise robust error measure-the Huber norm, based on which we propose the robust versions of Vivaldi and matrix factorization models as described in the next section.

Algorithm Design

Huber Norm

A simple choice of robust measure is the ℓ 1 -norm 4 , which has shown considerably less sensitivity to large measurement errors than ℓ 2 -norm measures [START_REF] Ke | Robust l1 norm factorization in the presence of outliers and missing data by alternative convex programming[END_REF].

However, ℓ 1 -norm is not continuously differentiable so its numerical minimization is difficult. In [START_REF] Huber | Robust regression: asymptotics, conjectures and monte carlo[END_REF], Huber presents an elegant error-measure defined as [START_REF] Chen | Phoenix: Towards an accurate, practical and decentralized network coordinate system[END_REF] and illustrated in Figure 1.

M ϵ (r) = { r 2 2ϵ , |r| ≤ ϵ |r| -ϵ 2 , |r| ≥ ϵ (8)
The Huber norm is a combination of ℓ 1 /ℓ 2 norm (see in Figure 1). The tradeoff of ℓ 1 or ℓ 2 is controlled by the parameter ϵ : for small errors |r| ≤ ϵ, it assumes the ℓ 2 norm, while for large errors |r| > ϵ, it assumes the ℓ 1 norm. We'll empirically investigate the role of parameter ϵ in our models in Section 4.3. Compared to ℓ 2 norm, the Huber norm is more robust since large errors only has a linear impact. On the other hand, it is easier to optimize than ℓ 1 norm in some sense because it is continuously differentiable.

M ǫ (r) r ℓ 1 norm ℓ 2 norm ǫ -ǫ
C * = argmin C ∑ (i,j)∈W M ϵ (pred C (i, j) -Y i,j ) (9)
In the next two subsections we will describe how we specify and solve (9) for the robust versions of Vivaldi and matrix factorization models, respectively.

Robust Vivaldi

Substituting (2) into (9), we may train the model to learn the coordinates in the Euclidean space X and the heights H via optimizing

X * , H * = argmin X,H ∑ (i,j)∈W M ϵ [∥X i -X j ∥ 2 + h i + h j -Y i,j ] (10)
We leverage two alternative methods, stochastic gradient descent and alternative damped-Newton to solve the above problem.

Stochastic Gradient Descent: One way to solve the problem is by stochastic gradient descent [START_REF] Barto | Pattern-recognizing stochastic learning automata[END_REF]. For each measurement record Y i,j , we do the following update on the coordinates X i and heights h i :

F i,j = M ϵ (∥X i -X j ∥ + h i + h j -Y i,j ) (11) X i,d ← X i,d -δ ∂ ∂X i,d F i,j (d = 1 • • • D) ( 12
)
h i ← max(0, h i -δ ∂ ∂h i F i,j ) ( 13
)
where δ is the learning rate. In each round, we first randomly shuffle the training data, and then do the updates as ( 11), ( 12), [START_REF] Ke | Robust l1 norm factorization in the presence of outliers and missing data by alternative convex programming[END_REF].

Alternative Damped-Newton: We then utilize another optimization schemealternative damped-Newton method [START_REF] Buchanan | Damped newton algorithms for matrix factorization with missing data[END_REF]. Instead of considering one sample at a time, alternative damped-Newton method considers all neighbors5 of one host at the same time. Specifically, for one host i, fixing the coordinates of other hosts, it tries to optimize the sum of prediction errors from i to all its neighbors:

F i = ∑ j:(i,j)∈W M ϵ (∥X i -X j ∥ 2 + h i + h j -Y i,j ) (14)
To achieve this efficiently, we first consider Newton's method. Let G = ∇ Xi F i be the gradient, H = H Xi F i be the Hessian. Then Newton's Method updates X i ← X i -G\H 6 . However, since M ′′ ϵ (x) = 0 for |x| < ϵ, H can often be singular and G\H undefined. To overcome this problem, we use Damped-Newton Method. Specifically, we introduce the damping factor λ and modify the update rule to:

X i ← X i -G\(H + λI) ( 15
)
Note that when λ is small, the update rule approximates a Newton update, but when λ grows larger, the update becomes similar to a gradient descent with learning rate 1/λ. We use an adaptive scheme to choose a proper λ-starting with λ = 1, try λ ← 2λ until F i decreases or λ becomes too large, and this finishes one update.

Robust Matrix Factorization

By instituting (5) into (9), we get the objective of our Robust Matrix Factorization model.

U * , V * = argmin U,V ∑ (i,j)∈W M ϵ [(U V T ) i,j -Y i,j ] (16)
Both stochastic gradient descent and alternative damped-Newton method can be applied in similar ways. Note that we only give the update rules for the out-coordinates U and the rules for V are symmetric.

Stochastic Gradient Descent: Let F i,j denote the prediction error of record Y i,j [START_REF] Mao | Ides: An internet distance estimation service for large networks. Selected Areas in Communications[END_REF]. We may minimize it using gradient descent on U i .

F i,j = M ϵ ( D ∑ d=1 U i,d V j,d -Y i,j ) (17)
U i,d ← U i,d -δ ∂ ∂U i,d F i,j (d = 1 • • • D) ( 18
)
Alternative Damped-Newton: Let F i denote the sum of prediction error from i to all its neighbors (19). We try to minimize F i by updating U i with alternative damped-Newton method [START_REF] Liao | Network distance prediction based on decentralized matrix factorization[END_REF]. Again, assuming G = ∇ Ui F i and H = H Ui F i , we have

F i = ∑ j:(i,j)∈W M ϵ ( D ∑ d=1 U i,d V j,d -Y ij ) ( 19
)
U i ← U i -G\(H + λI) (20)

Discussion

As can be seen, stochastic gradient descent and alternative damped-Newton actually work in two fashions. The former considers one measurement record at a time while the latter update the coordinate of one host based on the current coordinates of all its neighbors. Intuitively, methods that consider the coordinates of all neighbors of one node converges faster, i.e., requiring fewer iterations to reach a optimal value. This property is especially desirable when each node maintain its own coordinates and communicates with its neighbors to adjust the coordinates. Faster convergence, in this case, means that it takes less time for the dynamic system to become stable. However, stochastic gradient descent also has its merits. Since it has no need to compute the Hessian, and do the matrix inversion, the computational cost of one iteration is extremely cheap. Therefore, although it may take more iterations, it is still considerably faster than alternative damped-Newton method when running on one computer. In Section 4.4, we'll further investigate the convergence property of these two methods.

Experiments

In this section we empirically compare performance of our models: Robust Vivaldi and Robust MF, with traditional models: Vivaldi, DMF, IDES and Phoenix. We use three large public data sets for our experiments: Meridian [START_REF]Meridian data set[END_REF], P2PSim [START_REF]P2psim data set[END_REF], Harvard [START_REF]Harvard data set[END_REF], which are all collected with King method [START_REF] Gummadi | King: Estimating latency between arbitrary internet end hosts[END_REF]. The data sets are preprocessed by removing some hosts to guarantee that all the hosts have at least 32 neighbors. In addition, we are predicting the RTT between hosts, which should be symmetric (not considering factors such as network congestion), so for the original latency matrix Y , we transform it to (Y + Y T )/2. After these preprocessing steps, the three data sets have 2,500, 1740 and 1818 hosts and average latency of 91.8ms, 75.8ms, 85.7ms, respectively.

Overview of the Experiments

We have three parameters to be specified in the experiments: K -the number of measured neighbors of a host, D -the dimension of the coordinates and ϵ -the tradeoff parameter between ℓ 1 and ℓ 2 norm in the Huber norm [START_REF] Chen | Phoenix: Towards an accurate, practical and decentralized network coordinate system[END_REF]. Note that in all experiments, the K neighbors of any host are chosen randomly. In the experiments, we consider the cases when K = 16, 32, 64 and the choice of D are chosen by experiments to let the algorithms to achieve best accuracy. We found that Robust-Vivaldi always works best when D = 2. (This coincides the finding of [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF] that increasing the dimension can't significantly improve the prediction accuracy in Vivaldi model.) The matrix factorization methods should have a slightly lower dimension when K are small in order to avoid overfitting, but a higher dimension when K are large in order to improve accuracy. So we set D = 5 when K = 16, D = 6 when K = 32 and D = 7 when K = 64. In Robust Vivaldi and Robust-MF, we set ϵ = 7 and in Section 4.3 we will conduct further investigation on the choice of ϵ.

In Section 4.2, we give the results on the distribution of absolute error. We then used other two evaluation criteria for later experiments, Mean Absolute Error (MAE) and Rooted Mean Squared Error (RMSE), defined as follows MAE = average

(i,j)∈W * ( Ŷi,j -Y i,j ) RMSE = √ average (i,j)∈W * [ ( Ŷi,j -Y i,j ) 2 ] ( 21
)
where, W * denotes the indices of a held out test set. For both of the two criteria, smaller values mean better performance.

Comparison on Prediction Accuracy

In this subsection, we compare the prediction accuracy of our algorithms with Phoenix, DMF, IDES and Vivaldi. The comparison results of error distributions are given in Figure 2(a)-(i) and we also specify the comparison of the 80percentile error in Figure 2(j). From these results, we see that robust methods significantly outperform their non-robust counterparts. This observation verifies the robustness of the Huber norm in the application of network latency prediction.

It is also remarkable that although Vivaldi does poorly in all our test cases (which coincides with the conclusion of Phoenix [START_REF] Chen | Phoenix: Towards an accurate, practical and decentralized network coordinate system[END_REF] and DMF [START_REF] Liao | Network distance prediction based on decentralized matrix factorization[END_REF] that matrix factorization supersedes (non-robust) Vivaldi), Robust Vivaldi achieves much higher accuracy than other methods when K is small. When K = 16, it supersedes all other methods by 25%-30% in terms of 80-percentile error in all 3 data sets (see in Figure 2(j)). When K is smaller, the advantage is even more obvious. So Robust Vivaldi may be the preferred model in many applications.

The advantage of Robust Vivaldi may profit from that the number of parameters utilized by Vivaldi like models (three for each host) is much smaller than that of matrix factorization based models (2D for each host). According to the principle of Occam's razor, when there is no sufficient training data, a model with fewer parameters faces lower risk of the issue of overfitting and may perform better. On the other hand, performance of the methods based on matrix factorization improves gradually as K increases, taking lead when K = 64.

K = 16 K = 32 K = 64 R-Vivaldi R-MF Others R-Vivaldi R-MF Others R-Vivaldi R-MF
When we have sufficient training data, matrix factorization may capture more information with more parameters and achieve higher prediction accuracy. In summary, Vivaldi like model is preferred when we have fewer than 32 neighbors for each host, but when we really know much information about the system (say, an online P2P game system), matrix factorization based methods has the potential to provide better accuracy.

The Choice of ϵ

In Figure 3, we vary ϵ, the threshold between ℓ 1 norm and ℓ 2 norm, and give the results of both MAE and RMSE on the P2PSim data set. According to the definition in (21), MAE and RMSE actually corresponds to the ℓ 1 and ℓ 2 error measures respectively. So one would expect that if we minimize the ℓ 1 error (set ϵ = 0), MAE would be minimized; and if we use the ℓ 2 error (set a large ϵ), RMSE would be minimized.

Interestingly, this is not the case (see in Figure 3). Neither MAE is best optimized at ϵ = 0, or is RMSE optimized when we increasing ϵ. For Robust Vivaldi, RMSE is best optimized when ϵ = 40. For Robust MF, RMSE is best optimized when ϵ = 7. As ϵ grows beyond this threshold, the performance deteriorates greatly. On the other hand, when ϵ is relatively small (ϵ < 10), the MAE remains stable for Robust Vivaldi. For Robust MF, MAE drops a little when ϵ increases as long as ϵ < 7.

Theoretically speaking, ϵ is the threshold between small errors and large errors. As a rule of thumb, we recommend to use the 80-percentile error as ϵ, so a value between 5-15 is recommended (choose a percentile error as ϵ was recommended in [START_REF] Guitton | Robust inversion of seismic data using the huber norm[END_REF]).

Convergence Analysis

In this section we investigate the convergence of the two optimization schemes, stochastic gradient descent and alternative damped-Newton. Figure 4 shows how the MAE criteria of the two algorithms (on p2psim, K = 32) evolve as the number of iterations increases on both Robust Vivaldi and Robust MF models. Eventually the two methods converge to almost the same value. Apparently, alternative damped-Newton converges much faster, reaching a stationary point within 20 iterations. Stochastic gradient descent, on the other hand, taking more (about 80) iterations for convergence. However, due to its efficiency in each round, it still runs much faster than alternative damped-Newton. On a typical 2.4GHz machine, Stochastic Gradient Descent takes less than 10 seconds to compute a coordinate for any data sets we have used while Alternative Newton can take about 2 minutes. These empirical results coincide the discussion in Section 3.4.

Conclusion and Future works

In this paper, we argue that the ℓ 2 -norm widely used in traditional NCS approaches is not robust for the noisy network latency data. We therefore introduce an elegant error measure, the Huber norm to network latency prediction, based on which we upgrade the traditional Vivaldi and matrix factorization NC-S approaches into more robust versions. We conduct extensive experiments and verify the robustness of the upgraded models. According to the results, we recommend Robust Vivaldi as the first choice. However, when there are sufficient historical data, Robust MF is also considerable. We also provide two different learning methods for the models: the alternative damped-Newton method which takes fewer iterations to converge, and the stochastic gradient descent method which is slower in convergence but faster in terms of CPU time. As our future work, we hope to find factors that could capture the noise and further boost the accuracy of NCS.

Fig. 1 :

 1 Fig. 1: The Huber norm

Fig. 3 :

 3 Fig.3: Effect of ϵ on the prediction error on the P2PSim data-set, K = 32.

Fig. 4 :

 4 Fig. 4: Convergence investigation

  Fig.2: Results of error distribution shown in (a)-(i). The x-axis is the cumulative fraction of records (in percentiles), and the y-axis is the corresponding prediction error (in milliseconds). In Table (j), we compare the 80-percentile error, where R-Vivaldi stands for Robust Vivaldi, R-MF stands for Robust MF and Others stands for the best result of IDES, Phoenix, DMF and Vivaldi in each test case.

						Others
	P2PSim	10.38 15.62 18.24	9.46	11.35 12.35	8.91	9.36 10.31
	Meridian 18.57 27.10 24.43 15.82 16.76 18.97	15.20 14.95 15.52
	Harvard 15.49 20.18 30.67	14.32 13.89 19.74	14.94 11.83 14.53
		(j) 80-percentile error (ms)

The ℓ 2 -norm of an error vector e = (e1, e2, ..., en) is defined as ∥e∥ 2 = √∑ n i=1 (ei) 2 .

The ℓ 1 -norm of an error vector e = (e1, e2, ..., en) is defined as ∥e∥ 1 = ∑ n i=1 |ei|.

The neighbors of one host i are the hosts j s.t. Yi,j is known, noted as j : (i, j) ∈ W .

X = A\B is the solution of A × X = B.


Norbert Blenn

Kassandra Charalampidou
email: k.charalampidou@student.tudelft.nl

Christian Doerr
email: c.doerr@tudelft.nl

Context-Sensitive Sentiment Classification of Short Colloquial Text

Keywords: Online Social Networks, Sentiment Analysis, Text Classification

The wide-spread popularity of online social networks and the resulting availability of data to researchers has enabled the investigation of new research questions, such as the analysis of information diffusion and how individuals are influencing opinion formation in groups. Many of these new questions however require an automatic assessment of the sentiment of user statements, a challenging task further aggravated by the unique communication style used in online social networks. This paper compares the sentiment classification performance of current analyzers against a human-tagged reference corpus, identifies the major challenges for sentiment classification in online social applications and describes a novel hybrid system that achieves higher accuracy in this type of environment.

Introduction

The amble availability of data from online social networks in machine-readable format has made it possible to investigate and evaluate a whole new set of research questions at a large scale, such as "how do trends form?", "what determines how influential a person is?" or "how do our friends and contacts shape our opinion?". Many research questions posed in online social network analysis thus require to be able to assess the context and meaning of a user's statements, identifying in the simplest case whether a sentence is a neutral, objective comment or a subjective opinion, or in more advanced scenarios tracing and quantifying the development and flow of positive/negative thoughts across a user's various communication threads.

In recent years, a number of methods for sentiment analysis have been proposed; these techniques have however been developed for and are consequently geared towards the extraction of meaning in large text corpora, such as product reviews, letters or articles. User communication in online social networks such as Facebook or Twitter has however very specific and challenging features: 1) Messages are short and highly abbreviated and therefore only a small angle of attack for an automatic classifier, 2) Text is very colloquial and typically deprived of any context information, thus making it difficult to infer the subject and reference of the sentiment.

Due to these special characteristics, traditional sentiment analysis methods do not provide sufficiently accurate results when applied towards online social network communications. This paper deviates from these established sentiment classification approaches and describes an alternative method utilizing additionally both grammatical and contextual information for increased detection accuracy. The contributions of this paper are two-fold: First, we evaluate a set of available sentiment classifiers against a dataset obtained from the social microblogging platform Twitter, and measure the detection performance of these automatic tools against a human classification. Second, we identify common problems in sentiment analysis and demonstrate how an alternative approach can provide a higher detection accuracy than previous context-less classifiers, and beside pure identification of sentiment polarization, can additionally provide a magnitude quantification of sentiments.

The remainder of this paper is structured as follows: Section 2 overviews previous work in sentiment classification, with a specific focus on online social network sentiment classification. Section 3 describes the evaluation corpus, compares the detection performance of existing approaches and discusses common problems with short colloquial text analysis. Section 4 introduces our hybrid approach and outlines additional application use cases. Section 5 summarizes our findings.

Related Work

Sentiment analysis, i.e., the extraction of an opinion's overall polarization and strength towards a particular subject matter, is a recent research direction [START_REF] Pang | Thumbs up? Sentiment classification using machine learning techniques[END_REF][START_REF] Turney | Thumbs up or thumbs down? semantic orientation applied to unsupervised classification of reviews[END_REF], and typically approached from a statistical, or machine-learning angle. Attention has been given particularly in the domain of movies [START_REF] Mishne | Predicting movie sales from blogger sentiment[END_REF][START_REF] Asur | Predicting the future with social media[END_REF], by analysis of social media data, as reflection of common opinion. It is found that prices of the movies industry have a strong correlation with observed outcome frequencies, and therefore they are considered as good indicator of future outcomes. Most recently published work either perform unsupervised learning on a provided corpus of perceived positive and negative texts such as product reviews [START_REF] Yu | Towards answering opinion questions: Separating facts from opinions and identifying the polarity of opinion sentences[END_REF][START_REF] Barbosa | Robust sentiment detection on twitter from biased and noisy data[END_REF], or use a set of curated keywords with positive or negative connotations to classify input [START_REF] Cilibrasi | Automatic meaning discovery using google[END_REF][START_REF] Pang | Thumbs up? Sentiment classification using machine learning techniques[END_REF].

Another common approach [START_REF] Yu | Towards answering opinion questions: Separating facts from opinions and identifying the polarity of opinion sentences[END_REF][START_REF] Barbosa | Robust sentiment detection on twitter from biased and noisy data[END_REF] is measuring sentence similarity between given data input and texts of specific polarity, which explores the hypothesis that opinion sentences will be more similar to other opinion sentences that to factual ones. Additionally, previous work [START_REF] Riloff | Learning extraction patterns for subjective expressions[END_REF][START_REF] Wiebe | Creating subjective and objective sentence classifiers from unannotated texts[END_REF] was focused on learning extraction patterns associated with objectivity (and subjectivity) in order to be used as features of objective/subjective classifiers. It is shown that this approach achieves higher recall and comparable precision than previous techniques. Apart from that, recent publications [START_REF] Jiang | Target-dependent twitter sentiment classification[END_REF][START_REF] Cambria | Sentic computing: Exploitation of common sense for the development of emotion-sensitive systems[END_REF], introduced the use of Natural Language Processing modules in order to extract concepts from the processed text and eventually derive sentiment out of them. In the very recent past, several of these general approaches have been specifically extended towards the mining of sentiments from online social media sources, in particular the microblogging platform Twitter [START_REF]Twitter[END_REF]. For our analysis, we focus on those approaches for which the original authors made a reference implementation available to us, specifically we compare the classification accuracy with the following classifiers:

Twitter Sentiment We used the bulk classification service available on the Twitter Sentiment website [START_REF] Go | Twitter sentiment classification using distant supervision[END_REF] in order to classify our test-set. This tool attaches to each tweet a polarity value: 0 for negative, 4 for positive and 2 for neutral-therefore we consider the first to describe subjective tweets, while neutral is for objective tweets. The main idea behind Twitter Sentiments approach is the use of emoticons as noisy labels for the training data which is shown that it increases the accuracy of different machine learning algorithms (Naive Bayes, Maximum Entropy, and SVM). It is noted that the web service of Twitter Sentiment uses a Maximum Entropy classifier. Tweet Sentiments Our test-set was also tested through the API of Tweet-Sentiments [START_REF]Tweet sentiments[END_REF], a well known tool for analysing Twitter data and provide sentiment analysis on tweets. TweetSentiments is based on Support Vector Machines (SVM) and is using the LIBSVM library developed at Taiwan National University. It classifies tweets as positive, negative or neutral and these values are treated as stated previously. Lingpipe We also used the Sentiment Analysis tool of the LingPipe [START_REF]Lingpipe[END_REF] package which focuses on the subjective/objective (as well as positive/negative) sentence categorisation especially on the movie-review domain. This approach uses the usual machine learning algorithms (Naive Bayes, Maximum Entropy, SVM) and a Java API of the classifier is available online. Even though it comes with its own training set, we used the half of our hand-classified set to train the classifier, in order to have better results. The other half was used as test-set and results were compared to the corresponding hand-classified tweets.

Methodology, Test Corpus and Performance Evaluation

To evaluate the performance of established sentiment classifiers and create a benchmark for our developed solution, we randomly sampled a set of some 1,000 publicly readably messages from the microblogging platform Twitter. Prime use cases for sentiment analysis are for example research questions revolving around the spread of information, opinion formation and identification of influential relationships in social networks, and such processes are typically believed to be present in discussions around product and media such as music, book or movie reviews.

Data Acquisition and Processing. For our evaluation, we therefore collected a data-set of 1,073 randomly chosen tweets related to the five most popular films of the 83rd Academy Awards. We used the language detection library of Cybozu Labs [START_REF] Shuyo | Language Detection Library[END_REF], in order to eliminate the tweets written in any language other than English, while we also tried to remove advertising tweets out of the set. Multiple retweets of the same text were also removed to prevent performance over-or underestimation, as well as unnecessary tokens like link urls, "@" tags for mentioning a user, 'RT' tags etc. Each tweet of this test-set was classified by hand before the begin of the evaluation into an objective or subjective statement; this corpus is used throughout this work as a reference benchmark.

Objective Statement Subjective Statement

Does text contain an opinion of some form?

Does the sentiment use a relevant reference point?

no yes no yes Components in Sentiment Analysis. Starting point for any sentiment analysis (as shown in figure 1) is the detection of any form of opinion in written text. If the author expresses some form of judgement, the input can be considered a subjective statement, otherwise the data is classified as an objective claim. Example cases distinguished by such test are for example "I liked The King's Speech" versus, "The King's Speech was a really long movie.", respectively. Another case is given by subjective messages where the sentiment is not based on the relevant reference point (the title of the movie). For example the tweet "I like you, even when watching The King's Speech" is a positive tweet, but its not the opinion about the movie that is positive. Once the existence of a sentiment has been established, typically a classification step is performed to determine whether the speaker is expressing a positive or negative opinion over a particular subject matter.

Relevant Expression determine polarization and intensity determine polarization

Challenges for Classification in Short Colloquial Text. In many types of inputs, and specifically in micro-texts such as tweets or chats, however a prob-lem arises: conversations are highly abbreviated. As tweets offer only 140 characters of payload, messages are reduced to a bare minimum and several different thoughts -for example reactions to previous incoming messages -frequently are abbreviated and intertwined: "Watched King's Speech today in class. I love the end of the term." This results in a very small footprint on which sentiment analysis can be conducted, at least compared to the essay-and article-type classification previously used for polarization analysis. Previously established approaches, which for example operate using a statistical word-frequency analysis, are therefore less suited, as the low quantities of text and the high concept compression ratios are resulting in very high statistical fluctuations and noise during the detection. For this reason, we pursue a different approach in this work and analyze the grammatical structure of messages. By detecting which concepts a particular sentiment is referencing to, we can make more fine-grained decisions and consequently achieve a higher prediction accuracy especially in dense, intertwined texts. In the example above this concept is the end of the term (and therefore potentially a looser schedule) rather than the movie itself.

Automatic Detection and Tuning of Polarization Intensity. Finally, many applications and research hypotheses can be better served if not only the existence of a sentiment and its general polarization is known, but an absolute notion of "how positive" or negative a particular opinion can be derived. This would allow both a better assessment of how opinions are propagated and adopted, as a person with a strong negative attitude towards a particular concept is first expected to become less and less negative before developing a positive sentiment if at all. Without a quantification of polarization such trends would go unnoticed. Additionally, a quantitative measurement of attitude would allow of differentiation between alternatives, which in sum are all considered positively, but in a pairwise comparison are not equal.

If considered in previous work, this aspect is typically approached using manually curated word lists, as for example in [START_REF] Turney | Thumbs up or thumbs down? semantic orientation applied to unsupervised classification of reviews[END_REF]. When following this strategy in the application context of micro-messages, we however discovered two fundamental difficulties: 1) Users utilize a rich set of vocabulary to describe their opinions about concepts. Capturing and maintaining an accurate ranking of evaluative comments would require a significant effort in a practical setting. 2) Expressions indicating positive and negative sentiments and their relative differences are neither stable over time nor between different people, thus a method to re-adjust and "normalize" sentiment baselines over time or between say generally very positively oriented, neutral or pessimistic speakers will provide an advantage.

Evaluation of the State-of-the-Art. To evaluate the performance of existing sentiment classifiers, we let the set of available classifiers described in section 2 analyze and distinguish a reference body of tweets. As most methods do not allow for a sentiment quantification, we limited this evaluation to only a general polarization detection which is supported by all systems. Comparing the output against the previous human classification, we measured the overall accuracy of the automatic classifiers in distinguishing subjective from objective statements as shown in figure 2(a). Figure 2(b) shows the overall performance in correctly and incorrectly classified statements. As can be seen in the figure, the classification accuracy of all statistical sentiment analyzers is between 55 and 60%, whereas the proposed statisticalgrammatical hybrid approach yields a correct classification accuracy of about 85%, a 40% gain over previous work. Note also that the accuracy of existing system also varies significantly between the type of input data: Twitter Sentiment [START_REF] Go | Twitter sentiment classification using distant supervision[END_REF] for example is much stronger identifying objective statements compared to subjective ones, while Tweet Sentiment [START_REF]Tweet sentiments[END_REF] shows exactly the opposite behavior. The proposed hybrid solution on the other hand does not show any significant bias.

!! "# $ % & # ' ! ( & # ' ! !! "# $ $ # # !! " % #$ # # !! "

Sentiment Classification & Polarity Estimation

This section describes in detail the underlying concept of the proposed hybrid sentiment classifier. As shown in figure 1, the general task of sentiment analysis can be conducted in two general phases, first the detection of opinions in general (yielding to a categorization in objective and subjective text), after which a quantification of the polarity can be attempted. The following discussion mirrors these steps.

Grammatical Sentiment Classification

In order to classify a given message into subjective and objective we analyze the grammatical structure of a tweet. Subjectivity is mostly based on adjectives or verbs expressing the polarity related to the subject of the message. This means if directly expressing an emotion one usually uses a verb like "like/love/hate" whereas expressing the mood about something usually contains an adjective. Consider the examples: I'm feeling sick today, I liked the movie.

To determine the existence of a sentiment, we therefore invert the grammatical structure of a given text to detect the presence of verbs carrying an emotional meaning or to find the adjectives associated with the keywords we are performing the sentiment analysis on, in our case the titles of movies. Grammatical structure analysis is a mature research area and we use Klein and Manning's lexicographical parser [START_REF] Klein | Accurate unlexicalized parsing[END_REF] to determine the structure of the English texts of tweets after removing special characters as described in section 3. For a given text, this tool is estimating the grammatical structure. An example for the tweet "I liked the movie" is given in the following: Here, the parser is reasoning that "I" is the nominal subject of "liked", and "movie" is the direct object of the verb "liked". As mentioned, most tweets expressing a sentiment have this kind of structure. If an adjective is referring to a subject the likelihood is quite high that this tweet expresses the mood about something. Note however that it is in general possible that the speaker was using sarcasm or irony, which could not be detected from a grammatical viewpoint.

In a second step, we cross-check whether the word referring to the subject of a tweet is an adjective. This can be done using either a lexical database such as WordNet [START_REF]Wordnet. a lexical database for english[END_REF] or a part-of-speech Tagger [START_REF] Kristina Toutanova | Feature-rich part-of-speech tagging with a cyclic dependency network[END_REF], which will be used further in this discussion. Through such a tool, every word in a given sentence can be annotated with a tag identifying its purpose in the sentence [20], so the example "I liked the movie" is marked as:

I/PRP liked/VBD the/DT movie/NN
The part of speech tagger tells us that "I" is a personal pronoun, "liked" a verb in past tense, "the" a determiner and "movie" a noun. By connecting the so gathered information of a message we build simple rules to detect if a message is a subjective statement whereas all the others by inversion have to be objective:

1. if an adjective is referring to the subject 2. if an verb out of a list is referring to the subject 3. adjective + [movie, film] 4. [movie, film] is/looks [adjective] 5. love/hate + [movie, film]

Automatic Polarity Estimation

After the existence of a subjective component has been established, it is necessary to determine the overall polarity of the sentiment and if possible also the magnitude of the sentiment. In order to estimate the general polarity direction of words in the corpus, we used an unsupervised approach based on word correlations. This approach is inspired by the way a person is learning to judge which words have a positive or negative meaning, which is essentially a result of a lot of exposure to speech and written text, from which the learner infers which words appear in a positive or negative context.

The same basic principle, inferring which words appear together in a positive or negative context, can however be easily mirrored in a machine as well. Here, a computer would simply need to count how often a particular adjective has been encountered with a positive meaning compared to the frequency it has been observed with a negative connotation. To begin such an automatic classification, some notion of what is deemed positive or negative will be necessary. In our work, we have explored two general options, first by manually specifying a set of keywords one would associate with positive expressions such as "fantastic", "incredible", "amazing", which can read from existing databases such as [START_REF]Wordnet. a lexical database for english[END_REF], and second by looking at the most basic positive/negative expression commonly used in online messages such as chats, emails or microblogs: a positive smiley :-) and a negative smiley :-(. In the following, we will discuss the results for this second alternative.

From a list of one million tweets, we search for all tweets containing a positive smiley :-), :) or =) -in the following referred to as positive keywords -and created a list of texts containing at least one of those symbols. Similarly, a list of all tweets containing a negative smiley such as :-(, :( or =( -deemed negative keywords -was prepared. Using the techniques discussed above, we dissect all individual statements and count the number of co-occurrences between every detected word and the positive or negative keywords. To correct for differences in length of those two lists -as users typically write more positive than negative statements -, the two values are then normalized by the number of words in the list of messages containing positive words and the list of messages containing negative words. This results in a relative assessment of a particular word to appear in a positive or a negative context, where context is defined by the positive and negative keywords, respectively.

To arrive at a relative polarity of a particular word between the two extremes "positive" and "negative", it is now simply enough to subtract the relative frequencies. This number is positive if the word is typically used within a positive context and negative if the word typically occurring with a negative meaning.

As this number is biased by the number how often a word is used in general, a final correction step is executed in which each rating is multiplied by the term frequency measured in all tweets: the emphasis of frequently observed words is therefore reduced, and the value of unusual ones is lifted.

Fig. 3 shows the output of this simple procedure conducted over a body of one million tweets, and using just positive and negative smileys as corresponding positive and negative keywords. As can be seen, this unsupervised process leads to a clear and meaningful ranking of adjectives. We have repeated this analysis over a selection of datasets of different duration and verified the automatically generated polarity estimation against those done by a human. Typically, less than 7% of the words were considered wrongly placed in the overall order; out of a list of 30 adjectives between one and two placement were deemed higher or lower in the ranking by a human observer than by a machine. As this method can be executed without manual intervention, this new methodology can be continuously conducted to detect the general development of sentiments in entire online communities, as well as to identify whether the polarity of certain words shift in strength over time. A more comprehensive analysis is needed to see if the sentiment of adjectives change over time. However taking twitter data of durations of one week, one and two months the polarity seems to stabilize the longer the duration of observation.

Detecting Networks of Concepts

This general method is however not limited to determine the polarity strength of words in general, but can be used to detect and identify common concepts and their associated sentiments in general. To do so, it is simply necessary to swap out the two sets of keywords (which in the last section were :-), :), =) and :-(, :(, =(, respectively), and replace them with those terms and synonyms relevant to a particular study.

Consider for example a situation where one would to determine the associations made with the brands and products of two hypothetical tea manufacturers: McArrow's orange-peppermint tea and DrBrew's strawberry-melon tea. Here, one would populate keyword group 1 with words from the first area, i.e., McArrows, orange-peppermint, etc. and analogously keyword group 2 with words such as DrBrew, strawberry-melon, etc., and by the same means described above, this method would derive the set of words frequently used in combination with any of those keyword terms as well as the strength of their typical common appearance as shown in figure 4. The words A -I discovered to be co-located can however be themselves further interpreted, for example, 1) depending on how positively/negatively they are (as discussed above), or 2) which general topic areas or word field the concepts come from. Imagine for example words A and F in figure 4 to be "taste" and "flavor", while words D and E are "packaging" and "price". Clearly, such combined word co-localization, polarization and word-field analysis will provide a significant insight to our hypothetical tea manufacturer, which can also be eas-ily repeated over time to track its overall development, but also to the researcher interested in how particular opinions form, are spread and change over time. As a general example, we have applied this techniques towards the keywords "coffee" and "tea", and let the system arrange the resulting associated words according to their overall polarity strength. The overall abstract network can then be drawn in a similar manner as figure 3, and figure 5 shows the 27 strongest connections commonly made the terms coffee and tea. All bars indicating their affiliation towards the two beverages are colored by their polarity value. Red indicates a negative, green a positive and white a neutral polarity.

Conclusion

In this paper, we have presented an alternative method to determine the existence and strength of subjective opinions in short colloquial text, an application domain where existing approaches do not yield a high detection accuracy. The proposed system works through a combination of grammatical analysis with traditional word frequency analysis, does not need supervised training and improves the accuracy of previous work by about 40%.

Fig. 1 .

 1 Fig. 1. Sentiment classification involves a multi-stage process, in which not only the existence of a sentiment should be checked, but also the reference point and strength should be assessed. (Contributions of this work are indicated in green.)

Fig. 2 .

 2 Fig. 2. Classification accuracy of different sentiment analyzation methods.

  [I, liked, the, movie] (ROOT (S (NP (PRP I)) (VP (VBD liked) (NP (DT the) (NN movie))))) nsubj(liked-2, I-1) det(movie-4, the-3) dobj(liked-2, movie-4)

Fig. 3 .

 3 Fig. 3. Automatic polarity ranking of adjectives based on general Twitter messages.

Fig. 4 .

 4 Fig.4. The technique can be broadened to determine the concepts commonly associated with any keyword as well as the particular strength of the association.

Fig. 5 .

 5 Fig. 5. Polarization analysis of commonly used words with coffee and tea based on general Twitter messages.

Acknowledgements. This project was partially supported by the Transsector Research Academy for Complex Networks and Services (TRANS).