Songming Chen
email: songming.chen@ec-nantes.fr

Haixin Sun
email: haixin.sun@ec-nantes.fr

Vincent Frémont
email: vincent.fremont@ec-nantes.fr

A Semantic-Guided LiDAR-Vision Fusion Approach for Moving Objects Segmentation and State Estimation

Moving Objects Segmentation (MOS) is critical and indispensable for secure intelligent vehicle operation in the dynamic environment. For the state estimation task which is based on the assumption of static surroundings, to identify and filter out the moving objects plays an important role in robust ego-motion estimation. In this paper, a LiDAR-Vision fusion approach is developed to segment moving objects in the scene, which utilizes the LiDAR-based semantic segmentation as a prior and vision-based geometric information for validation. The effectiveness of our approach to segment moving objects is highlighted by the comparison with the traditional robust kernel-based outlier rejection methods. Our approach is benchmarked with three city category sequences in the KITTI dataset, which outperforms the kernel-based methods and achieves the leading results of 77.9% average fitness and 7.65 cm RMSE respectively.

I. INTRODUCTION

Exteroceptive sensors are crucial for the intelligent transportation system to perceive the surroundings and realize self-state estimation in the dynamic and unknown environments. Among them, the Light Detection and Ranging (LiDAR) and the camera sensors are commonly employed to measure the changes in the environment, on which basis, the high-level tasks such as object detection, state estimation and obstacle avoidance could be performed. On the one hand, the visual sensor captures the rich representation of the scene, which includes the color, texture and semantic information. However, the frame-based cameras are very sensitive to the illumination changes and do not work well in the aggressive motion situation. Besides, the scale ambiguity remains another challenge for the vision-based perception and state estimation. On the other hand, the LiDAR sensors are illumination-invariant and provide all-round Field Of View (FOV) perception. They could also accurately acquire the depth information for scale-aware estimation. Nevertheless, the the performance of LiDAR sensors degrades a lot in the extreme weather conditions, such as undergoing dense fog and heavy rain. Another drawback of LiDAR-based perception is the sparsity of 3D point clouds, which brings the difficulty for feature extraction and data association. The complementary features of the visual and range sensors encourage us to adaptively combine them for robust perception and state estimation, which efficiently compensates the individual sensory modality weakness.

With the advent of deep learning, object detection neural networks could be applied to predict the object position and class on the image plane [START_REF] Redmon | You only look once: Unified, real-time object detection[END_REF] and 3D point clouds [START_REF] Simon | Complexer-yolo: Real-time 3d object detection and tracking on semantic point clouds[END_REF] [START_REF] Yin | Center-based 3d object detection and tracking[END_REF] in an end-to-end manner. These neural inference frameworks are mature and can achieve the real-time performance for object detection, which facilitates the on-board integration. Nonetheless, for the objects with the same class, their states of motion (static or dynamic) are not distinguished during the neural inference. Moving objects are considered as the most unstable traffic participants, which will corrupt the state estimation and mapping process. Thus, more attention should be given to them when we design an intelligent transportation system. In this paper, we focus on the problem of moving objects segmentation and investigate their impact on the state estimation. A LiDAR-Vision fusion approach is proposed to combine the LiDAR-based semantic cues and vision-based geometric clues to identify the objects position and state of motion jointly. These non-permanent moving objects are then filtered out beforehand for the efficient state estimation and scene reconstruction. The contributions of this paper are listed as:

1) An efficient moving objects segmentation approach with the complementary LiDAR and visual sensors is proposed, which adaptively fuses the semantic and geometric information.

2) The extensive evaluation (qualitative and quantitative) of our approach has been made, which is shown to outperform the conventional robust kernel-based methods for outliers rejection.

3) The robust semantic-guided state estimation and scene reconstruction has been achieved in the highly dynamic scenarios. The rest of this paper has the outline as follows: In Section II, the related work and recent hybrid methods for moving objects segmentation will be covered. Then, the proposed methodology will be presented in Section III. After that, the experimental results and the corresponding analysis will be shown in Section IV. Finally, a brief conclusion and future perspectives will be given in Section V.

II. RELATED WORK

A. Vision-based method

