# CHOSEN: Contrastive Hypothesis Selection for Multi-View Depth Refinement

Di Qiu  Yinda Zhang  Thabo Beeler  Vladimir Tankovich  Christian Häne  Sean
Fanello  Christoph Rhemann  Sergio Orts Escolano

###### Abstract

We propose CHOSEN, a simple yet flexible, robust and effective multi-view
depth refinement framework. It can be employed in any existing multi-view
stereo pipeline, with straightforward generalization capability for different
multi-view capture systems such as camera relative positioning and lenses.
Given an initial depth estimation, CHOSEN iteratively re-samples and selects
the best hypotheses, and automatically adapts to different metric or intrinsic
scales determined by the capture system. The key to our approach is the
application of contrastive learning in an appropriate solution space and a
carefully designed hypothesis feature, based on which positive and negative
hypotheses can be effectively distinguished. Integrated in a simple baseline
multi-view stereo pipeline, CHOSEN delivers impressive quality in terms of
depth and normal accuracy compared to many current deep learning based multi-
view stereo pipelines.

Machine Learning, ICML

##  1 Introduction

Geometry acquisition through multi-view imagery is a crucial task in 3D
computer vision. In the multi-view stereo matching (MVS) framework, image
patches or features are matched and triangulated to find 3D points (Collins,
1996; Furukawa & Ponce, 2010). The dense geometry is usually represented as a
depth map for each view. Due to view dependent appearance, occlusion and self-
similarity in the real world scenarios, the matching signal is often too noisy
to directly give accurate and complete geometry. Traditionally, this problem
have been attacked by some carefully designed optimization and filtering
scheme (Barron & Poole, 2016; Taniai et al., ), directly on the depth map or
indirectly inside a matching cost volume, where they impose certain priors on
the smoothness of the resulting geometry, making use of the confidence of
matching and appearance in a larger spatial context.

With the advancement of deep learning, many research works have combined the
ideas with traditional MVS. Early works (Yao et al., 2018, 2019) typically
involve extracting convolutional features from the images, building one cost
volume (indexed by a sequence monotone depth hypotheses $d_{i}$ for each
pixel), or several in a multi-resolution hierarchy, and transform these cost
volumes using 3D convolutions into a ”probability volume” so that depth map
can be obtained by taking the expectation

$\hat{d}=\sum_{i}p_{i}d_{i}$ (1)

More recent works have more complicated designs regarding cost computation and
aggregation (Wang et al., 2021), visibility and uncertainty estimation (Zhang
et al., 2023a; Cheng et al., 2020), loss functions (Peng et al., 2022),
feature backbones (Cao et al., 2023), feature fusion (Zhang et al., 2023b),
and consequently have yielded impressive progress on various benchmarks.
However, the evaluation has been limited to point cloud reconstruction, and
little attention was paid to, and thus the lack thereof, the raw output’s
quality in terms of depth and normal accuracy. Moreover, the fixed training
and testing benchmarks also result in limited discussion on the learning and
inference task under the variance of the multi-view acquisition setups,
including different metric scales, camera relative positioning and lenses
(focal lengths). Therefore, for a new capture setup substantially different
from the training set, one is usually left with the job of determining what
hyper-parameters to choose for cost volumes and probably retrain the model of
choice. In fact, both of the problems can be attributed to the approach of
using Eq.(1) to obtain depth estimations: depths hypotheses at different
pixels, or across different datasets, may not be well aligned. The first
results in non-smoothness, and the second results in poor generalization.

In this work, we turn our attention to the problem of learning to refine depth
with multi-view images while keeping in mind that they can be from very
different setups, and how to best sample hypotheses for depth refinement. We
will discuss in Sec.3.1 the proper solution space to perform the learning
task, and present an alternative to the approach of Eq.(1) in Sec.3.2. Much as
inspired by the PatchMatch (Barnes et al., 2009; Bleyer et al., 2011)
methodology, our framework, named CHOSEN, learns to refine the depth by
iteratively re-sampling and selecting the best hypotheses, thus eliminating
the need of a ”probability volume”.

In the following we identify and underline the core design elements that
enable CHOSEN to produce significantly improved depth and normal quality:

  * •

Transformation of the depth hypotheses into a solution space defined by the
acquisition setup.

  * •

The use of first order approximation to sample spatial hypotheses to propagate
good hypotheses to their neighborhood.

  * •

A carefully designed hypothesis feature so that it’s informative for
contrastive learning.

  * •

Each hypothesis is evaluated independently so that the refinement is robust to
arbitrary hypothesis samples.

An overview of CHOSEN is illustrated in Fig.1.

To demonstrate the effectiveness of CHOSEN, in Sec.3.3 we describe how we
embed it in a minimalist MVS pipeline where the only extra learnable part is
the feature extraction using light-weight U-Nets (Ronneberger et al., 2015).
We perform comprehensive ablation experiments to justify our design, and
compare the quality of our refined depths with various recent deep learning
based MVS pipelines. Without bells and whistles, our baseline model is easy to
train, fast to converge, and already delivers impressive depth estimation
quality.

##  2 Related work

MVS algorithms are often categorized by the representation used to reconstruct
the output scene, e.g. volume (Kutulakos & Seitz, 2000; Kar et al., 2017; Ji
et al., 2017), point cloud (Furukawa & Ponce, 2010; Lhuillier & Quan, 2005;
Lin et al., 2018; Insafutdinov & Dosovitskiy, 2018), depth map (Galliani et
al., 2016; Tola et al., 2012; Schönberger et al., 2016), etc. However, depth
map is probably the most flexible and efficient representation among existing
ones. While depth map can be considered as a particular case of point cloud
representation, (e.g., pixel-wise point), it reduces the reconstruction task
to a per-view (2D) depth map estimation. These MVS approaches can be further
grouped in hand-crafted (traditional) methods or learning based solutions.
Traditional MVS pipelines extend the two-view case (Scharstein & Szeliski,
2002) by introducing a view-selection step that aggregates the cost from
multiple images to a given reference view. The view selection can be performed
per-camera (Galliani et al., 2015) or per-pixel (Schönberger et al., 2016).
These approaches (Galliani et al., 2015, 2016; Tola et al., 2012; Schönberger
et al., 2016) then rely on well engineered photometric cost functions (ZNCC,
SSD, SAD, etc.) to estimate the scene 3D geometry, by selecting the best depth
hypothesis that leads to the lowest aggregated cost. However these cost
functions usually perform poorly on texture-less or occluded areas, and under
complex lighting environments where photometric consistency is unreliable.
Hence further post-processing and propagation steps are used to improve the
final estimate (Schönberger et al., 2016; Galliani et al., 2015). We refer
readers to (Furukawa & Hernández, 2015) for additional details regarding
traditional multi-view stereo pipelines.

Recently, MVS algorithms have showed impressive quality of 3D reconstructions
in terms of accuracy and completeness, mostly thanks to the increase
popularity of deep learning based solutions (Yao et al., 2018, 2019; Yu & Gao,
2020; Gu et al., 2020; Wang et al., 2021; Zhang et al., 2023b; Cao et al.,
2023). These methods often make use of multi-scale feature extractors (Cheng
et al., 2020; Tankovich et al., 2021; Chang & Chen, 2018), cost-volumes
(Kendall et al., 2017; Khamis et al., 2018; Zhang et al., 2018), and guided
refinement (Yao et al., 2018; Pang et al., 2017; Khamis et al., 2018) to
retrieve the final 3D estimate. Typically, they leverage U-Nets (Ronneberger
et al., 2015) to build a single or a hierarchy of cost volumes with
predetermined depth hypotheses. Then, these cost volumes are regularized using
3D convolutions and the final depth map is regressed from the regularized
probability volume. However, to achieve high resolution depth accuracy, it
requires sampling a large number of depth planes, which is limited by memory
consumption.

Researchers are also opening other frontiers in deep learning based MVS. UCS-
Net (Cheng et al., 2020) and Vis-MVSNet (Zhang et al., 2023a) use some
uncertainty estimate for an adaptive generation of cost volumes. PVSNet (Xu &
Tao, 2020) and PatchmatchNet (Wang et al., 2021) learn to predict visibility
for each source image. The approach of Eq.(1) is considered critically in
(Peng et al., 2022), although it was only considered from the loss function
perspective. GeoMVSNet (Zhang et al., 2023b) proposes a geometry fusion
mechanism in the MVS pipline. Most recently, transformer based methods (Ding
et al., 2022; Cao et al., 2023, 2024) exploits the attention mechanism for
more robust matching and context awareness. In particular, MVSFormer (Cao et
al., 2023) has combined this approach with the powerful pre-trained DINO
features (Oquab et al., 2023).

It is worth mentioning that existing methods usually need to hand-tune hyper-
parameters such as the depth range, hypotheses spacing, and number of
hypotheses to ensure sufficient and accurate coverage for the new application.
Some of these methods adopt 2D convolutional neural networks to obtain final
depth estimations, using RGB image to guide depth up-sampling and refinement
(Khamis et al., 2018; Hui et al., 2016; Wang et al., 2021). Consequently,
these methods often generalize poorly to new camera setups or new scenes.

##  3 Framework

There are two important aspects in our CHOSEN framework. In Sec.3.1 we discuss
how to define a suitable solution space for the depth hypotheses and how to
sample them. This has to accommodate the fact that input depths can be of
arbitrary scale, and are computed from different multi-view systems. Then in
Sec.3.2 we detail our design of a ranking module that is able to process
arbitrarily sampled hypotheses, and how it can be trained to effectively and
robustly distinguish the good hypotheses from the bad ones.

Figure 1: CHOSEN’s hypotheses sampling and ranking mechanism. Each hypothesis
of each pixel is processed independently.

###  3.1 Hypothesis representation and sampling

#### Pseudo disparity representation

We find it crucial to operate in a transformed inverse depth representation,
which we call pseudo disparity - akin to disparity for rectified stereo pairs.
Denoting the metric depth as $D$, the pseudo disparity writes

$d=\frac{f*b}{D}$ (2)

where we choose $f$ to be the focal length (unit in pixels) of the reference
camera, and $b$ the metric distance between the reference camera and the
closest source camera. The scaling factor $f*b$ converts the inverse depth
into the pixel space, and approximates the correct accuracy level of the
capture setup in use, granted that the cameras have sufficient frustum overlap
and similar focal lengths. This representation not only allows us to build
hypothesis feature insensitive to the variance in metric or intrinsic scales,
but also defines the correct granularity in the solution space where we
distinguish the positive and negative samples for contrastive learning, thus
enabling our depth refinement model to learn and infer across various
acquisition setups.

#### Initial hypotheses sampling

