了解并避免无限递归R [英] Understand and avoid infinite recursion R

问题描述

在R中如何处理无限递归方面，我找不到任何建议.我想以最一般的方式说明我的问题，以便其他人可以从中受益.随时进行编辑.

I can't find any advice on how to deal with infinite recursion in R. I would like to illustrate my problem in the most general way so that others can benefit from it. Feel free to edit it.

我曾经运行过两次for循环

I used to run a double for loop

for (k in 1:n){ for (i in 1:m){
f[i,,k] <- an expression that depends on g[i-1,,k]
g[i,,k] <- a mixture of g[i-1,,k] and f[i,,k]}}

运行得很好，但现在我希望找到最适合我的标准的k.因此，我决定将其转换为函数，以便以后可以对其进行优化或单根化.我写了这样的东西:

This was running fine but now I hoped to find the k that would best fit my criterion. So I decided to turn it into a function so that i could later optimize or uniroot it. I wrote something like that :

f <- function(i,k){an expression that depends on g(i-1,k)}
g <- function(i,k){an expression that depends on g(i-1,k) and f(i,k)}

我认为这两个问题相似，但令我惊讶的是，我遇到了无限递归错误.

I thought the two problems were similar but to my great surprise, I get infinite recursion errors.

我阅读了有关最大内存的信息，但是我敢肯定还有一种更美观的方法.

I read about max memory but I am sure there is a more aesthetic way of doing it.

我的可复制示例:

library(memoise)

gradient <- function(x,y,tau){if (x-y > 0) {- tau} else {(1-tau)}}
aj <- c(-3,-4,-2,-3,-5,-6,-4,-5,-1,rep(-1,15))
f <- function(x,vec){sum(x^vec)-1}
root <- uniroot(f, interval=c(0,200), vec=aj)$root

memloss<-function(i,k){if (i==1) {c(rep(0,24))} else if (i <= 0 | k < -5) {0} else {gradient(dailyreturn[i-1],weight(i-1,k)%*%A[i-1,],0.0025)*A[i-1,]}}
memweight <- function(i,k){if (i==1) {c(rep(root,24)^aj)} else if (i <= 0 | k < -5) {0} else {(exp(- (2^(k)/(sqrt(1415))) * loss(i,k))) / (weight(i-1,k) %*%  exp(- 2^(k)/(sqrt(1415)) * loss(i,k)) ) * weight(i-1,k)}}
loss <- memoize(memloss)
weight <- memoize(memweight)

其中Dailyreturn是向量(长度为2080)

where dailyreturn is a vector (of length 2080)

A是1414 x 24矩阵

A is a 1414 x 24 matrix

我希望能帮上忙.

推荐答案

存在三个问题.

首先，您需要一个初始大小写进行递归. 以下将导致无限递归(i的值不断减小，但永不停止).

First, you need an initial case for your recursion. The following leads to infinite recursion (the value of i continually decreases, but that never stops).

f <- function(i) g(i-1)
g <- function(i) g(i-1) + f(i)
f(5)

以下内容将停止.

f <- function(i) g(i-1)
g <- function(i) if( i <= 0 ) 0 else g(i-1) + f(i)
f(5)

第二个问题是，其中一些值将被重新计算指数次.

The second problem is that some of those values will be re-computed an exponential number of times.

f(500) # Too long

更抽象地讲，对于i的所有值，考虑其顶点分别为f(i)和g(i)的图， 边缘对应于函数调用.递归使您可以像浏览树一样浏览该图. 但是在这种情况下，它不是一棵树，您最终会评估同一功能(探索同一节点)很多次.以下代码绘制了该图.

In more abstract terms, consider the graph whose vertices are f(i) and g(i), for all values of i, with edges corresponding to function calls. Recursion allows you to explore this graph as if it were a tree. But in this case, it is not a tree, and you end up evaluating the same function (exploring the same node) a very large number of times. The following code draw this graph.

library(igraph)
n <- 5
g <- graph.empty() 
g <- g + vertices( paste0("f(", 1:n, ")" ) )
g <- g + vertices( paste0("g(", 0:n, ")" ) )
for( i in 1:n) {
  g <- g + edge( paste0("f(", i ,")"), paste0( "g(", i-1, ")" ) )
  g <- g + edge( paste0("g(", i ,")"), paste0( "f(", i, ")" ) )
  g <- g + edge( paste0("g(", i ,")"), paste0( "g(", i-1, ")" ) )
}
plot(g)

一种解决方法是存储您已经计算出的值，以避免重新计算它们: 这称为记忆化.

One workaround is to store the values you have already computed to avoid recomputing them: this is called memoization.

library(memoise)
f <- function(i) G(i-1)
g <- function(i) if( i <= 0 ) 1 else G(i-1) + F(i)
F <- memoize(f)
G <- memoize(g)
f(500)

当您记住该函数时，递归调用的数量将变为线性， 但它仍然可能太大.您可以按照初始错误消息的建议增加限制:

When you memoise the function, the number of recursive calls becomes linear, but it can still be too large. You can increase the limit as suggested by the initial error message:

options( expressions = 5e5 )

如果这还不够，则可以使用越来越大的i值来预填充表. 以您的示例为例:

If this is not sufficient, you can prepopulate the table, by using increasingly larger values of i. With your example:

options( expressions = 5e5 )
loss(1000,10) # Does not work: Error: protect(): protection stack overflow
loss(500,10)  # Automatically stores the values of loss(i,100) for i=1:500
loss(1000,10) # Works

第三，可能有些函数调用不必要地增加了调用堆栈的大小. 在您的示例中，如果在错误后键入traceback()，您将看到许多中间函数 在调用堆栈中，因为weight(i,k)和loss(i,k)在函数参数内部使用. 如果将这些调用移到函数参数之外，则调用堆栈会变小，并且似乎可以正常工作.

Third, there may be function calls that needlessly increase the size of the call stack. In your example, if you type traceback() after the error, you will see that many intermediate functions are in the call stack, because weight(i,k) and loss(i,k) are used inside function arguments. If you move those calls outside the function arguments, the call stack is smaller, and it seems to work.

library(memoise)
gradient <- function(x,y,tau){
  if (x-y > 0) { - tau   } 
  else         { (1-tau) }
}
aj <- c(-3,-4,-2,-3,-5,-6,-4,-5,-1,rep(-1,15))
f <- function(x,vec){sum(x^vec)-1}
root <- uniroot(f, interval=c(0,200), vec=aj)$root
memloss<-function(i,k){
  cat( "loss(", i, ",", k, ")\n", sep="" )
  if (i==1) {
    c(rep(0,24))
  } else if (i <= 0 | k < -5) {
    0
  } else {
    w <- weight(i-1,k)   # Changed
    gradient(dailyreturn[i-1],w%*%A[i-1,],0.0025)*A[i-1,]
  }
}
memweight <- function(i,k){
  cat( "weight(", i, ",", k, ")\n", sep="" )
  if (i==1) {
    c(rep(root,24)^aj)
  } else if (i <= 0 | k < -5) {
    0
  } else {
    w <- weight(i-1,k)  # Changed
    l <- loss(i,k)      # Changed
    (exp(- (2^(k)/(sqrt(1415))) * l)) / (w %*%  exp(- 2^(k)/(sqrt(1415)) * l) ) * w
  }
}
loss <- memoize(memloss)
weight <- memoize(memweight)

A <- matrix(1, 1414, 24)
dailyreturn <- rep(1,2080)
options( expressions = 1e5 )
loss(1400,10)

这篇关于了解并避免无限递归R的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！