The visual sensors provide dense texture and color information of the scene, which facilitates the geometric correspondence establishment and contextual understanding. In [START_REF] Frémont | Mono-vision based moving object detection in complex traffic scenes[END_REF], a purely geometric mono-vision based approach is proposed for moving objects segmentation in challenging urban areas. The epipolar, trifocal tensor, and structure consistency constraints are flexibly combined to classify the pixel-wise non-static points. The dynamic pixels are then clustered by the connected components labeler for instance-level moving objects segmentation. The optical flow consistency analysis also helps to segment the moving objects from the static background. In [START_REF] Wang | Towards dense moving object segmentation based robust dense rgb-d slam in dynamic scenarios[END_REF], the dynamic objects are identified with optical flow-based point trajectories clustering and these moving objects are then excluded from dense SLAM estimation in dynamic environments. In [START_REF] Namdev | Motion segmentation of multiple objects from a freely moving monocular camera[END_REF], the Flow Vector Bound (FVB) constraint is combined with graph-based clustering for incremental motion segmentation. Nonetheless, the aforementioned methods only leverage geometric information for the object clustering, which often fails in complex scenes. A novel Semantic-Guided RANSAC approach is thus presented in [START_REF] Chen | Mono-vision based moving object detection using semantic-guided ransac[END_REF] for moving objects segmentation in heavy traffic scenarios. The semantic constraint provides potential moving objects prior and the geometric epipolar residuals are used for the final moving objects verification, which exhibits promising results. Despite of the efficient moving objects segmentation on the visual image plane, the scale metric remains ambiguous, which can be solved by the integration of stereo vision system [START_REF] Wang | Multiple obstacle detection and tracking using stereo vision: Application and analysis[END_REF] or range-based sensors [START_REF] Rodríguez | Visual confirmation of mobile objects tracked by a multi-layer lidar[END_REF].

B. LiDAR-based method

For LiDAR-based perception and state estimation, robust kernels are commonly adopted to ease the negative impact of outliers. The identified outliers could then be clustered to construct the moving objects in the scene. It is shown in [START_REF] Babin | Analysis of robust functions for registration algorithms[END_REF] that, the outlier filters such as Tukey, Huber and Cauchy kernels could greatly mitigate the outliers effect for point clouds registration. Besides, the data-driven ResNet50based method is proposed in [START_REF] Ruchti | Mapping with dynamic-object probabilities calculated from single 3d range scans[END_REF] to infer the point-wise probability of being dynamic with only a single frame. On this basis, the scene reconstruction module takes the network output of dynamic objects probability for static components mapping. Then, the SpSequenceNet is designed in [START_REF] Shi | Spsequencenet: Semantic segmentation network on 4d point clouds[END_REF] to operate directly on 4D point clouds (consecutive 3D point clouds) for moving objects segmentation. Both the spatial and temporal information of LiDAR point clouds are exploited to extract the motion status. However, the SpSequenceNet training and prediction are computationally intensive due to the massive point clouds size. Recently, an innovative range image-based algorithm named Removert is presented in [START_REF] Kim | Remove, then revert: Static point cloud map construction using multiresolution range images[END_REF]. In the Removert framework, the dynamic objects are pruned from the query LiDAR scans via scanto-map consistency check. Meanwhile, the pre-built map is corrected with the multi-scale false prediction reverting. As the prior map is not trivially accessible, the map-free method in [START_REF] Chen | Moving object segmentation in 3d lidar data: A learning-based approach exploiting sequential data[END_REF] inputs the inter-frame range-image residuals to the semantic segmentation networks for the real-time class-agnostic moving objects segmentation. Nonetheless, the end-to-end network needs the ground truth binary masks for training that are quite time-consuming to prepare and refine.

C. Hybrid Methods

In order to overcome the individual sensor limitations, the hybrid methods which take advantage of the LiDAR and visual sensors are proposed in [START_REF] Rodríguez | Visual confirmation of mobile objects tracked by a multi-layer lidar[END_REF] [15] [16] [17]. The stereo vision systems are adopted in [START_REF] Rodríguez | Visual confirmation of mobile objects tracked by a multi-layer lidar[END_REF] to improve the object detection and tracking results of the LiDAR-based perception. Specifically, the vision-based system confirms the surrounding objects existence and their dynamic behavior are better modeled due to the dense visual measurements. In [START_REF] Fu | Camera-based semantic enhanced vehicle segmentation for planar lidar[END_REF], the vision-based segmentation result is fused with the planar LiDAR-based prediction, which achieves an improving 2D Intersection-Over-Union (IOU) rate on the Bird-Eye-View (BEV) plane. Besides, the RGB images are converted to a polar-grid representation in [START_REF] Madawi | Rgb and lidar fusion based 3d semantic segmentation for autonomous driving[END_REF], which augments the LiDAR point clouds with the color information for the efficient semantic segmentation. A novel architecture to fuse the precise LiDAR depth information and ERFNet-based visual semantics is presented in [START_REF] Barea | Vehicle detection and localization using 3d lidar point cloud and image semantic segmentation[END_REF], which is shown to obtain satisfying objects segmentation results both on the image and BEV plane.