The initial depth hypotheses are constructed as a $H\times W\times N$ volume
where we will look for the optimal hypothesis per pixel that has the lowest
matching cost. In case there is no initial depth available, we initialize the
volume using uniformly spaced slices in the range
$[d_{\text{min}},d_{\text{max}}]$, where the number of slices can be chosen so
that the slices sit $1\text{-px}$ apart from each other, and initialize the
depth $\hat{d}$ to be the one with lowest matching cost. We refer to the
corresponding cost volume as the full cost volume. In case an previous depth
$\hat{d}$ is available, the volume will be restricted to be uniformly spaced
in $[\hat{d}-M,\hat{d}+M]$. A cost volume built using this set of hypotheses
is referred to as a local cost volume, and $\hat{d}$ will be updated to be the
one with lowest matching cost in the local volume. In addition, we apply
uniform random perturbation in $\mathcal{U}[-0.5,0.5]$ to each hypothesis at
each pixel for both volumes to robustify the training and estimation. Note
that there are no other particular restrictions on choices of $N$ or $M$ as
long as the spacing is appropriate and the coverage is sufficient, and in
particular they can be changed without re-training.

Figure 2: Overview of the baseline MVS with our CHOSEN depth refinement. The
winner hypothesis is from the initial full range cost volume, followed by
applying the hypotheses sampling and best hypothesis selection. Initial
sampling and spatial sampling are applied in an alternating fashion. Spatial
sampling is facilitated through first order propagation as defined in Eq.(3).
Key to this pipeline is the design of the hypothesis feature, defined in
Sec.4.2. The refined depth is upsampled to the higher resolution using nearest
neighbor, and the same refinement procedure will be applied.

#### Spatial hypothesis sampling

Inspired by the PatchMatch framework (Barnes et al., 2009; Bleyer et al.,
2011), we use spatial hypotheses to expand good solutions into their vicinity.
Specifically, we sample a set of hypotheses for each pixel by collecting the
propagated depths from its spatial neighbors. The propagation is facilitated
through first order approximation. Denote $\partial
d=(\partial_{x}d,\partial_{y}d)$ to be gradient of the depth $d$,
$\mathbf{p}^{\prime}=\mathbf{p}+\Delta\mathbf{p}$ be a spatial neighbor of the
pixel $\mathbf{p}$. The propagated depth from $\mathbf{p}^{\prime}$ to
$\mathbf{p}$ is defined as

$d_{\mathbf{p}^{\prime}\to\mathbf{p}}=d_{\mathbf{p}^{\prime}}-\partial
d_{\mathbf{p}^{\prime}}\cdot\Delta\mathbf{p}$ (3)

In practice we use a fixed set of $\Delta\mathbf{p}$’s for each pixel, though
it is more of a convenience than requirement. We conduct sampling and best
hypothesis selection in multiple iterations and resolutions.

###  3.2 Contrastive learning for hypothesis ranking

It is crucial to keep in mind that we don’t assume any structure in the
sampled set of hypotheses. In fact, many among them can be wildly bad samples,
especially if the initial depth is too noisy. Hence it implies that each
hypothesis should be evaluated independently, and our task is to learn to
distinguish the good hypotheses from the bad ones.

To achieve our objective, we designate the ranking model to be a small MLP
that takes a hypothesis feature and its context feature, and outputs a score
for the input hypothesis. Among all the hypotheses at a particular pixel, the
one with the highest score will be selected to be the updated depth estimation
$\hat{d}$. The ranking and selection goes on iteratively to refine the depth
estimation, where the new $\hat{d}$ will be used to generate better hypotheses
with the updated context feature.

Our design for the hypothesis feature and context update mechanism is
illustrated in Fig.1. There are three general guidelines we have followed when
we design the hypothesis feature: (1) It should inform how well the matching
is given by the hypothesis; (2) It should inform how well the hypothesis fits
into the current spatial context; (3) It should be robust to different camera
setups and resolutions. With these in mind, we propose to use the
concatenation of the following three simple quantities computed from a
hypothesis $d_{i}$:

$[\mathbf{c}(d_{i}),\mathbf{e}(d_{i}),\mathbf{f}(\hat{d})]$ (4)

The first term $\mathbf{c}(d_{i})$ consists of the matching costs linearly
interpolated from the cost volume for a fixed set of perturbations

$\mathbf{c}(d_{i})=[c(d_{i}+\epsilon)\text{ for }\epsilon\in\\{-1,0,1\\}]$ (5)

Note that $\epsilon$ is defined in the pseudo disparity space.

The second term $\mathbf{e}(d_{i})$ is a ”tamed” version of the second-order
error in the one-ring neighborhood $\mathcal{N}$ of the pixel $\mathbf{p}$.
Note that the error is computed against ${\hat{d}}$ in the pseudo disparity
space so that it can work across different metric and intrinsic scales.

$\mathbf{e}(d_{i})=[\text{tanh}(\hat{d}_{\mathbf{p}+\Delta
p}-\partial\hat{d}_{\mathbf{p}^{\prime}}\cdot\Delta p-d_{i})\text{ for
}\Delta\mathbf{p}\in\mathcal{N}]$ (6)

Finally, $\mathbf{f}(\hat{d})$ is a learned context feature of the previous
refined depth, whose inputs are the concatenation of $\mathbf{c}(\hat{d})$,
$\mathbf{e}(\hat{d})$ and the feature from a U-Net describing the reference
view’s high level appearance. We use a two-layer convolution network to
initialize $\mathbf{f}(\hat{d})$, and subsequently we use a convolutional
gated recurrent unit (GRU) to update $\mathbf{f}(\hat{d})$ given the updated
$\hat{d}$. We remark that the overall iterative update is similar to the RAFT
(Teed & Deng, 2020) framework, with the addition of the geometric error term
$\mathbf{e}(d)$. We will discuss its crucial contribution in our ablation
study in Sec.4.2.

We use a contrastive loss to supervise the ranking module. Let $d_{\text{gt}}$
be the ground truth depth and ${\mathcal{D}}={d_{i}}$ be the set of input
hypotheses. We define the positive sample group to be those within $1$-pseudo
disparity of the ground truth

$\mathcal{D}^{+}=\\{d_{i}\in\mathcal{D}:|d_{i}-d_{\text{gt}}|<=1\\}$ (7)

Denote the score of $d_{i}$ to be $s(d_{i})$. Our contrastive loss is defined
as

$\mathcal{L}_{\text{cl}}=-\log(\sum_{d_{i}\in\mathcal{D}^{+}}\frac{\exp(s(d_{i}))}{\sum_{d_{i}\in\mathcal{D}}\exp(s(d_{i}))})$
(8)

###  3.3 Baseline MVS design

It should be noted that our method can be embedded end-to-end in any deep
learning based MVS framework. Here we will demonstrate the design of a simple
end-to-end MVS pipeline. We use simple feature correlation as the matching
cost, so that there are no learnable components for cost volume filtering,
depth refinement, or confidence prediction. The only learnable parts are the
ranking MLP, context update convolutional layers, the light-weight U-Nets used
for extracting matching feature as well as the high level appearance of the
reference view.

Hence our matching component is very noisy, and suboptimal in the cases where
there are large view distortion, relative rotation or scale change. One should
expect straightforward improvement when additional techniques are
incorporated, such as cost volume filtering (Yao et al., 2018), learnable
aggregation (Zhang et al., 2023a), other feature extraction backbones (Cao et
al., 2023), etc. Even with noisy feature correlation matching signal, we show
in Sec.4.3 that it can achieve superior quality in depth and normal compared
to many state-of-art MVS works on the DTU dataset, highlighting the robustness
of our approach.

#### Feature extraction

We use a two-stream feature extraction architecture similar to (Teed & Deng,
2020). First, we use a matching feature network extracts distinctive features
that are then used to evaluate the cost of depth hypotheses between the
reference and other source views. Second, we use a context feature network
that learns high-level spatial cues for learnable hypothesis selection,
applied only on the reference image. Both networks are based on a light-weight
U-Net architecture (Ronneberger et al., 2015) which extracts features from
coarse to fine.

#### Matching cost aggregation

We choose the negative correlation as the matching cost:

$c_{v}(d)=-\text{corr}(\mathbf{f}_{v\to\text{ref}}(d),\mathbf{f}_{\text{ref}})$
(9)

where $\mathbf{f}_{v\to\text{ref}}(d)$ denotes the $v$-th source view feature
warped to the reference view through the hypothesis $d$. We aggregate the
costs from all source views to have a single cost volume simply as

$c(d)=\frac{1}{\Sigma_{v}w_{v}(d)}\Sigma_{i}w_{v}(d)c_{v}(d)$ (10)

where

$w_{i}(d)=\text{Sigmoid}(\alpha(\delta-c_{i}(d))^{3})$ (11)

computes the weighting for each view and hypothesis, and $\alpha$ is chosen so
that it downplays the contribution from higher cost, increases the importance
of lower cost, and not sensitive if the cost is close to $\delta$, thanks to
the cubic exponent.

#### Cost volume pyramid

As an optional benefit, we observe that it’s possible to compute the matching
costs for lower resolution depth using higher resolution feature.
Specifically, we construct a grid ${(x_{p},y_{p})}_{p}$, indexed by lower
resolution pixels, which samples the corresponding locations in the higher
resolution feature. We can then compute the warped pixel location and the
matching costs using the camera intrinsics and features corresponding to the
higher resolution.

In practice, we typically compute one additional cost volume using higher
resolution features. The new hypotheses are centered around the hypothesis of
lowest cost in the coarse cost volume, spaced according the scale defined by
the higher resolution pseudo disparity space. These two cost volumes now form
a cost volume pyramid, which will be used to provide both coarse and fine
matching information to the our ranking module through $\mathbf{c}(d)$ in
Eq.(5). We will demonstrate in Sec.4.2 that using the higher resolution
feature can unblock a higher level of accuracy even at lower resolution
output, but it’s otherwise not crucial to the success of our hypothesis
ranking module.

#### Overall pipeline

Our baseline MVS pipeline, as depicted in Figure 2, starts by extracting
features from a reference view and multiple source views. The first depth
estimation $\hat{d}$ is obtained as the lowest cost hypothesis from the full
cost volume. A cost volume pyramid is then constructed around the previous
depth estimation. The refinement is performed on a hierarchy of resolutions.
The refined depth from lower resolution will be upsampled using nearest-
neighbor and set to be the initial depth for the next higher resolution.

#### Training

Similar to the contrastive loss used in (Tankovich et al., 2021), we supervise
the feature matching using a simple contrastive loss

