A new algorithm for the determination of the initial flavour of $B_s^0$ mesons is presented. The algorithm is based on two neural networks and exploits the $b$ hadron production mechanism at a hadron collider. The first network is trained to select charged kaons produced in association with the $B_s^0$ meson. The second network combines the kaon charges to assign the $B_s^0$ flavour and estimates the probability of a wrong assignment. The algorithm is calibrated using data corresponding to an integrated luminosity of 3 fb$^{-1}$ collected by the LHCb experiment in proton-proton collisions at 7 and 8 TeV centre-of-mass energies. The calibration is performed in two ways: by resolving the $B_s^0$-$bar{B}_s^0$ flavour oscillations in $B_s^0 to D_s^- pi^+$ decays, and by analysing flavour-specific $B_{s 2}^{*}(5840)^0 to B^+ K^-$ decays. The tagging power measured in $B_s^0 to D_s^- pi^+$ decays is found to be $(1.80 pm 0.19({rm stat}) pm 0.18({rm syst}))$%, which is an improvement of about 50% compared to a similar algorithm previously used in the LHCb experiment.