III. PRESENTATION OF THE METHOD

In this section, the proposed LiDAR-Vision fusion approach for real-time moving objects segmentation is detailed. And its overall pipeline is shown in Fig. 1. To start with, the LiDAR measurements are used to extract the 3D regions of interest (ROI) for movable objects prediction (see Section III-A). Then, with the given calibration parameters, 2D ROI on the image plane can be generated via the 3D-2D perspective projection. In order to determine the state of motion for the potentially moving objects, the temporal consistency check is conducted via the optical flow tracking and epipolar geometry (see Section III-B). Subsequently, the instancelevel moving objects are back-projected and removed in the LiDAR point clouds for efficient state estimation and static scene mapping (see Section III-C). A resnet-based backbone is used to extract features on the flattened BEV images, which is followed by the center heatmap head and property regression heads. Specifically, the center heatmap head helps to locate the object centers and infer their semantic classes. And the attributes of objects' 3D size and yaw orientation can be obtained from the up-scaled feature maps with the property regression heads.

The outputs of the CenterPoint network are expressed as

{(C i x ,C i y ,C i z ), (L i ,W i , H i ), θ i , S i } i=1...n
, which represent center coordinates, dimensions, heading angles and semantic classes (vehicles, cyclists or pedestrians) of n detected objects respectively. The center-based 3D object detection gives absolute range and captures real-scale shapes of the objects, which is perspective distortion-free and facilitates the interactive perception and state estimation. Compared with anchorbased 3D object detection methods, the center-based method is more robust to predict the heading orientation through the rotation-invariant points fitting, especially during the egoturning phases1 (see Fig. 2). 2) 3D-2D Projection: In order to develop the LiDAR-Vision fusion approach, it is essential to transform the LiDAR-based detection results from the LiDAR frame F L to the image frame F I (see Fig. 3). We assume that the sensors are well synchronized and pre-calibrated with known extrinsic and intrinsic parameters. The perspective projection first takes eight corners F L {x i } i=1...8 of the 3D bounding box expressed in F L , and left-multiplies them with the LiDAR-Camera rigid transformation matrix C T L and image projection matrix I P C sequentially to get the corner coordinates in F I .

F I x i = I P C * C T L * F L x i (1)
Then the 2D bounding box boundaries can be extracted trivially from the span of the corner coordinates

F I {x i } i=1...8 .
It is notable that the perspective projection constructs the one-to-one mapping correspondences for the 3D bounding box in F L and 2D bounding box in F I , which provides the possibility for the bounding box back-projection. And during the 3D-2D perspective projection, the semantic labels of detected objects remain unchanged. 3) are not semantically consistent across two frames, they will be directly identified as dynamic points. After that, the matched features which belong to the background (rendered in blue, see Fig. 4), are used to estimate the fundamental matrix F within the RANSAC framework. Since the movable objects points (rendered in green, see Fig. 4) are excluded from the estimation, the RANSAC process will converge quickly and provide a reliable fundamental matrix estimation. With the paired background points (x i , x ′ i ) i=1...n and the estimated fundamental matrix F, the corresponding epipolar line l ′ i ∼ F x i with reduced coefficients [a i , b i , c i ] T can be obtained. And the Signed Epipolar Distance (SED)

d SED i from the point x ′ i = (u ′ i , v ′ i ) to line l ′ i is calculated as: d SED i = a i u ′ i + b i v ′ i + c i a 2 i + b 2 i (2)
Assuming that the measurement noise is normally distributed, then the calculated signed epipolar distance {d SED i } i=1...n will follow the Gaussian distribution as shown in Fig. 5, which lays the basis for outlier rejection. As the fundamental matrix transformation compensates the interframe ego-motion on the image plane, the static points will have close to zero (noise corruption) SEDs. On the contrary, the points on moving objects tend to get the SEDs exceeding the 3-sigma bounds, which will be classified as outliers and segmented from the static background. Nonetheless, it also needs to be mentioned that for objects following the degenerate motions within the epipolar plane, the epipolar constraint alone is not sufficient. This kind of degenerate motion usually happens when the ego-vehicle is following the moving object forward and constantly maintains the straight-line motion. In this case, the Flow Vector Bound (FVB) constraint [START_REF] Kundu | Moving object detection by multi-view geometric techniques from a single camera mounted robot[END_REF] can be leveraged to detect such moving points with low SEDs. Given the sequential images, the pixels parallax d FV B i of paired points (x i , x ′ i ) between two consecutive frames can be computed as:

x ′ i -KRK -1 x i = 1 z Kt d FV B i = x ′ i -KRK -1 x i ( 3
)
where the scalar z represents depth value and the matrices K, R and t stand for the camera intrinsics, interframe rotation and translation respectively. With a set of matched background points {(x i , x ′ i ) i=1...n }, their parallax bound [d FV B min , d FV B max ] can be easily found by Eq. 3. For the points with degenerate motions, if their parallax value is not within the interval of [d FV B min , d FV B max ], they will also be labeled as dynamic outliers.

2) 2D-3D Instance-Level MOS: The vision-based MOS validation further exploits the underlying geometric and semantic cues, to identify the truly dynamic points lying on the movable objects. The combination of semantic, epipolar and FVB constraints allows for better MOS recognition even in degenerated cases. From the statistical point of view, the likelihood of an object being dynamic depends on proportion of outliers lying inside, on which basis, we can obtain the instance-level MOS probability. In our case, the threshold of 50% is set for the instance-level MOS decision making. It means that for each movable object, if there are more than 50% of the points inside are classified as mobile, the object itself will be considered as a dynamic object. Then, the object bounding box 2D-3D back-projection as depicted in Fig. 7, is implemented to get the depth information. And all the points inside the truly moving objects (rendered in red, shown in Fig. 6) will be cleared for the following robust state estimation and consistent scene mapping. In brief, 2D-3D instance-level MOS algorithm can be summarized as: object {S i } 2D if the proportion of outliers in {R i } 2D exceeds the threshold 50%. 6: Implement the {S i } 2D back-projection to obtain {S i } 3D . 7: Exclude the points inside {S i } 3D for the following robust state estimation and consistent scene mapping.

Fig. 6. The 2D instance-level moving objects segmentation (rendered in red), along with their probability of being dynamic Fig. 7. The 3D instance-level moving objects segmentation via backprojection, and all the points inside will be classified as outliers

C. Robust State Estimation and Mapping

The robust state estimation is driven by the reliable correspondence matches across frames, where the estimated transformation j T i tends to minimize the overall distance between the paired correspondences {(p i , p j ) ∈ M}. In our pipeline, the 3D LiDAR scans are iteratively matched with the point-to-plane metric to deduce the vehicle ego-motion, which reaches centimeter-level precision. However, the existence of dynamic objects in the scene tends to cause the scan misalignment, thus degrading the registration accuracy of sequential LiDAR scans. In order to mitigate the impact of outliers in the objective function F( j T i ) minimization, the robust kernel functions ρ(r i j ) adaptively adjust the weights of the matches with large residuals.

F( j T i ) = ∑ (p i ,p j )∈M ρ((p j -j T i p i )⃗ n j ) (4)
where (p i , p j ) are the correspondences belonging to the matched points set M, and ⃗ n j is the normal vector around p j for calculating the point-to-plane distance. Nevertheless, the kernel-based Iterative Closest Point (ICP) method is not sufficient to handle the constant dynamic objects corruption. To solve this problem, our approach distinguishes the instancelevel moving objects with the semantic and geometric information fusion. With the segmented moving objects backprojected to the 3D LiDAR scans, the weighting coefficients ρ(r i j ) for the paired points lying inside the dynamic objects are uniformly assigned as zero, which further reduces the influence of dynamic objects in challenging scenarios. In order to align the LiDAR scans in the global frame, the poses from the state estimation thread will then be leveraged for static point clouds registration.

IV. EXPERIMENTAL RESULTS

In this section, the effectiveness of the proposed sensor fusion-based MOS and state estimation system is validated. The experimental evaluations are conducted with the challenging city category sequences 2 in the KITTI dataset [START_REF] Geiger | Vision meets robotics: The kitti dataset[END_REF], which were recorded in heavy traffic hours. The LiDAR-Camera sensor setup is adopted with the known calibration parameters, where the 64-layer Velodyne HDL-64E LiDAR gives accurate range information and the RGB-camera provides more contextual knowledge of the scene. In the KITTI dataset, only the front-view images are provided. So we focus only on the moving objects segmentation and static scene mapping within the visual sensor field of view. Extensive qualitative and quantitative results demonstrate that, the proposed semantic-guided MOS helps to robustify the pose estimation process in challenging heavy traffic scenarios. Moreover, the ghosting effect in scene reconstruction process is remarkably eliminated due to the moving objects removal.