$\mathcal{L}_{\text{fm}}=c(d_{\text{gt}})-\text{clip}(c(d^{-}),[\alpha,\beta])$
(12)

where $c(d_{\text{gt}})$ is the ground truth depth, and $d^{-}$ is the
negative sample that is at least $1$-pseudo disparity away from the ground
truth and has the lowest matching cost

$d^{-}=\arg\min_{|d-d_{\text{gt}}|>1}c(d)$ (13)

The loss will not penalize cost of $d^{-}$ already lower than $\alpha$ or
higher than $\beta$. We choose $\beta=1$ in lower resolution and $\alpha=0$
for all resolution, so that the learned features will be as distinctive as
possible. We found it better to choose a lower $\beta$ in higher resolution
(e.g. 0.8) due to the frequent appearance of local texture-less regions. Note
that there is no any kind of cost volume regularization. Furthermore, we
enforce the matching feature network to be only trained by the above loss,
meaning it will not be influenced by the depth refinement. Therefore, the
total loss of this baseline model is simply

$\mathcal{L}_{\text{fm}}+\mathcal{L}_{\text{cl}}$ (14)

where ${\mathcal{L}_{\text{fm}}}$ only updates the matching feature U-Net, and
${\mathcal{L}_{\text{cl}}}$ updates the context feature U-Net in the reference
view, the ranking MLP and the convolutional layers that initialize and update
${\mathbf{f}(\hat{d})}$ in Eq.(4).

##  4 Experiments

Method |  $\%<1$mm $\uparrow$ | MAE(@$<1$mm) $\downarrow$ |  $\%<5^{\circ}$(@$<1$mm) $\uparrow$ |  $\%<10^{\circ}$(@$<1$mm) $\uparrow$
---|---|---|---|---
baseline: ($\nicefrac{{1}}{{8}}$,$\nicefrac{{1}}{{4}}$,$\nicefrac{{1}}{{4}}$)-($\nicefrac{{1}}{{4}}$,$\nicefrac{{1}}{{2}}$,1) | $\mathbf{70.16}$ | $\mathbf{0.3669}$ | $\mathbf{45.53}$ | $\mathbf{73.34}$
baseline: ($\nicefrac{{1}}{{8}}$,$\nicefrac{{1}}{{4}}$,$\nicefrac{{1}}{{4}}$)-($\nicefrac{{1}}{{4}}$,$\nicefrac{{1}}{{2}}$,1) + BlendedMVS | $67.01$ | $0.3992$ | $43.77$ | $71.73$
baseline: ($\nicefrac{{1}}{{8}}$,$\nicefrac{{1}}{{8}}$,$\nicefrac{{1}}{{8}}$)-($\nicefrac{{1}}{{4}}$,$\nicefrac{{1}}{{2}}$,1) | $\mathbf{71.03}$ | $\mathbf{0.3558}$ | $\mathbf{68.16}$ | $\mathbf{84.01}$
baseline: ($\nicefrac{{1}}{{8}}$,$\nicefrac{{1}}{{8}}$,$\nicefrac{{1}}{{8}}$)-n.a. | $63.62$ | $0.3978$ | $57.31$ | $79.64$
baseline w/o selection: ($\nicefrac{{1}}{{8}}$,$\nicefrac{{1}}{{8}}$,$\nicefrac{{1}}{{8}}$)-($\nicefrac{{1}}{{4}}$,$\nicefrac{{1}}{{2}}$,1) | $59.33$ | $0.4282$ | $45.38$ | $74.41$
baseline w/o $\mathbf{e}(d)$ term: ($\nicefrac{{1}}{{8}}$,$\nicefrac{{1}}{{8}}$,$\nicefrac{{1}}{{8}}$)-($\nicefrac{{1}}{{4}}$,$\nicefrac{{1}}{{2}}$,1) | $55.26$ | $0.4223$ | $41.51$ | $66.63$
baseline w/o CHOSEN: ($\nicefrac{{1}}{{8}}$,$\nicefrac{{1}}{{8}}$,$\nicefrac{{1}}{{8}}$)-($\nicefrac{{1}}{{4}}$,$\nicefrac{{1}}{{2}}$,1) | $46.46$ | $0.4653$ | $20.90$ | $49.00$
MVSFormer (Cao et al., 2023) | $61.92$ | $0.4248$ | $18.96$ | $44.17$
GeoMVSNet (Zhang et al., 2023b) | $63.93$ | $0.4089$ | $15.18$ | $38.40$
GBi-Net (Mi et al., 2022) | $34.01$ | $0.4531$ | $13.78$ | $33.41$
IterMVS (Wang et al., 2022) | $51.09$ | $0.4524$ | $16.67$ | $37.50$
PatchMatchNet (Wang et al., 2021) | $56.19$ | $0.4260$ | $18.03$ | $41.82$
UCSNet (Gu et al., 2020) | $59.03$ | $0.3942$ | $31.31$ | $54.39$

Table 1: Comparison for estimated depths and normals on DTU testing set. We
mark our best results separately for $\nicefrac{{1}}{{8}}$ and
$\nicefrac{{1}}{{4}}$ output resolutions. Notice that so long as the finest
resolution matching features are used, the final depth accuracy metrics for
these two output resolutions are very similar. Our simple baselines offer
significant improvement in terms of depth quality even compared to the
strongest state-of-art MVS pipelines.

###  4.1 Implementation details

We evaluate our depth refinement method using the baseline MVS pipeline
described in Sec.3.3. Typically, we extract matching features at
$\nicefrac{{1}}{{8}}$, $\nicefrac{{1}}{{4}}$, $\nicefrac{{1}}{{2}}$ and $1$ of
the original resolution, and context features at $\nicefrac{{1}}{{8}}$ and
$\nicefrac{{1}}{{4}}$ of the original resolution. The depth is initialized by
winner-take-all from the full cost volume at $\nicefrac{{1}}{{8}}$ resolution
that has $N=128$ slices, and a cost volume pyramid is built on
$\nicefrac{{1}}{{8}}\,\&\,\nicefrac{{1}}{{4}}$ resolution matching features.
One refinement stage consists of 4 iterations, where twice on initial sampled
hypotheses and twice on spatially sampled hypotheses, in an alternating
fashion. After upsampling the refined depth using nearest neighbor, we repeat
the same refinement stage at $\nicefrac{{1}}{{4}}$ resolution, with a
$\nicefrac{{1}}{{4}}\,\&\,\nicefrac{{1}}{{2}}$ pyramid. Finally, the last
refinement stage is performed with a $\nicefrac{{1}}{{4}}\,\&\,1$ pyramid with
output at $\nicefrac{{1}}{{4}}$ resolution. Each refinement stage has their
own parameters for the ranking MLP and context update networks. We denote this
default configuration as
$(\nicefrac{{1}}{{8}},\nicefrac{{1}}{{4}},\nicefrac{{1}}{{4}})\,\&\,(\nicefrac{{1}}{{4}},\nicefrac{{1}}{{2}},1)$.
Different choices for cost volume pyramid configurations and their effects
will be discussed in Sec 4.2.

We set $M=4$ in the initial hypotheses sampling, giving $2M+1=9$ hypotheses.
For spatial sampling, we use a set of offsets ${\\{\Delta\mathbf{p}\\}}$
consists of dilated $3\times 3$ regular patches with dilation rate of $1$ and
$3$, without repeating the patch center, giving in total $17$ hypotheses for
each pixel. This offset configuration is the same as the one illustrated in
the spatial sampling part of Fig.1.

The model is trained and tested on a single NVIDIA A100 GPU (40G). We first
train with batch size 4, at input resolution $600\times 800$, up to 200k
iterations using the default Adam optimizer (Kingma & Ba, 2014) at a learning
rate of $0.001$. We then fine-tune for up to 50k iterations at input
resolution $1200\times 1600$ at a learning rate of $0.0005$. During training,
we fix the closest source view and randomly sample two from the remaining
source views, which is the only data augmentation we used. For testing, it
takes around $0.6$ seconds to run at $1200\times 1600$ with $5$ source views.
We provide results both from models trained on DTU (Jensen et al., 2014)
training set only, and on DTU mixed with the BlendedMVS (Yao et al., 2020)
dataset, which will be tagged specifically.

#### Depth & normal metrics

We use the following metrics to measure the quality of depth and its induced
normal map on the DTU evaluation dataset:

  * •

$\%<x$mm: the percentage of pixels that have less than $x$-mm of absolute
error.

  * •

MAE(@$<x$mm): the mean absolute error on pixels that have less than $x$-mm of
absolute error.

  * •

$\%<x^{\circ}$(@$<y$mm): the percentage of pixels where the normal is within
$x^{\circ}$ of angular error out of all pixels whose absolute error is less
than $y$-mm.

The ground truth depth are resized to the same resolution of the outputs using
nearest neighbor. The normals are computed from the 3D coordinate’s gradients
using the Sobel filter. All the above metrics are computed only on the valid
pixels where the ground-truth is available.

Color image

Ground truth

Ours

MVSFormer

GeoMVSNet

GBi-Net

Figure 3: Normal quality comparisons on DTU. Our simple baseline MVS trained
only on DTU produces significantly more accurate normals.

Figure 4: Direct application of our DTU + BlendedMVS trained baseline model on
instances from MultiFace (Knapitsch et al., 2017), Tanks & Temples and ETH3D
(Schops et al., 2017) datasets. Our simple baseline achieves consistent
generalization ability even though trained on substantially different data.

###  4.2 Ablation studies

#### Cost volume pyramid design

Here we study the effects of different cost volume pyramid configurations. We
choose the following variants of the configuration:

  * •

($\nicefrac{{1}}{{8}}$,$\nicefrac{{1}}{{4}}$,$\nicefrac{{1}}{{4}}$)-($\nicefrac{{1}}{{4}}$,$\nicefrac{{1}}{{2}}$,$1$):
There are 3 stages of refinement with
$\nicefrac{{1}}{{8}}\,\&\,\nicefrac{{1}}{{4}}$,
$\nicefrac{{1}}{{4}}\,\&\,\nicefrac{{1}}{{2}}$ and
$\nicefrac{{1}}{{8}}\,\&\,1$ cost volume pyramids, and output refined depth at
$\nicefrac{{1}}{{4}}$ resolution. This is our default configuration and we
also include the results trained on data mixed BlendedMVS.

  * •

