Etta Grover-Silva
email: etta.grover-silva@mines-paristech.fr

Xwégnon Ghislain Agoua
email: xwegnon.agoua@mines-paristech.fr

Robin Girard
email: robin.girard@mines-paristech.fr

Georges Karinotakis
email: georges.kariniotakis@mines-paristech.fr

A STOCHASTIC MULTI-TEMPORAL OPTIMAL POWER FLOW APPROACH FOR THE MANAGEMENT OF GRID CONNECTED STORAGE

Renewable energy (RE) integration into distribution grids is becoming more common in the context of the energy transition. The management of wind or solar generation due to their variability and low predictability are challenging for distribution system operators (DSO). To that may be added uncertainties related to electric load profiles. The role of flexibility, coming from decentralized storage devices, will be important for DSOs trying to manage uncertain loads as well as high levels of RE penetration. The introduction of automation and smart metering in distribution grids allows for the optimized management of storage devices to maximize the capability of current infrastructure to integrate RE generators. These optimized management strategies can be calculated with optimal power flow (OPF) algorithms. This paper uses a convex relaxation of the power flow equations to expand the multi-temporal deterministic approach presented in [1] to a stochastic one. The stochastic algorithm implies the integration of a scenario tree to plan the charging and discharging schedule of batteries one day in advance. When comparing deterministic and stochastic operation planning strategies, the stochastic method annually increases total economic benefit by 3.1% while requiring lower annual cycling of the battery therefore increasing battery life.

INTRODUCTION

Renewable energy generators are becoming more common in the distribution system as a result of the transition from traditional electric generation to more sustainable technologies. These decentralized generators, such as photovoltaic (PV) systems, introduce new technical difficulties for distribution system operators (DSO) including bi-directional power flow, over current and voltage profile shifting. Smart meters are gaining popularity as a solution to improved visibility and controllability in distribution grids. The automation of distribution grids can allow for the optimization of existing grid architecture to avoid unnecessary infrastructure upgrades. The new possibility to control decentralized generators and loads in the distribution system requires new and innovative management strategies. Optimal power flow algorithms are effective at calculating optimal set points for decentralized controllable devices while guaranteeing that no power quality requirements are violated. These types of algorithms can take into account the voltage and current constraints of an electrical distribution grid while minimizing an overall cost function.

At the distribution grid level, the uncertainties of renewable energy production and electric loads are high due to minimal aggregation effects. These uncertainties introduce a challenge for DSOs to optimize their controllable devices. Management strategies have been employed by DSOs to optimize decentralized controllable devices under uncertainty. These management strategies include real time flexibility of the system through grid connected storage or PV curtailment strategies managed by a real time distribution management system (DMS). However, real time control of a distribution system can imply sophisticated communication networks. This flexibility can also be scheduled on a day-ahead basis to reduce the need for real time power flow control. Stochastic optimization has been presented in the literature as effective for planning operational strategies of controllable grid connected devices under uncertainty. For example reactive power compensation under uncertainty was explored by using statistical probability distribution curves and a Monte Carlo sampling technique to represent prediction errors in an OPF algorithm [2]. A similar probability distribution using multi-stage stochastic programming with a chanceconstrained optimization problem uses probabilistic penalty constraints associated with prediction errors [3]. However, these techniques imply a precise estimation of the distribution profile of errors associated with each forecast. The use of scenarios to take uncertainties into account requires less detailed forecast data. Accounting for uncertainties through scenarios is present in the literature. For example, a simulation of a deterministic scenario and associated forecast limits of load and PV for a threephase distribution grid is presented in [4]. This analysis is a single time step analysis performed for each hour of the day. This daily analysis does not take into account variables that have temporal dependencies. A multitemporal algorithm is necessary to consider time dependent variables such as storage devices and controllable loads. Multi-temporal stochastic OPF can distribution grids to analyze the benefits of grid connected storage devices under uncertainty. the integration of multi-temporal and multi aspects into an OPF algorithm can increase exponentially the size of the problem. Therefore, intelligent scenario selection and a certain decoupling are effectively resolve this type of problem analysis. There exist few algorithms that take into account temporal dependencies and uncertainties same time for the distribution grid. This paper presents a stochastic OPF algorithm whose structure allows the integration of scenarios and multi temporal aspects for day ahead planning of st devices. It utilizes convex relaxations of the power flow equations in the form of a second order cone program (SOCP) and iterative cuts to guarantee exactness as described in [5]. Just as the convex relaxations exploit the radial geometry of distribution grids, a radial geometry is also used for the scenario tree. This innovati proposes a simple scenario generation strategy based on historical data that shows a higher performance in comparison to a deterministic day ahead planning strategy. The paper organization includes the definition of the algorithm in section 2, the algorithmic performance in section 3, the demonstration of such an algorithm for a French case study in section 4 followed by the case study results in section 5 and final conclusions in section 6.

STOCHASTIC OPTIMAL POWER FLOW ALGORITHM SOCP Optimization Problem Formulation

The SOCP optimization objective function is defined in eq. ( 1).

. ∑ , | , | ∑ ∑ , , , ,
Where the definition of node specific variables will use the convention below:

, is the price of electricity for the time step active power at the substation at time step resistance of branch ij, ℓ , is the square of the magnitude of the current on branch ij at time maximum PV injection at node j at time step the actual injection at node j at time step International Conference on Electricity Distribution dependent variables such as storage devices and temporal stochastic OPF can be applied to distribution grids to analyze the benefits of grid under uncertainty. However, temporal and multi-scenario aspects into an OPF algorithm can increase exponentially erefore, intelligent scenario are necessary to effectively resolve this type of problem for annual . There exist few algorithms that take into account temporal dependencies and uncertainties at the This paper presents a stochastic OPF algorithm whose structure allows the integration of scenarios and multitemporal aspects for day ahead planning of storage . It utilizes convex relaxations of the power flow form of a second order cone program (SOCP) and iterative cuts to guarantee exactness as described in [5]. Just as the convex relaxations exploit the radial geometry of distribution grids, a radial geometry is also used for the scenario tree. This innovative approach proposes a simple scenario generation strategy based on historical data that shows a higher performance in comparison to a deterministic day ahead planning

The paper organization includes the definition of the the algorithmic performance in section 3, the demonstration of such an algorithm for a French case study in section 4 followed by the case study results in section 5 and final conclusions in section 6.

OWER FLOW Formulation

The SOCP optimization objective function is defined in

, , (1)
Where the definition of node specific variables will use is the price of electricity for the time step t, , is the power at the substation at time step t, is the is the square of the magnitude at time t, , , is the at time step t,

, , is at time step t, and , , is the losses of the battery system at node

The optimization constraints include the PV power limits eq. ( 2), PV apparent power limits eq. power flow equations eq. ( 5) the current equation eq. ( 8)eq. ( 10), battery power constraints eq. constraints associated with the eq. ( 13).

, ,

, is the apparent power injection of the PV system at time step t, ̅ , power rating of the PV inverter, power of the PV system at time step power of branch ij at time step node j at time step t, , , is the active power injection of the battery system at node j reactive power of branch ij reactive load at node j at time step of branch ij, , , is the reactive power injection of the PV system at node j at time step voltage magnitude at node j at time step maximum voltage, is the minimum voltage, is the state of charge of the battery system at node time step t for scenario s. The temporal and scenario dependencies are a result of eq. ( 12). the losses of the battery system at node j at time step t.

The optimization constraints include the PV power limits , PV apparent power limits eq. ( 3) -eq. ( 4), the (5) -eq. ( 7), the relaxation of -eq. ( 9), the voltage limits , battery power constraints eq. ( 11) and the constraints associated with the battery capacity eq. ( 12) -

(2) (3) (4) , , , , , (5)
, , ,

, ,

(10)

, , , , , ,

(13)

is the apparent power injection of the PV is the maximum apparent power rating of the PV inverter, , , is the apparent em at time step t, , is the active at time step t, , , is the active load at is the active power injection of j at time step t, , is the at time step t, , , is the at time step t, is the reactance is the reactive power injection of the at time step t, , is the square of the voltage magnitude at node j at time step t, is the is the minimum voltage, , , , is the state of charge of the battery system at node j at . The temporal and scenario a result of eq. ( 12).

CIRED 2017

Scenario Generation and Structure

Scenarios are generated for the PV production and load profiles for each node. The scenarios are generated by using historical PV production and load regression is completed using a historical period of 60 days to then predict the 25 quantile of PV production and load profile for the next two day period. The deterministic approach analyzes a daily period consisting of 24 coupled time steps using the 50 th percentile for the PV production profiles for the predicted profiles. approach combines the 25 th and 75 th quantile scenario PV and load profiles to create 4 combination scenarios. These combination scenarios are then used i with the 50 th quantile scenario to generate four stochastic OPF problems, here after called calculation Within each of these four calculation blocks target period and a scenario period as shown by the time steps in black in Figure 2. The target period is defined as a period where there is only one variable representing the power of each battery system or controllable load also corresponds to the 50 th PV quantile and 50 quantile in all scenarios. The scenario characterized by multiple optimal values of the power injection or controllable load power step. The physical meaning of multiple optimal values of the controllable power injection is the optimal power injection for each unique scenario. The target is coupled with each independent scenario therefore finding the optimal injection of the target period for all following injection possibilities. These blocks include using the 50 quantile for the target period and the 4 combinat scenarios for the scenario period. The period for the first three blocks is 6 hours while the target period for the last block is 12 hours. The deterministic problem scenario tree is found in Figure 1 while the stochastic OPF scenario tree can be found in Figure PV production and load . The scenarios are generated by data. A quantile historical learning set predict the 25 th , 50 th and 75 th quantile of PV production and load profile for the next

The deterministic approach analyzes a 24 coupled time steps and percentile for the PV production and load

The stochastic quantile scenarios of PV and load profiles to create 4 combination scenarios. These combination scenarios are then used in conjunction quantile scenario to generate four stochastic calculation blocks. blocks there is a as shown by the time . The target period is defined as a period where there is only one variable representing the or controllable load which PV quantile and 50 th load . The scenario period is characterized by multiple optimal values of the battery or controllable load power for each time of multiple optimal values of the optimal power he target is coupled therefore finding the for all following include using the 50 th quantile for the target period and the 4 combination