A. Evaluation Metrics

The semantic-guided MOS efficiently reduces the outliers effect in the 3D LiDAR scan matching. In order to quantify the performance of LiDAR scan matching, the evaluation metrics of Relative Fitness (RF) and Relative Root Mean Square Error (RMSE) of the inlier correspondences {I} are used. They are defined as follow:

RF = |I| |M| , RMSE = 1 |I| ∑ (p i ,p j )∈I ∥p i -p j ∥ 2 (5)
where |•| is taking the cardinal number of a set. On the one hand, Relative Fitness (RF) measures the proportion of associated inliers {I} among all the matched point pairs {M}, and higher relative fitness represents better scan matching results. On the other hand, RMSE measures the root mean 2 http://www.cvlibs.net/datasets/kitti/raw data.php?type=city square errors of all inlier correspondences {(p i , p j ) ∈ I}, and lower RMSE stands for greater scan alignment.

B. Results Analysis

1) Qualitative results: The ability to segment dynamic components in surrounding environments is essential for the intelligent transportation system. In our approach, the movable objects ROI are predicted with the CenterPoint neural network. Then, the visual multi-view geometry constraints provide a sanity check for instance-level MOS validation. Such a combination allows for better recognition, which is capable of detecting tiny objects (see Fig. 8) and even partially occluded objects (see Fig. 6). The right-side vehicle in Fig. 6 is occluded on the image plane, which is quite difficult to detect with only visual hints. Nonetheless, the high-resolution LiDAR sensor receives the reflection from part of occluded vehicle and manages to predict its existence, as depicted in Fig. 7. Moreover, it is demonstrated in Fig. 8 that, the epipolar constraint compensates the vehicle egomotion which accurately classifies the parked car as static. And the flow vector bound constraint efficiently helps to identify the dynamic vehicle performing degenerate motions on the lane, which facilitates better contextual understanding of the driving area 3 . Since the moving objects are not temporally consistent, they do not belong to the permanent components of the scene. Therefore, moving objects should be eliminated from the mapping process in order to build a consistent representation of the scene, as shown in Fig. 10. The reconstructed static map will promote high-level tasks such as map-based localization and path planning.

2) Quantitative results: It is shown in Tab I and Tab II that, our semantic-guided MOS approach achieves the leading results of 77.9% average fitness and 7.65 cm RMSE respectively. Since the optimization-based state estimation is usually built upon the static environment assumption. The Fig. 10. The ghosting effect of a moving car is greatly reduced due to the semantic-guided moving objects segmentation and removal presence of dynamic objects in the scene may degrade the ego-motion estimation and complicate the map maintenance task. A two-stage prediction-then-validation pipeline is thus designed to segment instance-level objects in the scene. It is more efficient than the traditional kernel-based methods, since we concentrate on the ROIs instead of the whole points clouds. Compared to the end-to-end DL-methods, our approach relieves from motion segmentation ground truth annotation and training. The multiple constraints combination also ensures the robustness of dynamic outliers rejection in complex situations, such as handling objects with degenerated motions. V. CONCLUSION AND FUTURE WORK In this paper, we propose a novel pipeline to perform the efficient MOS that robustifies state estimation and facilitates consistent scene mapping in dynamic environments. The complementary range and visual sensors are combined to efficiently detect the truly moving objects, even in degenerated cases. The qualitative and quantitative experimental results demonstrate that, the proposed approach can outperform the traditional kernel-based methods in the complex traffic scenes. The future work plan will be devoted to onboard multi-camera and LiDAR fusion, where the front, side and rear camera images will be stitched for panoramic perception. The ablation study of different 3D object detection neural networks will also be conducted, which ensures the MOS robustness in various scenarios such as high-speed motion and mutual occlusion.

Fig. 1 .

 1 Fig. 1.Overview of the proposed LiDAR-Vision fusion approach for moving objects segmentation and state estimation

Fig. 2 .

 2 Fig. 2. The LiDAR-based 3D object detection results (rendered in green) with the CenterPoint network at the road intersection

Fig. 3 .

 3 Fig. 3. The LiDAR-based 3D object detection results mapped on the image plane through the perspective projection

Fig. 4 .

 4 Fig. 4. The background corner points (rendered in blue) are tracked with sparse optical flow and are used for robust fundamental matrix estimation