($\nicefrac{{1}}{{8}}$,$\nicefrac{{1}}{{8}}$,$\nicefrac{{1}}{{8}}$)-($\nicefrac{{1}}{{4}}$,$\nicefrac{{1}}{{2}}$,$1$):
There are 3 stages of refinement with
$\nicefrac{{1}}{{8}}\,\&\,\nicefrac{{1}}{{4}}$,
$\nicefrac{{1}}{{8}}\,\&\,\nicefrac{{1}}{{2}}$ and
$\nicefrac{{1}}{{8}}\,\&\,1$ cost volume pyramids, and output refined depth at
$\nicefrac{{1}}{{8}}$ resolution.

  * •

($\nicefrac{{1}}{{8}}$,$\nicefrac{{1}}{{8}}$,$\nicefrac{{1}}{{8}}$)-n.a: Only
the coarsest resolution matching feature is used. There are 3 stages of
refinement with $\nicefrac{{1}}{{8}}$ resolution feature, and output refined
depth at $\nicefrac{{1}}{{8}}$ resolution.

Quantitative results on DTU testing set are reported in the first four rows in
Tab.1. First of all, notice that even without cost volume pyramid, our method
performs reasonably well, indicating that the pyramid design mainly unblocks
higher accuracy at lower resolution output, but otherwise is an optional
feature. Second, we can observe from the first and third rows in Tab.1 that
the $\%<1$mm metrics are similar for the outputs at $\nicefrac{{1}}{{8}}$
resolution and $\nicefrac{{1}}{{4}}$ resolution, so long as the full
resolution matching features are used. Comparing $\nicefrac{{1}}{{8}}$ (third
and fourth rows) and $\nicefrac{{1}}{{4}}$ (first and second rows) output
resolution, we can observe that it becomes more difficult to get accurate
normals at higher resolution. This is due to the fact that high frequency
details only emerge in higher resolution, which may be impossible to obtain
without a photometric appearance model. Lastly, we remark that the worse
results from mixed data training is likely due to that BlendedMVS contains
images with severe aliasing artifacts, which could hurt our model training
with $\mathcal{L}_{\text{fm}}$.

#### Selection v.s. expectation

The ability to rank arbitrary hypotheses is essential to the success of our
depth refinement. Here we illustrate the point by comparing with an approach
where the learned score $s_{i}$ for each hypothesis $d_{i}$ is used for taking
a weighted average. In this ablated approach, the refined depth is obtained by

$\hat{d}=\frac{1}{\sum_{i}\exp(s_{i})}\sum_{i}\exp({s_{i}})\cdot d_{i}$

and we use smoothed $L^{1}$ loss between $\hat{d}$ and $d_{\text{g}t}$ in
place of $\mathcal{L}_{\text{c}l}$. Everything else in the pipeline stays the
same. Quantitative results are reported in the fifth row of Tab.1. We note
that this alternative approach based on weighted average is much less accurate
than the our approach based on ranking and selection. This can be attributed
to the difficult task of learning the weights for arbitrary hypotheses, while
learning to classify the hypotheses is a much easier task.

#### Hypothesis feature design

The ”tamed” second order error term $\mathbf{e}(d)$ in Eq.(4) can be viewed as
an extra component compared to the input feature design in the RAFT (Teed &
Deng, 2020) framework for optical flow estimation. Here we show that it is a
vital component in the hypothesis ranking model that improves the overall
smoothness and accuracy. Quantitative results on DTU testing set are reported
in the sixth row of Tab.1. Since each hypothesis is evaluated independently,
without the information about how well a particular hypothesis fits in the
local geometry, the model struggles to select the best hypothesis solely based
on matching and context information.

###  4.3 Comparisons on depths and normals

We collect the testing results from various recent deep learning based MVS
works in the last part of Tab.1. The outputs for the candidate models and
ground truths are resized to $\nicefrac{{1}}{{4}}$ of input resolution using
nearest neighbor. Our simple baseline MVS pipeline significantly outperforms
the strongest state-of-art in terms depth and normal quality. Visual
comparisons are shown in Fig.3.

###  4.4 Qualitative results

We demonstrate the excellent generalization ability of our simple baseline on
various datasets including MultiFace (Wuu et al., 2022), Tanks & Temples
(Knapitsch et al., 2017) and ETH3D (Schops et al., 2017). Results in Fig.4 use
the same baseline model trained on mixture of DTU and BlendedMVS reported in
Tab.1.

##  5 Limitations and Conclusion

One limitation of CHOSEN is that it becomes more expensive to sample and
select from a large number of hypotheses at high resolution. This is part of
the reason why we settled at $\nicefrac{{1}}{{4}}$ resolution to arrive at a
sweet spot of both performance and run time. Another limitation is that we did
not focus on bundle adjustment and joint filtering of depths for point cloud
and surface reconstruction, which we believe should be a subject of its own
interests, especially considering the proliferation of volumetric based
methods such as (Zhang et al., 2021).

We have demonstrated that CHOSEN is simple yet effective for multi-view depth
refinement. It iteratively re-samples and select the best hypotheses, and is
applicable to a wide range of multi-view capture setup. We have integrated
CHOSEN into a simple MVS baseline that delivers impressive quality in terms of
depth and normal accuracy.

