The Solid-Electrolyte Interphase (SEI) formed in lithium-ion batteries is a vital but poorly-understood class of materials, combining organic and inorganic components. An SEI allows a battery to function by protecting electrode materials from unwanted side reactions. We use a combination of classical sampling and a novel machine learning model to produce the first set of SEI candidate structures ranked by predicted energy, to be used in future machine learning applications and compared to experimental results. We hope that this work will be the start of a more quantitative understanding of lithium-ion battery interphases and an impetus to development of machine learning models for battery materials.