Linear model vs decision tree (in R)

I’ve used the R statistical language a bit, a long time ago. It was my first real encounter with data science, but future encounters used Matlab and Python. But lately I’ve been picking up R again, as it’s popular in the data science community.

As practise / demo, I thought I’d do a simple exploration of the strengths and weaknesses of linear models versus decision trees. This was inspired by Claudia Perlich at kdnuggets.

Let’s get started!

# the `predict_grid` function is attached
require(lattice)
require(rpart)

We’ll seed the random number generator so we get reproducible results:

N = 1000
set.seed(123456789)

Interactive data

Let’s try some data where the dependent variable depends strongly on the interaction between two inputs.

x = runif(N) * 2 - 1
y = runif(N) * 2 - 1
z = ifelse(x > y, 1, 0)

which looks like this

xyplot(x ~ y, group=z, grid=TRUE, asp=1)

Interactive data - linear fit

First let’s see how a linear fit performs:

linmod = glm(z ~ x + y, family=binomial(link='logit'))
glm.fit: algorithm did not convergeglm.fit: fitted probabilities numerically 0 or 1 occurred
summary(linmod)

Call:
glm(formula = z ~ x + y, family = binomial(link = "logit"))

Deviance Residuals: 
      Min         1Q     Median         3Q        Max  
-0.003177   0.000000   0.000000   0.000000   0.003253  

Coefficients:
            Estimate Std. Error z value Pr(>|z|)
(Intercept)     16.0      851.5   0.019    0.985
x             3660.7    55664.0   0.066    0.948
y            -3695.0    56387.9  -0.066    0.948

(Dispersion parameter for binomial family taken to be 1)

    Null deviance: 1.3861e+03  on 999  degrees of freedom
Residual deviance: 2.1237e-05  on 997  degrees of freedom
AIC: 6

Number of Fisher Scoring iterations: 25

Note that we get a warning because the results are too perfect: the linear model can separate these classes easily.

So what do the predictions look like graphically?

data = predict_grid(linmod, size=25);

which is perfect. A linear model can predict interactive data as long as it’s linear.

Interactive data - decision trees fit

Let’s see if decision trees can do the same.

dtmod = rpart(z ~ x + y,    method="class")
# summary(dtmod)  # more verbose results
dtmod
n= 1000 

node), split, n, loss, yval, (yprob)
      * denotes terminal node

 1) root 1000 493 0 (0.50700000 0.49300000)  
   2) x< 0.09964573 548 138 0 (0.74817518 0.25182482)  
     4) y>=-0.2762061 365  14 0 (0.96164384 0.03835616)  
       8) y>=-0.1460217 326   4 0 (0.98773006 0.01226994) *
       9) y< -0.1460217 39  10 0 (0.74358974 0.25641026)  
        18) x< -0.1961216 29   0 0 (1.00000000 0.00000000) *
        19) x>=-0.1961216 10   0 1 (0.00000000 1.00000000) *
     5) y< -0.2762061 183  59 1 (0.32240437 0.67759563)  
      10) x< -0.598692 65  15 0 (0.76923077 0.23076923)  
        20) y>=-0.7330697 49   2 0 (0.95918367 0.04081633) *
        21) y< -0.7330697 16   3 1 (0.18750000 0.81250000) *
      11) x>=-0.598692 118   9 1 (0.07627119 0.92372881) *
   3) x>=0.09964573 452  97 1 (0.21460177 0.78539823)  
     6) y>=0.399141 135  46 0 (0.65925926 0.34074074)  
      12) x< 0.6707242 80   5 0 (0.93750000 0.06250000) *
      13) x>=0.6707242 55  14 1 (0.25454545 0.74545455)  
        26) y>=0.8781129 10   0 0 (1.00000000 0.00000000) *
        27) y< 0.8781129 45   4 1 (0.08888889 0.91111111) *
     7) y< 0.399141 317   8 1 (0.02523659 0.97476341) *

There’s a lot of text, but what does it look like?

predict_grid(dtmod, size=25);
[1] 0

So the decision tree cannot really explain the interaction. The boundary is parallel to the x or y axis at any time, it does not take interaction into account. At most it can approximate this boundary with a really deep tree.

Non-linear data

First to make the data and show it:

x = runif(N) * 2 - 1
y = runif(N) * 2 - 1
z = ifelse(abs(x) < sqrt(2) / 2 & abs(y) < sqrt(2) / 2, 1, 0)
xyplot(x ~ y, group=z, grid=TRUE, asp=1)

Non-linear data - linear fit

We make a linear fit first. We know how to do that now, so let’s skip to the results:

[1] 0

As the terms “non-linear data” and “linear fit” suggest, they don’t mix very well. There’s just a slight gradient due to randomness, but nothing approximating a solution.

This is the case because the data isn’t separable by a straight line, not even approximately. Linear models have straight decision boundaries, so it can’t find a solution.

Non-linear data - decision trees fit

Let’s see how a decision tree does.

which is exactly right. Decision trees are good when there are no interactions, and boundaries are parallel to the coordinate axes.

XOR data

Let’s try another one: learn the binary XOR operation. Let’s do this quickly:

x = as.integer(rnorm(N) > 0)
y = as.integer(rnorm(N) > 0)
x[1:10]
 [1] 0 0 0 1 1 0 1 1 0 1