## References

  * Barnes et al. (2009) Barnes, C., Shechtman, E., Finkelstein, A., and Goldman, D. B.  PatchMatch: A randomized correspondence algorithm for structural image editing.  _ACM Transactions on Graphics (Proc. SIGGRAPH)_ , 28(3), August 2009.
  * Barron & Poole (2016) Barron, J. T. and Poole, B.  The fast bilateral solver.  In _European conference on computer vision_ , pp. 617–632. Springer, 2016.
  * Bleyer et al. (2011) Bleyer, M., Rhemann, C., and Rother, C.  Patchmatch stereo-stereo matching with slanted support windows.  In _Bmvc_ , volume 11, pp. 1–11, 2011.
  * Cao et al. (2023) Cao, C., Ren, X., and Fu, Y.  Mvsformer: Multi-view stereo by learning robust image features and temperature-based depth.  _Transactions of Machine Learning Research_ , 2023.
  * Cao et al. (2024) Cao, C., Ren, X., and Fu, Y.  Mvsformer++: Revealing the devil in transformer’s details for multi-view stereo.  _arXiv preprint arXiv:2401.11673_ , 2024.
  * Chang & Chen (2018) Chang, J.-R. and Chen, Y.-S.  Pyramid stereo matching network.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018.
  * Cheng et al. (2020) Cheng, S., Xu, Z., Zhu, S., Li, Z., Li, L. E., Ramamoorthi, R., and Su, H.  Deep stereo using adaptive thin volume representation with uncertainty awareness.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 2524–2534, 2020.
  * Collins (1996) Collins, R. T.  A space-sweep approach to true multi-image matching.  In _Proceedings CVPR IEEE Computer Society Conference on Computer Vision and Pattern Recognition_ , pp. 358–363. IEEE, 1996.
  * Ding et al. (2022) Ding, Y., Yuan, W., Zhu, Q., Zhang, H., Liu, X., Wang, Y., and Liu, X.  Transmvsnet: Global context-aware multi-view stereo network with transformers.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 8585–8594, 2022.
  * Furukawa & Hernández (2015) Furukawa, Y. and Hernández, C.  Multi-view stereo: A tutorial.  _Found. Trends Comput. Graph. Vis._ , 9(1-2):1–148, 2015.
  * Furukawa & Ponce (2010) Furukawa, Y. and Ponce, J.  Accurate, dense, and robust multiview stereopsis.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 32(8):1362–1376, 2010.
  * Galliani et al. (2015) Galliani, S., Lasinger, K., and Schindler, K.  Massively parallel multiview stereopsis by surface normal diffusion.  In _ICCV_ , 2015.
  * Galliani et al. (2016) Galliani, S., Lasinger, K., and Schindler, K.  Gipuma: Massively parallel multi-view stereo reconstruction.  _Publikationen der Deutschen Gesellschaft für Photogrammetrie, Fernerkundung und Geoinformation e. V_ , 25(361-369):2, 2016.
  * Gu et al. (2020) Gu, X., Fan, Z., Zhu, S., Dai, Z., Tan, F., and Tan, P.  Cascade cost volume for high-resolution multi-view stereo and stereo matching.  In _2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020_ , pp. 2492–2501. IEEE, 2020.
  * Hui et al. (2016) Hui, T., Loy, C. C., and Tang, X.  Depth map super-resolution by deep multi-scale guidance.  In _Computer Vision - ECCV 2016 - 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part III_ , volume 9907 of _Lecture Notes in Computer Science_ , pp. 353–369. Springer, 2016.
  * Insafutdinov & Dosovitskiy (2018) Insafutdinov, E. and Dosovitskiy, A.  Unsupervised learning of shape and pose with differentiable point clouds.  In _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada_ , pp. 2807–2817, 2018.
  * Jensen et al. (2014) Jensen, R., Dahl, A., Vogiatzis, G., Tola, E., and Aanæs, H.  Large scale multi-view stereopsis evaluation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 406–413, 2014.
  * Ji et al. (2017) Ji, M., Gall, J., Zheng, H., Liu, Y., and Fang, L.  Surfacenet: An end-to-end 3d neural network for multiview stereopsis.  In _IEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017_ , pp. 2326–2334. IEEE Computer Society, 2017.
  * Kar et al. (2017) Kar, A., Häne, C., and Malik, J.  Learning a multi-view stereo machine.  In _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pp. 365–376, 2017.
  * Kendall et al. (2017) Kendall, A., Martirosyan, H., Dasgupta, S., Henry, P., Kennedy, R., Bachrach, A., and Bry, A.  End-to-end learning of geometry and context for deep stereo regression.  In _IEEE International Conference on Computer Vision (ICCV)_ , 2017\.
  * Khamis et al. (2018) Khamis, S., Fanello, S., Rhemann, C., Kowdle, A., Valentin, J., and Izadi, S.  StereoNet: Guided hierarchical refinement for edge-aware depth prediction.  In _European Conference on Computer Vision (ECCV)_ , 2018.
  * Kingma & Ba (2014) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Knapitsch et al. (2017) Knapitsch, A., Park, J., Zhou, Q.-Y., and Koltun, V.  Tanks and temples: Benchmarking large-scale scene reconstruction.  _ACM Transactions on Graphics (ToG)_ , 36(4):1–13, 2017.
  * Kuhn et al. (2020) Kuhn, A., Sormann, C., Rossi, M., Erdler, O., and Fraundorfer, F.  Deepc-mvs: Deep confidence prediction for multi-view stereo reconstruction.  In _2020 International Conference on 3D Vision (3DV)_ , pp. 404–413. Ieee, 2020.
  * Kutulakos & Seitz (2000) Kutulakos, K. N. and Seitz, S. M.  A theory of shape by space carving.  _Int. J. Comput. Vis._ , 38(3):199–218, 2000\.  doi: 10.1023/A:1008191222954.  URL https://doi.org/10.1023/A:1008191222954.
  * Lhuillier & Quan (2005) Lhuillier, M. and Quan, L.  A quasi-dense approach to surface reconstruction from uncalibrated images.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 27(3):418–433, 2005.
  * Lin et al. (2018) Lin, C., Kong, C., and Lucey, S.  Learning efficient point cloud generation for dense 3d object reconstruction.  pp. 7114–7121. AAAI Press, 2018.
  * Mi et al. (2022) Mi, Z., Di, C., and Xu, D.  Generalized binary search network for highly-efficient multi-view stereo.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022.
  * Oquab et al. (2023) Oquab, M., Darcet, T., Moutakanni, T., Vo, H., Szafraniec, M., Khalidov, V., Fernandez, P., Haziza, D., Massa, F., El-Nouby, A., et al.  Dinov2: Learning robust visual features without supervision.  _arXiv preprint arXiv:2304.07193_ , 2023.
  * Pang et al. (2017) Pang, J., Sun, W., Ren, J., Yang, C., and Yan, Q.  Cascade residual learning: A two-stage convolutional neural network for stereo matching.  In _International Conference on Computer Vision-Workshop on Geometry Meets Deep Learning (ICCVW 2017)_ , 2017.
  * Peng et al. (2022) Peng, R., Wang, R., Wang, Z., Lai, Y., and Wang, R.  Rethinking depth estimation for multi-view stereo: A unified representation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 8645–8654, 2022.
  * Ronneberger et al. (2015) Ronneberger, O., Fischer, P., and Brox, T.  U-net: Convolutional networks for biomedical image segmentation.  _MICCAI_ , 2015.
  * Scharstein & Szeliski (2002) Scharstein, D. and Szeliski, R.  A taxonomy and evaluation of dense two-frame stereo correspondence algorithms.  _International journal of computer vision_ , 2002.
  * Schönberger et al. (2016) Schönberger, J. L., Zheng, E., Frahm, J., and Pollefeys, M.  Pixelwise view selection for unstructured multi-view stereo.  In _Computer Vision - ECCV 2016 - 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part III_ , volume 9907 of _Lecture Notes in Computer Science_ , pp. 501–518. Springer, 2016.
  * Schops et al. (2017) Schops, T., Schonberger, J. L., Galliani, S., Sattler, T., Schindler, K., Pollefeys, M., and Geiger, A.  A multi-view stereo benchmark with high-resolution images and multi-camera videos.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 3260–3269, 2017.
  * (36) Taniai, T., Matsushita, Y., Sato, Y., and Naemura, T.  Continuous stereo matching using local expansion moves.  _arXiv preprint arXiv:1603.08328_.
  * Tankovich et al. (2021) Tankovich, V., Hane, C., Zhang, Y., Kowdle, A., Fanello, S., and Bouaziz, S.  Hitnet: Hierarchical iterative tile refinement network for real-time stereo matching.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 14362–14372, 2021.
  * Teed & Deng (2020) Teed, Z. and Deng, J.  Raft: Recurrent all-pairs field transforms for optical flow.  In _European conference on computer vision_ , pp. 402–419. Springer, 2020.
  * Tola et al. (2012) Tola, E., Strecha, C., and Fua, P.  Efficient large-scale multi-view stereo for ultra high-resolution image sets.  _Mach. Vis. Appl._ , 23(5):903–920, 2012.
  * Wang et al. (2021) Wang, F., Galliani, S., Vogel, C., Speciale, P., and Pollefeys, M.  Patchmatchnet: Learned multi-view patchmatch stereo.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 14194–14203, 2021.
  * Wang et al. (2022) Wang, F., Galliani, S., Vogel, C., and Pollefeys, M.  Itermvs: Iterative probability estimation for efficient multi-view stereo, 2022.
  * Wuu et al. (2022) Wuu, C.-h., Zheng, N., Ardisson, S., Bali, R., Belko, D., Brockmeyer, E., Evans, L., Godisart, T., Ha, H., Huang, X., Hypes, A., Koska, T., Krenn, S., Lombardi, S., Luo, X., McPhail, K., Millerschoen, L., Perdoch, M., Pitts, M., Richard, A., Saragih, J., Saragih, J., Shiratori, T., Simon, T., Stewart, M., Trimble, A., Weng, X., Whitewolf, D., Wu, C., Yu, S.-I., and Sheikh, Y.  Multiface: A dataset for neural face rendering.  In _arXiv_ , 2022.  doi: 10.48550/ARXIV.2207.11243.  URL https://arxiv.org/abs/2207.11243.
  * Xu & Tao (2020) Xu, Q. and Tao, W.  Pvsnet: Pixelwise visibility-aware multi-view stereo network.  _CoRR_ , abs/2007.07714, 2020.  URL https://arxiv.org/abs/2007.07714.
  * Yao et al. (2018) Yao, Y., Luo, Z., Li, S., Fang, T., and Quan, L.  Mvsnet: Depth inference for unstructured multi-view stereo.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pp. 767–783, 2018.
  * Yao et al. (2019) Yao, Y., Luo, Z., Li, S., Shen, T., Fang, T., and Quan, L.  Recurrent mvsnet for high-resolution multi-view stereo depth inference.  In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019_ , pp. 5525–5534, 2019.
  * Yao et al. (2020) Yao, Y., Luo, Z., Li, S., Zhang, J., Ren, Y., Zhou, L., Fang, T., and Quan, L.  Blendedmvs: A large-scale dataset for generalized multi-view stereo networks.  _Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * Yu & Gao (2020) Yu, Z. and Gao, S.  Fast-mvsnet: Sparse-to-dense multi-view stereo with learned propagation and gauss-newton refinement.  In _2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020_ , pp. 1946–1955. IEEE, 2020.
  * Zhang et al. (2021) Zhang, J., Yang, G., Tulsiani, S., and Ramanan, D.  Ners: Neural reflectance surfaces for sparse-view 3d reconstruction in the wild.  _Advances in Neural Information Processing Systems_ , 34:29835–29847, 2021.
  * Zhang et al. (2023a) Zhang, J., Li, S., Luo, Z., Fang, T., and Yao, Y.  Vis-mvsnet: Visibility-aware multi-view stereo network.  _International Journal of Computer Vision_ , 131(1):199–214, 2023a.
  * Zhang et al. (2018) Zhang, Y., Khamis, S., Rhemann, C., Valentin, J., Kowdle, A., Tankovich, V., Schoenberg, M., Izadi, S., Funkhouser, T., and Fanello, S.  ActiveStereoNet: End-to-end self-supervised learning for active stereo systems.  _European Conference on Computer Vision (ECCV)_ , 2018.
  * Zhang et al. (2023b) Zhang, Z., Peng, R., Hu, Y., and Wang, R.  Geomvsnet: Learning multi-view stereo with geometry perception.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 21508–21518, 2023b.


# Disentangled Attribution Curves for Interpreting Random Forests and Boosted
Trees

Summer Devlin
EECS Department
UC Berkeley
<EMAIL_ADDRESS>Chandan Singh
EECS Department
UC Berkeley
<EMAIL_ADDRESS>W. James Murdoch
Statistics Department
UC Berkeley
<EMAIL_ADDRESS>Bin Yu
Statistics, EECS Department
UC Berkeley
<EMAIL_ADDRESS>
###### Abstract

Tree ensembles, such as random forests and AdaBoost, are ubiquitous machine
learning models known for achieving strong predictive performance across a
wide variety of domains. However, this strong performance comes at the cost of
interpretability (i.e. users are unable to understand the relationships a
trained random forest has learned and why it is making its predictions). In
particular, it is challenging to understand how the contribution of a
particular feature, or group of features, varies as their value changes. To
address this, we introduce Disentangled Attribution Curves (DAC), a method to
provide interpretations of tree ensemble methods in the form of (multivariate)
feature importance curves. For a given variable, or group of variables, DAC
plots the importance of a variable(s) as their value changes. We validate DAC
on real data by showing that the curves can be used to increase the accuracy
of logistic regression while maintaining interpretability, by including DAC as
an additional feature. In simulation studies, DAC is shown to out-perform
competing methods in the recovery of conditional expectations. Finally,
through a case-study on the bike-sharing dataset, we demonstrate the use of
DAC to uncover novel insights into a dataset.

##  1 Introduction

Modern machine learning models have demonstrated strong predictive performance
across a wide variety of settings. However, these models have become
increasingly difficult to interpret, limiting their use in fields such as
medicine [1] and policy-making [2]. Moreover, the use of such models has come
under increasing scrutiny as they struggle with issues such as fairness [3]
and regulatory pressure [4]. To address these concerns, research in
interpretable machine learning has received an increasing amount of attention
[5, 6]. Interpretable machine learning aims to increase the descriptive
accuracy of models (i.e. how well they can be described to a relevant
audience) without losing predictive accuracy [5].

Here, we focus on tree ensembles such as random forests [7] and AdaBoost [8],
which are widely used and known to have strong predictive performance.
However, their complex nonlinear form and sheer number of parameters has made
them difficult to interpret, beyond limited notions such as individual feature
importance [7, 9, 10].

To address these problems, we introduce Disentangled Attribution Curves (DAC),
a method which yields importance curves for any feature (or group of features)
to the predictions made by a tree ensemble model111Code, notebooks, and models
with a simple API for reproducing all results is available at
https://github.com/csinva/disentangled_attribution_curves.. These curves
provide a simple post-hoc way to interpret how different features interact
within a tree ensemble. Through experiments on real and simulated datasets, we
find that DAC provides meaningful interpretations, can identify groundtruth
importances, and can be used for simple feature engineering to improve
predictive accuracy for a linear model.

Figure 1: Toy example illustrating DAC. DAC succesfully learns that the
interaction between features determines the prediction, not the features in
isolation. (A) Tree representing the XOR function. (B, C) DAC single-feature
importance for Fever and Blood pressure, respectively. (D) DAC importance for
interaction between Fever and Blood pressure.

#### A simple example

Fig 1 demonstrates a simple example of how DAC works. The tree in Fig 1A
depicts a decision tree which performs binary classification using two
features (representing the XOR function). In this problem, knowing the value
of one of the features without knowledge of the other feature yields no
information - the classifier still has a 50% chance of predicting either
class. As a result, DAC produces curves which assign 0 importance to either
feature on its own (Fig 1B-C). Knowing both features yields perfect
information about the classifier, and thus the DAC curve for both features
together correctly shows that the interaction of the features produces the
model’s predictions.