Fig. 5 .

 5 Fig. 5. The Signed Epipolar Distance distribution of background points (rendered in blue)

Algorithm 1

 1 2D-3D Instance-Level MOS Algorithm Input: Predicted Movable Objects ROI {R i } 2D i=1...r Output: Validated MOS {S i } 2D, 3D i=1...s 1: Detect the Shi-Tomasi corners and track them with LKoptical flow between two consecutive image frames. 2: Estimate the fundamental matrix F with the feature matches belonging to the background. 3: Compute the SED residual distribution (µ SED , σ SED ) using Eq. 2 and the flow vector bound [d FV B min , d FV B max ] using Eq. 3 for the background points. 4: Check the motion status of points inside {R i } 2D i=1...r based on the semantic, epipolar and FVB constraints. 5: Classify the movable object {R i } 2D as validated dynamic

Fig. 8 .

 8 Fig. 8. The tiny moving object with degenerate motions (move along the epipolar plane) is successfully segmented with the FVB constraint

ROI LiDAR Scans Optical Flow Tracking + Epipolar Residuals Computation CenterPoint Net Prediction State Estimation Consistent Mapping Robust

		3D		3D MOS
		3D-2D		2D-3D
		Projection	Back-projection
	Visual Images	2D ROI	Consistency Check	2D MOS

TABLE I REGISTRATION

 I RESULTS BENCHMARKING WITH RF(%)

	Dataset	Methods Tukey	Huber	Cauchy	Ours
	2011 09 26 13	57.2%	55.6%	55.6%	57.7%
	2011 09 26 17	94.7%	94.7%	94.7%	95.7%
	2011 09 26 18	78.9%	79.5%	79.1%	80.2%
	Average	76.9%	76.6%	76.5%	77.9%

The LiDAR scan and RGB-image are extracted from the KITTI

09 26 drive 0014 sync sequence

The LiDAR scan and RGB-image are extracted from the KITTI 2011 09 26 drive 0013 sync sequence

* This work was carried out in the framework of the NExT Senior Talent Chair DeepCoSLAM, which was funded by the French Government (ANR-16-IDEX-0007). The first-author was also funded by China Scholarship Council.


Algorithms

1. A data is the numerical representation of an object, or the product of computation on numerical variables.

2. An algorithm describes a set of operations to be executed, to solve a given problem.

3. An algorithm takes data (its inputs), and performs operations on them, to produce other data (its outputs).

4. An algorithm is implemented (i.e., put into operation) via a description by a high level language, called source code, intelligible (i.e., compilable, then executable by a machine). 5. The same algorithm can be implemented in several different but equivalent ways (i.e., these variants produce the same outputs). 6. The disclosure of the source code implementing an algorithm amounts to exposing the entirety of the operations performed by it. 7. Algorithms can make use of variables. These variables are set at the beginning of its execution, or during its execution. 8. Algorithms can use randomness; they are then said to be nondeterministic or randomized. They are deterministic in the opposite case.

(a) A deterministic algorithm produces the same outputs for the same inputs, all variables being equal.

9.

The so-called non-explicit algorithms perform complex operations on data, that are not describable by a high-level language.

10. An algorithm or an implementation is said to be biased if it produces an output which diverges from the expectation. It is said to be buggy if this bias is unintentional. 11. The interaction between algorithms via their inputs/outputs composes a complex system.

(a) The dynamics of this interaction and its output are said to be emergent.

Algorithmic decisions

12. The input (resp. output) space is the set of combinations of values that the data can take as input (resp. output).

(a) The size of the input (resp. output) space is the number of such possible combinations.

13.

Executing a deterministic algorithm on the whole input space (with fixed variables and randomness), allows to fully characterize this algorithm (correspondence table).

(a) However, this method does not indicate in any way how to recover the source code of (i.e., retro-engineer) this algorithm.

14.

Releasing the source code of an algorithm allows to define its input and output spaces.

(a) An algorithm whose source code is open is not sufficient to describe a precise computation, in the absence of its input data, variables and sources of randomness.

15.

A so-called decision-making algorithm is like any other processing algorithm: its output takes a value among a predefined set; but this value is then called a decision and given to the user.

(a) A decision-making algorithm can then try to approach as closely as possible (i.e., to encode) a rational human judgment leading to a decision. (b) A decision-making algorithm can very well be purely random and take no input data; it is then a random generator of decisions (binary for example).

16.