The target period for is 6 hours while the target period for deterministic problem while the stochastic Figure 2.

alysis with a single scenario quantile of PV and load profiles Figure 2: Stochastic analysis with a four dimensional scenario tree using 25 th , 50 th and load profiles

After a scenario tree splits, the four combination scenarios are considered to be independent. Therefore the final optimal charging schedule of the battery is composed of the solution calculated during the target period for each block. For the deterministi target period is the same length as the total simulation period. Therefore only one problem is solved during the deterministic algorithm. The stochastic four different stochastic problems taking into account critical periods where scenarios could be significantly different. The coupling between the four blocks is done by setting the state of charge and power of the battery systems at the end of one target period equal to the time step of the next block's target period. optimal charging schedule is composed of the target periods of each block.

ALGORITHMIC PERFORMA

An annual analysis is performed to calculate the annual benefit possible from using a stochastic day ahead scheduling in comparison to the de scheduling. The algorithmic performance of the deterministic approach and the stochastic approach are shown in Approach Coupled time steps Deterministic 24 Stochastic 24

The deterministic algorithm has a in comparison to the stochastic algorithm.

CASE STUDY

Grid Feeder

Glasgow, 12-15 June 2017 Paper 0726

3/5

: Stochastic analysis with a four dimensional th and 75 th quantiles of PV and load profiles After a scenario tree splits, the four combination scenarios are considered to be independent. Therefore the final optimal charging schedule of the battery is composed of the solution calculated during the target period for each block. For the deterministic problem, the target period is the same length as the total simulation period. Therefore only one problem is solved during the deterministic algorithm. The stochastic algorithm solves four different stochastic problems taking into account where scenarios could be significantly different. The coupling between the four blocks is done by setting the state of charge and power of the battery systems at the end of one target period equal to the first time step of the next block's target period. The final daily optimal charging schedule is composed of the target PERFORMANCE An annual analysis is performed to calculate the annual benefit possible from using a stochastic day ahead scheduling in comparison to the deterministic day ahead scheduling. The algorithmic performance of the deterministic approach and the stochastic approach are The deterministic algorithm has a lower calculation time comparison to the stochastic algorithm.

CIRED 2017

An example urban electric grid in France was studied to demonstrate the use of the algorithm. The medium voltage distribution grid feeder is composed of 137 nodes with a nominal voltage of 30 kV and is assumed to be located in Nice, France. A map of the gr be found in Figure 3.

Generation and Load Profiles

Electric load profile data was simulated with a bottom up load simulator detailed in [6] for each low voltage substation. A statistically accurate representation of residential and commercial customer proportion, electri heating, living surface area and population was simulated using the INSEE building inventory database of France. The location of each load profile was determined randomly due to the fact that no grid load data was available. The transformer connecting th voltage feeder and the high voltage grid is an 8 MVA transformer serving 21 low voltage substations. profiles aligning with meteorological data in Grenoble France indicated a peak load of 3.0 MW during the summer and 7.7 MW during the winter load of respectively 2.8 MW and 4.2 MW. production data was based on the normalized real production of a PV plant in Grenoble France [7].

An amount of 20 PV systems and 20 battery systems were assigned to 20 nodes, a majority were chosen to be the same nodes as the nodes hosting low voltage substations. The size of these systems was chosen randomly to be between 35-250 kW. Characteristics of the final load profile nodes can be found in PV size information can be found in Figure 5 International Conference on Electricity Distribution

An example urban electric grid in France was studied to demonstrate the use of the algorithm. The medium voltage distribution grid feeder is composed of 137 nodes with a nominal voltage of 30 kV and is assumed to be located in Nice, France. A map of the grid topology can : Grid topology with low voltage substation connections of medium voltage urban feeder in Electric load profile data was simulated with a bottom up for each low voltage substation. A statistically accurate representation of residential and commercial customer proportion, electric heating, living surface area and population was simulated using the INSEE building inventory database of France. The location of each load profile was determined randomly due to the fact that no grid load data was available. The transformer connecting the medium voltage feeder and the high voltage grid is an 8 MVA serving 21 low voltage substations. Load with meteorological data in Grenoble, of 3.0 MW during the with an average load of respectively 2.8 MW and 4.2 MW. Solar system production data was based on the normalized real production of a PV plant in Grenoble France [7]. and 20 battery systems y were chosen to be the same nodes as the nodes hosting low voltage . The size of these systems was chosen 250 kW. Characteristics of the final load profile nodes can be found in Figure 4 and Figure 5.

Figure 1 :

 1 Figure 1: Deterministic analysis with a single scenario using the 50 th quantile of PV and load profiles

Figure 3 :

 3 Figure 3: Grid topology with low voltage substation connections of medium voltage urban feeder in France.

Figure 4 :Figure 5 :Figure 6 :

 456 Figure 4: Maximum and average load for node

Figure 4 :Figure 6 :

 46 Figure 4: Maximum and average load for indicated nodes

ACKNOWLEDGEMENTS

International Conference on Electricity Distribution