In this instance, due to their inability to describe interactions, common
feature-based importance scores would assign non-zero importance to both
features [7, 11, 10]. Consequently, these scalar feature-importance scores are
actually an opaque combination of the importance of the individual feature and
that feature’s interactions with other features. In contrast, DAC explicitly
disentangles the importances of individual features and the interactions
between them.

The paper is organized as follows: Sec 2 gives background on related methods,
Sec 3 introduces the method, Sec 4 displays results on both simulated and real
datasets, and Sec 5 ends with some conclusions.

##  2 Background

This section briefly covers related work and its relation to DAC.

###  2.1 Scalar importance scores

The most common interpretations for tree ensembles take the form of scalar
feature-importance scores. They are often useful, but their scalar form
restricts them from providing as much information as the curves provided by
DAC. Importantly, the importance scores for any feature implicitly contain
scores for the interaction of that feature with other features, making it
unclear how to interpret the feature importance in isolation.

Impurity-based scores (e.g. mean-decrease impurity) [11, 7] are widely used in
tree ensemble interpretation. These scores are computed by averaging the
impurity reduction for all splits where a feature is used. When using the Gini
impurity, these scores are sometimes referred to as the Gini importance.

Another popular score is the permutation importance (i.e. mean decrease
accuracy) [7]. It is defined as the mean decrease in classification accuracy
after permuting a feature over out-of-bag samples. More recently, this method
has been improved to develop conditional variable importance via a conditional
permutation scheme [9].

Besides these scores, there are some model-agnostic methods to compute feature
importance at the prediction-level (i.e. for one specific prediction) [12].
One popular example is Shap values, which provide prediction-level scores for
individual variables [13, 10].

#### Interaction importance scores

Moving beyond single-variable importance scores, some more recent methods look
for interactions between different variables.

For example, recent work [14, 15] stabilizes the training of random forests
and then extracts interactions by looking at co-occurrences of features along
decision paths. Additionally, some work has begun to address looking at
interactions at the prediction-level for random forests (e.g. [10]). Recent
methods in the deep learning literature follow a similar intuition of
explicitly computing importances for feature interactions [16, 17, 18]. There
also exist other methods for calculating interaction importance which are
model-agnostic [19, 20].

###  2.2 Importance curves

Some recent interpretation methods compute curves to convey importances for
different features as their value changes. However, these previous methods
operate solely on the inputs and outputs of a model, ignoring the rich
information contained within the model.

Let $\hat{f}$ be the fitted model of interest, $X$ the input features, $S$ the
set of the variables of interest, and $C$ the set of remaining variables.
Partial dependence plots (PDP) simply plot the expectation of the marginal
function on $X_{S}$ [21], which amounts to integrating out the values of
$X_{C}$: $\hat{f}(X_{S})=\mathbb{E}_{X_{C}}\hat{f}(X_{S},X_{C})$. This assumes
that the features in $S$ and $C$ are independent, otherwise the points being
averaged over do not accurately represent the underlying data distribution.
Independence is often an unrealistic assumption which can cause serious issues
for this method [9]. Individual conditional expectation (ICE) plots [22] are
very similar to PDP (but yield one curve for each data point), and suffer from
the same independence assumption.

Aggregated local effects (ALE) plots calculate local differences in
predictions based on the variable of interest, conditioned on $x_{C}$ [23].
Then these local effects are aggregated from some baseline. These local
effects ameliorate the issue with assuming independent variables, but
introduce sensitive hyperparameters, such as a window size and a baseline,
which can alter the interpretation. DAC helps fix the need for choosing these
hyperparameters by leveraging the internals of the random forest.

##  3 Disentangled Attribution Curves

DAC yields post-hoc interpretations for tree ensembles which have already been
trained. At a high level, DAC importance(s) for a feature (or a group of
features) correspond to a fitted model’s average prediction for training data
points classified using only that feature (or group of features). This
procedure ensures that the importances for individual features and their
interactions are disentangled, since the DAC importance for individual
features completely ignores other features.

DAC also satisfies the so-called missingness property [13]: features which are
not used in the forest do not contribute to the importance for any
predictions. This is trivially satisfied, as only features which are used by
the forest can change the DAC importance.

Intuitively, DAC is similar to a fairly natural interpretation: the
conditional expectation of the model’s predictions over the dataset
conditioned on particular values of a feature. However, DAC is superior to the
simple conditional expectation curve, as it is more faithful to the model’s
underlying process. For example, consider a model which places high importance
on only one of two correlated features. Conditional expectation will assign
both features a high importance, whereas DAC will successfully learn to assign
high importance to only the appropriate feature.

In this paper, we focus on cases where $S$ contains either one or two
variables, yielding importance curves or heatmaps, due to the difficulties
associated with visualizing more than 3 variables. However, DAC importances
can still be used to investigate higher-order interactions between variables.

DAC curves are constructed in a hierarchical fashion, mirroring the structure
of a tree ensemble model. In particular, a tree ensemble is a combination of
trees, and each tree is a combination of leaves. Given a trained random forest
or AdaBoost model, we first define DAC for individual leaves, then demonstrate
how to aggregate from leaves to trees, and trees to forests.

###  3.1 Attribution on leaves

At each leaf node $L$ on a tree $T$, a decision tree makes its prediction by
computing the average output value $Y_{i}$ over a subset $R_{L}$ of the input
data. Without loss of generality, assume this subset is computed by applying a
sequence of decision rules of the form $X_{p}\geq c$. Formally, for a path of
length $N$, this corresponds to the region $R$ defined below, resulting in
estimate $\hat{Y}$.

$\displaystyle R_{L}$ $\displaystyle=\bigcap_{j=1}^{N}\\{X_{p_{j}}\geq
c_{j}\\}$ (1) $\displaystyle\hat{Y}$
$\displaystyle=\frac{1}{|R_{L}|}\sum_{i:X_{i}\in R_{L}}Y_{i}$ (2)

Note that, to compute the region $R_{L}$ requires using information about the
set of variables $\\{X_{p_{j}}\\}_{j=1}^{N}$. To compute our DAC estimate for
a set of variables $S$, we restrict $R_{L}$ to $R_{L,S}$ by only using splits
for variables which are contained in $S$. In addition, we restrict our
consideration to data points $X$ which are close to the center of the leaf. In
particular, we require that $|x_{j}-\mu_{L,j}|\leq k\sigma_{L,j}$, for all
$j\in S$, where $k$ is a smoothing hyperparameter fixed to one throughout this
paper, and $\mu_{L,j},\sigma_{L,j}$ denote the mean and standard deviation of
$X_{j}$ contained in $R_{L}$ (if $|R_{L}|=1$, we set $\sigma_{L,j}=0$). This
yields our DAC estimate $\hat{Y}_{DAC}(S;L,T)$ for a single leaf:

$\displaystyle C_{L}$ $\displaystyle=\\{x\quad|\quad|x_{j}-\mu_{L,j}|\leq
k\sigma_{L,j}\ \forall j\in S\\}$ (3) $\displaystyle R_{S,L}$
$\displaystyle=\left(\bigcap_{j=1,p_{j}\in S}^{N}\\{X_{p_{j}}\geq
c_{j}\\}\right)\cap C_{L}$ (4) $\displaystyle\hat{Y}_{DAC}(S;L,T)$
$\displaystyle=\frac{1}{|R_{S,L}|}\sum_{i:X_{i}\in R_{S,L}}Y_{i}$ (5)

As $\hat{Y}_{DAC}(S;L,T)$ is computed using only splits involving variables
contained in $S$, we interpret it as the importance of those variables for
making the prediction at this particular leaf.

###  3.2 Aggregating leaf attributions to trees and forests

Given the estimates $\hat{Y}_{DAC}(S;L,T)$ for the contribution of a set of
variables $S$ to the prediction made at an individual leaf $L$ on tree $T$, we
now describe how to aggregate those contributions in order to produce an
importance curve for a decision tree. When computing the DAC contribution for
a particular point $x\in\mathbb{R}^{|S|}$, we take an average over the DAC
contributions of leaves $L$ which are “nearby” to $x$. To define proximity, we
use the same regions $C_{L}$ as with leaves. Given these regions, we formally
define the $DAC$ importance for a given tree at $x$ to be the weighted average
of regions $C_{L}$ containing $x$. We weight the average by the size of the
regions $|C_{L}|$ in order to account for the size of the leaves in our
calculation, and avoid giving undue influence to smaller leaves.

$\displaystyle f_{DAC}(x;S,T)$ $\displaystyle=\frac{1}{\sum_{L\text{ in
tree},x\in C_{L}}|C_{L}|}\underset{L\text{ in tree},x\in
C_{L}}{\sum}|C_{L}|\cdot\hat{Y}_{DAC}(S;L,T)$ (6)

Finally, given an ensemble of trees $T_{1},...,T_{M}$, with corresponding
weights $w_{1},...,w_{M}$, we simply define the attribution curve for the tree
ensemble to be the weighted average of the attributions for the individual
trees $f_{DAC}(x;S,T_{i})$. Note that this mirrors the prediction process for
the model, as the predictions for an ensemble of trees are computed by
averaging the predictions of it’s constituent trees. In particular, when the
ensemble is a random forest, $w_{i}=\frac{1}{M}$.

$\displaystyle f_{DAC}(x;S)=\sum_{i=1}^{M}w_{i}f_{DAC}(x;S,T_{i})$ (7)

###  3.3 An algorithm for computing DAC curves

Algorithm 1 presents pseudocode for computing the tree-level DAC curves
$f_{DAC}(x;S,T)$ introduced in Sec 3.1 and Sec 3.2. A simple analysis of the
algorithm shows that its time complexity is $O(n\cdot|S|)$, where $n$ is the
number of data points in the training set and $|S|$ is the cardinality of the
set of features of interest. For a forest, this complexity grows linearly with
the number of trees (although they can be very easily parallelized by
computing the curve for trees in parallel). In fact, both for-loops in
Algorithm 1 can be fully computed in parallel. Similarly, the space complexity
of this algorithm is $O(n\cdot|S|)$.

