3 ms·

They might be trying to talk about Rice's theorem? https://en.wikipedia.org/wiki/Rice%27s_theorem https://en.wikipedia.org/wiki/Rice%27s_theorem Formally, any

by mswphd 6mo ago

They might be trying to talk about Rice's theorem? https://en.wikipedia.org/wiki/Rice%27s_theorem https://en.wikipedia.org/wiki/Rice%27s_theorem Formally, any non-trivial semantic property of a Turing machine is undecidable. Semantic here (roughly) means "behavioral" questions of the turing machine. E.g. if you only look at the "language" it defines (viewing it as a black box), then it is undecidable to answer any question about that language (including things like if it terminates on all inputs). Practically though that isn't a complete no-go result. You can do various things, like 1. weaken the target you're looking for. if you're ok with admitting false positives or false negatives, Rice's theorem no longer applies, or 2. rephrase your question in terms of "syntatic properties", e.g. questions about how the code is implemented. Rust's borrow checker does this via lifetime annotations, for example.

vidarh 6mo ago
Rice's theorem is a close corollary, but I did mean the halting problem. Pointing to the halting problem was a bit of a throwaway quip because the "general shape" of it is an easy smell test for whether something is likely to be possible: If you have access to run a transform on data, you can use it to train a model that acts as a detector of whether that transform has been applied to the data. When you have a detector for a given property, you can use that detector to alter behaviour to exclude that property. And that is the abstract core of why the halting problem is unsolvable. In this case, if you have access to a mechanism for poisoning data, you can use that to train a detector. Once you have a detector, you can either exclude poisoned data, or use it for adversarial training. Either way: The existence of the poisoning mechanism can be directly used to derive the tools to create its own antidote. And that's back to the core of the halting problem.
- lxgr 6mo ago
  > If you have access to run a transform on data, you can use it to train a model that acts as a detector of whether that transform has been applied to the data. This still seems too handwavy. For example, you're implying that the transform is one that can be learned by gradient descent. As a trivial counterexample, you can't train a model to detect valid (text, SHA) pairs. This particular one doesn't seem to be a problem for your argument, but I still think your argument generally does not hold.
  - vidarh 6mo ago
    You can't train a model to detect arbitrary text to SHA, so yes, there are edge cases - this doesn't fully generalise. You can, however, trivially train a model to detect natural language to SHA. More specifically, for poisoning to work, the output needs to have qualities distinctly different in the poisoned or unpoisoned case, pretty much by definition, or we wouldn't notice the effect, and the reason the general case doesn't work for SHA is that you can feed in text that is likely statistically indistinguishable (you can feed SHA in as text) from the output, or "close enough".

by mswphd 6mo ago

vidarh 6mo ago

Rice's theorem is a close corollary, but I did mean the halting problem. Pointing to the halting problem was a bit of a throwaway quip because the "general shape" of it is an easy smell test for whether something is likely to be possible: If you have access to run a transform on data, you can use it to train a model that acts as a detector of whether that transform has been applied to the data. When you have a detector for a given property, you can use that detector to alter behaviour to exclude that property. And that is the abstract core of why the halting problem is unsolvable. In this case, if you have access to a mechanism for poisoning data, you can use that to train a detector. Once you have a detector, you can either exclude poisoned data, or use it for adversarial training. Either way: The existence of the poisoning mechanism can be directly used to derive the tools to create its own antidote. And that's back to the core of the halting problem.

lxgr 6mo ago
> If you have access to run a transform on data, you can use it to train a model that acts as a detector of whether that transform has been applied to the data. This still seems too handwavy. For example, you're implying that the transform is one that can be learned by gradient descent. As a trivial counterexample, you can't train a model to detect valid (text, SHA) pairs. This particular one doesn't seem to be a problem for your argument, but I still think your argument generally does not hold.
- vidarh 6mo ago
  You can't train a model to detect arbitrary text to SHA, so yes, there are edge cases - this doesn't fully generalise. You can, however, trivially train a model to detect natural language to SHA. More specifically, for poisoning to work, the output needs to have qualities distinctly different in the poisoned or unpoisoned case, pretty much by definition, or we wouldn't notice the effect, and the reason the general case doesn't work for SHA is that you can feed in text that is likely statistically indistinguishable (you can feed SHA in as text) from the output, or "close enough".