A decision is said to be biased if it is produced causally by data which should not lead to it.

Explanation of algorithmic decisions

17. The possibility of freely manipulating an algorithm source code, and thus of knowing each of its operations, and of interacting via its inputs and observing its outputs, allows it to be qualified as a white box.

18. The implementation of an algorithm can only be "transparent" by making it available as a white box. Indeed, the source code alone does not explain the decisions but constrains them.

19. The explanation of a decision is a projection on the language of the high level instructions of an algorithm having led to this particular decision. 20. A decision is said to be non-explicit, if the operations leading from the input data to this decision cannot be described by a high-level language.

21. An explanation is underdetermined if it describes only part of the data and computations that led to the decision.

22.

Varying the inputs in order to vary the decisions makes it possible to quantify the relative impact of these inputs.

23.

Decisions are identical within boundaries, each of which leads to another decision.

(a) A point on a decision boundary is defined as a specific location where a minute change in the input causes the decision to flip. (b) The decision boundaries of an algorithm are made up of all the points previously defined.

Black box algorithms

24.

A black box algorithm is said to be observable if any change of its variables is reflected in its outputs.

25.

A decision-making algorithm is said to be opaque to an individual if the latter cannot access to at least one of the following components: source code, inputs or variables.

26.

The execution of an algorithm on a machine controlled by an observer is in no way a guarantee of its white box nature for this same observer (closed source code, enclaves, encryption).

(a) This is all the more obvious for an execution on a third party machine (cf "There is no cloud, just someone else's computer").

27.

A black-box algorithm is an algorithm for which a user can only propose data as input and observe the outputs that result a priori causally from these inputs.

(a) a priori, because an algorithm can quite possibly respond with a fixed or random value regardless of its inputs. (b) In other words, the veil that turns an algorithm from white box to black box is the execution by a third party, or the multiple techniques of code obfuscation. In other words, even a known algorithm (white box) when executed by a third party becomes de facto a black box.

28. An explanation by a black-box algorithm is falsifiable, because there is always an explanation validating the output, which is not the explanation of the operations actually performed on the inputs (the bouncer problem).

29.

Let us call the stability assumption the fact that a black-box algorithm and its variables remain fixed during a period of interaction. 30. Under the stability assumption, two black-box algorithms are indistinguishable if all their outputs are equal for all their respective inputs.

(a) Two black box objects, which are indistinguishable, can be the same algorithm (their source code may indeed diverge), or two different algorithms (e.g., a bubble sort algorithm and a fusion sort algorithm); their outputs are expected to be identical. (b) Two algorithms are distinguishable if there exist two different outputs for at least one given input. (c) The distinguishability of two algorithms may then depend only on one particular input.

31.

Just as in the quantum domain, a simple interaction with a black box algorithm in order to observe its output may well modify its variables.

For instance by the re-training of this algorithm, incorporating the input used for the interaction.

(a) Any hope of reiterating an observation is thus potentially vain. In the worst case, the observation is "one shot". (b) The more favorable case of stable black boxes because unchanged by the observation is also possible. (c) The act of voluntarily providing particular data as input, so as to modify in a certain direction the internal state (or variables) of the black-box algorithm -and consequently, its outputs-, is called data poisoning.

32.

The size of the input space is directly related to the difficulty of observing properties of a black-box algorithm. The more this size increases, the more the curse of dimensionality is prevalent, and the more complex it is to observe these properties.

33.

Learning the result of several pairs of inputs/outputs can allow an extra/interpolation in the prediction of other outputs of the black box.

34. An algorithm can very well specialize its outputs (e.g., create a bias voluntarily) by taking into account solely one fraction of the input ("sandboxing").

35.

Neural networks, the pillars of modern advances in machine learning, are black boxes because they produce non-explicit decisions.

(a) A learning process proceeds through billions of trial-and-errors, and concludes with the positioning of the algorithm's variables at the values that have minimized its final error on known cases. (b) These variables being in gigantic quantity, and in the absence of algorithmic steps, there is thus no possible direct explanation of the resulting decisions. (c) Thus is achieved a trial and error pinpoint of the numerical elements that led to a given decision, on a given input (interpretation).

The algorithm (in white box) on the third party side 36. We call third party the entity that runs an algorithm that faces users (which then appears as a black box to them).