y[1:10]
 [1] 1 1 0 0 1 1 0 1 1 0
z = 1 - (x == y)
z[1:10]
 [1] 1 1 0 1 0 1 1 0 1 1

which looks like:

The linear and decision tree results look like:

So although this problem has interactions, due to the limited possiblities, they can also be represented as simple horizontal and vertical boundaries, and the decision tree performs well.

Since there are so few possiblities, the notion of linearity is not very interesting (xor is not linear in reals but is in some rings). Since the number of cutoffs needed is very limited, the decision tree performs well.

However, the linear model cannot solve this problem. This could have been expected, since the decision boundary is a straight line, and there is no straight line that solves this problem (in the original coordinates, at least).

Interactive, non-linear data

Say we want to feel superior to computers. Let’s make some data that’s simple for us but hard for the computer, by making it non-linear and interactive.

x = runif(N) * 2 - 1
y = runif(N) * 2 - 1
z = ifelse(abs(x - y) > 2 - sqrt(2), 1, 0)
xyplot(x ~ y, group=z, grid=TRUE, asp=1)

Haha, look at the sillycomputers messing it up!

Extra parameter - linear fit

But let’s say we help the models just a little bit. We’ll add a simple third parameter:

w = abs(x - y)

Here’s the result for the linear fit:

glm.fit: algorithm did not convergeglm.fit: fitted probabilities numerically 0 or 1 occurred

Suddenly it got the perfect result!

This happened becausein the new w variable, there is no interaction. The region in the left top and the region in the right bottom now overlap, making the problem linearly separable.

Extra parameter - decision tree

For the decision tree, we will use the same parameter w. Here is the result:

The decision tree, too, got it perfect! But the reason is different. The new parameter helped the decision tree because the w axis is perpendicular to the decision boundary. In w space, the cutoff is a simple point, not a curve as in x,y space.

Note that w = y - x, without the absolute value, would have also worked for the decision tree. It’d just be two cutoff points, but the boundary remains perpendicular. But it wouldn’t have helped the linear model at all, since there’d not be any linear decision boundary that solves the problem.

Here is a plot of x - y to illustrate the result:

v = x - y
w = abs(x - y)
xyplot(z ~ v)

A simple one-dimensional problem!

Previous models

Can you think of some new coordinates that solve the earlier difficulties the decision tree had for the “diagonal data”, and the linear model for the “square box data”?

Did you do it?

Here is one solution:

  • Diagonal data: adding a parameter w = x - y makes the separation line perpendicular to w. The problem is then very easy to solve for the decision tree (it was already easy for the linear model).
  • Square box data: adding a parameter w which is the higher one of abs(x) and abs(y), makes the problem easily solvable with a decision boundary at w = sqrt(2) / 2.

Today’s lessons

  • Linear models are bad at interactions (that can’t be separated by a straight line).
  • Decision trees are bad at ‘curved’ decision boundaries (that aren’t parallel to a coordinate).
  • Both can be improved a lot by smart choice of extra features. The choices should be focussed on overcomming their weakness, and are generally different for each model.

Impressions about R

I’m a novice at R, so don’t pay too much attention to this, I’ll probably change my mind.

  • It’s harder to find things on Google for me. I regularly get results for other languages when searching for R stuff. Maybe Google needs some time to figure our I’m doing R now.
  • Rstudio is quite nice. Similar to Matlab. It’s intuitive, although problem highlighting could be better/faster. It’s no match for PyCharm, but I really love PyCharm, so that’s not a very meaningful comparison.
  • I like R notebooks more than Jupyter ones, it feels like you’re working in one file instead of a hundred tiny ones pasted together, and it’s more smooth in general.
  • I’m finding the style of R less predictable than Python’s. Maybe I’m just not used to it yet. But it’s a bit confusing when things are ‘values’ and when they are ‘symbols’ whose name should match next time. And what dots mean in which case. Or why things about objects aren’t just properties of the object (especially dim(arr) <- value seems really weird). Or why array slices aren’t as simple as in Python (or even Matlab) - why would a function like head need to exist? Altogether it feels like a collection of tools, rather than a language (not necessarily bad for it’s purpose).
  • Functions with ~ seem cool, I’ll have to study that more.
