はじめに
ロジスティック回帰が線形分離不可能な分類問題を解けないことは有名な話です。だけど、「いや解けるだろ」「なんで解けないの？？？」と言われてしまうことがあるので*1、それができないことを説明しておこうと思います。
なお、この記事はこちらの記事を参考にしています。
誤った図解から学ぶロジスティック回帰の性質 - ill-identified diary
書きたいことは言い尽くされている感もあるので、こういう結論に至る過程を数式で書きます*2。
y=0.5を代入すればいい
さて、説明変数、目的変数
、パラメータ
、などを適当に定めたとします。すると、ロジスティック回帰の予測式はこんなやつになります（
は適当に学習できたとする）。
\begin{align}
\hat{y} = \frac{1}{1 +
\mathrm{e}^{-(\beta_0 + \sum_{i=1}^{n}\beta_i x_i)}
}
\end{align}
書き方の流儀はいろいろあると思いますが（を使うとか）、今回は上の式で行きます。
さて、今回は分離超平面の式に興味があるのでしたね。分離超平面ってどこ？ というと、のところです。なので、淡々と式を書き換えます。
\begin{align}
0.5 = \frac{1}{1 +
\mathrm{e}^{-(\beta_0 + \sum_{i=1}^{n}\beta_i x_i)}
}
\end{align}
両辺を逆数にします。
\begin{align}
2 = 1 + \mathrm{e}^{-(\beta_0 + \sum_{i=1}^{n}\beta_i x_i)}
\end{align}
とりあえず邪魔な1を反対側に移す。
\begin{align}
1 = \mathrm{e}^{-(\beta_0 + \sum_{i=1}^{n}\beta_i x_i)}
\end{align}
両辺の対数を取る。
\begin{align}
0 = -(\beta_0 + \sum_{i=1}^{n}\beta_i x_i)
\end{align}
マイナスは必要ないので消しましょう。
\begin{align}
0 = \beta_0 + \sum_{i=1}^{n}\beta_i x_i
\end{align}
もうだいたい終わってる気もしますが、たとえばとして適当に式を変形します。
\begin{align}
\beta_0 + \beta_1 x_1 + \beta_2 x_2 = 0
\end{align}
……はい、これは「直線の式」ですね。
が増えると係数と変数が増えていきますが、いずれにせよ線形の式なのは間違いありません。
とか
みたいなのが出てくる余地はありません。
「分離超平面」がかのような式で表わせる以上、線形分離不可能な分類問題は解けない、ということです。
非線形の問題も解く方法
あくまでも「分離境界が線形にならないといけない」というだけなので、データを非線形変換して解けるような空間に写像すればできます。代表的な方法は多項式を使うことです（SVMの多項式カーネルなんかと同じですが、明示的に特徴量空間を計算するのが相違点です）。
ということで、こちらの記事を御覧ください。どれくらい非線形でも行けるのかが書いてあります。