The above analysis assumes summation over $dac$ and $counts$ (the last lines
in the for-loop of Algorithm 1 happen in constant time. In practice, the size
of these arrays is determined by a pre-specified grid of $X$ values for which
the user would like to calculate DAC importances (used to find the size of
$dac$ and $counts$). With extremely large grids (beyond what is reasonable in
practice), the complexity of the algorithm would depend linearly on the sizes
of the arrays $dac$ and $counts$. The above analysis also assumes that the
total time complexity for finding the subset of points in each leaf which obey
the rules for that leaf across all leaves is $O(n)$.

Algorithm 1 DAC Importance curve generation for a tree

DAC(a tree $T,X,y$, set of features $S$, smoothing parameter $k$)

initialize importance array $dac$ with zero values

initialize counts array $counts$ with zero values

for each leaf $l$ in $T$ :

# Find the points in a leaf which use rules in $S$

Let $R$ be the set of rules encountered on the path from the root to $l$
concerning features in $S$

Let $X^{\prime}$ be the subset of points in $X$ such that for each point $x$,
$x$ complies with all rules in $R$

Let $y^{\prime}$ contain the corresponding $y$ values

# Ensure feature values in a leaf are not outliers

for each feature $i$ in $S$ :

Compute the mean and standard deviation of $X^{\prime}_{i}$, denoted
$\mu_{xi}$, $\sigma_{xi}$

Remove row $j$ in $X^{\prime}$ and $y^{\prime}$ if
$X^{\prime}_{j}\notin\mu_{xi}\pm k*\sigma_{xi}$

# Add the contribution of this leaf to the DAC curve

Define $\mu_{y}$ and $c_{y}$ to be the mean and cardinality of $y^{\prime}$
respectively

Define interval $int$ centered at $(\mu_{xi},...,\mu_{xj})$ and extending by
$\pm(\sigma_{xi},...,\sigma_{xj})$

$dac=dac+\mu_{y}\cdot c_{y}$ over interval $int$

$counts=counts+c_{y}$ to over interval $int$

return $c$ / $counts$ (normalize elementwise)

##  4 Results

We now validate, both quantitatively and qualitatively, our introduced DAC
importances. First, Sec 4.1 demonstrates that DAC curves can be used as
additional features in a linear model to help close the predictive gap between
linear models and random forests. Next, through simulation studies, Sec 4.2
quantifies that DAC curves provide a better approximation to conditional
expectation than other approaches. Finally, Sec 4.3 shows a case study on the
bike-sharing dataset, revealing insights into the data.

###  4.1 Automated feature engineering with DAC

We now show that single-feature DAC curves produced by Algorithm 1 can be used
as additional features to increase the accuracy of a logistic regression model
on real-world datasets. This increase in accuracy indicates that DAC curves
are capturing meaningful relationships in the data, which are predictive of
the outcome in question.

To compute these results, we use numerous classification datasets retrieved
from the Penn Machine Learning Benchmarks [24]. The datasets include a variety
of data types such as classifying liver disorders (the bupa dataset [25]) or
evaluating the condition of cars (the car dataset [26]). To find datasets
containing significant non-linear effects, we used only datasets where random
forests outperformed logistic regression by at least 5% (Fig S1 shows results
for datasets where random forests outperform logistic regression by any
positive margin).

We randomly partition each of the selected datasets into a training set (75%
of the data) and a testing set (25% of the data). We begin by training a
random forest model on the training set222all tree ensembles in this work are
trained using scikit-learn [27] and contain fifty trees.. Then, the fitted
model and the training data are used to identify the feature with the highest
Gini importance, and to compute the corresponding single-feature DAC curve.

We then use the computed DAC curve to define a new feature for use by a
logistic regression model. The curve is a univariate function which transforms
a single feature into its DAC importance. Therefore, for each data point $X$,
we append the value of the DAC curve at $X_{i}$, where $i$ is the important
feature. On the training set, we fit a logistic regression model using both
the original features and the new feature constructed above. Finally, we test
the fitted model on the testing set, where we we use the same DAC curve to
append the single-feature DAC feature on the testing set 333Importantly, the
DAC curve is constructed on the training set and never recieves any
information about the labels on the testing set..

Table 1 gives results for the accuracy on the testing set. In these instances,
adding a single DAC curve feature increased the prediction accuracy, with
increases ranging from 3.9% to 23%. The increased accuracy reduces the
predictive gap between logistic regression and random forests. In one instance
(the bupa dataset), logistic regression with a single DAC curve even
outperforms a random forest model (78.2% accuracy versus 75.9% accuracy for
the random forest). Classification results for more datasets are given in Fig
S1.

While we only append a single 1-dimensional curve here, this process of
feature-engineering can be used to append many DAC curves for different
features, and even multi-dimensional DAC curves to model interactions between
features.

Table 1: Accuracy results on various datasets. Logistic regression trained on data with one DAC curve as an extra feature outperforms logistic regression on the original features. |  monk3 |  irish |  monk1 |  hayes-roth |  bupa |  tokyo1 |  tic-tac-toe |  buggyCrx |  agaricus-lepiota |  car
---|---|---|---|---|---|---|---|---|---|---
RF Accuracy |  0.971 |  1.000 |  0.986 |  0.825 |  0.759 |  0.900 |  0.950 |  0.884 |  1.000 |  0.977
Logistic Accuracy |  0.734 |  0.776 |  0.583 |  0.400 |  0.690 |  0.792 |  0.650 |  0.740 |  0.946 |  0.650
Logistic Accuracy + DAC |  0.964 |  1.000 |  0.719 |  0.525 |  0.782 |  0.875 |  0.721 |  0.809 |  0.989 |  0.690
Difference |  0.230 |  0.224 |  0.137 |  0.125 |  0.092 |  0.083 |  0.071 |  0.069 |  0.042 |  0.039

###  4.2 Simulation results

We now use simulations to test how well DAC can recover interactions contained
in data. To do so, we generate synthetic data with complex interactions. The
functional form of these simulations is in Table 2, based on simulations used
in previous work [18].

Table 2: Simulation functions. $F_{1}({\mathbf{x}})$ | $\begin{aligned} &\pi^{x_{1}x_{2}}\sqrt{2x_{3}}-\sin^{-1}(0.5x_{4})+\log(|x_{3}+x_{5}|+1)\end{aligned}$
---|---
$F_{2}({\mathbf{x}})$ | $\begin{aligned} &\pi^{x_{1}x_{2}}\sqrt{2|x_{3}|}-\sin^{-1}(0.5x_{4})+\log(|x_{3}+x_{5}|+1)-x_{2}x5\end{aligned}$
$F_{3}({\mathbf{x}})$ | $\begin{aligned} &\exp|x_{1}-x_{3}|+|x_{2}x_{3}|-x_{3}^{2|x_{4}|}+\log(x_{4}^{2}+x_{5}^{2})\end{aligned}$
$F_{4}({\mathbf{x}})$ | $\begin{aligned} &\exp{|x_{1}-x_{3}|}+|x_{2}x_{3}|-x_{3}^{2|x_{4}|}+(x_{1}x_{4})^{2}+\log(x_{4}^{2}+x_{5}^{2})\end{aligned}$
$F_{5}({\mathbf{x}})$ | $\begin{aligned} &\frac{1}{1+x_{1}^{2}+x_{2}^{2}+x_{3}^{2}}+\sqrt{\exp(x_{4}+x_{5})}\end{aligned}$
$F_{6}({\mathbf{x}})$ | $\begin{aligned} &\exp{(|x_{2}x_{3}|+1)}-\exp(|x_{3}+x_{4}|+1)+\cos(x_{5})\end{aligned}$
$F_{7}({\mathbf{x}})$ | $\begin{aligned} &(\arctan(x_{1})+\arctan(x_{2}))^{2}+\max(x_{3}x_{4}+x_{6},0)-\frac{1}{1+(x_{4}x_{5})^{2}}+\sum_{i=1}^{5}{x_{i}}\end{aligned}$
$F_{8}({\mathbf{x}})$ | $\begin{aligned} &x_{1}x_{2}+2^{x_{3}+x_{5}}+2^{x_{3}+x_{4}+x_{5}}\end{aligned}$
$F_{9}({\mathbf{x}})$ | $\begin{aligned} &\arctan(x_{1}x_{2}+x_{3}x_{4})\sqrt{|x_{5}|}+\exp(x_{5}+x_{1})\end{aligned}$
$F_{10}({\mathbf{x}})$ | $\begin{aligned} &\sinh{(x_{1}+x_{2})}+\arccos\left(\arctan(x_{3}+x_{5})\right)+\cos(x_{4}+x_{5})\end{aligned}$

For each of the functions in Fig 2, we generate a training dataset of 70,000
points and a testing dataset of 15 million points. In all cases, data is
generated from a 5-dimensional multivariate Gaussian centered at zero, and
points lying outside the interval (-2, 2) are rejected. The data is drawn
using different covariance matrices: “IID” refers to the features being
independent, “Highly correlated” refers to the features being highly
correlated (covariance matrix has eigenvalues 2, 2, 1, 0, 0), and “Correlated”
is in between (for specifics, see Fig S3).

We then fit a tree ensemble regressor to the generated training data. From
these fitted models, we extract DAC/PDP curves using the training data444PDP
curves were calculated using the PDPbox library available at
https://github.com/SauceCat/PDPbox. Finally, as a proxy for learning the
groundtruth interactions, we measure the MSE between these curves and
conditional expectation curves calculated on the very large testing set.

Table 3 shows the matches between the DAC and PDP curves with the conditional
expectation curves. DAC (the left column) matches the conditional expectation
curves better than PDP (the right column) by a substantial margin for
different data distributions. This is true even when the features are
independent. Comparisons between rows are not meaningful, as they are
evaluated with different models and data distributions.

Table 3: Simulation results (averaged over the 5 variables in each of the ten functions in Table 2). Error is standard error of the mean. | DAC MSE | PDP MSE
---|---|---
RF IID | 0.776 $\pm$ 0.110 | 1.037 $\pm$ 0.147
RF correlated | 0.325 $\pm$ 0.052 | 0.477 $\pm$ 0.076
RF highly correlated | 0.553 $\pm$ 0.081 | 1.459 $\pm$ 0.213
Adaboost IID | 1.144 $\pm$ 0.162 | 13.688 $\pm$ 1.936
Adaboost correlated | 1.301 $\pm$ 0.184 | 21.300 $\pm$ 3.012
Adaboost highly correlated | 2.569 $\pm$ 0.115 | 12.895 $\pm$ 0.577

###  4.3 Qualitative results

We now use our methods in a case study to show how DAC can provide insights
into data. We study the Bike-sharing dataset, a popular dataset in
interpretability research [28], made open by the company Capital-Bikeshare
with additional features added in a later study [29]. The regression task in
the dataset is to predict the hourly count of rented bicycles using a number
of features such as the temperature, the time of day, and whether it is a
holiday. We fit a random forest to the data and then visualize single-feature
and multi-feature DAC curves to understand the interactions it has learned.

Fig 2 shows DAC curves for particular interactions within the data. The
heatmaps show 2-dimensional DAC curves (the mean number of rented bicycles in
this dataset is 188.7, corresponding to white on the heatmaps). The individual
curves on the sides of the heatmaps show 1-dimensional DAC curves for single-
feature importance.

Fig 2A shows a qualitatively interesting interaction between the features Hour
and Holiday. Within the single-variable context, the Hour feature shows two
peaks, corresponding to peak commute times during the day. The curve for
Holiday shows that people rent fewer bikes during the holidays (note that this
is a binary feature, but we can still evaluate the importance of it at non-
binary values based on the forest’s split points). Interestingly, during
holidays, the importance of the time of day decreases at peak commuter time,
and is now highest in the middle of the day. This makes intuitive sense, as
holidays specifically remove commuter traffic.

Fig 2B shows the interaction between Temp and Windspeed. The 1-dimensional
Temp curve has a very strong importance for the random forest’s predictions,
with higher temperatures resulting in higher model predictions. Windspeed has
a relatively smaller effect (note the scale difference for the 1-dimensional
curves), and a moderate wind results in the highest predictions. The
2-dimensional DAC curve is largely a superposition of these two curves,
suggesting little interaction, although at times there are traces of small
interactions between wind speed and temperature. Fig S2 shows more DAC curves
for strong interactions between features contained in this model.

Figure 2: DAC importances and interactions for a random forest fit to the
Bike-sharing dataset. Heatmaps show 2-dimensional DAC curves while side plots
show 1-dimensional DAC curves.

##  5 Conclusion

In this paper, we have introduced DAC interpretations for tree ensembles, such
as random forests and AdaBoost. For a given feature, or pair of features, DAC
produces an importance curve, or heat map, which displays the importance of
feature(s) as their value changes. This curve intuitively represents local
averages of the model’s predictions based only on the features(s) of interest.

Through an extensive validation, we show that DAC curves can be used as
features in a logistic regression model to increase its generalization
accuracy. Furthermore, in a simulation study, we show that DAC provides a
better approximation to the conditional expectation than competing methods.
Finally, through a case study on the bike sharing dataset, we show how DAC can
be used to extract insights from real data.

This work opens many potentially promising avenues for future work, such as
the use of DAC to automatically extract features (perhaps using higher-order
interactions), in order to close the gap between logistic regression and
random forests while preserving interpretability. Moreover, we think that
ideas used in DAC can be extended to a range of other complex models, such as
neural networks. Finally, DAC can be used to automatically explore and
identify higher-order interactions then the simple interactions analyzed here,
and give further insight into how a tree ensemble is making its predictions.

## Acknowledgements

This research was supported in part by grants ARO W911NF1710005, ONR
N00014-16-1-2664, NSF DMS-1613002, and NSF IIS 1741340, an NSERC PGS D
fellowship, and an Adobe research award. We thank the Center for Science of
Information (CSoI), a US NSF Science and Technology Center, under grant
agreement CCF-0939370.

## References

  * [1] Geert Litjens, Thijs Kooi, Babak Ehteshami Bejnordi, Arnaud Arindra Adiyoso Setio, Francesco Ciompi, Mohsen Ghafoorian, Jeroen AWM van der Laak, Bram van Ginneken, and Clara I Sánchez.  A survey on deep learning in medical image analysis.  Medical image analysis, 42:60–88, 2017.
  * [2] Tim Brennan and William L Oliver.  The emergence of machine learning techniques in criminology.  Criminology & Public Policy, 12(3):551–562, 2013.
  * [3] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel.  Fairness through awareness.  In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214–226. ACM, 2012.
  * [4] Bryce Goodman and Seth Flaxman.  European union regulations on algorithmic decision-making and a" right to explanation".  arXiv preprint arXiv:1606.08813, 2016.
  * [5] W James Murdoch, Chandan Singh, Karl Kumbier, Reza Abbasi-Asl, and Bin Yu.  Interpretable machine learning: definitions, methods, and applications.  arXiv preprint arXiv:1901.04592, 2019.
  * [6] Finale Doshi-Velez and Been Kim.  Towards a rigorous science of interpretable machine learning.  arXiv preprint arXiv:1702.08608, 2017.
  * [7] Leo Breiman.  Random forests.  Machine learning, 45(1):5–32, 2001.
  * [8] Yoav Freund, Robert E Schapire, et al.  Experiments with a new boosting algorithm.  In icml, volume 96, pages 148–156. Citeseer, 1996.
  * [9] Carolin Strobl, Anne-Laure Boulesteix, Thomas Kneib, Thomas Augustin, and Achim Zeileis.  Conditional variable importance for random forests.  BMC bioinformatics, 9(1):307, 2008.
  * [10] Scott M Lundberg, Gabriel G Erion, and Su-In Lee.  Consistent individualized feature attribution for tree ensembles.  arXiv preprint arXiv:1802.03888, 2018.
  * [11] Leo Breiman, Jerome Friedman, RA Olshen, and Charles J Stone.  Classification and regression trees.  Chapman and Hall/CRC, 1984.
  * [12] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.  Why should i trust you?: Explaining the predictions of any classifier.  In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1135–1144. ACM, 2016.
  * [13] Scott M Lundberg and Su-In Lee.  A unified approach to interpreting model predictions.  In Advances in Neural Information Processing Systems, pages 4768–4777, 2017.
  * [14] Sumanta Basu, Karl Kumbier, James B Brown, and Bin Yu.  iterative random forests to discover predictive and stable high-order interactions.  Proceedings of the National Academy of Sciences, page 201711236, 2018.
  * [15] Karl Kumbier, Sumanta Basu, James B Brown, Susan Celniker, and Bin Yu.  Refining interaction search through signed iterative random forests.  arXiv preprint arXiv:1810.07287, 2018.
  * [16] Chandan Singh, W James Murdoch, and Bin Yu.  Hierarchical interpretations for neural network predictions.  arXiv preprint arXiv:1806.05337, 2018.
  * [17] W James Murdoch, Peter J Liu, and Bin Yu.  Beyond word importance: Contextual decomposition to extract interactions from lstms.  arXiv preprint arXiv:1801.05453, 2018.
  * [18] Michael Tsang, Dehua Cheng, and Yan Liu.  Detecting statistical interactions from neural network weights.  arXiv preprint arXiv:1705.04977, 2017.
  * [19] Jerome H Friedman, Bogdan E Popescu, et al.  Predictive learning via rule ensembles.  The Annals of Applied Statistics, 2(3):916–954, 2008.
  * [20] Christoph Molnar, Giuseppe Casalicchio, and Bernd Bischl.  Quantifying interpretability of arbitrary machine learning models through functional decomposition.  arXiv preprint arXiv:1904.03867, 2019.
  * [21] Jerome H Friedman.  Greedy function approximation: a gradient boosting machine.  Annals of statistics, pages 1189–1232, 2001.
  * [22] Alex Goldstein, Adam Kapelner, Justin Bleich, and Emil Pitkin.  Peeking inside the black box: Visualizing statistical learning with plots of individual conditional expectation.  Journal of Computational and Graphical Statistics, 24(1):44–65, 2015.
  * [23] Daniel W Apley.  Visualizing the effects of predictor variables in black box supervised learning models.  arXiv preprint arXiv:1612.08468, 2016.
  * [24] Randal S Olson, William La Cava, Patryk Orzechowski, Ryan J Urbanowicz, and Jason H Moore.  Pmlb: a large benchmark suite for machine learning evaluation and comparison.  BioData mining, 10(1):36, 2017.
  * [25] James McDermott and Richard S Forsyth.  Diagnosing a disorder in a classification benchmark.  Pattern Recognition Letters, 73:41–43, 2016.
  * [26] Marko Bohanec and Vladislav Rajkovic.  Knowledge acquisition and explanation for multi-attribute decision making.  In 8th Intl Workshop on Expert Systems and their Applications, pages 59–78, 1988.
  * [27] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al.  Scikit-learn: Machine learning in python.  Journal of machine learning research, 12(Oct):2825–2830, 2011.
  * [28] Christoph Molnar.  Interpretable machine learning.  A Guide for Making Black Box Models Explainable, 2018.
  * [29] Hadi Fanaee-T and Joao Gama.  Event labeling combining ensemble detectors and background knowledge.  Progress in Artificial Intelligence, 2(2-3):113–127, 2014.

## Supplement

### Classification results extended

Figure S1: Logistic regression accuracy improves with and without DAC,
similiar to Table 1. Each point corresponds to classification accuracy for a
different dataset. These datasets are the datasets in PMLB [24] for which a
random forest outperforms logistic regression.

### Qualitative interactions extended

Fig S2A shows the interaction of the features temp with holiday. The peak
temperature to rent bikes is decidedly shifted during holidays, indicating
that people only bike during very fair weather on their holidays

Fig S2B shows the interaction between Month and Humidity. On its own, month is
a feature with a very simple effect that could be equally described by season:
people rent fewer bikes during the winter months. Adding humidity broadens the
peak month set, and adds more variation to the score on popular and unpopular
months. It is clear that people most prefer non-humid summer and fall days to
bike, but that biking on a humid hot day is only a slightly better than biking
on a humid cold day.

Figure S2: DAC importances and interactions in the Bike dataset.

### Simulation settings extended

Figure S3: Covariances for different simulation settings in Table 3. Logistic
regression accuracy improves with and without DAC, similiar to Table 1. Each
point corresponds to classification accuracy for a different dataset. These
datasets are the datasets in PMLB [24] for which a random forest outperforms
logistic regression by at least five percent.

### Finding conditional expectations in real datasets

It is difficult to validate that DAC curves are accurate as there is no
groundtruth for what importance should be. As a surrogate, we use the
conditional expectation curve calculated on an extremely large data sample.

Specifically, we analyze the regression datasets in PMLB (a disjoint set of
datasets as the classification datasets analyzed in Table 1). We fit the model
and DAC/PDP curves to 10% of the data. Then, we calculate the conditional
expectation curve of the predictions of the model on the other 90% of the
data. Table S1 shows the results for the mean squared error between the
conditional expectation curve and the DAC/PDP curves. The DAC curve incurs a
substantially smaller MSE, suggesting that even with limited data, it is able
to estimate the conditional expectations contained in the model.

Table S1: Mean squared error between importance curve (on a small data sample) and conditional expectation curve (on a large data sample). Averaged over multiple features on multiple datasets (9 total points). Error is standard error of the mean. DAC MSE | PDP MSE
---|---
11.843 $\pm$ 3.948 | 21.175 $\pm$ 7.058
Figure S4: MSE for DAC is generally lower than MSE for PDP. Each point
corresponds to MSE for a different dataset (1,521 points total). These
datasets are the regression datasets in PMLB [24] for which a random forest
outperforms logistic regression by at least five percent. Excluded a few
points for which the MSE is above $10^{6}$, as these points are poorly fit by
the random forest.