LS0tCnRpdGxlOiAiTGluZWFyIG1vZGVscyB2cyBkZWNpc2lvbiB0cmVlcyIKb3V0cHV0OgogIGh0bWxfZG9jdW1lbnQ6CiAgICBmaWdfaGVpZ2h0OiA0CiAgICBmaWdfd2lkdGg6IDQKICBodG1sX25vdGVib29rOgogICAgZmlnX2hlaWdodDogNAogICAgZmlnX3dpZHRoOiA0Ci0tLQoKSSd2ZSB1c2VkIHRoZSBSIHN0YXRpc3RpY2FsIGxhbmd1YWdlIGEgYml0LCBhIGxvbmcgdGltZSBhZ28uIEl0IHdhcyBteSBmaXJzdCByZWFsIGVuY291bnRlciB3aXRoIGRhdGEgc2NpZW5jZSwgYnV0IGZ1dHVyZSBlbmNvdW50ZXJzIHVzZWQgTWF0bGFiIGFuZCBQeXRob24uIEJ1dCBsYXRlbHkgSSd2ZSBiZWVuIHBpY2tpbmcgdXAgUiBhZ2FpbiwgYXMgaXQncyBwb3B1bGFyIGluIHRoZSBkYXRhIHNjaWVuY2UgY29tbXVuaXR5LgoKQXMgcHJhY3Rpc2UgLyBkZW1vLCBJIHRob3VnaHQgSSdkIGRvIGEgc2ltcGxlIGV4cGxvcmF0aW9uIG9mIHRoZSBzdHJlbmd0aHMgYW5kIHdlYWtuZXNzZXMgb2YgbGluZWFyIG1vZGVscyB2ZXJzdXMgZGVjaXNpb24gdHJlZXMuIFRoaXMgd2FzIGluc3BpcmVkIGJ5IFtDbGF1ZGlhIFBlcmxpY2ggYXQga2RudWdnZXRzXShodHRwOi8vd3d3LmtkbnVnZ2V0cy5jb20vMjAxNi8xMi9pbnRlcnZpZXdzLWRhdGEtc2NpZW50aXN0cy1jbGF1ZGlhLXBlcmxpY2guaHRtbCkuCgpMZXQncyBnZXQgc3RhcnRlZCEKCmBgYHtyLCBlY2hvPUZBTFNFLCBxdWlldD1UUlVFfQpybShsaXN0PWxzKCkpCnNvdXJjZSgndmlzX3ByZWQuUicpCmBgYApgYGB7ciwgcXVpZXQ9VFJVRX0KIyB0aGUgYHByZWRpY3RfZ3JpZGAgZnVuY3Rpb24gaXMgYXR0YWNoZWQKcmVxdWlyZShsYXR0aWNlKQpyZXF1aXJlKHJwYXJ0KQpgYGAKCldlJ2xsIHNlZWQgdGhlIHJhbmRvbSBudW1iZXIgZ2VuZXJhdG9yIHNvIHdlIGdldCByZXByb2R1Y2libGUgcmVzdWx0czoKCmBgYHtyfQpOID0gMTAwMApzZXQuc2VlZCgxMjM0NTY3ODkpCmBgYAoKR3JlYXQsIGxldCdzIGdldCBzdGFydGVkIQoKSW50ZXJhY3RpdmUgZGF0YQo9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09CgpMZXQncyB0cnkgc29tZSBkYXRhIHdoZXJlIHRoZSBkZXBlbmRlbnQgdmFyaWFibGUgZGVwZW5kcyBzdHJvbmdseSBvbiB0aGUgaW50ZXJhY3Rpb24gYmV0d2VlbiB0d28gaW5wdXRzLgoKYGBge3J9CnggPSBydW5pZihOKSAqIDIgLSAxCnkgPSBydW5pZihOKSAqIDIgLSAxCnogPSBpZmVsc2UoeCA+IHksIDEsIDApCmBgYAoKd2hpY2ggbG9va3MgbGlrZSB0aGlzCgpgYGB7cn0KeHlwbG90KHggfiB5LCBncm91cD16LCBncmlkPVRSVUUsIGFzcD0xKQpgYGAKCkludGVyYWN0aXZlIGRhdGEgLSBsaW5lYXIgZml0Ci0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KCkZpcnN0IGxldCdzIHNlZSBob3cgYSBsaW5lYXIgZml0IHBlcmZvcm1zOgoKYGBge3J9Cmxpbm1vZCA9IGdsbSh6IH4geCArIHksIGZhbWlseT1iaW5vbWlhbChsaW5rPSdsb2dpdCcpKQpzdW1tYXJ5KGxpbm1vZCkKYGBgCgpOb3RlIHRoYXQgd2UgZ2V0IGEgd2FybmluZyBiZWNhdXNlIHRoZSByZXN1bHRzIGFyZSAqdG9vKiBwZXJmZWN0OiB0aGUgbGluZWFyIG1vZGVsIGNhbiBzZXBhcmF0ZSB0aGVzZSBjbGFzc2VzIGVhc2lseS4KClNvIHdoYXQgZG8gdGhlIHByZWRpY3Rpb25zIGxvb2sgbGlrZSBncmFwaGljYWxseT8KCmBgYHtyfQpkYXRhID0gcHJlZGljdF9ncmlkKGxpbm1vZCwgc2l6ZT0yNSk7CmBgYAoKd2hpY2ggaXMgcGVyZmVjdC4gQSBsaW5lYXIgbW9kZWwgY2FuIHByZWRpY3QgaW50ZXJhY3RpdmUgZGF0YSBhcyBsb25nIGFzIGl0J3MgbGluZWFyLgoKSW50ZXJhY3RpdmUgZGF0YSAtIGRlY2lzaW9uIHRyZWVzIGZpdAotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCgpMZXQncyBzZWUgaWYgZGVjaXNpb24gdHJlZXMgY2FuIGRvIHRoZSBzYW1lLgoKYGBge3J9CmR0bW9kID0gcnBhcnQoeiB+IHggKyB5LCAJbWV0aG9kPSJjbGFzcyIpCiMgc3VtbWFyeShkdG1vZCkgICMgbW9yZSB2ZXJib3NlIHJlc3VsdHMKZHRtb2QKYGBgCgpUaGVyZSdzIGEgbG90IG9mIHRleHQsIGJ1dCB3aGF0IGRvZXMgaXQgbG9vayBsaWtlPwoKYGBge3J9CnByZWRpY3RfZ3JpZChkdG1vZCwgc2l6ZT0yNSk7CmBgYAoKU28gdGhlIGRlY2lzaW9uIHRyZWUgY2Fubm90IHJlYWxseSBleHBsYWluIHRoZSBpbnRlcmFjdGlvbi4gVGhlIGJvdW5kYXJ5IGlzIHBhcmFsbGVsIHRvIHRoZSB4IG9yIHkgYXhpcyBhdCBhbnkgdGltZSwgaXQgZG9lcyBub3QgdGFrZSBpbnRlcmFjdGlvbiBpbnRvIGFjY291bnQuIEF0IG1vc3QgaXQgY2FuIGFwcHJveGltYXRlIHRoaXMgYm91bmRhcnkgd2l0aCBhIHJlYWxseSBkZWVwIHRyZWUuCgpgYGB7ciwgZWNobz1GQUxTRSwgcXVpZXQ9VFJVRX0KdyA9IHggLSB5CiNkdG1vZCA9IHJwYXJ0KHogfiB3ICsgeCArIHksIAltZXRob2Q9ImNsYXNzIikKI3ByZWRpY3RfZ3JpZChkdG1vZCwgc2l6ZT01MCwgdHJ1ZV9jbHNfZnVuYz1mdW5jdGlvbiAoeCwgeSkgeyByZXR1cm4oaWZlbHNlKHggPiB5LCAxLCAwKSkgfSwgZXh0cmFfcGFyYW1fZnVuYz1mdW5jdGlvbih4LCB5KSB7IHJldHVybih4IC0geSkgfSk7CmBgYAoKTm9uLWxpbmVhciBkYXRhCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KCkZpcnN0IHRvIG1ha2UgdGhlIGRhdGEgYW5kIHNob3cgaXQ6CgpgYGB7cn0KeCA9IHJ1bmlmKE4pICogMiAtIDEKeSA9IHJ1bmlmKE4pICogMiAtIDEKeiA9IGlmZWxzZShhYnMoeCkgPCBzcXJ0KDIpIC8gMiAmIGFicyh5KSA8IHNxcnQoMikgLyAyLCAxLCAwKQp4eXBsb3QoeCB+IHksIGdyb3VwPXosIGdyaWQ9VFJVRSwgYXNwPTEpCmBgYAoKTm9uLWxpbmVhciBkYXRhIC0gbGluZWFyIGZpdAotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCgpXZSBtYWtlIGEgbGluZWFyIGZpdCBmaXJzdC4gV2Uga25vdyBob3cgdG8gZG8gdGhhdCBub3csIHNvIGxldCdzIHNraXAgdG8gdGhlIHJlc3VsdHM6CgpgYGB7ciwgZWNobz1GQUxTRSwgcXVpZXQ9VFJVRX0KbGlubW9kID0gZ2xtKHogfiB4ICsgeSwgZmFtaWx5PWJpbm9taWFsKGxpbms9J2xvZ2l0JykpCnByZWRpY3RfZ3JpZChsaW5tb2QsIHNpemU9MjUpOwpgYGAKCkFzIHRoZSB0ZXJtcyAibm9uLWxpbmVhciBkYXRhIiBhbmQgImxpbmVhciBmaXQiIHN1Z2dlc3QsIHRoZXkgZG9uJ3QgbWl4IHZlcnkgd2VsbC4gVGhlcmUncyBqdXN0IGEgc2xpZ2h0IGdyYWRpZW50IGR1ZSB0byByYW5kb21uZXNzLCBidXQgbm90aGluZyBhcHByb3hpbWF0aW5nIGEgc29sdXRpb24uCgpUaGlzIGlzIHRoZSBjYXNlIGJlY2F1c2UgdGhlIGRhdGEgaXNuJ3Qgc2VwYXJhYmxlIGJ5IGEgc3RyYWlnaHQgbGluZSwgbm90IGV2ZW4gYXBwcm94aW1hdGVseS4gTGluZWFyIG1vZGVscyBoYXZlIHN0cmFpZ2h0IGRlY2lzaW9uIGJvdW5kYXJpZXMsIHNvIGl0IGNhbid0IGZpbmQgYSBzb2x1dGlvbi4KCmBgYHtyLCBlY2hvPUZBTFNFLCBxdWlldD1UUlVFfQpnZXRfdyA9IGZ1bmN0aW9uKHgsIHkpCnsKICBOID0gbGVuZ3RoKHgpCiAgdiA9IG1hdHJpeCgwLCBsZW5ndGgoeCkpCiAgZm9yIChpIGluIDE6bGVuZ3RoKHgpKSB7CiAgICB2W2ldID0gaWZlbHNlKGFicyh4W2ldKSA+IGFicyh5W2ldKSwgYWJzKHhbaV0pLCBhYnMoeVtpXSkpCiAgfQogIHJldHVybih2KQp9CncgPSBnZXRfdyh4LCB5KQp4eXBsb3QoeiB+IHcpCiNsaW5tb2QgPSBnbG0oeiB+IHcgKyB4ICsgeSwgZmFtaWx5PWJpbm9taWFsKGxpbms9J2xvZ2l0JykpCiNwcmVkaWN0X2dyaWQobGlubW9kLCBzaXplPTUwLCB0cnVlX2Nsc19mdW5jPWZ1bmN0aW9uICh4LCB5KSB7IHJldHVybihpZmVsc2UoYWJzKHgpIDwgc3FydCgyKSAvIDIgJiBhYnMoeSkgPCBzcXJ0KDIpIC8gMiwgMSwgMCkpIH0sIGV4dHJhX3BhcmFtX2Z1bmM9Z2V0X3cpOwpgYGAKCk5vbi1saW5lYXIgZGF0YSAtIGRlY2lzaW9uIHRyZWVzIGZpdAotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCgpMZXQncyBzZWUgaG93IGEgZGVjaXNpb24gdHJlZSBkb2VzLgoKYGBge3IsIGVjaG89RkFMU0V9CmR0bW9kID0gcnBhcnQoeiB+IHggKyB5LCAJbWV0aG9kPSJjbGFzcyIpCnByZWQgPSBwcmVkaWN0X2dyaWQoZHRtb2QsIHNpemU9MjUsIHRydWVfY2xzX2Z1bmM9ZnVuY3Rpb24oeCwgeSkgeyBpZmVsc2UoYWJzKHgpIDwgc3FydCgyKSAvIDIgJiBhYnMoeSkgPCBzcXJ0KDIpIC8gMiwgMSwgMCkgfSk7CmBgYAoKd2hpY2ggaXMgZXhhY3RseSByaWdodC4gRGVjaXNpb24gdHJlZXMgYXJlIGdvb2Qgd2hlbiB0aGVyZSBhcmUgbm8gaW50ZXJhY3Rpb25zLCBhbmQgYm91bmRhcmllcyBhcmUgcGFyYWxsZWwgdG8gdGhlIGNvb3JkaW5hdGUgYXhlcy4KClhPUiBkYXRhCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KCkxldCdzIHRyeSBhbm90aGVyIG9uZTogbGVhcm4gdGhlIGJpbmFyeSBYT1Igb3BlcmF0aW9uLiBMZXQncyBkbyB0aGlzIHF1aWNrbHk6CgpgYGB7cn0KeCA9IGFzLmludGVnZXIocm5vcm0oTikgPiAwKQp5ID0gYXMuaW50ZWdlcihybm9ybShOKSA+IDApCnhbMToxMF0KeVsxOjEwXQp6ID0gMSAtICh4ID09IHkpCnpbMToxMF0KYGBgCgp3aGljaCBsb29rcyBsaWtlOgoKYGBge3IsIGVjaG89RkFMU0V9CiMgeHlwbG90KHggfiB5LCBjb2w9aWZlbHNlKHosICdyZWQnLCAnYmx1ZScpLCBncmlkPVRSVUUpICAjIGV4cGxpY2l0bHkgc2V0IHRoZSBjb2xvcgp4eXBsb3QoeCB+IHksIGdyb3VwPXosIGdyaWQ9VFJVRSwgYXNwPTEpCiMgdXNlIHRoaXMgdG8gc2F2ZToKIyBkZXYuY29weShwbmcsIGZpbGVuYW1lPSJ4b3IucG5nIik7CiMgZGV2Lm9mZigpOwpgYGAKClRoZSBsaW5lYXIgYW5kIGRlY2lzaW9uIHRyZWUgcmVzdWx0cyBsb29rIGxpa2U6CgpgYGB7ciwgZWNobz1GQUxTRX0KbGlubW9kID0gZ2xtKHogfiB4ICsgeSwgZmFtaWx5PWJpbm9taWFsKGxpbms9J2xvZ2l0JykpCmRhdGEgPSBwcmVkaWN0X2dyaWQobGlubW9kLCBkaW1zPWMoMCwgMSwgMCwgMSksIHNpemU9MjUpOwpgYGAKCmBgYHtyLCBlY2hvPUZBTFNFfQpkdG1vZCA9IHJwYXJ0KHogfiB4ICsgeSwgCW1ldGhvZD0iY2xhc3MiKQpkYXRhID0gcHJlZGljdF9ncmlkKGR0bW9kLCBkaW1zPWMoMCwgMSwgMCwgMSksIHNpemU9MjUpOwpgYGAKClNvIGFsdGhvdWdoIHRoaXMgcHJvYmxlbSBoYXMgaW50ZXJhY3Rpb25zLCBkdWUgdG8gdGhlIGxpbWl0ZWQgcG9zc2libGl0aWVzLCB0aGV5IGNhbiBhbHNvIGJlIHJlcHJlc2VudGVkIGFzIHNpbXBsZSBob3Jpem9udGFsIGFuZCB2ZXJ0aWNhbCBib3VuZGFyaWVzLCBhbmQgdGhlIGRlY2lzaW9uIHRyZWUgcGVyZm9ybXMgd2VsbC4gCgpTaW5jZSB0aGVyZSBhcmUgc28gZmV3IHBvc3NpYmxpdGllcywgdGhlIG5vdGlvbiBvZiBsaW5lYXJpdHkgaXMgbm90IHZlcnkgaW50ZXJlc3RpbmcgKHhvciBpcyBub3QgbGluZWFyIGluIHJlYWxzIGJ1dCBpcyBpbiBzb21lIHJpbmdzKS4gU2luY2UgdGhlIG51bWJlciBvZiBjdXRvZmZzIG5lZWRlZCBpcyB2ZXJ5IGxpbWl0ZWQsIHRoZSBkZWNpc2lvbiB0cmVlIHBlcmZvcm1zIHdlbGwuCgpIb3dldmVyLCB0aGUgbGluZWFyIG1vZGVsIGNhbm5vdCBzb2x2ZSB0aGlzIHByb2JsZW0uIFRoaXMgY291bGQgaGF2ZSBiZWVuIGV4cGVjdGVkLCBzaW5jZSB0aGUgZGVjaXNpb24gYm91bmRhcnkgaXMgYSBzdHJhaWdodCBsaW5lLCBhbmQgdGhlcmUgaXMgbm8gc3RyYWlnaHQgbGluZSB0aGF0IHNvbHZlcyB0aGlzIHByb2JsZW0gKGluIHRoZSBvcmlnaW5hbCBjb29yZGluYXRlcywgYXQgbGVhc3QpLgoKSW50ZXJhY3RpdmUsIG5vbi1saW5lYXIgZGF0YQo9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09CgpTYXkgd2Ugd2FudCB0byBmZWVsIHN1cGVyaW9yIHRvIGNvbXB1dGVycy4gTGV0J3MgbWFrZSBzb21lIGRhdGEgdGhhdCdzIHNpbXBsZSBmb3IgdXMgYnV0IGhhcmQgZm9yIHRoZSBjb21wdXRlciwgYnkgbWFraW5nIGl0IG5vbi1saW5lYXIgYW5kIGludGVyYWN0aXZlLgoKYGBge3J9CnggPSBydW5pZihOKSAqIDIgLSAxCnkgPSBydW5pZihOKSAqIDIgLSAxCnogPSBpZmVsc2UoYWJzKHggLSB5KSA+IDIgLSBzcXJ0KDIpLCAxLCAwKQp4eXBsb3QoeCB+IHksIGdyb3VwPXosIGdyaWQ9VFJVRSwgYXNwPTEpCmBgYAoKYGBge3IsIGVjaG89RkFMU0V9Cmxpbm1vZCA9IGdsbSh6IH4geCArIHksIGZhbWlseT1iaW5vbWlhbChsaW5rPSdsb2dpdCcpKQpkYXRhID0gcHJlZGljdF9ncmlkKGxpbm1vZCwgc2l6ZT0yNSk7CmBgYAoKYGBge3IsIGVjaG89RkFMU0V9CmR0bW9kID0gcnBhcnQoeiB+IHggKyB5LCAJbWV0aG9kPSJjbGFzcyIpCmRhdGEgPSBwcmVkaWN0X2dyaWQoZHRtb2QsIHNpemU9MjUpOwpgYGAKCkhhaGEsIGxvb2sgYXQgdGhlIHNpbGx5Y29tcHV0ZXJzIG1lc3NpbmcgaXQgdXAhCgpFeHRyYSBwYXJhbWV0ZXIgLSBsaW5lYXIgZml0Ci0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KCkJ1dCBsZXQncyBzYXkgd2UgaGVscCB0aGUgbW9kZWxzIGp1c3QgYSBsaXR0bGUgYml0LiBXZSdsbCBhZGQgYSBzaW1wbGUgdGhpcmQgcGFyYW1ldGVyOgoKYGBge3J9CncgPSBhYnMoeCAtIHkpCmBgYAoKSGVyZSdzIHRoZSByZXN1bHQgZm9yIHRoZSBsaW5lYXIgZml0OgoKYGBge3IsIGVjaG89RkFMU0V9Cmxpbm1vZCA9IGdsbSh6IH4gdyArIHggKyB5LCBmYW1pbHk9Ymlub21pYWwobGluaz0nbG9naXQnKSkKZGF0YSA9IHByZWRpY3RfZ3JpZChsaW5tb2QsIHNpemU9MjUsIHRydWVfY2xzX2Z1bmM9ZnVuY3Rpb24gKHgsIHkpIHsgcmV0dXJuKGlmZWxzZShhYnMoeCAtIHkpID4gMiAtIHNxcnQoMiksIDEsIDApKSB9LCBleHRyYV9wYXJhbV9mdW5jPWZ1bmN0aW9uKHgsIHkpIHsgcmV0dXJuKGFicyh4IC0geSkpIH0pOwpgYGAKClN1ZGRlbmx5IGl0IGdvdCB0aGUgcGVyZmVjdCByZXN1bHQhCgpUaGlzIGhhcHBlbmVkIGJlY2F1c2VpbiB0aGUgbmV3IGBgd2BgIHZhcmlhYmxlLCB0aGVyZSBpcyBubyBpbnRlcmFjdGlvbi4gVGhlIHJlZ2lvbiBpbiB0aGUgbGVmdCB0b3AgYW5kIHRoZSByZWdpb24gaW4gdGhlIHJpZ2h0IGJvdHRvbSBub3cgb3ZlcmxhcCwgbWFraW5nIHRoZSBwcm9ibGVtIGxpbmVhcmx5IHNlcGFyYWJsZS4KCkV4dHJhIHBhcmFtZXRlciAtIGRlY2lzaW9uIHRyZWUKLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQoKRm9yIHRoZSBkZWNpc2lvbiB0cmVlLCB3ZSB3aWxsIHVzZSB0aGUgc2FtZSBwYXJhbWV0ZXIgYGB3YGAuIEhlcmUgaXMgdGhlIHJlc3VsdDoKCmBgYHtyLCBlY2hvPUZBTFNFfQpkdG1vZCA9IHJwYXJ0KHogfiB3ICsgeCArIHksIAltZXRob2Q9ImNsYXNzIikKZGF0YSA9IHByZWRpY3RfZ3JpZChkdG1vZCwgc2l6ZT01MCwgdHJ1ZV9jbHNfZnVuYz1mdW5jdGlvbiAoeCwgeSkgeyByZXR1cm4oaWZlbHNlKGFicyh4IC0geSkgPiAyIC0gc3FydCgyKSwgMSwgMCkpIH0sIGV4dHJhX3BhcmFtX2Z1bmM9ZnVuY3Rpb24oeCwgeSkgeyByZXR1cm4oYWJzKHggLSB5KSkgfSkKYGBgCgpUaGUgZGVjaXNpb24gdHJlZSwgdG9vLCBnb3QgaXQgcGVyZmVjdCEgQnV0IHRoZSByZWFzb24gaXMgZGlmZmVyZW50LiBUaGUgbmV3IHBhcmFtZXRlciBoZWxwZWQgdGhlIGRlY2lzaW9uIHRyZWUgYmVjYXVzZSB0aGUgYGB3YGAgYXhpcyBpcyBwZXJwZW5kaWN1bGFyIHRvIHRoZSBkZWNpc2lvbiBib3VuZGFyeS4gSW4gYGB3YGAgc3BhY2UsIHRoZSBjdXRvZmYgaXMgYSBzaW1wbGUgcG9pbnQsIG5vdCBhIGN1cnZlIGFzIGluIGBgeCx5YGAgc3BhY2UuCgpOb3RlIHRoYXQgYGB3ID0geSAtIHhgYCwgd2l0aG91dCB0aGUgYWJzb2x1dGUgdmFsdWUsIHdvdWxkIGhhdmUgYWxzbyB3b3JrZWQgZm9yIHRoZSBkZWNpc2lvbiB0cmVlLiBJdCdkIGp1c3QgYmUgdHdvIGN1dG9mZiBwb2ludHMsIGJ1dCB0aGUgYm91bmRhcnkgcmVtYWlucyBwZXJwZW5kaWN1bGFyLiBCdXQgaXQgd291bGRuJ3QgaGF2ZSBoZWxwZWQgdGhlIGxpbmVhciBtb2RlbCBhdCBhbGwsIHNpbmNlIHRoZXJlJ2Qgbm90IGJlIGFueSBsaW5lYXIgZGVjaXNpb24gYm91bmRhcnkgdGhhdCBzb2x2ZXMgdGhlIHByb2JsZW0uCgpIZXJlIGlzIGEgcGxvdCBvZiBgYHggLSB5YGAgdG8gaWxsdXN0cmF0ZSB0aGUgcmVzdWx0OgoKYGBge3J9CnYgPSB4IC0geQp3ID0gYWJzKHggLSB5KQp4eXBsb3QoeiB+IHYpCmBgYAoKQSBzaW1wbGUgb25lLWRpbWVuc2lvbmFsIHByb2JsZW0hCgpQcmV2aW91cyBtb2RlbHMKLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQoKQ2FuIHlvdSB0aGluayBvZiBzb21lIG5ldyBjb29yZGluYXRlcyB0aGF0IHNvbHZlIHRoZSBlYXJsaWVyIGRpZmZpY3VsdGllcyB0aGUgZGVjaXNpb24gdHJlZSBoYWQgZm9yIHRoZSAiZGlhZ29uYWwgZGF0YSIsIGFuZCB0aGUgbGluZWFyIG1vZGVsIGZvciB0aGUgInNxdWFyZSBib3ggZGF0YSI/CgpEaWQgeW91IGRvIGl0PwoKSGVyZSBpcyBvbmUgc29sdXRpb246CgoqIERpYWdvbmFsIGRhdGE6IGFkZGluZyBhIHBhcmFtZXRlciBgYHcgPSB4IC0geWBgIG1ha2VzIHRoZSBzZXBhcmF0aW9uIGxpbmUgcGVycGVuZGljdWxhciB0byBgYHdgYC4gVGhlIHByb2JsZW0gaXMgdGhlbiB2ZXJ5IGVhc3kgdG8gc29sdmUgZm9yIHRoZSBkZWNpc2lvbiB0cmVlIChpdCB3YXMgYWxyZWFkeSBlYXN5IGZvciB0aGUgbGluZWFyIG1vZGVsKS4KKiBTcXVhcmUgYm94IGRhdGE6IGFkZGluZyBhIHBhcmFtZXRlciBgYHdgYCB3aGljaCBpcyB0aGUgaGlnaGVyIG9uZSBvZiBgYGFicyh4KWBgIGFuZCBgYGFicyh5KWBgLCBtYWtlcyB0aGUgcHJvYmxlbSBlYXNpbHkgc29sdmFibGUgd2l0aCBhIGRlY2lzaW9uIGJvdW5kYXJ5IGF0IGBgdyA9IHNxcnQoMikgLyAyYGAuCgpUb2RheSdzIGxlc3NvbnMKPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQoKKiBMaW5lYXIgbW9kZWxzIGFyZSBiYWQgYXQgaW50ZXJhY3Rpb25zICh0aGF0IGNhbid0IGJlIHNlcGFyYXRlZCBieSBhIHN0cmFpZ2h0IGxpbmUpLgoqIERlY2lzaW9uIHRyZWVzIGFyZSBiYWQgYXQgJ2N1cnZlZCcgZGVjaXNpb24gYm91bmRhcmllcyAodGhhdCBhcmVuJ3QgcGFyYWxsZWwgdG8gYSBjb29yZGluYXRlKS4KKiBCb3RoIGNhbiBiZSBpbXByb3ZlZCBhIGxvdCBieSBzbWFydCBjaG9pY2Ugb2YgZXh0cmEgZmVhdHVyZXMuIFRoZSBjaG9pY2VzIHNob3VsZCBiZSBmb2N1c3NlZCBvbiBvdmVyY29tbWluZyB0aGVpciB3ZWFrbmVzcywgYW5kIGFyZSBnZW5lcmFsbHkgZGlmZmVyZW50IGZvciBlYWNoIG1vZGVsLgoKSW1wcmVzc2lvbnMgYWJvdXQgUgo9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09CgpJJ20gYSBub3ZpY2UgYXQgUiwgc28gZG9uJ3QgcGF5IHRvbyBtdWNoIGF0dGVudGlvbiB0byB0aGlzLCBJJ2xsIHByb2JhYmx5IGNoYW5nZSBteSBtaW5kLgoKKiBJdCdzIGhhcmRlciB0byBmaW5kIHRoaW5ncyBvbiBHb29nbGUgZm9yIG1lLiBJIHJlZ3VsYXJseSBnZXQgcmVzdWx0cyBmb3Igb3RoZXIgbGFuZ3VhZ2VzIHdoZW4gc2VhcmNoaW5nIGZvciBSIHN0dWZmLiBNYXliZSBHb29nbGUgbmVlZHMgc29tZSB0aW1lIHRvIGZpZ3VyZSBvdXIgSSdtIGRvaW5nIFIgbm93LgoqIFJzdHVkaW8gaXMgcXVpdGUgbmljZS4gU2ltaWxhciB0byBNYXRsYWIuIEl0J3MgaW50dWl0aXZlLCBhbHRob3VnaCBwcm9ibGVtIGhpZ2hsaWdodGluZyBjb3VsZCBiZSBiZXR0ZXIvZmFzdGVyLiBJdCdzIG5vIG1hdGNoIGZvciBbUHlDaGFybV0oaHR0cHM6Ly9tYXJrdi5ubC9ibG9nL3B5Y2hhcm0pLCBidXQgSSByZWFsbHkgbG92ZSBQeUNoYXJtLCBzbyB0aGF0J3Mgbm90IGEgdmVyeSBtZWFuaW5nZnVsIGNvbXBhcmlzb24uCiogSSBsaWtlIFIgbm90ZWJvb2tzIG1vcmUgdGhhbiBKdXB5dGVyIG9uZXMsIGl0IGZlZWxzIGxpa2UgeW91J3JlIHdvcmtpbmcgaW4gb25lIGZpbGUgaW5zdGVhZCBvZiBhIGh1bmRyZWQgdGlueSBvbmVzIHBhc3RlZCB0b2dldGhlciwgYW5kIGl0J3MgbW9yZSBzbW9vdGggaW4gZ2VuZXJhbC4KKiBJJ20gZmluZGluZyB0aGUgc3R5bGUgb2YgUiBsZXNzIHByZWRpY3RhYmxlIHRoYW4gUHl0aG9uJ3MuIE1heWJlIEknbSBqdXN0IG5vdCB1c2VkIHRvIGl0IHlldC4gQnV0IGl0J3MgYSBiaXQgY29uZnVzaW5nIHdoZW4gdGhpbmdzIGFyZSAndmFsdWVzJyBhbmQgd2hlbiB0aGV5IGFyZSAnc3ltYm9scycgd2hvc2UgbmFtZSBzaG91bGQgbWF0Y2ggbmV4dCB0aW1lLiBBbmQgd2hhdCBkb3RzIG1lYW4gaW4gd2hpY2ggY2FzZS4gT3Igd2h5IHRoaW5ncyBhYm91dCBvYmplY3RzIGFyZW4ndCBqdXN0IHByb3BlcnRpZXMgb2YgdGhlIG9iamVjdCAoZXNwZWNpYWxseSBgYGRpbShhcnIpIDwtIHZhbHVlYGAgc2VlbXMgcmVhbGx5IHdlaXJkKS4gT3Igd2h5IGFycmF5IHNsaWNlcyBhcmVuJ3QgYXMgc2ltcGxlIGFzIGluIFB5dGhvbiAob3IgZXZlbiBNYXRsYWIpIC0gd2h5IHdvdWxkIGEgZnVuY3Rpb24gbGlrZSBgaGVhZGAgbmVlZCB0byBleGlzdD8gQWx0b2dldGhlciBpdCBmZWVscyBsaWtlIGEgY29sbGVjdGlvbiBvZiB0b29scywgcmF0aGVyIHRoYW4gYSBsYW5ndWFnZSAobm90IG5lY2Vzc2FyaWx5IGJhZCBmb3IgaXQncyBwdXJwb3NlKS4KKiBGdW5jdGlvbnMgd2l0aCBgYH5gYCBzZWVtIGNvb2wsIEknbGwgaGF2ZSB0byBzdHVkeSB0aGF0IG1vcmUuCgoK

Comments

No comments yet

You need to be logged in to comment.