NVIDIA / NVIDIA/cudf

[FEA] rolling median()

Open
#6,276 8 comments 0 reactions 0 assignees View on GitHub
feature request libcudf Python
Dominant language
C++
Stars
9.8k
Forks
1.1k
Avg merge
3d 6m
Merged PRs (30d)
278

Description

Use case: Run a sliding window robust z-score as part of standard EEG preprocessing step. Point is to denoise a non-stationary signal. This is a general outlier detection procedure that could have value outside EEG.

(There was a previous request last year but seems to have stalled: https://github.com/rapidsai/cudf/issues/2135)

The robust z-score uses the **median** for the first (expectation) and second (variance, standard deviation) moments. This is instead of the average.

Current operation takes about 30 minutes for 10^7x20 element data frame in pandas. cuDF could bring this down to seconds.

**Describe the solution you'd like**
Like to have a median() agg added to rolling or UDF for apply.

For robust z the function is:

$$z_i = \kappa\frac{x_i-median(x)}{median(absolute\{(x_i-median(x))\})}$$
$$\text{where } \kappa\textrm{ := scaling factor}$$
$$x \subseteq X \text{, }X\text{ column vector in DF} $$

So, some possible solution to get the sliding robust z once we have the median working with apply are: 1) run the median twice (once of the original and then again on the median absolute values of the substracted residuals), and 2) right a custom UDF once the median function solution is known.

**Describe alternatives you've considered**
I have tried writing a UDF but the issue is the **sort()** needed for the median calculation. I tried a numba nopython pandas rolling.apply solution. This works if I copy the windowed array (x2 = x.copy()). It spits out an error when run with cuDF. I believe it's a memory and/or broadcasting issue (I've seen two kinds of errors). If I don't copy then the pandas numba code sorts the original array and propagates this corrupt data back to the original DF.

**Additional context**
Here is an example of the numba solution that works (this is for example to test on cuDF, of course pandas has a rolling median() agg).

>code

```
@nb.jit(nopython=True)
def udf_median(x):
##version 0
#mu = np.median(x)
##version 1
x2 = x.copy()
x2.sort()
n = len(x2)
k = int(n/2)
if n%2 == 0:
mu = (x2[k]+x2[k+1])/2
else:
mu = x2[k]
return mu

df = pd.DataFrame()
df['a'] = (-5,-3,-1,0.2,-2)
df['b'] = (5,-3,1,-0.2,-2)
print('original df')
print(df)
rolling = df.rolling(window=3,axis=0)
print("panda call\nwin=3 rolling median")
print(rolling.apply(udf_median, engine='numba', raw=True))
print('df after rolling call - if copy is not done, then corrupted original df')
print(df)

print("\ncuDF call")
df = cudf.DataFrame()
df['a'] = (-5,-3,-1,0.2,-2)
df['b'] = (5,-3,1,-0.2,-2)
rolling = df.rolling(window=3,axis=0)
print(rolling.apply(udf_median))

```

>output
original df
a b
0 -5.0 5.0
1 -3.0 -3.0
2 -1.0 1.0
3 0.2 -0.2
4 -2.0 -2.0
panda call
win=3 rolling median
a b
0 NaN NaN
1 NaN NaN
2 -3.0 1.0
3 -1.0 -0.2
4 -1.0 -0.2
df after rolling call - if copy is not done, then corrupted original df
(in this case the df is intact due to the copy function, comment that out to see the error)
a b
0 -5.0 5.0
1 -3.0 -3.0
2 -1.0 1.0
3 0.2 -0.2
4 -2.0 -2.0

cuDF call

RuntimeError Traceback (most recent call last)
/usr/local/lib/python3.6/site-packages/numba/core/errors.py in new_error_context(fmt_, *args, **kwargs)
744 try:
--> 745 yield
746 except NumbaError as e:

40 frames
RuntimeError: NRT required but not enabled

During handling of the above exception, another exception occurred:

LoweringError Traceback (most recent call last)
cudf/_lib/rolling.pyx in cudf._lib.rolling.rolling()

cudf/_lib/aggregation.pyx in cudf._lib.aggregation.make_aggregation()

cudf/_lib/aggregation.pyx in cudf._lib.aggregation._AggregationFactory.from_udf()

/usr/local/lib/python3.6/site-packages/numba/core/utils.py in reraise(tp, value, tb)
79 if value.__traceback__ is not tb:
80 raise value.with_traceback(tb)
---> 81 raise value
82
83

LoweringError: Failed in nopython mode pipeline (step: nopython mode backend)
NRT required but not enabled

File "", line 6:
def udf_median(x):

##version 1
x2 = x.copy()
^

During: lowering "$0.3 = call $0.2(func=$0.2, args=[], kws=(), vararg=None)" at (6)

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.