Unstable Prediction Probabilities We have a data set of a company that needs to predict their employee resignation status.
So We developed four classification models "Bagging","Boosting", "RandomForest" and "Logistic".
The task we have is to predict the resignation probability of the non resigned employees of the data set.
The non resigned employees are also in the training set. So technically we have to do the prediction on the training set too.
The problem occurred is when a specific observation is in the test set it gives a prediction probability which is completely different from the prediction probability when it is in the training set.
E.g. when the employee no 00 is in the test set the prediction probability is 30% but when he is in the training set the probability is 7%.
We fitted the models with and without feature selections. For both methods the problem exists. 
What would be the problems in the models and what can we do to overcome this problem?
 A: A first answer
Providing a definitive answer wil be difficult without knowing more about your data, understanding the models and chosen hyperparameters, and performing various checks on the results. 
One possible cause of such behaviour is, as you hint in the question title, model instability. 

Intuitively, a stable algorithm is one for which the prediction does not change much when the training data is modified slightly.

Which is the opposite of what seems to be happening to you (see here for a detailed description of algorithmic stability) Variance of $K$-fold cross-validation estimates as $f(K)$: what is the role of "stability"? 
Without going into the details of the above post, the stabilty of a model will depend on:


*

*The inherent algorithm being used: for example decision trees are notoriously unstable, while $L_2$ ridge regression is inherently more stable (for appropriate regularization parameter) 

*The size of the data set

*The number of outliers, their distribution, and their values 


This is assuming there are no pre-processing or feature selection steps beforehand as these will add many more possible sources of instability. For example Lasso on correlated features is known to be unstable. 
What you could try
Assuming your objective is to reduce the instability of your algorithm, you could try the following


*

*Add $L_2$ regularization, or a combination of $L_1$ and $L_2$ (elastic net) 

*Use different, more stable, algorithms (e.g. bagged regularizers, soft margin SVM with regularization etc..)

*Transform your data (remove outliers, obtain more data, perform PCA, compression etc..) 

*Add "robustifying" steps to your algorithm. These will depend on the algorithm and may or may not exist. An example are the robustifying iterations added to the following LOESS algorithm
Note that algorithm stability does not necessarily imply better predictions or performance of your model... 
A toy example
The same polynomial linear regression algorithm is unstable in the LHS, and stable in the RHS. More data points reduce the effect of outliers on the model. 