(a) The relative novelty and generalization of the white-box/blackbox dichotomy stems from the placement in production of userfacing decision-making algorithms. The previous use of algorithms was rather to advise an institution, which in turn was the intermediary between the algorithm and the users. Disintermediation thus motivates the understanding of what is feasible or intelligible in this new type of interaction. (b) The placement of source code by a third party on a public server for inspection cannot imply any conclusion of transparency. Indeed, and trivially, nothing proves that it is indeed the algorithm that is actually running in the service in question.

Audit of algorithms

37. A class of algorithmic audits seeks to establish the validity or not in a black box algorithm of predicates defined beforehand; e.g., for this precise input, this particular output must not be returned.

38.

Under the hypothesis of stability, another class seeks to establish the trends at work in the input-output relationship (substitute model).

(a) The greater the quantity of input-output relations observed, the more it is possible to construct a precise representation (surrogate) of the algorithm (e.g., to approximate it finely). Thus, for a budget of inputs tending towards the size of the input space, the algorithm can be approximated with an arbitrarily small error.

39. Shannon's maxim (or Kerckhoffs's), which specifies that one must make the assumption that "the adversary (i.e., the observer) knows the system (i.e., the algorithm here)", seems to be little used in practice in the domain: third parties rely largely on security through obscurity.

Shortcuts

40. What is a black box algorithm for which I can predict all outputs? An algorithm for which I have a perfect surrogate, in the sense of its indistinguishability on all possible inputs (??) from this surrogate. 41. A black-box algorithm falls under the definition of proprietary software, because it does not exhibit a single of the four points defining free software.

(a) Either the impossibility to execute, to distribute, to study, or to modify this software.

Implications and societal distortions

42. An algorithm is also said to be biased if it produces decisions considered as "unfair" by a group of individuals.

(a) The notion of fairness for a decision-making algorithm would like to measure the balance of decisions for groups of individuals represented by specific inputs. (b) The very principle of some classification algorithms is to discriminate individuals from their inputs. (c) A classification algorithm will be considered fair or unfair according to the intersection of its boundaries with a set of socially constructed boundaries.

43.

The doubt that the possibility of sandboxing casts on any audit attempt is glaringly illustrated.

(a) "Diesel gate": a qualified auditor was confronted with an alternative reality (discrimination on a "auditor" flag in the input), i.e., a specialization of the outputs in view of obtaining a certification, while the rest of the users experienced a completely different reality. (b) Shadow banning practices offer the illusion to a user that he is being treated normally, while the third party has decided to lower his visibility (on a social network for example). (c) The same applies to proposals from third parties to open up interfaces (APIs) to audit their algorithms. There is no guarantee in practice that the outputs are those that a standard user may observe.

44.

A biased algorithm is not wrong as such. It has been placed in front of the users on the decision of the third party, who ordered it. Thus the fault falls transitively and naturally on the latter. 45. The practices of whistleblowers can find a societal legitimacy simply in the exhibition of an algorithm outputs judged improper (e.g., Tay bot). Even if some had voluntarily and abusively manufactured the inputs that would lead to this improper behavior.

(a) The problem here is not in the input-output correspondence, but rather in the absence of regulation/censorship on certain outputs by the algorithm (accountability, i.e., third party responsibility). (b) In other words, some outputs should never be proposed, by construction or constraint.

46.

Ranking or recommendation systems are decision-making algorithms that filter and rank objects from a large catalog for a user (personalization). 47. A filter bubble is the result of the over-personalization of a recommendation algorithm with regard to its outputs for a particular user.

(a) A corollary is the collapse of the diversity of proposals made by the algorithm to this user. (b) A particular case (rabbit-hole) is the result of the increasing interaction of a user with the personalization made to him by an algorithm, thus creating a phenomenon of amplification of the algorithmic reaction.

48.

The so-called predictive algorithms group together the techniques whose aim is to maximize a metric (such as the appreciation of the users of what is proposed to them) on the future behavior of the users in front of their proposals (i.e., outputs).

(a) An algorithm does not know what a user wants. To produce this illusion, it can exploit what other users -whom it considers similarhave chosen in the past. In other words: so-called predictive algorithms do not predict the future, they encode the past to replay it. (b) Knowing the many biases that can afflict decision-making algorithms, a common flaw is to take the algorithmic decision as a reliable prediction and to impose it on everyone by justifying it as scientifically indisputable.

49.

Proponents of privacy online suggest that it is possible to interact with black boxes via one part of a user's personal data, but that the other part will remain secret, or even non-inferrable.

(a) Due to the masses of data available for training algorithms and the accuracy of their inferences, the possibility of providing inputs that do not allow for correct inference of the rest of the "hidden" data becomes negligible.

----