Neural Computation of Decisions in Optimization Problems

Neural Computation of Decisions in Optimization Problems

J. J. Hopfield, D. W. Tank
Biological Cybernetics, 1985

Introduction

From the perspective of neuroscience, the authors first review their high-level goal, i.e. understanding the structure and connection of neurons.

One of the central goals of research in neuroscience is to understand how the biophysical properties of neurons and neural organization combine to provide such impressive computing power and speed.

Then they propose their opinion on the key point of neuron organization.

Parallel analog computation in a network of neurons is thus a natural way to organize a nervous system to solve optimization problems.

Specifically, in this paper, they showed the power of the proposed analog computational networks by testing on TSP.

We quantitatively demonstrate the computational power and speed of collective analog networks of neurons in solving optimization problems rapidly.

Background on Hopfield Network

The figure below illustrates an unit neuron in a Hopfield network.

According to Kirchhoff's Current Law, we have that
C_i \frac{du_i}{dt} = \sum^N_{j = 1} T_{ij} v_j - u_i / R_i + I_i
v_j = g_j (u_j)
where T_{ij} = 1 / R_{ij}, I_i is the current bias for neural i, g_j is the activation function for neuron j, and R_i is a parallel combination of R_{i0} and R_{ij}:
1 / R_i = 1 / R_{i0} + \sum^N_{j = 1} 1 / R_{ij} .
For simplicity, we can further set C_i, R_i and g_i independent of i, define T_{ij} / C and I_i / C as T_{ij} and I_i, which leads to the following equation:
du_i / dt = -u_i / \tau + \sum^N_{j = 1} T_{ij} v_j + I_i ,
where \tau = RC, and v_j = g (u_j).
Given an initial value for u_i, this equation of motion provides a full description of the time evolution of the state of the circuit.

There are two key properties of the Hopfield network as shown in earlier work:

  • The equations of motion for a network with symmetric connections, i.e. T_{ij} = T_{ji}, always lead to a convergence to stable states;
  • When the width of the amplifier gain curve is narrow - the high-gain limit - the stable states of a network comprised of N neurons are the local minima of the quantity
    E = -1/2 \sum^N_{i = 1} \sum^N_{j = 1} T_{ij} V_i V_j - \sum^N_{i = 1} V_i I_i .
    And in the high-gain limit, the minima only occur at corners of the feasible space, which is a N-dimensional hypercube defined by V_i = 0 or 1.

Consequently,

Networks of neurons with this basic organization can be used to compute solutions to specific optimization poblems by first choosing connectivities T_{ij} and input bias currents I_i which appropriately represent the function to be minimized.

Network Formulation for TSP

For a TSP with N cities, the representation scheme in this work has a complexity of O(N^2), as the route is represented as a permutation matrix, in which the location of each city is represented as the output states of N neurons in an one-hot encoding fashion. Each neuron is labelled by two indices, in which the first index X represents the city, and the seond index i represents its order in the route.

To solve TSP with the Hopfield network, the energy function should include two parts:

  • The first part favors solutions in the form of a permutation matrix, which guanrantees the feasibility of the solution;
  • The second part favors solutions with shorter distance.

The first part of the energy function is defined as
E_1 = A / 2 \sum_X \sum_i \sum_{j \neq i} V_{Xi} V_{Xj} + B / 2 \sum_i \sum_X \sum_{Y \neq X} V_{Xi} V_{Yi} + C / 2 (\sum_X \sum_i V_{Xi} - n)^2 .
The first term and second term mean that there is only one non-zero element in each row and each column of the matrix respectively, and the third term means that there is exactly n non-zero elements in the matrix. Only a permutation matrix can reach the minimum of this energy function with E_1 = 0.

