[HN Gopher] Kolmogorov Neural Networks can represent discontinuo...
___________________________________________________________________
Kolmogorov Neural Networks can represent discontinuous functions
Author : ubj
Score : 106 points
Date : 2023-11-05 05:13 UTC (17 hours ago)
(HTM) web link (arxiv.org)
(TXT) w3m dump (arxiv.org)
| arjvik wrote:
| Abstract: In this paper, we show that the Kolmogorov two hidden
| layer neural network model with a continuous, discontinuous
| bounded or unbounded activation function in the second hidden
| layer can precisely represent continuous, discontinuous bounded
| and all unbounded multivariate functions, respectively.
| littlestymaar wrote:
| How can you back-propagate through it if it's not continuous
| (and as such, non-differentiable)?
| mandarax8 wrote:
| Doesn't have to be continuously differentiable to be
| differentiable right?
| Kevin09210 wrote:
| Don't downvote. Explain
| pvitz wrote:
| Haven't downvoted, but the "continuously" in
| "continuously differentiable" refers to the derivative
| and not to the function itself. (Also, from
| differentiable follows continuous, but not the other way
| around (sufficient, but not necessary).)
| littlestymaar wrote:
| I need to be continuous to be differentiable.
|
| That being said, if it's only discontinuous in a few number
| of places you could extend the derivative everywhere by
| taking either the left or the right derivative, and then
| you'd end up with a gradient being defined everywhere, but
| not continuous. But then does gradient descent work if the
| gradient isn't continuous?
| amelius wrote:
| You can also extend the derivative such that you compute
| it numerically and then some slight discontinuities are
| certainly not a problem.
| PeterisP wrote:
| One of the common - if not the most common - activation
| function is 'rectified linear unit' (ReLU) which is a
| fancy name for y=max(x,0), which has a discontinuous
| gradient (1 if x>0, 0 if x<0) and that works mostly fine.
| yorwba wrote:
| Even in the continuous case, there are nowhere-differentiable
| continuous functions
| https://en.wikipedia.org/wiki/Weierstrass_function where
| attempting to use back-propagation is unlikely to go well.
|
| The paper only gives an existence result for the general
| case, and may require an arbitrarily complex activation
| function to represent arbitrarily complex multivariate
| functions, so it's unlikely to be useful for machine-learning
| applications.
| ndriscoll wrote:
| I can't remember now and never gave measure theory a proper
| study, but isn't there a happy result that you can quotient
| out by a space of functions with zero integral to get an
| almost everywhere differentiable function or something?
| Maybe that's for L2:continuous, not
| continuous:differentiable?
|
| Even a result like f(x) = nice(x) + evil(x) with |evil| <
| epsilon should be "happy enough" right?
|
| Edit: I may have been misremembering the Lebesgue
| decomposition theorem which is not quite so nice, as the
| singular part doesn't just go away.
| yorwba wrote:
| For a "happy enough" approximation to the Weierstrass
| function, you can cut off the series once a^n/(1 - a) <
| epsilon and get a function that's differentiable
| everywhere. But it'll have an extremely large number of
| local optima, which is still bad for gradient descent.
| tnecniv wrote:
| That's not a requirement for universal approximation. It
| might make your life harder when you have to train the
| network, but that's just an implementation detail anyway /s
| ubj wrote:
| The paper only gives a representation result, so no method is
| known yet for constructing the component functions `g` for
| the discontinuous case. See the last paragraph of the
| Conclusion.
|
| It may turn out that the correct representation can be
| constructed using an alternate method than backpropagation.
| But this is still an open question.
| magicalhippo wrote:
| This isn't my field at all, so this might be silly.
|
| I was thinking about some weird activation function like
| say 0 for x < 0.5 0.5 for x in
| [0.5, 1] 0.1x + 1 for x > 1
|
| While it is piece-wise differentiable, similar to ReLU, I'm
| guessing regular backpropagation would have would struggle
| with it.
|
| My probably silly thought was, what if you used a smoothed
| version for computing the differentials for the
| backpropagation step, while keeping the discontinuous
| function for actual evaluation? My thought was this would
| make backprop sensitive to the step changes in the
| function, while allowing for discontinuous activation.
|
| Of course this example function is just something random
| without any further thought, so probably not a useful one
| in actual usage.
| cgreerrun wrote:
| You can use the straight through operator!
|
| During the forward pass you sample a discrete outcome given
| your NN weights to get an error for backprop. During the
| backward pass you directly propogate through the weights.
|
| This GradTree paper[1] does a good job covering how to do
| discrete gradient-based optimization (i.e. NNs w/ discrete
| representations).
|
| Another option is to use a GFlowNet[2]. Then you have a NN
| policy that takes discrete actions like you're playing an RL
| game. You're not back-propogating through something that
| isn't continuous, but you're utilizing a NN to make informed
| decisions about a problem with a discrete representation.
|
| [1] GradTree (https://arxiv.org/pdf/2305.03515.pdf) [2]
| GFlowNet (https://arxiv.org/abs/2111.09266)
| lucidrains wrote:
| gradtree is cool! thanks for the share!
| smaddox wrote:
| It might also be possible to solve a corresponding convex
| optimization problem, similar to
| https://arxiv.org/pdf/2303.03382.pdf
| ubj wrote:
| If an appropriate dual problem is found this could be
| possible.
|
| I'm baffled why Mert Pilanci's work in this area hasn't
| received more attention. His proofs of a zero duality gap
| for neural networks are impressive.
| smaddox wrote:
| Well, the approach currently doesn't apply to
| architectures being used in practice, and it's not clear,
| at least to me, if it can scale to large datasets.
| codethief wrote:
| Sounds like this improves upon the known results for continuous
| functions?
| https://en.m.wikipedia.org/wiki/Universal_approximation_theo...
| petters wrote:
| The abstract says it can represent "all unbounded multivariate
| functions." But there are uncomputable functions, so there must
| be some restriction.
| yorwba wrote:
| The representation for uncomputable functions will be
| uncomputable, of course. There's only a countable number of
| computable functions, so most functions are uncomputable, but
| that usually doesn't stop mathematicians from proving theorems
| about them.
| magnio wrote:
| The restriction is that it requires an activation function
| depending on the function it is approximating. Hence, if you
| want the NN to emulate an uncomputable function, the activation
| function probably has to be uncomputable as well.
| scotty79 wrote:
| What is a Kolmogorov Neural Network?
| esafak wrote:
| See Figure 1 and
| https://cs.uwaterloo.ca/~y328yu/classics/Hecht-Nielsen.pdf
| dboreham wrote:
| Oh, there actually is a Figure 1.
| sega_sai wrote:
| It is a pretty cool result. Basically the lay summary (from my
| understanding) is that a multivariate function with n-arguments
| can be perfectly represented by a network with 2 hidden layers
| (one having width n and another width 2n) and two activation
| functions.
| bilsbie wrote:
| How would this ability show up if we built gpt out of these? More
| out of the box thinking?
___________________________________________________________________
(page generated 2023-11-05 23:02 UTC)