Figure 7: Charging schedule for July 11, 2012 of stochastic and deterministic planning methods (top) and associated load profile, PV production and The authors would like to thank provision of some of the data used in this study. Mr. Thibaut Barbier is thanked for his support with the simulated load curves. This work is being carried out as a part of the research and innovation project SENSIBLE (Storage ENabled SustaInable energy for BuiLding communitiEs -www.h2020received funding from the European Union's under the Horizon 2020 Framework Programme (Grant No 645963). It is also supported from a PhD grant ADEME (Agence de l'Environnement et de la Matrise de l'Energie) and ARMINES.

5/5

The authors would like to thank ENEDIS for the of some of the data used in this study. Mr. Thibaut Barbier is thanked for his support with the This work is being carried out as a part of the research and innovation project SENSIBLE (Storage ENabled SustaInable energy for BuiLdings and -projectsensible.eu) that has received funding from the European Union's under the Horizon 2020 Framework Programme (Grant No is also supported from a PhD grant by de l'Environnement et de la Matrise de

CIRED 2017 As seen by the figure above, the stochastic battery charging schedule is more conservative using the battery less during the day. While the number of the battery systems are lower in the stochastic case study the economic annual benefit is higher as seen in

CONCLUSION

This paper has presented two day operations scheduling for a distribution grid: one deterministic method and one stochastic method. These two methods are then compared quantifying the benefits of using stochastic analysis in distribution grid for storage operations management. The primary difference between the stochastic and deterministic analysis is that the stochastic algorithm calculated a more conservative use of the battery systems. This conservative usage decreases number of cycles per year of the battery while increasing economic benefit by 3.1%. Another advantage of this type of algorithm is that the quantile regression method used to calculate the scenarios calculation burden and requires a short historical data set of only three months. Future work cou improving the scenario generation method to be more precise and integrating parallel programming to decrease the calculation time.

As seen by the figure above, the stochastic battery tive using the battery number of full cycles of in the stochastic case study nefit is higher as seen in Table 1.

This table shows that stochastic day ahead planning not y increases the battery life by decreasing the annual but also increases annual economic benefit This paper has presented two day-ahead battery operations scheduling for a distribution grid: one deterministic method and one stochastic method. These two methods are then compared quantifying the benefits of using stochastic analysis in distribution grid for storage The primary difference between the stochastic and deterministic analysis is that the stochastic algorithm calculated a more conservative use of the battery systems. This conservative usage decreases the number of cycles per year of the battery while %. Another advantage he quantile regression used to calculate the scenarios has a low calculation burden and requires a short historical data set Future work could be done on improving the scenario generation method to be more precise and integrating parallel programming to decrease


S Biasotti

E Moscoso Thompson

M Aono

A Ben Hamza

B Bustos

S Dong

B Du

A Fehri

H Li

F A Limberger

M Masoumi

M Rezaei

I Sipiran

L Sun

A Tatsuma

S Velasco Forero

R C Wilson

Y Wu

J Zhang

T Zhao

F Fornasa

A Giachetti

Shrec'17 Track: Retrieval of surfaces with similar relief patterns

Keywords: Descriptors (according to ACM CCS): I, 3, 3 [Computer Graphics]: Picture/Image Generation-Line and curve generation

This paper presents the results of the SHREC'17 contest on retrieval of surfaces with similar relief patterns. The proposed task was created in order to verify the possibility of retrieving surface patches with a relief pattern similar to an example from a database of small surface elements. This task, related to many real world applications, requires an effective characterization of local "texture" information not depending on patch size and bending. Retrieval performances of the proposed methods reveal that the problem is not quite easy to solve and, even if some of the proposed methods demonstrate promising results, further research is surely needed to find effective relief pattern characterization techniques for practical applications.

Introduction

The challenge of this SHREC'17 track is to evaluate the performance of existing retrieval algorithms when a 3D surface is characterized by different relief patterns, such as knitted fabrics. This task is particularly challenging and interesting for practical applications, for example to retrieve artworks' patterns, artists' styles or to classify natural structures like tree barks [OVSP13], rock types or engravings [ZPS * 16], etc. A peculiar characteristic of patterns is the fact their style does not depend by the overall structure of the shape rather than it identifies parts and local properties that are independent of the global shape.

The key point in this retrieval task is to find a patch descriptor and a distance measure that do not depend on the patch bending and are robust to different mesh samplings, but only on the relief pattern characterizing its surface, that can have different size and a depth of a few millimeters.

Data acquisition and processing

15 different textiles (with well defined and specific relief patterns) have been placed in different poses possibly lying on differently shaped objects and stretched, so that the same surface assumes different space embeddings (examples of different embeddings of the same patch are shown in Figure 1.

Then, their surface has been acquired with an Intel Realsense F200 depth sensor and the 3D System Sense app. [sen]. Exported meshes, without texture, have been processed to remove inconsistencies and 12 patches of approximately 100 -200cm 2 have then been obtained for each textile class. With this procedure 180 models have been created. These models are also referred as original surfaces.

To each patch, three processing operations (two adaptive simplifications to 10K and 5K vertices and one re-sampling operation to 15K vertices) have been applied to each scan. All these transformations have been designed to alter the mesh connectivity of the original scans, see Figure 2. These processing operations were automatically done using the ReMESH software [AF06]. Then, all dangling edges and self-intersections have been manually removed, so that the final patches are oriented, made of a single connected component and locally a regular. At the end of these processing operations, the full dataset is made of 720 models (180 original surfaces plus 540 tessellation variations). Figure 3 shows a representative patch for each class of patterns.

To test the methods and tune the parameters, the participants were provided with a set of examples. Such a set contains three sample patterns in different poses with four different samplings on the mesh.

Evaluation

Participants were asked to send dissimilarity matrices (of size 720x720) for the whole dataset. The challenge is to retrieve the patches that are closest to a given query. To analysis how methods are really independent of the spatial bending and robust to different tessellations, we evaluated the the retrieval performance both on the whole dataset (720 models) and on the subset of 180 scans (the similarity scores over the 180 models are derived from the matrices submitted The retrieval performances of the proposed methods were then evaluated according to the classical measures used in [SMKF04], e.g. Nearest Neighbor (NN), First Tier (FT), Second Tier (ST), e-measure (E) and Discounted Cumulated Gain (DCG). Furthermore, Precision-Recall plots have been analyzed and from the PR curves the Mean Average Precision (MAP), e.g. the average of all precision values computed for each subject in the retrieved list was estimated. As a further evaluation measure, we consider the confusion matrices obtained from the NN classification deduced from the similarity matrices.

Participants and methods

Ten groups subscribed to the contest but only six finally submitted their contributions with (up to three) dissimilarity matrices. A total of 14 runs/matrices have been evaluated and compared, including one created with a simple baseline method.

In the following sections we present all the participants and proposed methods.

Statistics of Local Features Extracted from Local Binary

Pattern Image (LBPI), by Atsushi Tatsuma and Masaki Aono

In order to capture texture features of surface object, authors estimate statistics of local features extracted from the depth-buffer image as a shape descriptor of the surface object. To emphasize the texture of surface object, they convert the depth-buffer image into the Local Binary Pattern (LBP) [OPH94] image.

Figure 4 shows the overview of our feature extraction process. As a preprocessing, authors perform the normalization of the position and scale for a given surface object. They translate the mean of the vertices to the origin, and normalize the size of the surface object to the unit sphere.

After normalization of the surface object, they render a depthbuffer image from the viewpoint defined by the mean of the facenormal vectors. To emphasize the texture of the surface object represented with depth values, they convert the depth-buffer image into the LBP image. And then, they extract local features from the LBP image. For feature detection and description algorithm, the KAZE features [START_REF] Alcantarilla | Kaze features[END_REF] are employed.

To obtain the shape descriptor of the surface object, authors calculate the mean, covariance matrix, skewness, and kurtosis of the local features. Let x 1 , x 2 , . . . , x N be the local features of size N. The mean µ, covariance matrix C, skewness s, and kurtosis k are calculated as follows [START_REF] Mardia | Measures of multivariate skewness and kurtosis with applications[END_REF]:

µ = 1 N N ∑ i=1 x i , C = 1 N N ∑ i=1 (x i -µ)(x i -µ) , s = 1 N 2 N ∑ i=1 N ∑ j=1 {(x i -µ) C -1 (x i -µ)} 3 , k = 1 N N ∑ i=1 {(x i -µ) C -1 (x i -µ)} 2 .
Since the covariance matrix C lies on the Riemannian manifold of symmetric positive semi-define matrices, the method used maps the covariance matrix onto a point in the Euclidean space by using Pennec et al.'s method [PFA06]. The final shape descriptor is obtained by concatenating the mean, covariance, skewness, and kurtosis of the local features. The shape descriptor is normalized with the signed square rooting and 2 normalization [START_REF] Jégou | Negative evidences and co-occurences in image retrieval: The benefit of PCA and whitening[END_REF]. For the dissimilarity between two shape descriptors, the Euclidean distance is employed.

Kinetic Laplace-Beltrami operator, by Frederico A.

Limberger and Richard C. Wilson (KLBO-FV-IWKS/KLBO-SV-IWKS)

The key idea of this method is to test a curvature-based Laplace-Beltrami operator (KLBO) to describe the relief patterns of surfaces. After computing the eigendecomposition of the KLBO, the Improved Wave Kernel signature (IWKS) [LW15] is computed and encoded using two different encoding schemes: the Fisher Vector (FV) or the Super Vector (SV). Lastly, differences between encodings are computed using Euclidean distance, after reducing feature dimensionality by computing PCA. In the following, we explain in more details each one of these steps.

The KLBO is a method which computes the underlying spectral components of 3D meshes using a curvature-based kinetic term, which removes the influence of shape's articulations. By defining the Lagrangian of the dynamics over the object's surface using classical field theory (1), it is possible to weight the physical field using a smooth positive kinetic density. The Lagrangian density of the system is given by:

L(φ, φ, φ, x,t) = T -V (1)
where T is the kinetic energy and V is the potential energy, and φ represents a field defined over the surface of the object. By weighting T in the Euler-Lagrange equation, which is given by the action of the system (S(L) = Ldxdt) it is possible to weight the kinetic energy differently across the field. After computing all respective derivations, it leads to the following generalized eigenproblem:

W φ = λAKφ (2)
where K is a diagonal matrix where the diagonal element K ii is the respective mean curvature H i of the vertex v i . This formulation is similar to the already known generalized eigenproblem (W φ = λAφ), where W is also given by

W (i, j) =    (cot αi j +cot βi j ) 2 if (i, j) ∈ E, ∑ k =i W (i, k) if i = j. ( 3
)
and A is a diagonal matrix where A ii represents the area of the Voronoi diagram around v i . Differently from the standard approach, the proposed formulation is less variant to non-rigid motions since articulated regions are downweighted by the curvature-based kinetic term. Therefore, the knitted fabrics or other materials do not need to be bended in a specific way.

After computing the shape spectrum (λ, φ) using (2), participants compute the IWKS which is a spectral descriptor based on the Wave Kernel Signature [START_REF] Schlickewei | The wave kernel signature: A quantum mechanical approach to shape analysis[END_REF]. To encode the local spectral descriptors they use two methods: the Fisher Vector (KLBO-FV-IWKS run) and the Super Vector (KLBO-SV-IWKS run). For more details about them and how to encode local features using these Parameters and Performances: Authors computed the first 300 eigenvalues and eigenfunctions of the KLBO using the cotangent scheme method with the kinetic-energy modifications. Then, they computed the IWKS with 100 frequencies using iwksvar = 5. For computing the dictionary, they used the first 29 models of the database to create GMMs with 38 components for each signature frequency. All experiments were performed in Matlab in a Windows PC (Intel Core i7 3.4GHz, 8GB RAM). In the beginning, all meshes were resampled to 10K faces. It takes, in average, 7 seconds to resample and compute the every model signature. The time for computing all IWKS descriptors, including the KLBO eigendecomposition, was 82 minutes. The times for computing either the FV or SV encoding for all signatures was 105 seconds and 410 seconds, respectively.

Signature Quadratic Form by Ivan Siprian and Benjamin Bustos (SQFD)

This method consists of applying the Signature Quadratic Form Distance (SQFD) [BUS09] along with intrinsic spectral descriptors. On the one hand, the SQFD distance is a suitable and effective alternative to compare 3D objects represented as a collection of local features [START_REF] Sipiran | Scalable 3d shape retrieval using local features and the signature quadratic form distance[END_REF]. On the other hand, spectral features have proven to be robust against several transformations while keeping discriminative geometric information. This proposal combines these two methods in order to represent and assess the similarity between relief patterns.

Let M be a 3D shape. First a set of local descriptors is computed on M. The computation of spectral descriptors depends, in turn, on the computation of the Laplace-Beltrami operaror and its eigendecomposition. As the complexity of this decomposition is directly related to the number of vertices of the input mesh, input models are simplified to have approximately 20,000 vertices by using the QSlim algorithm [GH97].

A local descriptor for each vertex is thus estimated in the simplified mesh. We denote the set of local descriptors of the mesh M as F M . The approach to use the SQFD distance establishes that we need to compute a more compact representation called signature. Let us suppose the existence of a local clustering on F M that groups similar local descriptors such that the number of clusters is n and F M = C 1 C 2 . . .Cn. The signature is defined as The local clustering is a key ingredient of the computation of the signatures. Participants use an adaptive clustering method that searches groups of descriptors using two distance penalties. The method uses an intra-cluster penalty λ that accounts for the maximum distance between descriptors in the same cluster. Also, the method uses an inter-cluster penalty β that accounts for the minimum distance between centroids of different clusters. In addition, the clustering method only preserves clusters with a number of descriptors greater than a parameter Nm. More details can be found in [START_REF] Sipiran | Scalable 3d shape retrieval using local features and the signature quadratic form distance[END_REF].

S M = {(c M i , w M i ), i = 1, . . . ,
Given two objects M and N, and their respective signatures S M and S N , the Signature Quadratic Form Distance is defined as

SQFD(S M , S N ) = (w M | -w N ) • A sim • (w M | -w N ) T (4)
where (w M |w N ) denotes the concatenation of two weight vectors.

The matrix A sim is a block similarity matrix that stores the correlation coefficients between clusters. To transform a distance between cluster centroids to a correlation coefficient, it is necessary to apply a similarity function and the Gaussian similarity function sim(c i , c j ) = exp(-αd 2 (c i , c j )).

(5) was chosen. Furthermore, it is necessary to choose the value of parameter α and the ground distance for descriptors. In all the proposed experiments, the choice were α = 0.9 and L 2 as ground distance. More details about the computation of signatures and the SQFD distance can be found in [START_REF] Sipiran | Scalable 3d shape retrieval using local features and the signature quadratic form distance[END_REF].

Experimental Settings

Authors proposed three runs using different configurations of the method. Here we describe the parameters used in each run a. The cosine similarity (CMC-1) between the upper triangular matrix with diagonal, i.e., for two covariance matrices,Σ i and Firstly, they calculate all the interior dihedral angles of the model surface. Then, the distribution histogram is calculated in different intervals. Finally, they adopt the Manhattan distance between histograms to describe the similarity of models. Besides, they set two interval values, bin=130:10:230 and bin=105:3:255 (Unit of Measure: Degree), and the dimension of the feature vector is 11 and 51 respectively.

Σ j , D 1 (Σ i , Σ j ) := triu(Σi) T triu(Σi) ||triu(Σi)||||triu(Σi)|| b. The von Neuman divergence (CMC-2) for two covariance matrices [DT08], Σ i and Σ j , D 2 (Σ i , Σ j ) := tr(Σ 1 log Σ i - Σ i log Σ j -Σ i + Σ j ) c.

HOG of the Geometry images Based on paper [SBR16]

, authors converted the model into a geometry image. Firstly, they use authalic parametrization to parametrize a 3D model over a spherical domain. Then, the spherical parametrization is mapped onto an octahedron. Finally, they cut the octahedron along its edges to output a flat and regular geometry image. They further use the VLFeat function vl_hog to extract the HOG features of geometry images to evaluate similarity between models.

Geodesic Multi-resolution (GMR) Approach by Majid

Masoumi, Mahsa Rezaei, A. Ben Hamza

Authors use a geodesic multi-resolution descriptor [MLH16] by incorporating the vertex area into the definition of spectral graph wavelet [LB13] in a bid to capture more geometric information and, hence, further improve its discriminative ability. Moreover, Mexican hat wavelet has been utilized as a generating kernel, which considers all frequencies equally-important overall as opposed to the cubic spline kernel [LB13]. Furthermore, in order to capture the spatial relations between features, the proposed geodesic multiresolution descriptor is weighted by geodesic exponential kernel.

While the approach focuses primarily on 3D object retrieval, this framework is fairly general and can be used to address a variety of shape analysis problems, including segmentation and classification [MH17].

The geodesic multi-resolution framework consists of four main steps. The first step is to represent each 3D shape in the dataset D by a spectral graph wavelet signature matrix S, where S = (s 1 , . . . , sm) ∈ R p×m , and s i is the p-dimensional local descriptor at vertex i and m is the number of mesh vertices. In the second step , the area-weighted spectral graph wavelet signatures s i are mapped to high-dimensional mid-level feature vectors using the soft-assignment coding step of the BoF model, resulting in a k × m matrix U = (u 1 , . . . , um) whose columns are the k-dimensional midlevel feature codes. In the third step, the k × k geodesic multiresolution matrix F is computed using the mid-level feature codes matrix and a geodesic exponential kernel as follows:

F = UKU , (6)
where U is a k × m matrix of geodesic multi-resolution codes (i.e. mid-level features), and K = (κ i j ) is an m×m geodesic exponential kernel matrix whose elements are given by

κ i j = exp - d 2 i j ε , (7)
with d i j denoting the geodesic distance between any pair of mesh vertices v i and v j , and ε is a positive, carefully chosen parameter that determines the width of the kernel. Then F is reshaped into a k 2 -dimensional global descriptor x i . In the fourth step, the geodesic multi-resolution vectors x i of all n shapes in the dataset are arranged into a k 2 × n data matrix X = (x 1 , . . . , xn). Finally, a query x is compared to all data points in X using 1 -distance to find the most relevant shapes to the query. The lower the value of this distance is, the more similar the shapes are.

Baseline method: Curvature Histograms (CH)

As a baseline of the benchmark we have implemented the histogram of the minimal curvature. In our settings, for every surface, we computed the value of the minimal curvature on each vertex using an implementation of the method [CSM03]. Then, an histogram of 128 bins is kept as signature of the that surface, see Fig- ure 6. As distance between two surfaces we adopt the Manhattan distance between the corresponding histograms. The histograms of curvature used as baseline are not multi-resolution neither store any adjacency of relationship between the elements of the surface.

Results

Retrieval scores obtained by the different runs of the proposed methods are shown in Table 1. It is possible to see that globally the performances appear rather poor. Sufficiently good results on first retrieval (NN) should not mislead, as they are clearly biased by the inclusion in the dataset of four different meshes representing the same acquired patch. If we estimate the same scores on a subset of the data with single instances of each patch (180 patches with 12 differently shaped patches for each class), this effect is removed (Table 5). The method that seems more effective in retrieving similar patterns independently on the background shape is therefore not the one with top performances on the whole dataset (KLBO-FV-IWKS), but CMC-2 that actually increases many retrieval scores on the single-instances dataset. This could mean that the method is not robust against remeshing.

KLBO-FV-IWKS demonstrates a sufficient ability in pattern retrieval, but, on the other hand, seems to include in the similarity estimation information on the global shape, not only on the relieved pattern. Note that even if a method correct large scale bending of a shape, a signature may depend on the global area and contour of the shape while in our task it is important to characterize statistically the relief pattern.

Other methods seem mostly to fail both in retrieve patches with similar shape and similar pattern.

To better understand the behavior of the methods, it is interesting to investigate the performances of the methods for the different classes of patterns. Figures 7 and8 ods are not similarly ranked for all the classes, as methods that are not successful on selected classes are often good on others. Figure 11 shows the Precision vs Recall plot for class 9 showing that for this pattern (regularly spaced motifs of about 1-2 cm of size) the method giving the best performances on most classes (CMC-2) is not effective, while LBPI gives sufficiently good results. This fact shows that methods may be differently tuned for pattern size and depth and a combination of them could be largely improve the retrieval scores.

Given a dissimilarity matrix, the associated confusion matrix CM is a squared matrix whose order is equal to the number of classes (15) in the dataset. For a row i in CM, the element CM(i, j) gives the number of items which have been misclassified, resulting as elements of class j rather then elements of class i. Thus, the classification matrix CM of an ideal classification system should be a diagonal matrix, such that the element CM(i, i) equals the number of items belonging to the ith class. The confusion matrices shown in Figure 12 give an overview of the correct/incorrect classification achieved when the NN is used as a classifier. These matrices are estimated on the 180 patches original dataset without remeshings, so they are not biased by global shape matching. The perfect matrix should contain only a diagonal of yellow elements while the others should be green. What is interesting is that some classes (like 4 and 10) are challenging for all methods while others are quite well kept by several techniques (for instance 1, 4, 9, 15). CMC-2 is also able to provide for some classes high precision values at high recall values. Classes with larger and more relieved patterns seems to be more easily characterized and this is probably related to the noisy real-world acquisition. No method is successful in retrieving patches of the same class.

Discussion

The retrieval of surface patches with different spatial embeddings but with same relief patterns given an example is a practical task with several potential applications. One particular application that is interesting for track organizers is, for example, artworks' analysis, where the aim is to characterize materials (studied in the Scan4Reco project [sca]) and styles or repeated decorations (incision on beard and hair, helmets, etc) on Cultural Heritage artifacts (such as those analyzed in the GRAVITATE project [GRA]). Several authors recently proposed methods to characterize these patterns, however, the lack of labeled datasets was a limit in evaluating them. For this reason we proposed a novel dataset realized bending differently relieved tissues and acquiring patches with a depth sensor and organized a specific Shape Retrieval contest. This dataset includes patterns of different spatial frequency and resulted more challenging than expected, also due to the fact that it was created with a noisy real world capture of depth data. However, as humans can distinguish and assign the pattern visually on renderings, it is expected that algorithms that can retrieve correctly the same class instances given an example could be developed.

The simple curvature-based baseline method as well as more sophisticated global spectral approaches proposed by participants showed quite poor results. A few methods demonstrated more promising results, especially for selected relief patterns. The Kinetic weighting of Laplace-Beltrami operator proposed by Lim-berger&Wilson seems effective in the removal of surface bending, even if the descriptor appears to be still influenced by the patch shape. Velasco-Forero&Fehri as well as Tatsuma&Aono showed that exploiting image processing methods for 2D texture may be a viable solution, but that methods should be improved for practical applications.

Figure 1 :

 1 Figure 1: Renderings of the 12 patches acquired and cropped for a single tissue class.

Figure 2 :

 2 Figure 2: Detail of an original mesh scan and its three sampling variations.

Figure 3 :

 3 Figure 3: Example meshes acquired on the 15 tissue classes.

!Figure 4 :

 4 Figure 4: Overview of feature extraction process based on statistics of local features.

  n}, where c M i = ∑ d∈C i d |Ci| and w M i = |Ci| |FM | . Each element in the signature contains the average descriptor in the cluster (c M i ) and a weight (w M i ) to quantify how representative is the cluster in the collection of local descriptors.

•

  SQFD(WKS). Participants used the normalized Wave Kernel Signature[START_REF] Schlickewei | The wave kernel signature: A quantum mechanical approach to shape analysis[END_REF] as local descriptor. The parameters for local clustering were λ = 0.2, β = 0.4, Nm = 30. • SQFD(HKS). The normalized Heat Kernel Signature [SOG09] was used as local descriptor. The parameters for local clustering were λ = 0.2, β = 0.4, Nm = 30. • SQFD(SIHKS). The Scale-invariant Heat Kernel Signature [BK10] was used as local descriptor. The parameters for local clustering were λ = 0.01, β = 0.02, Nm = 20. 4.4. Covariance descriptor by morphological analysis of curvature estimations by Santiago Velasco-Forero and Amin Fehri The proposed method computes an image covariance descriptor from morphological transformation of local estimation of curvature for a given 3-dimensional mesh S. A scheme to illustrated the description of the method is given in Fig. 5. Four main components are used to compute this descriptor: 1. First, the local principal curvatures, κ 1 , κ 2 and the Gaussian curvature, κ G = κ 1 , κ 2 are computed [CSM03, ACSD * 03]. The estimation of κ 1 and κ 2 is performed by the largest and smallest eigenvalues of a smoothed estimation of local normal sections [Pey11]. Authors fixed 11 as smoothing parameter. 2. Second, curvature values on the three-dimensional surface are projected to a flat surface (two dimensional). Accordingly, the boundary of the mesh, i.e. the set of vertices that are only referenced by a single triangle in the mesh was found. This set is denoted by Boundary(S). Then, a support vector machine (SVM) was trained in a regression problem from the 3D coordinate of Boundary(S) to a discrete square of value from [0, 256] × [0, 256], i.e. T : R 3 → Z 2 . In this way it is possible to represent the curvature information (κ 1 , κ 2 , κ G ) of S by three images. 3. At this point, it is possible to take advantage of image processing texture descriptors to characterize the original 3D surface. Participants used mathematical morphology operators in this task [Soi13]. For binary or grey-scale images, they are simple in the sense that they usually have an intuitive interpretation. Erosion ε SE (I) (or minimum operator in a neighborhood) shrinks bright objects, whereas dilation δ SE (I) (or maximum operator in a neighborhood) expands bright objects at the boundary. The size and shape of the effect is controlled by the structuring element SE (neighborhood). The morphological opening γ SE (•) is an idempotent transformation defined by composition of erosion and dilation, i.e. γ SE (I) = δ SE (ε SE (I)). As the goal is to characterize the local texture of the curvature, rather than finding an optimal fixed value of size of SE, authors focus on a range of values for the scale parameter. Thus, they produce 32 transformations of each curvature image by considering: 1) γ SE• operator by considering SE• as disks with radius from 1 to 16 2) The maximum of γ SE0 , γ SE45 , γ SE90 where SEx a discrete line of angle x and radius from 1 to 32 by 2. In conclusion, they have 96 images from each 3-dimensional mesh S. 4. Finally, the covariance matrix of 96 images is computed, to produce a descriptor as a square matrix of size 96 × 96 in the sense of [TPM06]. 5. The similarity between two meshes is calculated via their representation as covariance matrices by using the following measures:

Figure 5 :

 5 Figure 5: Proposed method includes three local curvature estimations, a projection from T : R 3 → Z 2 and a set of morphological transformation by opening. The final descriptor is covariance matrix of size 96 × 96. Details are included in Section 4.4.

Figure 6 :

 6 Figure 6: Two surfaces (left) and the corresponding histograms of minimal curvature (right).

  depict the Precision-Recall curves for the whole dataset of 720 patches and the original set of 180 models, respectively. Details of the Precision-Recall curves of some specific classes are shown in the Figures 9, 10 and 11.The most interesting fact is that the performances of the meth-NN 1-Tier 2-

Figure 7 :

 7 Figure 7: Precision vs. Recall plot for all the proposed runs on the full dataset.

Figure 8 :

 8 Figure 8: Precision vs. Recall plot for all the proposed runs on the single patch instances dataset. Overall results are similar, but CMC behaves now better than KLBO and NN performances are decreased.

Figure 9 :

 9 Figure 9: Precision vs. Recall plot for the best runs of each participants on class 1 objects, characterized by the pattern on the left. Best methods (CMC-2 and LBPI) are able to retrieve similar patterns given the examples.

Figure 10 :

 10 Figure 10: Precision vs. Recall plot for the best runs of each participants on class 4 objects, characterized by the pattern on the left. No method is successful in retrieving patches of the same class.

Figure 11 :

 11 Figure 11: Precision vs. Recall plot for the best runs of each participants on class 9 objects, characterized by the pattern on the left.

Table 1 :

 1 Retrieval scores of the different runs proposed on the full set of surface patches. NN values are biased by the remeshing of the same patches.

		Tier e	DCG mAP
	CH	0.196 0.089 0.160 0.077 0.500 0.122
	LBPI	0.828 0.248 0.400 0.232 0.697 0.283
	IDAH-1	0.390 0.157 0.254 0.145 0.578 0.174
	IDAH-2	0.306 0.141 0.244 0.127 0.559 0.163
	GI HOG	0.686 0.107 0.176 0.102 0.561 0.131
	SQFD-SIHKS	0.168 0.127 0.239 0.106 0.532 0.158
	SQFD-HKS	0.536 0.117 0.192 0.110 0.558 0.139
	SQFD-WKS	0.510 0.112 0.191 0.102 0.549 0.136
	CMC-1	0.718 0.258 0.372 0.247 0.673 0.260
	CMC-2	0.763 0.272 0.389 0.261 0.686 0.271
	CMC-3	0.647 0.219 0.323 0.208 0.639 0.218
	KLBO-FV-IWKS 0.986 0.333 0.449 0.332 0.759 0.339
	KLBO-SV-IWKS 0.978 0.287 0.409 0.283 0.732 0.296
	GMR	0.079 0.066 0.128 0.054 0.474 0.113

Table 2 :

 2 Retrieval scores on the partial dataset with single instances of each patch.

		NN 1-Tier 2-Tier e	DCG mAP
	CH	0.206 0.132 0.222 0.145 0.437 0.165
	LBPI	0.339 0.207 0.353 0.237 0.518 0.250
	IDAH-1	0.272 0.163 0.262 0.175 0.480 0.201
	IDAH-2	0.339 0.182 0.271 0.181 0.503 0.215
	GI HOG	0.089 0.069 0.130 0.097 0.373 0.118
	SQFD-SIHKS	0.167 0.111 0.213 0.157 0.423 0.163
	SQFD-HKS	0.106 0.066 0.137 0.102 0.376 0.123
	SQFD-WKS	0.067 0.073 0.148 0.108 0.380 0.129
	CMC-1	0.600 0.342 0.461 0.274 0.641 0.371
	CMC-2	0.633 0.363 0.494 0.293 0.662 0.390
	CMC-3	0.533 0.281 0.394 0.242 0.596 0.308
	KLBO-FV-IWKS 0.522 0.295 0.412 0.247 0.603 0.307
	KLBO-SV-IWKS 0.489 0.249 0.375 0.235 0.570 0.273
	GMR	0.061 0.061 0.119 0.089 0.364 0.112

c 2017 The Author(s) Eurographics Proceedings c 2017 The Eurographics Association.

Acknowledgments This work was partially supported by the Scan4Reco project funded by European Union's Horizon 2020 Framework Programme for Research and Innovation under grant agreement no 665091 and the GRAVITATE project, European project H2020 REFLECTIVE, grant agreement n. 665155, (2015-2018). A. Tatsuma and M. Aono were supported by Kayamori Foundation of Informational Science Advancement, Toukai Foundation for Technology, and JSPS KAKENHI Grant Numbers 26280038, 15K15992.


Elena Viorica Epure
email: elena.epure@malix.univ-paris1.fr

Rebecca Deneckere
email: rebecca.deneckere@univ-paris1.fr

Camille Salinesi
email: camille.salinesi@univ-paris1.fr

Rébecca Deneckere

Analyzing Perceived Intentions of Public Health-Related Communication on Twitter Preprint

Keywords: intention mining, text mining, natural language processing, classification, machine learning, Twitter, speech acts, linguistics

Introduction

The Internet has nurtured a highly available and accessible environment for disseminating health information. While in 2001, 70 000 websites contained healthrelated information [START_REF] Cline | Consumer health information seeking on the internet: the state of the art[END_REF], the order of magnitude for healthcare-verbatim websites only, has increased by three by 2013 in the United States [START_REF] Fox | Health online 2013[END_REF]. Correlated to the massive production of online health-related content, the number of online health information seekers has doubled in this period, reaching 100 million [START_REF] Cline | Consumer health information seeking on the internet: the state of the art[END_REF][START_REF] Fox | Health online 2013[END_REF]. Nowadays, the dissemination and consumption of health information have been also impacted by the tremendous adoption of social media [START_REF] Perrin | Social media update 2016[END_REF]. This has led to the creation of communities, fostered by the interpersonal interactions with acknowledged advantages such as anonymity and 24-hour availability [START_REF] Cline | Consumer health information seeking on the internet: the state of the art[END_REF].

Social media allows to disseminate health information, express beliefs, feelings about health matters and react to existing content. One's beliefs are built on or altered by the information to which he or she is exposed [START_REF] Cline | Consumer health information seeking on the internet: the state of the art[END_REF]. This could be further reflected in new behavioral intentions and eventually new behaviors [START_REF] Ajzen | The theory of planned behavior[END_REF].

Social media has even a stronger influence on consumers because of the social norms: the attitudes and behaviors of the community towards health matters are transparent in this online environment. This aspect could be exploited to promote healthy behavior such as quitting smoking. However, inaccurate information, available to a very large and generally vulnerable target-people impacted directly or indirectly by chronic diseases, could become harmful and have mass consequences [START_REF] Cline | Consumer health information seeking on the internet: the state of the art[END_REF]. Therefore, there is an urge in healthcare to understand the effects of the exposure to health information disseminated through social media, on consumers. The reason is to predict these effects as potential immediate or long-term behaviors [START_REF] Cline | Consumer health information seeking on the internet: the state of the art[END_REF][START_REF] Calvert | An ecological view of internet health information seeking behavior predictors: Findings from the chain study[END_REF]. However, suitable methods are necessary for this.

In the current paper, we propose a means to discover automatically the perceived intentions of the Twitter public posts. We call them perceived because they are interpreted from the stance of the information consumer. The link between perceived intentions and revealing or predicting behavior is as follows. First, the perceived intentions are a behavioral component of health disseminators. Second, the perceived intentions allow to create automatic techniques to measure the impact of various message formulation on health information consumers, similar to message framing [START_REF] O'keefe | The relative persuasiveness of gain-framed loss-framed messages for encouraging disease prevention behaviors[END_REF]. For instance, is a consumer more likely to read an online, health-related article if its link is tweeted in a rhetorical question or in an informative fact? Third, we want to support the automatic discovery of collective narratives concerning healthcare, as they can be strong drivers for behaviors [START_REF] Houghton | Modeling the influence of narratives on collective behavior case study[END_REF]. Automatic techniques already exist for identifying components of the crowd narratives such as topics or events [START_REF] Prieto | Twitter: A good place to detect health conditions[END_REF]. However, disseminators' disposition towards presented events is necessary for a thorough narrative's representation [START_REF] Murphy | The role of clinical records in narrative medicine: A discourse of message[END_REF].

Related Work

Related works to analyze the exposure to health information disseminated on social media rely on traditional research methods [START_REF] Calvert | An ecological view of internet health information seeking behavior predictors: Findings from the chain study[END_REF][START_REF] Cline | Consumer health information seeking on the internet: the state of the art[END_REF][START_REF] O'keefe | The relative persuasiveness of gain-framed loss-framed messages for encouraging disease prevention behaviors[END_REF]. First, data is gathered through interviews and questionnaires. In order to reach people consuming online health information, clinics, hospitals or online communities are targeted. Then, the data is analyzed using statistics or qualitative methods. Although, these methods empowered the healthcare community to gain valuable insights, there are several limitations. The research results are mainly descriptive. However, for acting on the existing knowledge, predictive models are required too. Further, an extensive study is rarely possible, the reported samples being at best of several thousand subjects. These studies also come with localization and time-span constraints. In reality an online community could include worldwide members. Moreover, the questions of how certain results change over time, or how the discovered knowledge depends on current temporal trends, or how predictions could be made in real-time are challenging to answer.

Computer science methods to complement existing studies, by exploiting automatically social media in creating predictive models, exist [START_REF] Ding | Mining user consumption intention from social media using domain adaptive convolutional neural network[END_REF][START_REF] Hemphill | Tweet acts: How constituents lobby congress via twitter[END_REF][START_REF] Wang | Mining user intents in twitter[END_REF]. However, predicting behavior in social media requires deep consideration of underlying processes, of how the cause-the disseminated health information-leads to the effects-the behavior changes. Hence, a solution should go beyond the black-box approach often employed in data mining and incorporate also theoretical knowledge from humanities. In conflict resolution, a model for predicting behavior changes from Twitter, based on narrative theory, is proposed [START_REF] Houghton | Modeling the influence of narratives on collective behavior case study[END_REF]. Focused on perception, Myslin et al. [START_REF] Myslin | Using twitter to examine smoking behavior and perceptions of emerging tobacco products[END_REF] discover narrative-related elements from tweets about smoking: genres (e.g. first-hand experience, opinion) and themes (e.g. cessation, pleasure). Priesto et al. [START_REF] Prieto | Twitter: A good place to detect health conditions[END_REF] identify health topics from tweets, similar to narrative's themes (e.g. depression, flue). Though, a solid start for our long-term goal, these works can be augmented with more high-level behavioral cues.

Research Design

Our objective is to analyze the perceived intentions of the publicly disseminated tweets. Specifically, several research questions are identified:

1. Could a valid taxonomy of perceived intentions, representative for Twitter public communication be defined? 2. How do various supervised machine learning algorithms with various configurations of features compare for discovering perceived intentions? 3. What are the most predictive features for each type of intention? Data Collection. We collected two sets of tweets via Twitter Streaming API. The first consists of 2714 tweets and the second of 43153 tweets. The first set was fetched by the keyword autoimmune. The second set was collected with commonly used medical terms and jargon, proposed by Ridpath et al. [START_REF] Ridpath | Looking at research consent forms through a participant-centered lens[END_REF]. Even though the communication on autoimmune diseases was initially targetted, we included the second set for data diversity in evaluation, thus aiming at the input generalizability. Further, we sampled randomly 600 tweets from the first set and 500 tweets from the second set, with no message format duplicates. The selected 1100 tweets were used in the intention taxonomy's validation and in creating the ground-truth corpus for the machine learning experiment.

Research Method. For the first research question, we considered as valid an intention taxonomy that is consistently applied by raters, showing thus an alignment in the tweets' perception and ensuring experimental reproducibility. For this, the selected corpus was tagged in parallel by two raters: one expert involved in defining the taxonomy, the other seeing the taxonomy for the first time (researcher in computer science). The taxonomy was briefly presented as the inexperienced rater was expected to rather rely on its intuition when tagging. At least one intention had to be chosen per tweet. More intentions were allowed when the tweet had multiple sentences or one intention could not be clearly conveyed. After the tagging, the Fleiss' Kappa statistical test [START_REF] Fleiss | Large sample standard errors of kappa and weighted kappa[END_REF] was used for evaluating the validity. When multiple tags were used, an alignment of the sets was necessary. For instance, [t 1 , t 2 ] and [t 2 , t 1 , t 3 ] would align as: t 1 -t 1 , t 2 -t 2 , t 3 -unknown. The test considers the degree of agreement for each such pair and the probability of agreeing by chance. A score of the Fleiss' Kappa test over 0.6 is considered a good result, specifically between 0.61 and 0.8 substantial and between 0.81 and 0.99 almost perfect [START_REF] Fleiss | Large sample standard errors of kappa and weighted kappa[END_REF]. Further, for assessing if the taxonomy was representative, a tag other was created to be used when none of the proposed intentions was a suitable choice and its frequency was computed.

For the next research questions, several steps were required. First, the truth set was created based on the tagged corpus. For each non-agreement, a discussion took place between the raters and a collective final decision was made. In the final corpus1 , 89% of the tweets were single-tag and the rest had associated 2-3 intentions. Second, text processing and Tweet NLP [START_REF] Owoputi | Improved part-ofspeech tagging for online conversational text with word clusters[END_REF] were applied for feature extraction. Two types of features were defined: Content and Discourse features. Content features consisted of standard text mining features: BagOfWords and OpinionKeywords. These were computed after the corpus' lower case conversion and lemmatisation. BagOfWords was a dictionary of tokens and their frequencies. The tokens were extracted from the pre-processed Twitter corpus before the classification. OpinionKeywords included the frequencies and ratios of negative and positive opinion words from a predefined lexicon [START_REF] Liu | Opinion observer: Analyzing and comparing opinions on the web[END_REF]: freqPositiveWords, ratioPositiveWords, freqNegativeWords, ratioNegativeWords. Discourse features are novel and defined by considering linguistic means to express intentions. They are described in Section 5, after introducing the proposed taxonomy.

Logistic Regression, Linear SVM, Random Forest and Multinomial Naive Bayes were the selected classifiers. The scikit-sklearn2 implementations were used with default parameters. Multinomial Naive Bayes was selected as its library's implementation allowed continuous features too. Naive Bayes and Random Forest handled inherently multiple classes while Logistic Regression and Linear SVM in an on-versus-all strategy. Various configurations of features were evaluated: discourse features only (DiscF ), content features only (ContF ), all features (AllF ). Also, the features were scaled beforehand. The metrics for performance evaluation of the single-tag corpus were precision, recall and f-score. These were computed as macro scores, weighted by the support of each intention and averaged over 10 folds. Same evaluation decisions were applied within each fold in cross-validation. The hamming loss was used to evaluate the accurate prediction of multi-tag corpus. For this, the single-tag corpus was the train set and the multi-tag corpus the test set. The hamming loss is the ratio of intentions in average that are incorrectly predicted. Finally, with no interaction in models, the most predictive features per intention were found by analyzing the weights of the best classifier, trained on standardized features' values [START_REF] Gelman | Scaling regression inputs by dividing by two standard deviations[END_REF].

An Intention Taxonomy for Public Tweets

Human behavior is intrinsically intentional as thoroughly discussed in philosophy [START_REF] Bratman | Intention, plans, and practical reason[END_REF] and psychology [START_REF] Ajzen | The theory of planned behavior[END_REF]. Though, behavior is not necessarily linked to only physical human acts but also to language. Generally, people communicate with various intentions. Utterances are considered thus as acting through words while their leading intentions are called speech acts [START_REF] Searle | Speech acts[END_REF]. For example, This hospital has a nonstop emergency service asserts the speaker' belief about the world while Could you please give me a painkiller? requires the listener to act. Searle [START_REF] Searle | Speech acts[END_REF] proposed five classes of speech acts. An assertive is used for stating information being true or false about the state of affairs in the speaker's world. A commissive denotes the engagement of the speaker to a future course of action. A directive implies the listener carrying out an action as a result of the speaker's utterance. An expressive is used to express the speaker's feelings towards the state of affairs in the world. Finally, a declarative is the type of utterance, changing the world' state such as firing someone. The speech act theory emerged over time, as a highly-adopted framework to extract or predict behavior from text.

However, we aimed at more granular intentions than Searle's classes [START_REF] Searle | Speech acts[END_REF]. This was enabled by the work of Vanderveken [START_REF] Vanderveken | Meaning and speech acts[END_REF] who proposed a lexicalization of the intentions through 300 English verbs. These verbs are organized in five hierarchies where the roots are the speech act classes and each level is a specialization of the parents. Our taxonomy emerged from the Vanderveken's theoretical work [START_REF] Vanderveken | Meaning and speech acts[END_REF] but its refinement was based on manual corpus analysis. Thus, we empirically discovered that assertive and directive classes cover most of Twitter public communication (see Table 1). These findings are not surprising considering that public tweets rarely contain personal feelings (expressive) or personal goals (commissive). Such communication takes place rather privately. Moreover, declarative speech acts are very rare even in live settings. The rational behind the association of intentions to tweets is presented further. An assert is a tweet that clearly conveys the message such as news or personal public declarations. Though often it has a url, the linked resource appears with the role to sustain or detail the message. A hypothesize is a tweet containing a weak assertion such as probable statements or hypothetical questions. Compared to the assertives, a propose is a tweet that always references an external resource, which must be accessed in order to consume the message. The propose tweets usually provide key or opinion words about the resource's content and could be considered a weak attempt to make the reader access the url. In contrast, a direct is a strong attempt to make the reader act to demands, requests, invitations, encouragements or questions. Finally, advise and warn, which are very similar, are directives to a future action or resource consumption that is supposed to be good or bad for the reader.

Discourse Features for Intention Discovery

A person could use Twitter for addressing utterances to the community or to specific users. In a live communication, the utterance's intention is implicitly understood from the utterance's content, speaker's gestures and voice. Though not as rich as this case, the written tweets have also characteristics that convey their intentions. We relate them to Discourse features, which are further presented.

PronominalKeywords are frequencies of various pronominal forms. The first person singular (freq1stPersonSg) is chosen because it could be a sign of personal declarations specific to assert tweets (e.g. I'm for vaccination.). Similarly, the third person (freq3rdPerson) could be linked to assert tweets when reporting. By contrary, the first person plural form ( freq1stPersonPl ) or second person (freq2ndPerson) could be cues of direct tweets (e.g. We must vaccinate our kids! You should too). Further, PunctuationMarks are indicators of the discourse' functions: the presence of exclamation (hasExclamation), interrogation (hasQuestion), ellipsis (hasEllipsis; for omissions, hesitations); colon (hasColon; for titles, explanations) or quotes (hasQuotes). QuestionKeywords complements the punctuations for revealing discourse functions (e.g. questions). We separate the frequency of what, when, where, why, who (freq5W ), from that of how (freq1H ) because how is also used in advice or proposals (e.g. How I Gave Up Smoking).

The frequency of EmoticonCues (freqEmoticons) could be inversely correlated with the impersonal reporting; hence possibly linked to assert and propose tweets. Both ASCII and Unicode emoticons were checked. TitleCues (hasTitle) seems to be an often marker for news, being thus a potential discriminator for the assert and propose tweets (e.g: New Releases in Science). VerbPhrases (hasVerb, present and past participles not considered) could be an indicator of weak directives when false. These tweets often lack the subject-predicate form. VerbMoods contains hasImperative, which is frequent in requests, demands; thus being an indicator of direct tweets. For identifying imperatives, we created a rulebased algorithm, having as input the part-of-speech (POS) tags. VerbKeywords encompasses features regarding the modals (hasCan, hasCould, hasMust, has-May, hasMight, hasShould ). Modals could show various intentions: hypothesize, advise, direct etc. For verb features, negative forms were identified too.

SyntaticConstructs features are created with the goal of incorporating syntactic characteristics of the discourse. The assumption was that tweets with same intention might share similar discourse form. We used the POS tags in order to dynamically discover representative POS-related features. The way we proceeded was: POS-tag the corpus using a dedicated tweet NLP parser [START_REF] Owoputi | Improved part-ofspeech tagging for online conversational text with word clusters[END_REF]; compute the normalized frequencies of each two consecutive POS tags from the output; select those with a score of at least 0.5 per intention. The final syntactic features are: hasNV, hasNN, hasAN, hasNComma, hasPN, hasDN, hasVN, hasCommaU, hasNP. The encoding of these features is: N nouns; V verbs, A adjectives, Comma punctuation, P pre-, post-position or subordinating conjunctions, D determiners, and U urls. Compared to the original output of the parser [START_REF] O'keefe | The relative persuasiveness of gain-framed loss-framed messages for encouraging disease prevention behaviors[END_REF], two changes were made. N incorporates also the proper nouns (the symbol ˆ) and pronouns (the symbol O). Comma replaces ,.

Results and Discussion

The first research question sought to answer if the proposed intention taxonomy was representative for Twitter public communication and valid. The condition of being representative could be considered fulfilled through artifact design, by being both theory-and corpus-driven. Relying on theory, we ensured that the taxonomy was linguistically representative for written utterances. Relying on corpus analysis, we ensured that the taxonomy was mapped on the actual Twitter public communication. Further, we agreed that a high frequency of the tag other would denote a lack of representativeness. However, other was used only in 0.005 of the cases by both raters, supporting thus our taxonomy's design. The tag other replaced expressives such as greetings or commissive such as public promises. The Fleiss' Kappa test was performed to assess the taxonomy's validity (see Table 2). The overall intention-wise Fleiss' Kappa score was 71.5% (z=40.9, p=0.001) being considered a substantial result. All intentions apart from advise and other achieved substantial scores. The result for other is not surprising given its very low frequency. The overall class-wise Fleiss' Kappa score was 78.3% (z=28.1, p=0.001), showing thus that mismatches occurred sometimes between intentions of the same class. Related works of speech act tagging for tweets reported similar results (Kappa scores between 0.6 and 0.85) [START_REF] Ding | Mining user consumption intention from social media using domain adaptive convolutional neural network[END_REF][START_REF] Hemphill | Tweet acts: How constituents lobby congress via twitter[END_REF][START_REF] Wang | Mining user intents in twitter[END_REF]. Several decisions were made for the final corpus creation. 82% of mismatches between raters concerned the advise tweets, specifically with propose (55%), direct (25%), assert (15%), warn (5%). By further manual analysis, we concluded a tweet was an advice either because it redirected the reader to an external source that actually contained an advice or it directly contained the advice. The first case corresponded to mismatches involving propose (e.g. [START_REF] Cline | Consumer health information seeking on the internet: the state of the art[END_REF] Steps to Heal Leaky Gut and Autoimmune Disease URL), while the second case to mismatches regarding direct (e.g. #TipTuesday: Vitamin D deficiency is linked to autoimmune diseases. Add mushrooms to Thanksgiving! ) and assert (The quicker you receive treatment, the better your chances for a good recovery from #Stroke are). It might be surprising an advice is stated as an assert but this is an example of indirect speech acts. Nevertheless, what emerges is that an advise tweet could be ultimately a propose, direct or assert too. Considering its low Fless' Kappa score, we decided for now to transform the advise tweets in their secondary speech acts. Moreover, we transformed the warn tweets too because of insufficient instances (0.02% of the corpus) and for maintaining consistency with advise.

The next research question looked into the comparison of classifiers with different features' configuration. The results are summarized in Table 3. Statistically, Logistic Regression and Linear SVM are comparable (p > 0.5, two-tailed t-test) and both outperformed Random Forest. Multinomial Naive Bayes is not reported as yielded results similar to Random Forest for DiscF and ContF, and worse for AllF. We can notice that DiscF systemically leads to similar results as AllF (apart from hypothesize with Logistic Regression) and improves results over ContF up to 5 times with Random Forest. For multi-label classification, the minimum hamming loss scores are obtained when using DiscF with Logistic Regression (0.287) and Linear SVM (0.264).

The last research question aimed at the evaluation of the features' predictive power in relation to each intention. This was assessed based on the features' weights estimated for Linear SVM. As expected, for assert, the most predictive discourse features are related to reporting information or making public declarations: hasVerb, hasNV, hasQuotes, freq3rdPerson, freq1stPersonPl, freq1stPersonSg. The most representative content features seem to be related to news and particularly to scientific ones ("implications", "future", "bacteria", "influence"). For hypothesize, both the discourse and content features reveal the importance of modals ("might", "may" and "could"). Apart from these, the most important discourse feature is hasQuestion. For direct, hasImperative is the most discriminatory feature. This also emerges from top predictive content features that contain multiple verbs ("know", "learn", "read", "check", "enjoy"). Then, features linked to requests, encouragements and questions follow in importance in the classification of direct: for discourse features-hasQuestion, hasExclamation, freq2ndPerson, freq1H, freq5W; for content features -"what", "please", "let". For propose, the top most important discourse features are related to news summaries (hasTitle, freq5W, hasColon) and advice or warnings (freq1H, hasMust, hasShould, freq2ndPerson). These features are correlated to the content ones, which incorporate interrogation cues ("why", "how"), impersonal scientific words ("epidemic", "lupus") and advice/warning words ("step", "recipes", "good"). Finally, the POS-related features appear highly predictive for all intentions, in particular for assert, direct and hypothesize.

In conclusion, the proposed discourse features improved significantly the discovery of intentions and we often observed that they were also correlated to the top most important content features. However, the discourse features benefit of being much fewer (30 vs. 4608) and corpus-independent, allowing thus reproducibility on other medical English corpora. In the analyzed corpus, the most popular intentions are assert (46%) and propose (41%) revealing thus that Twit- ter is publicly used for information dissemination. However, it is quite interesting that the strategies are different, half of the tweets' messages being self-standing (assert) while the other half requiring external redirection (propose). The ratio of direct tweets (18%) shows also a significant expected reaction from consumers, by replying or following advice, warnings, requests or invitations. Similar to us, Godea et al. [START_REF] Godea | An analysis of twitter data on e-cigarette sentiments and promotion[END_REF] identify tweets' purposes in healthcare (advertising, informational, positive or negative opinions). However, we focus on intentions as established by pragmatics, ensuring thus a domain-independent, general approach.

Conclusion and Future Work

An approach for analyzing the perceived intentions in the Twitter public communication was proposed. An intention taxonomy for public tweets was defined and validated. Its automatic discovery proved effective, with f-scores between 0.73 and 0.8 using Linear SVM and discourse features only. The most predictive content features were often linked to the discourse ones and intentions, acting thus as a positive feedback loop to the proposed taxonomy and features' decisions. Future work must address several limits. As advise and warn had low scores, the taxonomy must be revised and experiments deployed with more raters. Twitter private communication should be researched too, including intentions from expressive and commissive. The impact of parameters' values on classifiers' performance must be assessed. Finally, as the proposed approach is domainindependent, we envision a large-scale analysis of public, health-related tweets. Information dissemination in different communities (e.g. diseases) can be compared. The public's reactions to the same, but differently formulated messages can be analyzed (e.g. which formulation is most re-tweeted?). Then, within a community, conflicting narratives could emerge. The work of Houghton et al. [START_REF] Houghton | Modeling the influence of narratives on collective behavior case study[END_REF] can be extended to identify them while also considering disseminators' dis-position as perceived intentions. The current work is our first attempt in joining narrative medicine, for bringing the patient as a subject back into medicine [START_REF] Kalitzkus | Narrative-based medicine: Potential, pitfalls, and practice[END_REF].

Table 1 .

 1 Identified intentions from Twitter public communication.

	Class	Intention	Tweet Example
	Assertive assert	New study reveals autoimmune/inflammatory syndrome
			triggered by HPV vaccine URL
	Assertive hypothesize Vitamin B1 may help relieve fatigue in Hashimoto's thyroid
			patients URL
	Directive propose	The gut microbiota and inflammatory bowel disease #mi-
			crobiology #autoimmune URL #gutmicrobiota
	Directive direct	Are you a Cure Champion? Sign up for the Walk to Cure
			Psoriasis in a city near you...URL
	Directive advise	How To Avoid Holiday Autoimmune Flares URL
	Directive warn	Why you shouldn't be going from competition to competi-
			tion URL #thyroid #metabolism #autoimmune

Table 2 .

 2 Fleiss' Kappa reported as result, z-score for intentions and classes.

	Assertive: 0.8,27.2	Directive: 0.8,27.1		Other:0.41,13.9
	assert hypothesize propose advise	direct	warn	other
	0.77, 26.4 0.78, 26.7 0.70, 24.1 0.49, 16.7 0.68, 23.3 0.76, 25.9	0.35, 12.1

Table 3 .

 3 Results of the classification experiment using various feature sets.

			LogisticRegression RandomForest	LinearSVM
	Intention	Metric DiscF ContF AllF DiscF ContF AllF DiscF ContF AllF
	assert sup.=416	precision recall f-score	0.75 0.83 0.79	0.67 0.71 0.69	0.77 0.84 0.80	0.70 0.79 0.74	0.57 0.64 0.60	0.66 0.86 0.74	0.77 0.82 0.80	0.69 0.66 0.68	0.79 0.83 0.81
	hypothesize sup.=49	precision recall f-score	0.62 0.41 0.49	0.62 0.10 0.18	0.77 0.47 0.58	0.65 0.49 0.56	0.50 0.06 0.11	0.60 0.12 0.20	0.71 0.76 0.73	0.55 0.33 0.41	0.75 0.55 0.64
	direct sup.=119	precision recall f-score	0.71 0.79 0.75	0.66 0.18 0.28	0.78 0.75 0.76	0.70 0.70 0.70	0.59 0.11 0.18	0.67 0.35 0.46	0.75 0.82 0.78	0.50 0.27 0.35	0.77 0.79 0.78
	propose sup.=391	precision recall f-score	0.80 0.72 0.76	0.63 0.79 0.70	0.79 0.75 0.77	0.74 0.66 0.70	0.57 0.71 0.64	0.75 0.70 0.72	0.80 0.72 0.76	0.62 0.76 0.68	0.78 0.76 0.77

http://tinyurl.com/hk9t83y

http://scikit-learn.org/stable/supervised learning.html


Cristian Dumitrescu
email: cristiand43@gmail.com

An extension of Schoning's algorithm

Keywords:

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction

It is well known that 3SAT is NP-complete.

Proposition 1. (see [Papadimitriou,94] and [START_REF] Hopcroft | [END_REF]). 3SAT is NPcomplete.

Proof. For the proof, see (see [Papadimitriou,94] and [START_REF] Hopcroft | [END_REF]).

The presentation of the original algorithm

We will first present a well known randomized algorithm for 3SAT. This is Schoning's algorithm from 1991 (see [Schoning, 1991]). We also note that Papadimitriou also discussed a similar algorithm for 2SAT in 1991 (see [Papadimitriou, 1991]).

It is known that Papadimitriou's algorithm finds a solution in quadratic time with high probability for 2SAT. Only exponential bounds are known for Schoning's algorithm for 3SAT.

Schoning's algorithm for 3SAT

Input: a 3SAT expression in 𝑛 variables.

Guess an initial truth assignment, uniformly at random.

Repeat 3 • 𝑛 times:

If the expression is satisfied by the actual assignment, stop and accept.

Let C be some clause not being satisfied by the actual assignment. Pick one of the three literals in the clause at random, and flip its truth value.

Update.

Stop and reject, the expression is not satisfiable.

The extension of Schoning's algorithm

We assume that the reader is familiar with the random walk model (based on the Hamming distance to a solution) associated with the algorithm. This is discussed in detail in [Schoning, 1991], and [Papadimitriou, 1991]. Definition 1. A truth valuation v(x) of a variable x is a real number in the interval [0,1]. We note the difference between a truth valuation and a truth assignment, where the truth assignment for a variable can be only 0 or 1. Definition 2. Given two truth valuations for n variables (𝑣 1 (x 1 ), 𝑣 1 (x 2 ), 𝑣 1 (x 3 ), … … 𝑣 1 (x 𝑛 ) ) , and (𝑣 2 (x 1 ), 𝑣 2 (x 2 ), 𝑣 2 (x 3 ), … … 𝑣 𝑛 (x 𝑛 ) ) , the Hamming distance between these truth valuations is by definition 𝑑(𝑣 1 , 𝑣 2 ) = |𝑣 1 (x 1 ) -𝑣 2 (x 1 )| + |𝑣 1 (x 2 ) -𝑣 2 (x 2 )| + ⋯ … . . + |𝑣 1 (x 𝑛 ) -𝑣 2 (𝑥 𝑛 )|. Note that this definition can be also applied for a 3SAT clause, but involving only the variables that appear in the clause. Thus, if we consider a clause (x, y, z) , with the valuation (v(x), v(y), v(z)), then the distance between this clause and (0, 0, 0) is simply d = v(x) + v(y) + v(z).

Definition 3. The truth valuation of 𝑥 ˅ 𝑦 is v(x ˅ y) = v(x) + v(y) -v(x) • v(y).
The valuation of the negation of a variable ¬x is v(¬x) = 1 -v(x). It is clear that if we are given a truth valuation for the n variables that appear in a 3SAT expression, then for any 3SAT clause we can calculate the truth valuation of that clause

v(x ˅ y ˅ z) = v(x) + v(y) + v(z) -v(x) • v(y) -v(x) • v(z) -v(y) • v(z) + v(x) • v(y) • v(z)
. The truth valuation of the whole 3SAT expression is the product of the truth valuations of all the clauses. Definition 4. We will call a variable x locked, if its truth valuation at a given moment is 0 or 1.

We are ready to present the extension of Schoning's algorithm, the preliminary version.

Extension of Schoning's algorithm for 3SAT (preliminary version)

Input: a 3SAT expression in 𝑛 variables. Let C be some clause that has a minimal truth valuation. If there are more than one, then pick one at random. . Choose one of the literals in the clause at random (only choose between literals that are connected to variables that are not locked), and with equal probability Stop and reject, the expression is not satisfiable.

Initialize all variables with a truth valuation such that each variable has a truth valuation of

Proposition 2. We consider the case of one dimensional symmetric random walks (like the coin tossing game). For fixed t, the probability that the first passage through r occurs before epoch t

• r 2 tends to √ 2 π • ∫ e -1 2 •s 2 ds ∞ 1 √t = 2 (1 -R( 1 √t
)) , as r → ∞ , where R is the normal distribution.

Proof. For the proof, see [Feller, 1968], chapter 3. This means that the waiting time for the first passage through r increases with the square of r. The expected traveled distance in r 2 steps is r.

We note that in terms of the random walk model ( [Schoning, 1991], and [Papadimitriou, 1991]), we have here a one dimensional symmetric random walk. At any moment, the Hamming distance from the current truth valuation (for all the n variables) to the truth assignment solution (if it exists) can increase or decrease by . The expected traveled distance in 2 • n 4 steps is √2 • n 2 , and that is more than sufficient, because we have n variables, and each variable must perform n steps towards 0 or 1 from the initial truth valuation of 1 2 (for a total of n 2 steps towards a solution). We also distinguish between this random walk in terms of the Hamming distance towards a solution, and the random walks that are performed by each variable , starting at

1 2 .
Observation 1. The problem is that, because we are dealing with perfectly symmetric random walks for every variable, it is equally likely that a variable will be locked in the wrong truth assignment, as it is to be locked in the correct truth assignment. The locking mechanism has to be avoided.

We focus instead in the direction of travel in the multiple random walks associated to each variable. Proposition 3. If 0 < x < 1 , then in N steps performed by a symmetric random walk (as described above, for each variable), the probability that less (less or equal) than x • N time units are spent on the right side of Proof. For the proof, see [Feller, 1968], chapter 3.

That means that a reasonable amount of time units , each variable has the correct direction of travel, in terms of the current truth valuation. If the variables with the wrong direction of travel can be detected and their direction of travel corrected, then with high probability there is a moment when all the variables are on the correct side of , then give this variable the truth assignment 0 or 1 with equal probability 1 2 . This last case will not happen very often.

The idea is to temporarily convert a truth valuation to a truth assignment , but only for the purpose of testing the truth assignment at each step of the algorithm. The algorithm will still work only with truth valuations.

In the following version of the algorithm, the locking mechanism will not come into play. The important thing is the direction of travel , in terms of the random walk associated to each variable.

Extension of Schoning's algorithm for 3SAT

Input: a 3SAT expression in 𝑛 variables.

Initialize all variables with a truth valuation such that each variable has a truth valuation of

1 2 . Repeat 2 • 𝑛 2 times:
Temporarily convert the current truth valuation to a truth assignment, and check whether this truth assignment is a solution for the given 3SAT expression. If it is a solution, stop and return the solution.

Let C be some clause that has a minimal truth valuation. If there are more than one, then pick one at random. . Choose one of the literals in the clause at random, and with equal probability Stop and reject, the expression is not satisfiable.

Observation 2. The purpose of the algorithm is to make the truth valuations for each clause equal to 1. When it finds a clause with a truth valuation with a minimal value, it knows that some of the variables involved in the clause do not have the correct direction of travel (in terms of the corresponding random walk). As a consequence, it puts more pressure on those variables to get to the right direction of travel (or to get on the correct side of ). We know that in a random walk associated to a variable, the changes in the direction of travel (or visits through 1 2 ) in N trials increases only as √N . With high probability, at some point in time, all the variables will be on the correct side of 1 2 , in terms of the corresponding random walks.

Discussion and conclusions

For general implications, related to efficiently solving NPcomplete problems, see [Fortnow, 2013]. An interesting application is related to the problem of automated theorem proving using an efficient algorithm for NPcomplete problems (see [A1]). The impact of this type of algorithm in mathematics, cryptography, science in general is hard to estimate.

Aknowledgements.

I emphasize that Professor Fortnow's book ( [Fortnow, 2013]) was a great source of inspiration and motivation that led me to seriously consider this problem. Also, Professor Uwe Schoning , Professor Lance Fortnow, and Professor C. Papadimitriou corrected some errors that I had in many previous versions of this paper, and for that I am very grateful. I must emphasize though, that the final version of my paper did not receive feedback from these experts in the field, so I do not claim that I have their endorsement. If there are still flaws in my work, that is all my fault.

Appendices

A1. Godel's letter to John von Neumann. In his letter, Godel writes: "One can obviously easily construct a Turing machine, which for every formula F in first order predicate logic and every natural number n, allows one to decide if there is a proof of F of length n (length = number of symbols). Let 𝜓(𝐹, 𝑛) be the number of steps the machine requires for this and let 𝜑(𝑛) = 𝑚𝑎𝑥 𝐹 𝜓(𝐹, 𝑛). The question is how fast 𝜑(𝑛) grows for any optimal machine" (see [Godel, 1956]. Now we consider this. In [START_REF] Hopcroft | [END_REF], we have theorem 13.1, at page 325, where it is proved that for each Turing machine (deterministic or nondeterministic) M that is time bounded by a polynomial 𝑝(𝑛), a log-space algorithm exists, that takes as input a string x and produces a Boolean expression 𝐸 𝑥 that is satisfiable if and only if M accepts x.

This means that the process of seeking a proof (of reasonable length) of a mathematical statement can be completely automatized. With the algorithm presented in this paper, Godel's vision can be made reality.

  𝑛 4 times: If all variables are locked, then return the corresponding truth assignment.

  more of equal) than (1 -x) • N time units are spent on the left side of as N → ∞ .

2 ,

 2 A conversion from a truth valuation to a truth assignment is done as follows. If the variable x has the truth valuation v(x) > 1 then give this variable the truth assignment 1. If the variable x has the truth valuation v(x) < 1 2 , then give this variable the truth assignment 0. If the variable x has the truth valuation v(x) = 1 2