(Two questions: 1. Why not use the row sum and column sum to represent the first and second term? 2. How can this function guanrantee that there won't be several distinct loops in the matrix?)

The second part of the energy function is defined as
E_2 = D / 2 \sum_X \sum_{Y \ neq X} \sum_i d_{XY} V_{Xi} (V_{Y, i + 1} + V_{Y, i - 1}) .
This function represents the total length of the tour. For notational convenience, subscripts are defined as modulo n to represent the tour loop.

The final energy function is E = E_1 + E_2.

If A, B and C are sufficiently large, all the really low energy states of a network described by this function will have the form of a valid tour. The total energy of that state will be the length of the tour, and the states with the shortest path will be the lowest energy states.

Next, we map the energy function of TSP to the standard form of the energy function in the Hopfield network:
T_{Xi, Yj} = -A \delta_{XY} (1 - \delta_{ij}) - B \delta_{ij} (1 - \delta_{XY}) - C - D d_{XY} (\delta_{j, i + 1} + \delta_{j, i - 1}) ,
I_{Xi} = + C n ,
where \delta_{ij} = 1 \ if \ i = j \ and \ 0 \ otherwise .

Simulation Results

  • The activation function is set as g(u) = \frac{1}{2} (1 + \tanh (u / u_0));
  • The instance is generated by sampling N points uniformly in an unit square;
  • The choice of the random initial point leads to different convergence solution;
  • The proposed method achieves close-to-best solutions for 10 cities, good solutions for 30 cities. No larger instance size is considered. The method performs much better than random search, but is not compared with other human-designed heuristics.

Conclusion

I suppose the key idea of this paper is that we can relate some kinds of optimization problems with the dynamics of a specific type of dynamic system, such as the Hopfield network. But I'm not convinced that this is a scalable approach to solving combinatorial optimization problems.

In BP networks, our goal is encoded in the objective function, and we update the network weights to optimize this function. In Hopfield networks, our goal is encoded in the connection weights of the network, and the optimal solution is acquired by the system dynamic.

It deserves to investigate what is the current status of the Hopfiled network and how can we combine it with the deep learning paradigm.

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末茫船,一起剝皮案震驚了整個濱河市祝高,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌轻庆,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,378評論 6 516
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件彼绷,死亡現(xiàn)場離奇詭異巍佑,居然都是意外死亡,警方通過查閱死者的電腦和手機萤衰,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,970評論 3 399
  • 文/潘曉璐 我一進店門猜旬,熙熙樓的掌柜王于貴愁眉苦臉地迎上來脆栋,“玉大人倦卖,你說我怎么就攤上這事〕锿拢” “怎么了糖耸?”我有些...
    開封第一講書人閱讀 168,983評論 0 362
  • 文/不壞的土叔 我叫張陵丘薛,是天一觀的道長。 經(jīng)常有香客問我洋侨,道長,這世上最難降的妖魔是什么希坚? 我笑而不...
    開封第一講書人閱讀 59,938評論 1 299
  • 正文 為了忘掉前任,我火速辦了婚禮裁僧,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘聊疲。我一直安慰自己,他們只是感情好获洲,可當(dāng)我...
    茶點故事閱讀 68,955評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著最爬,像睡著了一般。 火紅的嫁衣襯著肌膚如雪爱致。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,549評論 1 312
  • 那天蒜鸡,我揣著相機與錄音牢裳,去河邊找鬼逢防。 笑死蒲讯,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的判帮。 我是一名探鬼主播溉箕,決...
    沈念sama閱讀 41,063評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼悦昵,長吁一口氣:“原來是場噩夢啊……” “哼肴茄!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起但指,我...
    開封第一講書人閱讀 39,991評論 0 277
  • 序言:老撾萬榮一對情侶失蹤寡痰,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后棋凳,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體拦坠,經(jīng)...
    沈念sama閱讀 46,522評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,604評論 3 342
  • 正文 我和宋清朗相戀三年贞滨,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片晓铆。...
    茶點故事閱讀 40,742評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡绰播,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出幅垮,到底是詐尸還是另有隱情尾组,我是刑警寧澤忙芒,帶...
    沈念sama閱讀 36,413評論 5 351
  • 正文 年R本政府宣布讳侨,位于F島的核電站,受9級特大地震影響潮峦,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜忱嘹,卻給世界環(huán)境...
    茶點故事閱讀 42,094評論 3 335
  • 文/蒙蒙 一耕渴、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧橱脸,春花似錦分苇、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,572評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽靖秩。三九已至乌叶,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間准浴,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,671評論 1 274
  • 我被黑心中介騙來泰國打工求橄, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留葡公,地道東北人罐农。 一個月前我還...
    沈念sama閱讀 49,159評論 3 378
  • 正文 我出身青樓催什,卻偏偏與公主長得像,于是被迫代替她去往敵國和親蒲凶。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,747評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 漸變的面目拼圖要我怎么拼? 我是疲乏了還是投降了肄方? 不是不允許自己墜落, 我沒有滴水不進的保護膜。 就是害怕變得面...
    悶熱當(dāng)乘涼閱讀 4,252評論 0 13
  • 夜鶯2517閱讀 127,728評論 1 9
  • 版本:ios 1.2.1 亮點: 1.app角標(biāo)可以實時更新天氣溫度或選擇空氣質(zhì)量逝薪,建議處女座就不要選了蝴罪,不然老想...
    我就是沉沉閱讀 6,905評論 1 6
  • 我是一名過去式的高三狗,很可悲要门,在這三年里我沒有戀愛,看著同齡的小伙伴們一對兒一對兒的欢搜,我的心不好受。怎么說呢炒瘟,高...
    小娘紙閱讀 3,392評論 4 7
  • 那一年,我選擇了獨立遠行缘琅,火車帶著我在前進的軌道上爬行了超過23個小時; 那一年刷袍,我走過泥濘的柏油路,在那個遠離故...
    木芽閱讀 1,642評論 4 5